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   kind = TREE_CODE_CLASS (code);
3801   if (code == NOP_EXPR || code == FLOAT_EXPR || code == CONVERT_EXPR)
3802     {
3803       tree subop;
3804
3805       /* Special case for conversion ops that can have fixed point args.  */
3806       arg0 = TREE_OPERAND (t, 0);
3807
3808       /* Don't use STRIP_NOPS, because signedness of argument type matters.  */
3809       if (arg0 != 0)
3810         STRIP_TYPE_NOPS (arg0);
3811
3812       if (arg0 != 0 && TREE_CODE (arg0) == COMPLEX_CST)
3813         subop = TREE_REALPART (arg0);
3814       else
3815         subop = arg0;
3816
3817       if (subop != 0 && TREE_CODE (subop) != INTEGER_CST
3818 #if ! defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
3819           && TREE_CODE (subop) != REAL_CST
3820 #endif /* not REAL_IS_NOT_DOUBLE, or REAL_ARITHMETIC */
3821           )
3822         /* Note that TREE_CONSTANT isn't enough:
3823            static var addresses are constant but we can't
3824            do arithmetic on them.  */
3825         wins = 0;
3826     }
3827   else if (kind == 'e' || kind == '<'
3828            || kind == '1' || kind == '2' || kind == 'r')
3829     {
3830       register int len = tree_code_length[(int) code];
3831       register int i;
3832       for (i = 0; i < len; i++)
3833         {
3834           tree op = TREE_OPERAND (t, i);
3835           tree subop;
3836
3837           if (op == 0)
3838             continue;           /* Valid for CALL_EXPR, at least.  */
3839
3840           if (kind == '<' || code == RSHIFT_EXPR)
3841             {
3842               /* Signedness matters here.  Perhaps we can refine this
3843                  later.  */
3844               STRIP_TYPE_NOPS (op);
3845             }
3846           else
3847             {
3848               /* Strip any conversions that don't change the mode.  */
3849               STRIP_NOPS (op);
3850             }
3851
3852           if (TREE_CODE (op) == COMPLEX_CST)
3853             subop = TREE_REALPART (op);
3854           else
3855             subop = op;
3856
3857           if (TREE_CODE (subop) != INTEGER_CST
3858 #if ! defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
3859               && TREE_CODE (subop) != REAL_CST
3860 #endif /* not REAL_IS_NOT_DOUBLE, or REAL_ARITHMETIC */
3861               )
3862             /* Note that TREE_CONSTANT isn't enough:
3863                static var addresses are constant but we can't
3864                do arithmetic on them.  */
3865             wins = 0;
3866
3867           if (i == 0)
3868             arg0 = op;
3869           else if (i == 1)
3870             arg1 = op;
3871         }
3872     }
3873
3874   /* If this is a commutative operation, and ARG0 is a constant, move it
3875      to ARG1 to reduce the number of tests below.  */
3876   if ((code == PLUS_EXPR || code == MULT_EXPR || code == MIN_EXPR
3877        || code == MAX_EXPR || code == BIT_IOR_EXPR || code == BIT_XOR_EXPR
3878        || code == BIT_AND_EXPR)
3879       && (TREE_CODE (arg0) == INTEGER_CST || TREE_CODE (arg0) == REAL_CST))
3880     {
3881       tem = arg0; arg0 = arg1; arg1 = tem;
3882
3883       tem = TREE_OPERAND (t, 0); TREE_OPERAND (t, 0) = TREE_OPERAND (t, 1);
3884       TREE_OPERAND (t, 1) = tem;
3885     }
3886
3887   /* Now WINS is set as described above,
3888      ARG0 is the first operand of EXPR,
3889      and ARG1 is the second operand (if it has more than one operand).
3890
3891      First check for cases where an arithmetic operation is applied to a
3892      compound, conditional, or comparison operation.  Push the arithmetic
3893      operation inside the compound or conditional to see if any folding
3894      can then be done.  Convert comparison to conditional for this purpose.
3895      The also optimizes non-constant cases that used to be done in
3896      expand_expr.
3897
3898      Before we do that, see if this is a BIT_AND_EXPR or a BIT_OR_EXPR,
3899      one of the operands is a comparison and the other is a comparison, a
3900      BIT_AND_EXPR with the constant 1, or a truth value.  In that case, the
3901      code below would make the expression more complex.  Change it to a
3902      TRUTH_{AND,OR}_EXPR.  Likewise, convert a similar NE_EXPR to
3903      TRUTH_XOR_EXPR and an EQ_EXPR to the inversion of a TRUTH_XOR_EXPR.  */
3904
3905   if ((code == BIT_AND_EXPR || code == BIT_IOR_EXPR
3906        || code == EQ_EXPR || code == NE_EXPR)
3907       && ((truth_value_p (TREE_CODE (arg0))
3908            && (truth_value_p (TREE_CODE (arg1))
3909                || (TREE_CODE (arg1) == BIT_AND_EXPR
3910                    && integer_onep (TREE_OPERAND (arg1, 1)))))
3911           || (truth_value_p (TREE_CODE (arg1))
3912               && (truth_value_p (TREE_CODE (arg0))
3913                   || (TREE_CODE (arg0) == BIT_AND_EXPR
3914                       && integer_onep (TREE_OPERAND (arg0, 1)))))))
3915     {
3916       t = fold (build (code == BIT_AND_EXPR ? TRUTH_AND_EXPR
3917                        : code == BIT_IOR_EXPR ? TRUTH_OR_EXPR
3918                        : TRUTH_XOR_EXPR,
3919                        type, arg0, arg1));
3920
3921       if (code == EQ_EXPR)
3922         t = invert_truthvalue (t);
3923
3924       return t;
3925     }
3926
3927   if (TREE_CODE_CLASS (code) == '1')
3928     {
3929       if (TREE_CODE (arg0) == COMPOUND_EXPR)
3930         return build (COMPOUND_EXPR, type, TREE_OPERAND (arg0, 0),
3931                       fold (build1 (code, type, TREE_OPERAND (arg0, 1))));
3932       else if (TREE_CODE (arg0) == COND_EXPR)
3933         {
3934           t = fold (build (COND_EXPR, type, TREE_OPERAND (arg0, 0),
3935                            fold (build1 (code, type, TREE_OPERAND (arg0, 1))),
3936                            fold (build1 (code, type, TREE_OPERAND (arg0, 2)))));
3937
3938           /* If this was a conversion, and all we did was to move into
3939              inside the COND_EXPR, bring it back out.  But leave it if
3940              it is a conversion from integer to integer and the
3941              result precision is no wider than a word since such a
3942              conversion is cheap and may be optimized away by combine,
3943              while it couldn't if it were outside the COND_EXPR.  Then return
3944              so we don't get into an infinite recursion loop taking the
3945              conversion out and then back in.  */
3946
3947           if ((code == NOP_EXPR || code == CONVERT_EXPR
3948                || code == NON_LVALUE_EXPR)
3949               && TREE_CODE (t) == COND_EXPR
3950               && TREE_CODE (TREE_OPERAND (t, 1)) == code
3951               && TREE_CODE (TREE_OPERAND (t, 2)) == code
3952               && (TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 1), 0))
3953                   == TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 2), 0)))
3954               && ! (INTEGRAL_TYPE_P (TREE_TYPE (t))
3955                     && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 1), 0)))
3956                     && TYPE_PRECISION (TREE_TYPE (t)) <= BITS_PER_WORD))
3957             t = build1 (code, type,
3958                         build (COND_EXPR,
3959                                TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 1), 0)),
3960                                TREE_OPERAND (t, 0),
3961                                TREE_OPERAND (TREE_OPERAND (t, 1), 0),
3962                                TREE_OPERAND (TREE_OPERAND (t, 2), 0)));
3963           return t;
3964         }
3965       else if (TREE_CODE_CLASS (TREE_CODE (arg0)) == '<')
3966         return fold (build (COND_EXPR, type, arg0,
3967                             fold (build1 (code, type, integer_one_node)),
3968                             fold (build1 (code, type, integer_zero_node))));
3969    }
3970   else if (TREE_CODE_CLASS (code) == '2'
3971            || TREE_CODE_CLASS (code) == '<')
3972     {
3973       if (TREE_CODE (arg1) == COMPOUND_EXPR)
3974         return build (COMPOUND_EXPR, type, TREE_OPERAND (arg1, 0),
3975                       fold (build (code, type,
3976                                    arg0, TREE_OPERAND (arg1, 1))));
3977       else if ((TREE_CODE (arg1) == COND_EXPR
3978                 || (TREE_CODE_CLASS (TREE_CODE (arg1)) == '<'
3979                     && TREE_CODE_CLASS (code) != '<'))
3980                && (! TREE_SIDE_EFFECTS (arg0) || current_function_decl != 0))
3981         {
3982           tree test, true_value, false_value;
3983           tree lhs = 0, rhs = 0;
3984
3985           if (TREE_CODE (arg1) == COND_EXPR)
3986             {
3987               test = TREE_OPERAND (arg1, 0);
3988               true_value = TREE_OPERAND (arg1, 1);
3989               false_value = TREE_OPERAND (arg1, 2);
3990             }
3991           else
3992             {
3993               tree testtype = TREE_TYPE (arg1);
3994               test = arg1;
3995               true_value = convert (testtype, integer_one_node);
3996               false_value = convert (testtype, integer_zero_node);
3997             }
3998
3999           /* If ARG0 is complex we want to make sure we only evaluate
4000              it once.  Though this is only required if it is volatile, it
4001              might be more efficient even if it is not.  However, if we
4002              succeed in folding one part to a constant, we do not need
4003              to make this SAVE_EXPR.  Since we do this optimization
4004              primarily to see if we do end up with constant and this
4005              SAVE_EXPR interferes with later optimizations, suppressing
4006              it when we can is important.
4007
4008              If we are not in a function, we can't make a SAVE_EXPR, so don't
4009              try to do so.  Don't try to see if the result is a constant
4010              if an arm is a COND_EXPR since we get exponential behavior
4011              in that case.  */
4012
4013           if (TREE_CODE (arg0) != SAVE_EXPR && ! TREE_CONSTANT (arg0)
4014               && current_function_decl != 0
4015               && ((TREE_CODE (arg0) != VAR_DECL
4016                    && TREE_CODE (arg0) != PARM_DECL)
4017                   || TREE_SIDE_EFFECTS (arg0)))
4018             {
4019               if (TREE_CODE (true_value) != COND_EXPR)
4020                 lhs = fold (build (code, type, arg0, true_value));
4021
4022               if (TREE_CODE (false_value) != COND_EXPR)
4023                 rhs = fold (build (code, type, arg0, false_value));
4024
4025               if ((lhs == 0 || ! TREE_CONSTANT (lhs))
4026                   && (rhs == 0 || !TREE_CONSTANT (rhs)))
4027                 arg0 = save_expr (arg0), lhs = rhs = 0;
4028             }
4029
4030           if (lhs == 0)
4031             lhs = fold (build (code, type, arg0, true_value));
4032           if (rhs == 0)
4033             rhs = fold (build (code, type, arg0, false_value));
4034
4035           test = fold (build (COND_EXPR, type, test, lhs, rhs));
4036
4037           if (TREE_CODE (arg0) == SAVE_EXPR)
4038             return build (COMPOUND_EXPR, type,
4039                           convert (void_type_node, arg0),
4040                           strip_compound_expr (test, arg0));
4041           else
4042             return convert (type, test);
4043         }
4044
4045       else if (TREE_CODE (arg0) == COMPOUND_EXPR)
4046         return build (COMPOUND_EXPR, type, TREE_OPERAND (arg0, 0),
4047                       fold (build (code, type, TREE_OPERAND (arg0, 1), arg1)));
4048       else if ((TREE_CODE (arg0) == COND_EXPR
4049                 || (TREE_CODE_CLASS (TREE_CODE (arg0)) == '<'
4050                     && TREE_CODE_CLASS (code) != '<'))
4051                && (! TREE_SIDE_EFFECTS (arg1) || current_function_decl != 0))
4052         {
4053           tree test, true_value, false_value;
4054           tree lhs = 0, rhs = 0;
4055
4056           if (TREE_CODE (arg0) == COND_EXPR)
4057             {
4058               test = TREE_OPERAND (arg0, 0);
4059               true_value = TREE_OPERAND (arg0, 1);
4060               false_value = TREE_OPERAND (arg0, 2);
4061             }
4062           else
4063             {
4064               tree testtype = TREE_TYPE (arg0);
4065               test = arg0;
4066               true_value = convert (testtype, integer_one_node);
4067               false_value = convert (testtype, integer_zero_node);
4068             }
4069
4070           if (TREE_CODE (arg1) != SAVE_EXPR && ! TREE_CONSTANT (arg0)
4071               && current_function_decl != 0
4072               && ((TREE_CODE (arg1) != VAR_DECL
4073                    && TREE_CODE (arg1) != PARM_DECL)
4074                   || TREE_SIDE_EFFECTS (arg1)))
4075             {
4076               if (TREE_CODE (true_value) != COND_EXPR)
4077                 lhs = fold (build (code, type, true_value, arg1));
4078
4079               if (TREE_CODE (false_value) != COND_EXPR)
4080                 rhs = fold (build (code, type, false_value, arg1));
4081
4082               if ((lhs == 0 || ! TREE_CONSTANT (lhs))
4083                   && (rhs == 0 || !TREE_CONSTANT (rhs)))
4084                 arg1 = save_expr (arg1), lhs = rhs = 0;
4085             }
4086
4087           if (lhs == 0)
4088             lhs = fold (build (code, type, true_value, arg1));
4089
4090           if (rhs == 0)
4091             rhs = fold (build (code, type, false_value, arg1));
4092
4093           test = fold (build (COND_EXPR, type, test, lhs, rhs));
4094           if (TREE_CODE (arg1) == SAVE_EXPR)
4095             return build (COMPOUND_EXPR, type,
4096                           convert (void_type_node, arg1),
4097                           strip_compound_expr (test, arg1));
4098           else
4099             return convert (type, test);
4100         }
4101     }
4102   else if (TREE_CODE_CLASS (code) == '<'
4103            && TREE_CODE (arg0) == COMPOUND_EXPR)
4104     return build (COMPOUND_EXPR, type, TREE_OPERAND (arg0, 0),
4105                   fold (build (code, type, TREE_OPERAND (arg0, 1), arg1)));
4106   else if (TREE_CODE_CLASS (code) == '<'
4107            && TREE_CODE (arg1) == COMPOUND_EXPR)
4108     return build (COMPOUND_EXPR, type, TREE_OPERAND (arg1, 0),
4109                   fold (build (code, type, arg0, TREE_OPERAND (arg1, 1))));
4110
4111   switch (code)
4112     {
4113     case INTEGER_CST:
4114     case REAL_CST:
4115     case STRING_CST:
4116     case COMPLEX_CST:
4117     case CONSTRUCTOR:
4118       return t;
4119
4120     case CONST_DECL:
4121       return fold (DECL_INITIAL (t));
4122
4123     case NOP_EXPR:
4124     case FLOAT_EXPR:
4125     case CONVERT_EXPR:
4126     case FIX_TRUNC_EXPR:
4127       /* Other kinds of FIX are not handled properly by fold_convert.  */
4128
4129       if (TREE_TYPE (TREE_OPERAND (t, 0)) == TREE_TYPE (t))
4130         return TREE_OPERAND (t, 0);
4131
4132       /* Handle cases of two conversions in a row.  */
4133       if (TREE_CODE (TREE_OPERAND (t, 0)) == NOP_EXPR
4134           || TREE_CODE (TREE_OPERAND (t, 0)) == CONVERT_EXPR)
4135         {
4136           tree inside_type = TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 0), 0));
4137           tree inter_type = TREE_TYPE (TREE_OPERAND (t, 0));
4138           tree final_type = TREE_TYPE (t);
4139           int inside_int = INTEGRAL_TYPE_P (inside_type);
4140           int inside_ptr = POINTER_TYPE_P (inside_type);
4141           int inside_float = FLOAT_TYPE_P (inside_type);
4142           int inside_prec = TYPE_PRECISION (inside_type);
4143           int inside_unsignedp = TREE_UNSIGNED (inside_type);
4144           int inter_int = INTEGRAL_TYPE_P (inter_type);
4145           int inter_ptr = POINTER_TYPE_P (inter_type);
4146           int inter_float = FLOAT_TYPE_P (inter_type);
4147           int inter_prec = TYPE_PRECISION (inter_type);
4148           int inter_unsignedp = TREE_UNSIGNED (inter_type);
4149           int final_int = INTEGRAL_TYPE_P (final_type);
4150           int final_ptr = POINTER_TYPE_P (final_type);
4151           int final_float = FLOAT_TYPE_P (final_type);
4152           int final_prec = TYPE_PRECISION (final_type);
4153           int final_unsignedp = TREE_UNSIGNED (final_type);
4154
4155           /* In addition to the cases of two conversions in a row
4156              handled below, if we are converting something to its own
4157              type via an object of identical or wider precision, neither
4158              conversion is needed.  */
4159           if (inside_type == final_type
4160               && ((inter_int && final_int) || (inter_float && final_float))
4161               && inter_prec >= final_prec)
4162             return TREE_OPERAND (TREE_OPERAND (t, 0), 0);
4163
4164           /* Likewise, if the intermediate and final types are either both
4165              float or both integer, we don't need the middle conversion if
4166              it is wider than the final type and doesn't change the signedness
4167              (for integers).  Avoid this if the final type is a pointer
4168              since then we sometimes need the inner conversion.  Likewise if
4169              the outer has a precision not equal to the size of its mode.  */
4170           if ((((inter_int || inter_ptr) && (inside_int || inside_ptr))
4171                || (inter_float && inside_float))
4172               && inter_prec >= inside_prec
4173               && (inter_float || inter_unsignedp == inside_unsignedp)
4174               && ! (final_prec != GET_MODE_BITSIZE (TYPE_MODE (final_type))
4175                     && TYPE_MODE (final_type) == TYPE_MODE (inter_type))
4176               && ! final_ptr)
4177             return convert (final_type, TREE_OPERAND (TREE_OPERAND (t, 0), 0));
4178
4179           /* If we have a sign-extension of a zero-extended value, we can
4180              replace that by a single zero-extension.  */
4181           if (inside_int && inter_int && final_int
4182               && inside_prec < inter_prec && inter_prec < final_prec
4183               && inside_unsignedp && !inter_unsignedp)
4184             return convert (final_type, TREE_OPERAND (TREE_OPERAND (t, 0), 0));
4185
4186           /* Two conversions in a row are not needed unless:
4187              - some conversion is floating-point (overstrict for now), or
4188              - the intermediate type is narrower than both initial and
4189                final, or
4190              - the intermediate type and innermost type differ in signedness,
4191                and the outermost type is wider than the intermediate, or
4192              - the initial type is a pointer type and the precisions of the
4193                intermediate and final types differ, or
4194              - the final type is a pointer type and the precisions of the
4195                initial and intermediate types differ.  */
4196           if (! inside_float && ! inter_float && ! final_float
4197               && (inter_prec > inside_prec || inter_prec > final_prec)
4198               && ! (inside_int && inter_int
4199                     && inter_unsignedp != inside_unsignedp
4200                     && inter_prec < final_prec)
4201               && ((inter_unsignedp && inter_prec > inside_prec)
4202                   == (final_unsignedp && final_prec > inter_prec))
4203               && ! (inside_ptr && inter_prec != final_prec)
4204               && ! (final_ptr && inside_prec != inter_prec)
4205               && ! (final_prec != GET_MODE_BITSIZE (TYPE_MODE (final_type))
4206                     && TYPE_MODE (final_type) == TYPE_MODE (inter_type))
4207               && ! final_ptr)
4208             return convert (final_type, TREE_OPERAND (TREE_OPERAND (t, 0), 0));
4209         }
4210
4211       if (TREE_CODE (TREE_OPERAND (t, 0)) == MODIFY_EXPR
4212           && TREE_CONSTANT (TREE_OPERAND (TREE_OPERAND (t, 0), 1))
4213           /* Detect assigning a bitfield.  */
4214           && !(TREE_CODE (TREE_OPERAND (TREE_OPERAND (t, 0), 0)) == COMPONENT_REF
4215                && DECL_BIT_FIELD (TREE_OPERAND (TREE_OPERAND (TREE_OPERAND (t, 0), 0), 1))))
4216         {
4217           /* Don't leave an assignment inside a conversion
4218              unless assigning a bitfield.  */
4219           tree prev = TREE_OPERAND (t, 0);
4220           TREE_OPERAND (t, 0) = TREE_OPERAND (prev, 1);
4221           /* First do the assignment, then return converted constant.  */
4222           t = build (COMPOUND_EXPR, TREE_TYPE (t), prev, fold (t));
4223           TREE_USED (t) = 1;
4224           return t;
4225         }
4226       if (!wins)
4227         {
4228           TREE_CONSTANT (t) = TREE_CONSTANT (arg0);
4229           return t;
4230         }
4231       return fold_convert (t, arg0);
4232
4233 #if 0  /* This loses on &"foo"[0].  */
4234     case ARRAY_REF:
4235         {
4236           int i;
4237
4238           /* Fold an expression like: "foo"[2] */
4239           if (TREE_CODE (arg0) == STRING_CST
4240               && TREE_CODE (arg1) == INTEGER_CST
4241               && !TREE_INT_CST_HIGH (arg1)
4242               && (i = TREE_INT_CST_LOW (arg1)) < TREE_STRING_LENGTH (arg0))
4243             {
4244               t = build_int_2 (TREE_STRING_POINTER (arg0)[i], 0);
4245               TREE_TYPE (t) = TREE_TYPE (TREE_TYPE (arg0));
4246               force_fit_type (t, 0);
4247             }
4248         }
4249       return t;
4250 #endif /* 0 */
4251
4252     case COMPONENT_REF:
4253       if (TREE_CODE (arg0) == CONSTRUCTOR)
4254         {
4255           tree m = purpose_member (arg1, CONSTRUCTOR_ELTS (arg0));
4256           if (m)
4257             t = TREE_VALUE (m);
4258         }
4259       return t;
4260
4261     case RANGE_EXPR:
4262       TREE_CONSTANT (t) = wins;
4263       return t;
4264
4265     case NEGATE_EXPR:
4266       if (wins)
4267         {
4268           if (TREE_CODE (arg0) == INTEGER_CST)
4269             {
4270               HOST_WIDE_INT low, high;
4271               int overflow = neg_double (TREE_INT_CST_LOW (arg0),
4272                                          TREE_INT_CST_HIGH (arg0),
4273                                          &low, &high);
4274               t = build_int_2 (low, high);
4275               TREE_TYPE (t) = type;
4276               TREE_OVERFLOW (t)
4277                 = (TREE_OVERFLOW (arg0)
4278                    | force_fit_type (t, overflow && !TREE_UNSIGNED (type)));
4279               TREE_CONSTANT_OVERFLOW (t)
4280                 = TREE_OVERFLOW (t) | TREE_CONSTANT_OVERFLOW (arg0);
4281             }
4282           else if (TREE_CODE (arg0) == REAL_CST)
4283             t = build_real (type, REAL_VALUE_NEGATE (TREE_REAL_CST (arg0)));
4284         }
4285       else if (TREE_CODE (arg0) == NEGATE_EXPR)
4286         return TREE_OPERAND (arg0, 0);
4287
4288       /* Convert - (a - b) to (b - a) for non-floating-point.  */
4289       else if (TREE_CODE (arg0) == MINUS_EXPR && ! FLOAT_TYPE_P (type))
4290         return build (MINUS_EXPR, type, TREE_OPERAND (arg0, 1),
4291                       TREE_OPERAND (arg0, 0));
4292
4293       return t;
4294
4295     case ABS_EXPR:
4296       if (wins)
4297         {
4298           if (TREE_CODE (arg0) == INTEGER_CST)
4299             {
4300               if (! TREE_UNSIGNED (type)
4301                   && TREE_INT_CST_HIGH (arg0) < 0)
4302                 {
4303                   HOST_WIDE_INT low, high;
4304                   int overflow = neg_double (TREE_INT_CST_LOW (arg0),
4305                                              TREE_INT_CST_HIGH (arg0),
4306                                              &low, &high);
4307                   t = build_int_2 (low, high);
4308                   TREE_TYPE (t) = type;
4309                   TREE_OVERFLOW (t)
4310                     = (TREE_OVERFLOW (arg0)
4311                        | force_fit_type (t, overflow));
4312                   TREE_CONSTANT_OVERFLOW (t)
4313                     = TREE_OVERFLOW (t) | TREE_CONSTANT_OVERFLOW (arg0);
4314                 }
4315             }
4316           else if (TREE_CODE (arg0) == REAL_CST)
4317             {
4318               if (REAL_VALUE_NEGATIVE (TREE_REAL_CST (arg0)))
4319                 t = build_real (type,
4320                                 REAL_VALUE_NEGATE (TREE_REAL_CST (arg0)));
4321             }
4322         }
4323       else if (TREE_CODE (arg0) == ABS_EXPR || TREE_CODE (arg0) == NEGATE_EXPR)
4324         return build1 (ABS_EXPR, type, TREE_OPERAND (arg0, 0));
4325       return t;
4326
4327     case CONJ_EXPR:
4328       if (TREE_CODE (TREE_TYPE (arg0)) != COMPLEX_TYPE)
4329         return arg0;
4330       else if (TREE_CODE (arg0) == COMPLEX_EXPR)
4331         return build (COMPLEX_EXPR, TREE_TYPE (arg0),
4332                       TREE_OPERAND (arg0, 0),
4333                       fold (build1 (NEGATE_EXPR,
4334                                     TREE_TYPE (TREE_TYPE (arg0)),
4335                                     TREE_OPERAND (arg0, 1))));
4336       else if (TREE_CODE (arg0) == COMPLEX_CST)
4337         return build_complex (type, TREE_OPERAND (arg0, 0),
4338                               fold (build1 (NEGATE_EXPR,
4339                                             TREE_TYPE (TREE_TYPE (arg0)),
4340                                             TREE_OPERAND (arg0, 1))));
4341       else if (TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MINUS_EXPR)
4342         return fold (build (TREE_CODE (arg0), type,
4343                             fold (build1 (CONJ_EXPR, type,
4344                                           TREE_OPERAND (arg0, 0))),
4345                             fold (build1 (CONJ_EXPR,
4346                                           type, TREE_OPERAND (arg0, 1)))));
4347       else if (TREE_CODE (arg0) == CONJ_EXPR)
4348         return TREE_OPERAND (arg0, 0);
4349       return t;
4350
4351     case BIT_NOT_EXPR:
4352       if (wins)
4353         {
4354           t = build_int_2 (~ TREE_INT_CST_LOW (arg0),
4355                            ~ TREE_INT_CST_HIGH (arg0));
4356           TREE_TYPE (t) = type;
4357           force_fit_type (t, 0);
4358           TREE_OVERFLOW (t) = TREE_OVERFLOW (arg0);
4359           TREE_CONSTANT_OVERFLOW (t) = TREE_CONSTANT_OVERFLOW (arg0);
4360         }
4361       else if (TREE_CODE (arg0) == BIT_NOT_EXPR)
4362         return TREE_OPERAND (arg0, 0);
4363       return t;
4364
4365     case PLUS_EXPR:
4366       /* A + (-B) -> A - B */
4367       if (TREE_CODE (arg1) == NEGATE_EXPR)
4368         return fold (build (MINUS_EXPR, type, arg0, TREE_OPERAND (arg1, 0)));
4369       else if (! FLOAT_TYPE_P (type))
4370         {
4371           if (integer_zerop (arg1))
4372             return non_lvalue (convert (type, arg0));
4373
4374           /* If we are adding two BIT_AND_EXPR's, both of which are and'ing
4375              with a constant, and the two constants have no bits in common,
4376              we should treat this as a BIT_IOR_EXPR since this may produce more
4377              simplifications.  */
4378           if (TREE_CODE (arg0) == BIT_AND_EXPR
4379               && TREE_CODE (arg1) == BIT_AND_EXPR
4380               && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
4381               && TREE_CODE (TREE_OPERAND (arg1, 1)) == INTEGER_CST
4382               && integer_zerop (const_binop (BIT_AND_EXPR,
4383                                              TREE_OPERAND (arg0, 1),
4384                                              TREE_OPERAND (arg1, 1), 0)))
4385             {
4386               code = BIT_IOR_EXPR;
4387               goto bit_ior;
4388             }
4389
4390           /* (A * C) + (B * C) -> (A+B) * C.  Since we are most concerned
4391              about the case where C is a constant, just try one of the
4392              four possibilities.  */
4393
4394           if (TREE_CODE (arg0) == MULT_EXPR && TREE_CODE (arg1) == MULT_EXPR
4395               && operand_equal_p (TREE_OPERAND (arg0, 1),
4396                                   TREE_OPERAND (arg1, 1), 0))
4397             return fold (build (MULT_EXPR, type,
4398                                 fold (build (PLUS_EXPR, type,
4399                                              TREE_OPERAND (arg0, 0),
4400                                              TREE_OPERAND (arg1, 0))),
4401                                 TREE_OPERAND (arg0, 1)));
4402         }
4403       /* In IEEE floating point, x+0 may not equal x.  */
4404       else if ((TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
4405                 || flag_fast_math)
4406                && real_zerop (arg1))
4407         return non_lvalue (convert (type, arg0));
4408     associate:
4409       /* In most languages, can't associate operations on floats
4410          through parentheses.  Rather than remember where the parentheses
4411          were, we don't associate floats at all.  It shouldn't matter much.
4412          However, associating multiplications is only very slightly
4413          inaccurate, so do that if -ffast-math is specified.  */
4414       if (FLOAT_TYPE_P (type)
4415           && ! (flag_fast_math && code == MULT_EXPR))
4416         goto binary;
4417
4418       /* The varsign == -1 cases happen only for addition and subtraction.
4419          It says that the arg that was split was really CON minus VAR.
4420          The rest of the code applies to all associative operations.  */
4421       if (!wins)
4422         {
4423           tree var, con;
4424           int varsign;
4425
4426           if (split_tree (arg0, code, &var, &con, &varsign))
4427             {
4428               if (varsign == -1)
4429                 {
4430                   /* EXPR is (CON-VAR) +- ARG1.  */
4431                   /* If it is + and VAR==ARG1, return just CONST.  */
4432                   if (code == PLUS_EXPR && operand_equal_p (var, arg1, 0))
4433                     return convert (TREE_TYPE (t), con);
4434
4435                   /* If ARG0 is a constant, don't change things around;
4436                      instead keep all the constant computations together.  */
4437
4438                   if (TREE_CONSTANT (arg0))
4439                     return t;
4440
4441                   /* Otherwise return (CON +- ARG1) - VAR.  */
4442                   t = build (MINUS_EXPR, type,
4443                              fold (build (code, type, con, arg1)), var);
4444                 }
4445               else
4446                 {
4447                   /* EXPR is (VAR+CON) +- ARG1.  */
4448                   /* If it is - and VAR==ARG1, return just CONST.  */
4449                   if (code == MINUS_EXPR && operand_equal_p (var, arg1, 0))
4450                     return convert (TREE_TYPE (t), con);
4451
4452                   /* If ARG0 is a constant, don't change things around;
4453                      instead keep all the constant computations together.  */
4454
4455                   if (TREE_CONSTANT (arg0))
4456                     return t;
4457
4458                   /* Otherwise return VAR +- (ARG1 +- CON).  */
4459                   tem = fold (build (code, type, arg1, con));
4460                   t = build (code, type, var, tem);
4461
4462                   if (integer_zerop (tem)
4463                       && (code == PLUS_EXPR || code == MINUS_EXPR))
4464                     return convert (type, var);
4465                   /* If we have x +/- (c - d) [c an explicit integer]
4466                      change it to x -/+ (d - c) since if d is relocatable
4467                      then the latter can be a single immediate insn
4468                      and the former cannot.  */
4469                   if (TREE_CODE (tem) == MINUS_EXPR
4470                       && TREE_CODE (TREE_OPERAND (tem, 0)) == INTEGER_CST)
4471                     {
4472                       tree tem1 = TREE_OPERAND (tem, 1);
4473                       TREE_OPERAND (tem, 1) = TREE_OPERAND (tem, 0);
4474                       TREE_OPERAND (tem, 0) = tem1;
4475                       TREE_SET_CODE (t,
4476                                      (code == PLUS_EXPR ? MINUS_EXPR : PLUS_EXPR));
4477                     }
4478                 }
4479               return t;
4480             }
4481
4482           if (split_tree (arg1, code, &var, &con, &varsign))
4483             {
4484               if (TREE_CONSTANT (arg1))
4485                 return t;
4486
4487               if (varsign == -1)
4488                 TREE_SET_CODE (t,
4489                                (code == PLUS_EXPR ? MINUS_EXPR : PLUS_EXPR));
4490
4491               /* EXPR is ARG0 +- (CON +- VAR).  */
4492               if (TREE_CODE (t) == MINUS_EXPR
4493                   && operand_equal_p (var, arg0, 0))
4494                 {
4495                   /* If VAR and ARG0 cancel, return just CON or -CON.  */
4496                   if (code == PLUS_EXPR)
4497                     return convert (TREE_TYPE (t), con);
4498                   return fold (build1 (NEGATE_EXPR, TREE_TYPE (t),
4499                                        convert (TREE_TYPE (t), con)));
4500                 }
4501
4502               t = build (TREE_CODE (t), type,
4503                          fold (build (code, TREE_TYPE (t), arg0, con)), var);
4504
4505               if (integer_zerop (TREE_OPERAND (t, 0))
4506                   && TREE_CODE (t) == PLUS_EXPR)
4507                 return convert (TREE_TYPE (t), var);
4508               return t;
4509             }
4510         }
4511     binary:
4512 #if defined (REAL_IS_NOT_DOUBLE) && ! defined (REAL_ARITHMETIC)
4513       if (TREE_CODE (arg1) == REAL_CST)
4514         return t;
4515 #endif /* REAL_IS_NOT_DOUBLE, and no REAL_ARITHMETIC */
4516       if (wins)
4517         t1 = const_binop (code, arg0, arg1, 0);
4518       if (t1 != NULL_TREE)
4519         {
4520           /* The return value should always have
4521              the same type as the original expression.  */
4522           if (TREE_TYPE (t1) != TREE_TYPE (t))
4523             t1 = convert (TREE_TYPE (t), t1);
4524
4525           return t1;
4526         }
4527       return t;
4528
4529     case MINUS_EXPR:
4530       if (! FLOAT_TYPE_P (type))
4531         {
4532           if (! wins && integer_zerop (arg0))
4533             return build1 (NEGATE_EXPR, type, arg1);
4534           if (integer_zerop (arg1))
4535             return non_lvalue (convert (type, arg0));
4536
4537           /* (A * C) - (B * C) -> (A-B) * C.  Since we are most concerned
4538              about the case where C is a constant, just try one of the
4539              four possibilities.  */
4540
4541           if (TREE_CODE (arg0) == MULT_EXPR && TREE_CODE (arg1) == MULT_EXPR
4542               && operand_equal_p (TREE_OPERAND (arg0, 1),
4543                                   TREE_OPERAND (arg1, 1), 0))
4544             return fold (build (MULT_EXPR, type,
4545                                 fold (build (MINUS_EXPR, type,
4546                                              TREE_OPERAND (arg0, 0),
4547                                              TREE_OPERAND (arg1, 0))),
4548                                 TREE_OPERAND (arg0, 1)));
4549         }
4550       /* Convert A - (-B) to A + B.  */
4551       else if (TREE_CODE (arg1) == NEGATE_EXPR)
4552         return fold (build (PLUS_EXPR, type, arg0, TREE_OPERAND (arg1, 0)));
4553
4554       else if (TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
4555                || flag_fast_math)
4556         {
4557           /* Except with IEEE floating point, 0-x equals -x.  */
4558           if (! wins && real_zerop (arg0))
4559             return build1 (NEGATE_EXPR, type, arg1);
4560           /* Except with IEEE floating point, x-0 equals x.  */
4561           if (real_zerop (arg1))
4562             return non_lvalue (convert (type, arg0));
4563         }
4564
4565       /* Fold &x - &x.  This can happen from &x.foo - &x.
4566          This is unsafe for certain floats even in non-IEEE formats.
4567          In IEEE, it is unsafe because it does wrong for NaNs.
4568          Also note that operand_equal_p is always false if an operand
4569          is volatile.  */
4570
4571       if ((! FLOAT_TYPE_P (type) || flag_fast_math)
4572           && operand_equal_p (arg0, arg1, 0))
4573         return convert (type, integer_zero_node);
4574
4575       goto associate;
4576
4577     case MULT_EXPR:
4578       if (! FLOAT_TYPE_P (type))
4579         {
4580           if (integer_zerop (arg1))
4581             return omit_one_operand (type, arg1, arg0);
4582           if (integer_onep (arg1))
4583             return non_lvalue (convert (type, arg0));
4584
4585           /* ((A / C) * C) is A if the division is an
4586              EXACT_DIV_EXPR.   Since C is normally a constant,
4587              just check for one of the four possibilities.  */
4588
4589           if (TREE_CODE (arg0) == EXACT_DIV_EXPR
4590               && operand_equal_p (TREE_OPERAND (arg0, 1), arg1, 0))
4591             return TREE_OPERAND (arg0, 0);
4592
4593           /* (a * (1 << b)) is (a << b)  */
4594           if (TREE_CODE (arg1) == LSHIFT_EXPR
4595               && integer_onep (TREE_OPERAND (arg1, 0)))
4596             return fold (build (LSHIFT_EXPR, type, arg0,
4597                                 TREE_OPERAND (arg1, 1)));
4598           if (TREE_CODE (arg0) == LSHIFT_EXPR
4599               && integer_onep (TREE_OPERAND (arg0, 0)))
4600             return fold (build (LSHIFT_EXPR, type, arg1,
4601                                 TREE_OPERAND (arg0, 1)));
4602         }
4603       else
4604         {
4605           /* x*0 is 0, except for IEEE floating point.  */
4606           if ((TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
4607                || flag_fast_math)
4608               && real_zerop (arg1))
4609             return omit_one_operand (type, arg1, arg0);
4610           /* In IEEE floating point, x*1 is not equivalent to x for snans.
4611              However, ANSI says we can drop signals,
4612              so we can do this anyway.  */
4613           if (real_onep (arg1))
4614             return non_lvalue (convert (type, arg0));
4615           /* x*2 is x+x */
4616           if (! wins && real_twop (arg1) && current_function_decl != 0)
4617             {
4618               tree arg = save_expr (arg0);
4619               return build (PLUS_EXPR, type, arg, arg);
4620             }
4621         }
4622       goto associate;
4623
4624     case BIT_IOR_EXPR:
4625     bit_ior:
4626       {
4627       register enum tree_code code0, code1;
4628
4629       if (integer_all_onesp (arg1))
4630         return omit_one_operand (type, arg1, arg0);
4631       if (integer_zerop (arg1))
4632         return non_lvalue (convert (type, arg0));
4633       t1 = distribute_bit_expr (code, type, arg0, arg1);
4634       if (t1 != NULL_TREE)
4635         return t1;
4636
4637       /* (A << C1) | (A >> C2) if A is unsigned and C1+C2 is the size of A
4638          is a rotate of A by C1 bits.  */
4639       /* (A << B) | (A >> (Z - B)) if A is unsigned and Z is the size of A
4640          is a rotate of A by B bits.  */
4641
4642       code0 = TREE_CODE (arg0);
4643       code1 = TREE_CODE (arg1);
4644       if (((code0 == RSHIFT_EXPR && code1 == LSHIFT_EXPR)
4645           || (code1 == RSHIFT_EXPR && code0 == LSHIFT_EXPR))
4646           && operand_equal_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg1,0), 0)
4647           && TREE_UNSIGNED (TREE_TYPE (TREE_OPERAND (arg0, 0))))
4648         {
4649           register tree tree01, tree11;
4650           register enum tree_code code01, code11;
4651
4652           tree01 = TREE_OPERAND (arg0, 1);
4653           tree11 = TREE_OPERAND (arg1, 1);
4654           code01 = TREE_CODE (tree01);
4655           code11 = TREE_CODE (tree11);
4656           if (code01 == INTEGER_CST
4657             && code11 == INTEGER_CST
4658             && TREE_INT_CST_HIGH (tree01) == 0
4659             && TREE_INT_CST_HIGH (tree11) == 0
4660             && ((TREE_INT_CST_LOW (tree01) + TREE_INT_CST_LOW (tree11))
4661               == TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (arg0, 0)))))
4662             return build (LROTATE_EXPR, type, TREE_OPERAND (arg0, 0),
4663                       code0 == LSHIFT_EXPR ? tree01 : tree11);
4664           else if (code11 == MINUS_EXPR
4665                 && TREE_CODE (TREE_OPERAND (tree11, 0)) == INTEGER_CST
4666                 && TREE_INT_CST_HIGH (TREE_OPERAND (tree11, 0)) == 0
4667                 && TREE_INT_CST_LOW (TREE_OPERAND (tree11, 0))
4668                   == TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (arg0, 0)))
4669                 && operand_equal_p (tree01, TREE_OPERAND (tree11, 1), 0))
4670             return build (code0 == LSHIFT_EXPR ? LROTATE_EXPR : RROTATE_EXPR,
4671                         type, TREE_OPERAND (arg0, 0), tree01);
4672           else if (code01 == MINUS_EXPR
4673                 && TREE_CODE (TREE_OPERAND (tree01, 0)) == INTEGER_CST
4674                 && TREE_INT_CST_HIGH (TREE_OPERAND (tree01, 0)) == 0
4675                 && TREE_INT_CST_LOW (TREE_OPERAND (tree01, 0))
4676                   == TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (arg0, 0)))
4677                 && operand_equal_p (tree11, TREE_OPERAND (tree01, 1), 0))
4678             return build (code0 != LSHIFT_EXPR ? LROTATE_EXPR : RROTATE_EXPR,
4679                         type, TREE_OPERAND (arg0, 0), tree11);
4680         }
4681
4682       goto associate;
4683       }
4684
4685     case BIT_XOR_EXPR:
4686       if (integer_zerop (arg1))
4687         return non_lvalue (convert (type, arg0));
4688       if (integer_all_onesp (arg1))
4689         return fold (build1 (BIT_NOT_EXPR, type, arg0));
4690       goto associate;
4691
4692     case BIT_AND_EXPR:
4693     bit_and:
4694       if (integer_all_onesp (arg1))
4695         return non_lvalue (convert (type, arg0));
4696       if (integer_zerop (arg1))
4697         return omit_one_operand (type, arg1, arg0);
4698       t1 = distribute_bit_expr (code, type, arg0, arg1);
4699       if (t1 != NULL_TREE)
4700         return t1;
4701       /* Simplify ((int)c & 0x377) into (int)c, if c is unsigned char.  */
4702       if (TREE_CODE (arg0) == INTEGER_CST && TREE_CODE (arg1) == NOP_EXPR
4703           && TREE_UNSIGNED (TREE_TYPE (TREE_OPERAND (arg1, 0))))
4704         {
4705           int prec = TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (arg1, 0)));
4706           if (prec < BITS_PER_WORD && prec < HOST_BITS_PER_WIDE_INT
4707               && (~TREE_INT_CST_LOW (arg0)
4708                   & (((HOST_WIDE_INT) 1 << prec) - 1)) == 0)
4709             return build1 (NOP_EXPR, type, TREE_OPERAND (arg1, 0));
4710         }
4711       if (TREE_CODE (arg1) == INTEGER_CST && TREE_CODE (arg0) == NOP_EXPR
4712           && TREE_UNSIGNED (TREE_TYPE (TREE_OPERAND (arg0, 0))))
4713         {
4714           int prec = TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (arg0, 0)));
4715           if (prec < BITS_PER_WORD && prec < HOST_BITS_PER_WIDE_INT
4716               && (~TREE_INT_CST_LOW (arg1)
4717                   & (((HOST_WIDE_INT) 1 << prec) - 1)) == 0)
4718             return build1 (NOP_EXPR, type, TREE_OPERAND (arg0, 0));
4719         }
4720       goto associate;
4721
4722     case BIT_ANDTC_EXPR:
4723       if (integer_all_onesp (arg0))
4724         return non_lvalue (convert (type, arg1));
4725       if (integer_zerop (arg0))
4726         return omit_one_operand (type, arg0, arg1);
4727       if (TREE_CODE (arg1) == INTEGER_CST)
4728         {
4729           arg1 = fold (build1 (BIT_NOT_EXPR, type, arg1));
4730           code = BIT_AND_EXPR;
4731           goto bit_and;
4732         }
4733       goto binary;
4734
4735     case RDIV_EXPR:
4736       /* In most cases, do nothing with a divide by zero.  */
4737 #if !defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
4738 #ifndef REAL_INFINITY
4739       if (TREE_CODE (arg1) == REAL_CST && real_zerop (arg1))
4740         return t;
4741 #endif
4742 #endif /* not REAL_IS_NOT_DOUBLE, or REAL_ARITHMETIC */
4743
4744       /* In IEEE floating point, x/1 is not equivalent to x for snans.
4745          However, ANSI says we can drop signals, so we can do this anyway.  */
4746       if (real_onep (arg1))
4747         return non_lvalue (convert (type, arg0));
4748
4749       /* If ARG1 is a constant, we can convert this to a multiply by the
4750          reciprocal.  This does not have the same rounding properties,
4751          so only do this if -ffast-math.  We can actually always safely
4752          do it if ARG1 is a power of two, but it's hard to tell if it is
4753          or not in a portable manner.  */
4754       if (TREE_CODE (arg1) == REAL_CST)
4755         {
4756           if (flag_fast_math
4757               && 0 != (tem = const_binop (code, build_real (type, dconst1),
4758                                           arg1, 0)))
4759             return fold (build (MULT_EXPR, type, arg0, tem));
4760           /* Find the reciprocal if optimizing and the result is exact. */
4761           else if (optimize)
4762             {
4763               REAL_VALUE_TYPE r;
4764               r = TREE_REAL_CST (arg1);
4765               if (exact_real_inverse (TYPE_MODE(TREE_TYPE(arg0)), &r))
4766                   {
4767                     tem = build_real (type, r);
4768                     return fold (build (MULT_EXPR, type, arg0, tem));
4769                   }
4770             }
4771         }
4772       goto binary;
4773
4774     case TRUNC_DIV_EXPR:
4775     case ROUND_DIV_EXPR:
4776     case FLOOR_DIV_EXPR:
4777     case CEIL_DIV_EXPR:
4778     case EXACT_DIV_EXPR:
4779       if (integer_onep (arg1))
4780         return non_lvalue (convert (type, arg0));
4781       if (integer_zerop (arg1))
4782         return t;
4783
4784       /* If arg0 is a multiple of arg1, then rewrite to the fastest div
4785          operation, EXACT_DIV_EXPR.
4786
4787          Note that only CEIL_DIV_EXPR and FLOOR_DIV_EXPR are rewritten now.
4788          At one time others generated faster code, it's not clear if they do
4789          after the last round to changes to the DIV code in expmed.c.  */
4790       if ((code == CEIL_DIV_EXPR || code == FLOOR_DIV_EXPR)
4791           && multiple_of_p (type, arg0, arg1))
4792         return fold (build (EXACT_DIV_EXPR, type, arg0, arg1));
4793
4794       /* If we have ((a / C1) / C2) where both division are the same type, try
4795          to simplify.  First see if C1 * C2 overflows or not.  */
4796       if (TREE_CODE (arg0) == code && TREE_CODE (arg1) == INTEGER_CST
4797           && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST)
4798         {
4799           tree new_divisor;
4800
4801           new_divisor = const_binop (MULT_EXPR, TREE_OPERAND (arg0, 1), arg1, 0);
4802           tem = const_binop (FLOOR_DIV_EXPR, new_divisor, arg1, 0);
4803
4804           if (TREE_INT_CST_LOW (TREE_OPERAND (arg0, 1)) == TREE_INT_CST_LOW (tem)
4805               && TREE_INT_CST_HIGH (TREE_OPERAND (arg0, 1)) == TREE_INT_CST_HIGH (tem))
4806             {
4807               /* If no overflow, divide by C1*C2.  */
4808               return fold (build (code, type, TREE_OPERAND (arg0, 0), new_divisor));
4809             }
4810         }
4811
4812       /* Look for ((a * C1) / C3) or (((a * C1) + C2) / C3),
4813          where C1 % C3 == 0 or C3 % C1 == 0.  We can simplify these
4814          expressions, which often appear in the offsets or sizes of
4815          objects with a varying size.  Only deal with positive divisors
4816          and multiplicands.   If C2 is negative, we must have C2 % C3 == 0.
4817
4818          Look for NOPs and SAVE_EXPRs inside.  */
4819
4820       if (TREE_CODE (arg1) == INTEGER_CST
4821           && tree_int_cst_sgn (arg1) >= 0)
4822         {
4823           int have_save_expr = 0;
4824           tree c2 = integer_zero_node;
4825           tree xarg0 = arg0;
4826
4827           if (TREE_CODE (xarg0) == SAVE_EXPR && SAVE_EXPR_RTL (xarg0) == 0)
4828             have_save_expr = 1, xarg0 = TREE_OPERAND (xarg0, 0);
4829
4830           STRIP_NOPS (xarg0);
4831
4832           /* Look inside the dividend and simplify using EXACT_DIV_EXPR
4833              if possible.  */
4834           if (TREE_CODE (xarg0) == MULT_EXPR
4835               && multiple_of_p (type, TREE_OPERAND (xarg0, 0), arg1))
4836             {
4837               tree t;
4838
4839               t = fold (build (MULT_EXPR, type,
4840                                fold (build (EXACT_DIV_EXPR, type,
4841                                             TREE_OPERAND (xarg0, 0), arg1)),
4842                                TREE_OPERAND (xarg0, 1)));
4843               if (have_save_expr)
4844                 t = save_expr (t);
4845               return t;
4846
4847             }
4848
4849           if (TREE_CODE (xarg0) == MULT_EXPR
4850               && multiple_of_p (type, TREE_OPERAND (xarg0, 1), arg1))
4851             {
4852               tree t;
4853
4854               t = fold (build (MULT_EXPR, type,
4855                                fold (build (EXACT_DIV_EXPR, type,
4856                                             TREE_OPERAND (xarg0, 1), arg1)),
4857                                TREE_OPERAND (xarg0, 0)));
4858               if (have_save_expr)
4859                 t = save_expr (t);
4860               return t;
4861             }
4862
4863           if (TREE_CODE (xarg0) == PLUS_EXPR
4864               && TREE_CODE (TREE_OPERAND (xarg0, 1)) == INTEGER_CST)
4865             c2 = TREE_OPERAND (xarg0, 1), xarg0 = TREE_OPERAND (xarg0, 0);
4866           else if (TREE_CODE (xarg0) == MINUS_EXPR
4867                    && TREE_CODE (TREE_OPERAND (xarg0, 1)) == INTEGER_CST
4868                    /* If we are doing this computation unsigned, the negate
4869                       is incorrect.  */
4870                    && ! TREE_UNSIGNED (type))
4871             {
4872               c2 = fold (build1 (NEGATE_EXPR, type, TREE_OPERAND (xarg0, 1)));
4873               xarg0 = TREE_OPERAND (xarg0, 0);
4874             }
4875
4876           if (TREE_CODE (xarg0) == SAVE_EXPR && SAVE_EXPR_RTL (xarg0) == 0)
4877             have_save_expr = 1, xarg0 = TREE_OPERAND (xarg0, 0);
4878
4879           STRIP_NOPS (xarg0);
4880
4881           if (TREE_CODE (xarg0) == MULT_EXPR
4882               && TREE_CODE (TREE_OPERAND (xarg0, 1)) == INTEGER_CST
4883               && tree_int_cst_sgn (TREE_OPERAND (xarg0, 1)) >= 0
4884               && (integer_zerop (const_binop (TRUNC_MOD_EXPR,
4885                                               TREE_OPERAND (xarg0, 1), arg1, 1))
4886                   || integer_zerop (const_binop (TRUNC_MOD_EXPR, arg1,
4887                                                  TREE_OPERAND (xarg0, 1), 1)))
4888               && (tree_int_cst_sgn (c2) >= 0
4889                   || integer_zerop (const_binop (TRUNC_MOD_EXPR, c2,
4890                                                  arg1, 1))))
4891             {
4892               tree outer_div = integer_one_node;
4893               tree c1 = TREE_OPERAND (xarg0, 1);
4894               tree c3 = arg1;
4895
4896               /* If C3 > C1, set them equal and do a divide by
4897                  C3/C1 at the end of the operation.  */
4898               if (tree_int_cst_lt (c1, c3))
4899                 outer_div = const_binop (code, c3, c1, 0), c3 = c1;
4900
4901               /* The result is A * (C1/C3) + (C2/C3).  */
4902               t = fold (build (PLUS_EXPR, type,
4903                                fold (build (MULT_EXPR, type,
4904                                             TREE_OPERAND (xarg0, 0),
4905                                             const_binop (code, c1, c3, 1))),
4906                                const_binop (code, c2, c3, 1)));
4907
4908               if (! integer_onep (outer_div))
4909                 t = fold (build (code, type, t, convert (type, outer_div)));
4910
4911               if (have_save_expr)
4912                 t = save_expr (t);
4913
4914               return t;
4915             }
4916         }
4917
4918       goto binary;
4919
4920     case CEIL_MOD_EXPR:
4921     case FLOOR_MOD_EXPR:
4922     case ROUND_MOD_EXPR:
4923     case TRUNC_MOD_EXPR:
4924       if (integer_onep (arg1))
4925         return omit_one_operand (type, integer_zero_node, arg0);
4926       if (integer_zerop (arg1))
4927         return t;
4928
4929       /* Look for ((a * C1) % C3) or (((a * C1) + C2) % C3),
4930          where C1 % C3 == 0.  Handle similarly to the division case,
4931          but don't bother with SAVE_EXPRs.  */
4932
4933       if (TREE_CODE (arg1) == INTEGER_CST
4934           && ! integer_zerop (arg1))
4935         {
4936           tree c2 = integer_zero_node;
4937           tree xarg0 = arg0;
4938
4939           if (TREE_CODE (xarg0) == PLUS_EXPR
4940               && TREE_CODE (TREE_OPERAND (xarg0, 1)) == INTEGER_CST)
4941             c2 = TREE_OPERAND (xarg0, 1), xarg0 = TREE_OPERAND (xarg0, 0);
4942           else if (TREE_CODE (xarg0) == MINUS_EXPR
4943                    && TREE_CODE (TREE_OPERAND (xarg0, 1)) == INTEGER_CST
4944                    && ! TREE_UNSIGNED (type))
4945             {
4946               c2 = fold (build1 (NEGATE_EXPR, type, TREE_OPERAND (xarg0, 1)));
4947               xarg0 = TREE_OPERAND (xarg0, 0);
4948             }
4949
4950           STRIP_NOPS (xarg0);
4951
4952           if (TREE_CODE (xarg0) == MULT_EXPR
4953               && TREE_CODE (TREE_OPERAND (xarg0, 1)) == INTEGER_CST
4954               && integer_zerop (const_binop (TRUNC_MOD_EXPR,
4955                                              TREE_OPERAND (xarg0, 1),
4956                                              arg1, 1))
4957               && tree_int_cst_sgn (c2) >= 0)
4958             /* The result is (C2%C3).  */
4959             return omit_one_operand (type, const_binop (code, c2, arg1, 1),
4960                                      TREE_OPERAND (xarg0, 0));
4961         }
4962
4963       goto binary;
4964
4965     case LSHIFT_EXPR:
4966     case RSHIFT_EXPR:
4967     case LROTATE_EXPR:
4968     case RROTATE_EXPR:
4969       if (integer_zerop (arg1))
4970         return non_lvalue (convert (type, arg0));
4971       /* Since negative shift count is not well-defined,
4972          don't try to compute it in the compiler.  */
4973       if (TREE_CODE (arg1) == INTEGER_CST && tree_int_cst_sgn (arg1) < 0)
4974         return t;
4975       /* Rewrite an LROTATE_EXPR by a constant into an
4976          RROTATE_EXPR by a new constant.  */
4977       if (code == LROTATE_EXPR && TREE_CODE (arg1) == INTEGER_CST)
4978         {
4979           TREE_SET_CODE (t, RROTATE_EXPR);
4980           code = RROTATE_EXPR;
4981           TREE_OPERAND (t, 1) = arg1
4982             = const_binop
4983               (MINUS_EXPR,
4984                convert (TREE_TYPE (arg1),
4985                         build_int_2 (GET_MODE_BITSIZE (TYPE_MODE (type)), 0)),
4986                arg1, 0);
4987           if (tree_int_cst_sgn (arg1) < 0)
4988             return t;
4989         }
4990
4991       /* If we have a rotate of a bit operation with the rotate count and
4992          the second operand of the bit operation both constant,
4993          permute the two operations.  */
4994       if (code == RROTATE_EXPR && TREE_CODE (arg1) == INTEGER_CST
4995           && (TREE_CODE (arg0) == BIT_AND_EXPR
4996               || TREE_CODE (arg0) == BIT_ANDTC_EXPR
4997               || TREE_CODE (arg0) == BIT_IOR_EXPR
4998               || TREE_CODE (arg0) == BIT_XOR_EXPR)
4999           && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST)
5000         return fold (build (TREE_CODE (arg0), type,
5001                             fold (build (code, type,
5002                                          TREE_OPERAND (arg0, 0), arg1)),
5003                             fold (build (code, type,
5004                                          TREE_OPERAND (arg0, 1), arg1))));
5005
5006       /* Two consecutive rotates adding up to the width of the mode can
5007          be ignored.  */
5008       if (code == RROTATE_EXPR && TREE_CODE (arg1) == INTEGER_CST
5009           && TREE_CODE (arg0) == RROTATE_EXPR
5010           && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
5011           && TREE_INT_CST_HIGH (arg1) == 0
5012           && TREE_INT_CST_HIGH (TREE_OPERAND (arg0, 1)) == 0
5013           && ((TREE_INT_CST_LOW (arg1)
5014                + TREE_INT_CST_LOW (TREE_OPERAND (arg0, 1)))
5015               == GET_MODE_BITSIZE (TYPE_MODE (type))))
5016         return TREE_OPERAND (arg0, 0);
5017
5018       goto binary;
5019
5020     case MIN_EXPR:
5021       if (operand_equal_p (arg0, arg1, 0))
5022         return arg0;
5023       if (INTEGRAL_TYPE_P (type)
5024           && operand_equal_p (arg1, TYPE_MIN_VALUE (type), 1))
5025         return omit_one_operand (type, arg1, arg0);
5026       goto associate;
5027
5028     case MAX_EXPR:
5029       if (operand_equal_p (arg0, arg1, 0))
5030         return arg0;
5031       if (INTEGRAL_TYPE_P (type)
5032           && TYPE_MAX_VALUE (type)
5033           && operand_equal_p (arg1, TYPE_MAX_VALUE (type), 1))
5034         return omit_one_operand (type, arg1, arg0);
5035       goto associate;
5036
5037     case TRUTH_NOT_EXPR:
5038       /* Note that the operand of this must be an int
5039          and its values must be 0 or 1.
5040          ("true" is a fixed value perhaps depending on the language,
5041          but we don't handle values other than 1 correctly yet.)  */
5042       tem = invert_truthvalue (arg0);
5043       /* Avoid infinite recursion.  */
5044       if (TREE_CODE (tem) == TRUTH_NOT_EXPR)
5045         return t;
5046       return convert (type, tem);
5047
5048     case TRUTH_ANDIF_EXPR:
5049       /* Note that the operands of this must be ints
5050          and their values must be 0 or 1.
5051          ("true" is a fixed value perhaps depending on the language.)  */
5052       /* If first arg is constant zero, return it.  */
5053       if (integer_zerop (arg0))
5054         return arg0;
5055     case TRUTH_AND_EXPR:
5056       /* If either arg is constant true, drop it.  */
5057       if (TREE_CODE (arg0) == INTEGER_CST && ! integer_zerop (arg0))
5058         return non_lvalue (arg1);
5059       if (TREE_CODE (arg1) == INTEGER_CST && ! integer_zerop (arg1))
5060         return non_lvalue (arg0);
5061       /* If second arg is constant zero, result is zero, but first arg
5062          must be evaluated.  */
5063       if (integer_zerop (arg1))
5064         return omit_one_operand (type, arg1, arg0);
5065       /* Likewise for first arg, but note that only the TRUTH_AND_EXPR
5066          case will be handled here.  */
5067       if (integer_zerop (arg0))
5068         return omit_one_operand (type, arg0, arg1);
5069
5070     truth_andor:
5071       /* We only do these simplifications if we are optimizing.  */
5072       if (!optimize)
5073         return t;
5074
5075       /* Check for things like (A || B) && (A || C).  We can convert this
5076          to A || (B && C).  Note that either operator can be any of the four
5077          truth and/or operations and the transformation will still be
5078          valid.   Also note that we only care about order for the
5079          ANDIF and ORIF operators.  If B contains side effects, this
5080          might change the truth-value of A. */
5081       if (TREE_CODE (arg0) == TREE_CODE (arg1)
5082           && (TREE_CODE (arg0) == TRUTH_ANDIF_EXPR
5083               || TREE_CODE (arg0) == TRUTH_ORIF_EXPR
5084               || TREE_CODE (arg0) == TRUTH_AND_EXPR
5085               || TREE_CODE (arg0) == TRUTH_OR_EXPR)
5086           && ! TREE_SIDE_EFFECTS (TREE_OPERAND (arg0, 1)))
5087         {
5088           tree a00 = TREE_OPERAND (arg0, 0);
5089           tree a01 = TREE_OPERAND (arg0, 1);
5090           tree a10 = TREE_OPERAND (arg1, 0);
5091           tree a11 = TREE_OPERAND (arg1, 1);
5092           int commutative = ((TREE_CODE (arg0) == TRUTH_OR_EXPR
5093                               || TREE_CODE (arg0) == TRUTH_AND_EXPR)
5094                              && (code == TRUTH_AND_EXPR
5095                                  || code == TRUTH_OR_EXPR));
5096
5097           if (operand_equal_p (a00, a10, 0))
5098             return fold (build (TREE_CODE (arg0), type, a00,
5099                                 fold (build (code, type, a01, a11))));
5100           else if (commutative && operand_equal_p (a00, a11, 0))
5101             return fold (build (TREE_CODE (arg0), type, a00,
5102                                 fold (build (code, type, a01, a10))));
5103           else if (commutative && operand_equal_p (a01, a10, 0))
5104             return fold (build (TREE_CODE (arg0), type, a01,
5105                                 fold (build (code, type, a00, a11))));
5106
5107           /* This case if tricky because we must either have commutative
5108              operators or else A10 must not have side-effects.  */
5109
5110           else if ((commutative || ! TREE_SIDE_EFFECTS (a10))
5111                    && operand_equal_p (a01, a11, 0))
5112             return fold (build (TREE_CODE (arg0), type,
5113                                 fold (build (code, type, a00, a10)),
5114                                 a01));
5115         }
5116
5117       /* See if we can build a range comparison.  */
5118       if (0 != (tem = fold_range_test (t)))
5119         return tem;
5120
5121       /* Check for the possibility of merging component references.  If our
5122          lhs is another similar operation, try to merge its rhs with our
5123          rhs.  Then try to merge our lhs and rhs.  */
5124       if (TREE_CODE (arg0) == code
5125           && 0 != (tem = fold_truthop (code, type,
5126                                        TREE_OPERAND (arg0, 1), arg1)))
5127         return fold (build (code, type, TREE_OPERAND (arg0, 0), tem));
5128
5129       if ((tem = fold_truthop (code, type, arg0, arg1)) != 0)
5130         return tem;
5131
5132       return t;
5133
5134     case TRUTH_ORIF_EXPR:
5135       /* Note that the operands of this must be ints
5136          and their values must be 0 or true.
5137          ("true" is a fixed value perhaps depending on the language.)  */
5138       /* If first arg is constant true, return it.  */
5139       if (TREE_CODE (arg0) == INTEGER_CST && ! integer_zerop (arg0))
5140         return arg0;
5141     case TRUTH_OR_EXPR:
5142       /* If either arg is constant zero, drop it.  */
5143       if (TREE_CODE (arg0) == INTEGER_CST && integer_zerop (arg0))
5144         return non_lvalue (arg1);
5145       if (TREE_CODE (arg1) == INTEGER_CST && integer_zerop (arg1))
5146         return non_lvalue (arg0);
5147       /* If second arg is constant true, result is true, but we must
5148          evaluate first arg.  */
5149       if (TREE_CODE (arg1) == INTEGER_CST && ! integer_zerop (arg1))
5150         return omit_one_operand (type, arg1, arg0);
5151       /* Likewise for first arg, but note this only occurs here for
5152          TRUTH_OR_EXPR.  */
5153       if (TREE_CODE (arg0) == INTEGER_CST && ! integer_zerop (arg0))
5154         return omit_one_operand (type, arg0, arg1);
5155       goto truth_andor;
5156
5157     case TRUTH_XOR_EXPR:
5158       /* If either arg is constant zero, drop it.  */
5159       if (integer_zerop (arg0))
5160         return non_lvalue (arg1);
5161       if (integer_zerop (arg1))
5162         return non_lvalue (arg0);
5163       /* If either arg is constant true, this is a logical inversion.  */
5164       if (integer_onep (arg0))
5165         return non_lvalue (invert_truthvalue (arg1));
5166       if (integer_onep (arg1))
5167         return non_lvalue (invert_truthvalue (arg0));
5168       return t;
5169
5170     case EQ_EXPR:
5171     case NE_EXPR:
5172     case LT_EXPR:
5173     case GT_EXPR:
5174     case LE_EXPR:
5175     case GE_EXPR:
5176       /* If one arg is a constant integer, put it last.  */
5177       if (TREE_CODE (arg0) == INTEGER_CST
5178           && TREE_CODE (arg1) != INTEGER_CST)
5179         {
5180           TREE_OPERAND (t, 0) = arg1;
5181           TREE_OPERAND (t, 1) = arg0;
5182           arg0 = TREE_OPERAND (t, 0);
5183           arg1 = TREE_OPERAND (t, 1);
5184           code = swap_tree_comparison (code);
5185           TREE_SET_CODE (t, code);
5186         }
5187
5188       /* Convert foo++ == CONST into ++foo == CONST + INCR.
5189          First, see if one arg is constant; find the constant arg
5190          and the other one.  */
5191       {
5192         tree constop = 0, varop = NULL_TREE;
5193         int constopnum = -1;
5194
5195         if (TREE_CONSTANT (arg1))
5196           constopnum = 1, constop = arg1, varop = arg0;
5197         if (TREE_CONSTANT (arg0))
5198           constopnum = 0, constop = arg0, varop = arg1;
5199
5200         if (constop && TREE_CODE (varop) == POSTINCREMENT_EXPR)
5201           {
5202             /* This optimization is invalid for ordered comparisons
5203                if CONST+INCR overflows or if foo+incr might overflow.
5204                This optimization is invalid for floating point due to rounding.
5205                For pointer types we assume overflow doesn't happen.  */
5206             if (POINTER_TYPE_P (TREE_TYPE (varop))
5207                 || (! FLOAT_TYPE_P (TREE_TYPE (varop))
5208                     && (code == EQ_EXPR || code == NE_EXPR)))
5209               {
5210                 tree newconst
5211                   = fold (build (PLUS_EXPR, TREE_TYPE (varop),
5212                                  constop, TREE_OPERAND (varop, 1)));
5213                 TREE_SET_CODE (varop, PREINCREMENT_EXPR);
5214
5215                 /* If VAROP is a reference to a bitfield, we must mask
5216                    the constant by the width of the field.  */
5217                 if (TREE_CODE (TREE_OPERAND (varop, 0)) == COMPONENT_REF
5218                     && DECL_BIT_FIELD(TREE_OPERAND
5219                                       (TREE_OPERAND (varop, 0), 1)))
5220                   {
5221                     int size
5222                       = TREE_INT_CST_LOW (DECL_SIZE
5223                                           (TREE_OPERAND
5224                                            (TREE_OPERAND (varop, 0), 1)));
5225                     tree mask, unsigned_type;
5226                     int precision;
5227                     tree folded_compare;
5228
5229                     /* First check whether the comparison would come out
5230                        always the same.  If we don't do that we would
5231                        change the meaning with the masking.  */
5232                     if (constopnum == 0)
5233                       folded_compare = fold (build (code, type, constop,
5234                                                     TREE_OPERAND (varop, 0)));
5235                     else
5236                       folded_compare = fold (build (code, type,
5237                                                     TREE_OPERAND (varop, 0),
5238                                                     constop));
5239                     if (integer_zerop (folded_compare)
5240                         || integer_onep (folded_compare))
5241                       return omit_one_operand (type, folded_compare, varop);
5242
5243                     unsigned_type = type_for_size (size, 1);
5244                     precision = TYPE_PRECISION (unsigned_type);
5245                     mask = build_int_2 (~0, ~0);
5246                     TREE_TYPE (mask) = unsigned_type;
5247                     force_fit_type (mask, 0);
5248                     mask = const_binop (RSHIFT_EXPR, mask,
5249                                         size_int (precision - size), 0);
5250                     newconst = fold (build (BIT_AND_EXPR,
5251                                             TREE_TYPE (varop), newconst,
5252                                             convert (TREE_TYPE (varop),
5253                                                      mask)));
5254                   }
5255
5256
5257                 t = build (code, type, TREE_OPERAND (t, 0),
5258                            TREE_OPERAND (t, 1));
5259                 TREE_OPERAND (t, constopnum) = newconst;
5260                 return t;
5261               }
5262           }
5263         else if (constop && TREE_CODE (varop) == POSTDECREMENT_EXPR)
5264           {
5265             if (POINTER_TYPE_P (TREE_TYPE (varop))
5266                 || (! FLOAT_TYPE_P (TREE_TYPE (varop))
5267                     && (code == EQ_EXPR || code == NE_EXPR)))
5268               {
5269                 tree newconst
5270                   = fold (build (MINUS_EXPR, TREE_TYPE (varop),
5271                                  constop, TREE_OPERAND (varop, 1)));
5272                 TREE_SET_CODE (varop, PREDECREMENT_EXPR);
5273
5274                 if (TREE_CODE (TREE_OPERAND (varop, 0)) == COMPONENT_REF
5275                     && DECL_BIT_FIELD(TREE_OPERAND
5276                                       (TREE_OPERAND (varop, 0), 1)))
5277                   {
5278                     int size
5279                       = TREE_INT_CST_LOW (DECL_SIZE
5280                                           (TREE_OPERAND
5281                                            (TREE_OPERAND (varop, 0), 1)));
5282                     tree mask, unsigned_type;
5283                     int precision;
5284                     tree folded_compare;
5285
5286                     if (constopnum == 0)
5287                       folded_compare = fold (build (code, type, constop,
5288                                                     TREE_OPERAND (varop, 0)));
5289                     else
5290                       folded_compare = fold (build (code, type,
5291                                                     TREE_OPERAND (varop, 0),
5292                                                     constop));
5293                     if (integer_zerop (folded_compare)
5294                         || integer_onep (folded_compare))
5295                       return omit_one_operand (type, folded_compare, varop);
5296
5297                     unsigned_type = type_for_size (size, 1);
5298                     precision = TYPE_PRECISION (unsigned_type);
5299                     mask = build_int_2 (~0, ~0);
5300                     TREE_TYPE (mask) = TREE_TYPE (varop);
5301                     force_fit_type (mask, 0);
5302                     mask = const_binop (RSHIFT_EXPR, mask,
5303                                         size_int (precision - size), 0);
5304                     newconst = fold (build (BIT_AND_EXPR,
5305                                             TREE_TYPE (varop), newconst,
5306                                             convert (TREE_TYPE (varop),
5307                                                      mask)));
5308                   }
5309
5310
5311                 t = build (code, type, TREE_OPERAND (t, 0),
5312                            TREE_OPERAND (t, 1));
5313                 TREE_OPERAND (t, constopnum) = newconst;
5314                 return t;
5315               }
5316           }
5317       }
5318
5319       /* Change X >= CST to X > (CST - 1) if CST is positive.  */
5320       if (TREE_CODE (arg1) == INTEGER_CST
5321           && TREE_CODE (arg0) != INTEGER_CST
5322           && tree_int_cst_sgn (arg1) > 0)
5323         {
5324           switch (TREE_CODE (t))
5325             {
5326             case GE_EXPR:
5327               code = GT_EXPR;
5328               arg1 = const_binop (MINUS_EXPR, arg1, integer_one_node, 0);
5329               t = build (code, type, TREE_OPERAND (t, 0), arg1);
5330               break;
5331
5332             case LT_EXPR:
5333               code = LE_EXPR;
5334               arg1 = const_binop (MINUS_EXPR, arg1, integer_one_node, 0);
5335               t = build (code, type, TREE_OPERAND (t, 0), arg1);
5336               break;
5337
5338             default:
5339               break;
5340             }
5341         }
5342
5343       /* If this is an EQ or NE comparison with zero and ARG0 is
5344          (1 << foo) & bar, convert it to (bar >> foo) & 1.  Both require
5345          two operations, but the latter can be done in one less insn
5346          on machines that have only two-operand insns or on which a
5347          constant cannot be the first operand.  */
5348       if (integer_zerop (arg1) && (code == EQ_EXPR || code == NE_EXPR)
5349           && TREE_CODE (arg0) == BIT_AND_EXPR)
5350         {
5351           if (TREE_CODE (TREE_OPERAND (arg0, 0)) == LSHIFT_EXPR
5352               && integer_onep (TREE_OPERAND (TREE_OPERAND (arg0, 0), 0)))
5353             return
5354               fold (build (code, type,
5355                            build (BIT_AND_EXPR, TREE_TYPE (arg0),
5356                                   build (RSHIFT_EXPR,
5357                                          TREE_TYPE (TREE_OPERAND (arg0, 0)),
5358                                          TREE_OPERAND (arg0, 1),
5359                                          TREE_OPERAND (TREE_OPERAND (arg0, 0), 1)),
5360                                   convert (TREE_TYPE (arg0),
5361                                            integer_one_node)),
5362                            arg1));
5363           else if (TREE_CODE (TREE_OPERAND (arg0, 1)) == LSHIFT_EXPR
5364                    && integer_onep (TREE_OPERAND (TREE_OPERAND (arg0, 1), 0)))
5365             return
5366               fold (build (code, type,
5367                            build (BIT_AND_EXPR, TREE_TYPE (arg0),
5368                                   build (RSHIFT_EXPR,
5369                                          TREE_TYPE (TREE_OPERAND (arg0, 1)),
5370                                          TREE_OPERAND (arg0, 0),
5371                                          TREE_OPERAND (TREE_OPERAND (arg0, 1), 1)),
5372                                   convert (TREE_TYPE (arg0),
5373                                            integer_one_node)),
5374                            arg1));
5375         }
5376
5377       /* If this is an NE or EQ comparison of zero against the result of a
5378          signed MOD operation whose second operand is a power of 2, make
5379          the MOD operation unsigned since it is simpler and equivalent.  */
5380       if ((code == NE_EXPR || code == EQ_EXPR)
5381           && integer_zerop (arg1)
5382           && ! TREE_UNSIGNED (TREE_TYPE (arg0))
5383           && (TREE_CODE (arg0) == TRUNC_MOD_EXPR
5384               || TREE_CODE (arg0) == CEIL_MOD_EXPR
5385               || TREE_CODE (arg0) == FLOOR_MOD_EXPR
5386               || TREE_CODE (arg0) == ROUND_MOD_EXPR)
5387           && integer_pow2p (TREE_OPERAND (arg0, 1)))
5388         {
5389           tree newtype = unsigned_type (TREE_TYPE (arg0));
5390           tree newmod = build (TREE_CODE (arg0), newtype,
5391                                convert (newtype, TREE_OPERAND (arg0, 0)),
5392                                convert (newtype, TREE_OPERAND (arg0, 1)));
5393
5394           return build (code, type, newmod, convert (newtype, arg1));
5395         }
5396
5397       /* If this is an NE comparison of zero with an AND of one, remove the
5398          comparison since the AND will give the correct value.  */
5399       if (code == NE_EXPR && integer_zerop (arg1)
5400           && TREE_CODE (arg0) == BIT_AND_EXPR
5401           && integer_onep (TREE_OPERAND (arg0, 1)))
5402         return convert (type, arg0);
5403
5404       /* If we have (A & C) == C where C is a power of 2, convert this into
5405          (A & C) != 0.  Similarly for NE_EXPR.  */
5406       if ((code == EQ_EXPR || code == NE_EXPR)
5407           && TREE_CODE (arg0) == BIT_AND_EXPR
5408           && integer_pow2p (TREE_OPERAND (arg0, 1))
5409           && operand_equal_p (TREE_OPERAND (arg0, 1), arg1, 0))
5410         return build (code == EQ_EXPR ? NE_EXPR : EQ_EXPR, type,
5411                       arg0, integer_zero_node);
5412
5413       /* If X is unsigned, convert X < (1 << Y) into X >> Y == 0
5414          and similarly for >= into !=.  */
5415       if ((code == LT_EXPR || code == GE_EXPR)
5416           && TREE_UNSIGNED (TREE_TYPE (arg0))
5417           && TREE_CODE (arg1) == LSHIFT_EXPR
5418           && integer_onep (TREE_OPERAND (arg1, 0)))
5419         return build (code == LT_EXPR ? EQ_EXPR : NE_EXPR, type,
5420                       build (RSHIFT_EXPR, TREE_TYPE (arg0), arg0,
5421                              TREE_OPERAND (arg1, 1)),
5422                       convert (TREE_TYPE (arg0), integer_zero_node));
5423
5424       else if ((code == LT_EXPR || code == GE_EXPR)
5425                && TREE_UNSIGNED (TREE_TYPE (arg0))
5426                && (TREE_CODE (arg1) == NOP_EXPR
5427                    || TREE_CODE (arg1) == CONVERT_EXPR)
5428                && TREE_CODE (TREE_OPERAND (arg1, 0)) == LSHIFT_EXPR
5429                && integer_onep (TREE_OPERAND (TREE_OPERAND (arg1, 0), 0)))
5430         return
5431           build (code == LT_EXPR ? EQ_EXPR : NE_EXPR, type,
5432                  convert (TREE_TYPE (arg0),
5433                           build (RSHIFT_EXPR, TREE_TYPE (arg0), arg0,
5434                                  TREE_OPERAND (TREE_OPERAND (arg1, 0), 1))),
5435                  convert (TREE_TYPE (arg0), integer_zero_node));
5436
5437       /* Simplify comparison of something with itself.  (For IEEE
5438          floating-point, we can only do some of these simplifications.)  */
5439       if (operand_equal_p (arg0, arg1, 0))
5440         {
5441           switch (code)
5442             {
5443             case EQ_EXPR:
5444             case GE_EXPR:
5445             case LE_EXPR:
5446               if (INTEGRAL_TYPE_P (TREE_TYPE (arg0)))
5447                 return constant_boolean_node (1, type);
5448               code = EQ_EXPR;
5449               TREE_SET_CODE (t, code);
5450               break;
5451
5452             case NE_EXPR:
5453               /* For NE, we can only do this simplification if integer.  */
5454               if (! INTEGRAL_TYPE_P (TREE_TYPE (arg0)))
5455                 break;
5456               /* ... fall through ...  */
5457             case GT_EXPR:
5458             case LT_EXPR:
5459               return constant_boolean_node (0, type);
5460             default:
5461               abort ();
5462             }
5463         }
5464
5465       /* An unsigned comparison against 0 can be simplified.  */
5466       if (integer_zerop (arg1)
5467           && (INTEGRAL_TYPE_P (TREE_TYPE (arg1))
5468               || POINTER_TYPE_P (TREE_TYPE (arg1)))
5469           && TREE_UNSIGNED (TREE_TYPE (arg1)))
5470         {
5471           switch (TREE_CODE (t))
5472             {
5473             case GT_EXPR:
5474               code = NE_EXPR;
5475               TREE_SET_CODE (t, NE_EXPR);
5476               break;
5477             case LE_EXPR:
5478               code = EQ_EXPR;
5479               TREE_SET_CODE (t, EQ_EXPR);
5480               break;
5481             case GE_EXPR:
5482               return omit_one_operand (type,
5483                                        convert (type, integer_one_node),
5484                                        arg0);
5485             case LT_EXPR:
5486               return omit_one_operand (type,
5487                                        convert (type, integer_zero_node),
5488                                        arg0);
5489             default:
5490               break;
5491             }
5492         }
5493
5494       /* An unsigned <= 0x7fffffff can be simplified.  */
5495       {
5496         int width = TYPE_PRECISION (TREE_TYPE (arg1));
5497         if (TREE_CODE (arg1) == INTEGER_CST
5498             && ! TREE_CONSTANT_OVERFLOW (arg1)
5499             && width <= HOST_BITS_PER_WIDE_INT
5500             && TREE_INT_CST_LOW (arg1) == ((HOST_WIDE_INT) 1 << (width - 1)) - 1
5501             && TREE_INT_CST_HIGH (arg1) == 0
5502             && (INTEGRAL_TYPE_P (TREE_TYPE (arg1))
5503                 || POINTER_TYPE_P (TREE_TYPE (arg1)))
5504             && TREE_UNSIGNED (TREE_TYPE (arg1)))
5505           {
5506             switch (TREE_CODE (t))
5507               {
5508               case LE_EXPR:
5509                 return fold (build (GE_EXPR, type,
5510                                     convert (signed_type (TREE_TYPE (arg0)),
5511                                              arg0),
5512                                     convert (signed_type (TREE_TYPE (arg1)),
5513                                              integer_zero_node)));
5514               case GT_EXPR:
5515                 return fold (build (LT_EXPR, type,
5516                                     convert (signed_type (TREE_TYPE (arg0)),
5517                                              arg0),
5518                                     convert (signed_type (TREE_TYPE (arg1)),
5519                                              integer_zero_node)));
5520               default:
5521                 break;
5522               }
5523           }
5524       }
5525
5526       /* If we are comparing an expression that just has comparisons
5527          of two integer values, arithmetic expressions of those comparisons,
5528          and constants, we can simplify it.  There are only three cases
5529          to check: the two values can either be equal, the first can be
5530          greater, or the second can be greater.  Fold the expression for
5531          those three values.  Since each value must be 0 or 1, we have
5532          eight possibilities, each of which corresponds to the constant 0
5533          or 1 or one of the six possible comparisons.
5534
5535          This handles common cases like (a > b) == 0 but also handles
5536          expressions like  ((x > y) - (y > x)) > 0, which supposedly
5537          occur in macroized code.  */
5538
5539       if (TREE_CODE (arg1) == INTEGER_CST && TREE_CODE (arg0) != INTEGER_CST)
5540         {
5541           tree cval1 = 0, cval2 = 0;
5542           int save_p = 0;
5543
5544           if (twoval_comparison_p (arg0, &cval1, &cval2, &save_p)
5545               /* Don't handle degenerate cases here; they should already
5546                  have been handled anyway.  */
5547               && cval1 != 0 && cval2 != 0
5548               && ! (TREE_CONSTANT (cval1) && TREE_CONSTANT (cval2))
5549               && TREE_TYPE (cval1) == TREE_TYPE (cval2)
5550               && INTEGRAL_TYPE_P (TREE_TYPE (cval1))
5551               && TYPE_MAX_VALUE (TREE_TYPE (cval1))
5552               && TYPE_MAX_VALUE (TREE_TYPE (cval2))
5553               && ! operand_equal_p (TYPE_MIN_VALUE (TREE_TYPE (cval1)),
5554                                     TYPE_MAX_VALUE (TREE_TYPE (cval2)), 0))
5555             {
5556               tree maxval = TYPE_MAX_VALUE (TREE_TYPE (cval1));
5557               tree minval = TYPE_MIN_VALUE (TREE_TYPE (cval1));
5558
5559               /* We can't just pass T to eval_subst in case cval1 or cval2
5560                  was the same as ARG1.  */
5561
5562               tree high_result
5563                 = fold (build (code, type,
5564                                eval_subst (arg0, cval1, maxval, cval2, minval),
5565                                arg1));
5566               tree equal_result
5567                 = fold (build (code, type,
5568                                eval_subst (arg0, cval1, maxval, cval2, maxval),
5569                                arg1));
5570               tree low_result
5571                 = fold (build (code, type,
5572                                eval_subst (arg0, cval1, minval, cval2, maxval),
5573                                arg1));
5574
5575               /* All three of these results should be 0 or 1.  Confirm they
5576                  are.  Then use those values to select the proper code
5577                  to use.  */
5578
5579               if ((integer_zerop (high_result)
5580                    || integer_onep (high_result))
5581                   && (integer_zerop (equal_result)
5582                       || integer_onep (equal_result))
5583                   && (integer_zerop (low_result)
5584                       || integer_onep (low_result)))
5585                 {
5586                   /* Make a 3-bit mask with the high-order bit being the
5587                      value for `>', the next for '=', and the low for '<'.  */
5588                   switch ((integer_onep (high_result) * 4)
5589                           + (integer_onep (equal_result) * 2)
5590                           + integer_onep (low_result))
5591                     {
5592                     case 0:
5593                       /* Always false.  */
5594                       return omit_one_operand (type, integer_zero_node, arg0);
5595                     case 1:
5596                       code = LT_EXPR;
5597                       break;
5598                     case 2:
5599                       code = EQ_EXPR;
5600                       break;
5601                     case 3:
5602                       code = LE_EXPR;
5603                       break;
5604                     case 4:
5605                       code = GT_EXPR;
5606                       break;
5607                     case 5:
5608                       code = NE_EXPR;
5609                       break;
5610                     case 6:
5611                       code = GE_EXPR;
5612                       break;
5613                     case 7:
5614                       /* Always true.  */
5615                       return omit_one_operand (type, integer_one_node, arg0);
5616                     }
5617
5618                   t = build (code, type, cval1, cval2);
5619                   if (save_p)
5620                     return save_expr (t);
5621                   else
5622                     return fold (t);
5623                 }
5624             }
5625         }
5626
5627       /* If this is a comparison of a field, we may be able to simplify it.  */
5628       if ((TREE_CODE (arg0) == COMPONENT_REF
5629            || TREE_CODE (arg0) == BIT_FIELD_REF)
5630           && (code == EQ_EXPR || code == NE_EXPR)
5631           /* Handle the constant case even without -O
5632              to make sure the warnings are given.  */
5633           && (optimize || TREE_CODE (arg1) == INTEGER_CST))
5634         {
5635           t1 = optimize_bit_field_compare (code, type, arg0, arg1);
5636           return t1 ? t1 : t;
5637         }
5638
5639       /* If this is a comparison of complex values and either or both
5640          sizes are a COMPLEX_EXPR, it is best to split up the comparisons
5641          and join them with a TRUTH_ANDIF_EXPR or TRUTH_ORIF_EXPR.  This
5642          may prevent needless evaluations.  */
5643       if ((code == EQ_EXPR || code == NE_EXPR)
5644           && TREE_CODE (TREE_TYPE (arg0)) == COMPLEX_TYPE
5645           && (TREE_CODE (arg0) == COMPLEX_EXPR
5646               || TREE_CODE (arg1) == COMPLEX_EXPR))
5647         {
5648           tree subtype = TREE_TYPE (TREE_TYPE (arg0));
5649           tree real0 = fold (build1 (REALPART_EXPR, subtype, arg0));
5650           tree imag0 = fold (build1 (IMAGPART_EXPR, subtype, arg0));
5651           tree real1 = fold (build1 (REALPART_EXPR, subtype, arg1));
5652           tree imag1 = fold (build1 (IMAGPART_EXPR, subtype, arg1));
5653
5654           return fold (build ((code == EQ_EXPR ? TRUTH_ANDIF_EXPR
5655                                : TRUTH_ORIF_EXPR),
5656                               type,
5657                               fold (build (code, type, real0, real1)),
5658                               fold (build (code, type, imag0, imag1))));
5659         }
5660
5661       /* From here on, the only cases we handle are when the result is
5662          known to be a constant.
5663
5664          To compute GT, swap the arguments and do LT.
5665          To compute GE, do LT and invert the result.
5666          To compute LE, swap the arguments, do LT and invert the result.
5667          To compute NE, do EQ and invert the result.
5668
5669          Therefore, the code below must handle only EQ and LT.  */
5670
5671       if (code == LE_EXPR || code == GT_EXPR)
5672         {
5673           tem = arg0, arg0 = arg1, arg1 = tem;
5674           code = swap_tree_comparison (code);
5675         }
5676
5677       /* Note that it is safe to invert for real values here because we
5678          will check below in the one case that it matters.  */
5679
5680       invert = 0;
5681       if (code == NE_EXPR || code == GE_EXPR)
5682         {
5683           invert = 1;
5684           code = invert_tree_comparison (code);
5685         }
5686
5687       /* Compute a result for LT or EQ if args permit;
5688          otherwise return T.  */
5689       if (TREE_CODE (arg0) == INTEGER_CST && TREE_CODE (arg1) == INTEGER_CST)
5690         {
5691           if (code == EQ_EXPR)
5692             t1 = build_int_2 ((TREE_INT_CST_LOW (arg0)
5693                                == TREE_INT_CST_LOW (arg1))
5694                               && (TREE_INT_CST_HIGH (arg0)
5695                                   == TREE_INT_CST_HIGH (arg1)),
5696                               0);
5697           else
5698             t1 = build_int_2 ((TREE_UNSIGNED (TREE_TYPE (arg0))
5699                                ? INT_CST_LT_UNSIGNED (arg0, arg1)
5700                                : INT_CST_LT (arg0, arg1)),
5701                               0);
5702         }
5703
5704 #if 0 /* This is no longer useful, but breaks some real code.  */
5705       /* Assume a nonexplicit constant cannot equal an explicit one,
5706          since such code would be undefined anyway.
5707          Exception: on sysvr4, using #pragma weak,
5708          a label can come out as 0.  */
5709       else if (TREE_CODE (arg1) == INTEGER_CST
5710                && !integer_zerop (arg1)
5711                && TREE_CONSTANT (arg0)
5712                && TREE_CODE (arg0) == ADDR_EXPR
5713                && code == EQ_EXPR)
5714         t1 = build_int_2 (0, 0);
5715 #endif
5716       /* Two real constants can be compared explicitly.  */
5717       else if (TREE_CODE (arg0) == REAL_CST && TREE_CODE (arg1) == REAL_CST)
5718         {
5719           /* If either operand is a NaN, the result is false with two
5720              exceptions: First, an NE_EXPR is true on NaNs, but that case
5721              is already handled correctly since we will be inverting the
5722              result for NE_EXPR.  Second, if we had inverted a LE_EXPR
5723              or a GE_EXPR into a LT_EXPR, we must return true so that it
5724              will be inverted into false.  */
5725
5726           if (REAL_VALUE_ISNAN (TREE_REAL_CST (arg0))
5727               || REAL_VALUE_ISNAN (TREE_REAL_CST (arg1)))
5728             t1 = build_int_2 (invert && code == LT_EXPR, 0);
5729
5730           else if (code == EQ_EXPR)
5731             t1 = build_int_2 (REAL_VALUES_EQUAL (TREE_REAL_CST (arg0),
5732                                                  TREE_REAL_CST (arg1)),
5733                               0);
5734           else
5735             t1 = build_int_2 (REAL_VALUES_LESS (TREE_REAL_CST (arg0),
5736                                                 TREE_REAL_CST (arg1)),
5737                               0);
5738         }
5739
5740       if (t1 == NULL_TREE)
5741         return t;
5742
5743       if (invert)
5744         TREE_INT_CST_LOW (t1) ^= 1;
5745
5746       TREE_TYPE (t1) = type;
5747       if (TREE_CODE (type) == BOOLEAN_TYPE)
5748         return truthvalue_conversion (t1);
5749       return t1;
5750
5751     case COND_EXPR:
5752       /* Pedantic ANSI C says that a conditional expression is never an lvalue,
5753          so all simple results must be passed through pedantic_non_lvalue.  */
5754       if (TREE_CODE (arg0) == INTEGER_CST)
5755         return pedantic_non_lvalue
5756           (TREE_OPERAND (t, (integer_zerop (arg0) ? 2 : 1)));
5757       else if (operand_equal_p (arg1, TREE_OPERAND (expr, 2), 0))
5758         return pedantic_omit_one_operand (type, arg1, arg0);
5759
5760       /* If the second operand is zero, invert the comparison and swap
5761          the second and third operands.  Likewise if the second operand
5762          is constant and the third is not or if the third operand is
5763          equivalent to the first operand of the comparison.  */
5764
5765       if (integer_zerop (arg1)
5766           || (TREE_CONSTANT (arg1) && ! TREE_CONSTANT (TREE_OPERAND (t, 2)))
5767           || (TREE_CODE_CLASS (TREE_CODE (arg0)) == '<'
5768               && operand_equal_for_comparison_p (TREE_OPERAND (arg0, 0),
5769                                                  TREE_OPERAND (t, 2),
5770                                                  TREE_OPERAND (arg0, 1))))
5771         {
5772           /* See if this can be inverted.  If it can't, possibly because
5773              it was a floating-point inequality comparison, don't do
5774              anything.  */
5775           tem = invert_truthvalue (arg0);
5776
5777           if (TREE_CODE (tem) != TRUTH_NOT_EXPR)
5778             {
5779               t = build (code, type, tem,
5780                          TREE_OPERAND (t, 2), TREE_OPERAND (t, 1));
5781               arg0 = tem;
5782               arg1 = TREE_OPERAND (t, 2);
5783               STRIP_NOPS (arg1);
5784             }
5785         }
5786
5787       /* If we have A op B ? A : C, we may be able to convert this to a
5788          simpler expression, depending on the operation and the values
5789          of B and C.  IEEE floating point prevents this though,
5790          because A or B might be -0.0 or a NaN.  */
5791
5792       if (TREE_CODE_CLASS (TREE_CODE (arg0)) == '<'
5793           && (TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
5794               || ! FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (arg0, 0)))
5795               || flag_fast_math)
5796           && operand_equal_for_comparison_p (TREE_OPERAND (arg0, 0),
5797                                              arg1, TREE_OPERAND (arg0, 1)))
5798         {
5799           tree arg2 = TREE_OPERAND (t, 2);
5800           enum tree_code comp_code = TREE_CODE (arg0);
5801
5802           STRIP_NOPS (arg2);
5803
5804           /* If we have A op 0 ? A : -A, this is A, -A, abs (A), or abs (-A),
5805              depending on the comparison operation.  */
5806           if ((FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (arg0, 1)))
5807                ? real_zerop (TREE_OPERAND (arg0, 1))
5808                : integer_zerop (TREE_OPERAND (arg0, 1)))
5809               && TREE_CODE (arg2) == NEGATE_EXPR
5810               && operand_equal_p (TREE_OPERAND (arg2, 0), arg1, 0))
5811             switch (comp_code)
5812               {
5813               case EQ_EXPR:
5814                 return pedantic_non_lvalue
5815                   (fold (build1 (NEGATE_EXPR, type, arg1)));
5816               case NE_EXPR:
5817                 return pedantic_non_lvalue (convert (type, arg1));
5818               case GE_EXPR:
5819               case GT_EXPR:
5820                 return pedantic_non_lvalue
5821                   (convert (type, fold (build1 (ABS_EXPR,
5822                                                 TREE_TYPE (arg1), arg1))));
5823               case LE_EXPR:
5824               case LT_EXPR:
5825                 return pedantic_non_lvalue
5826                   (fold (build1 (NEGATE_EXPR, type,
5827                                  convert (type,
5828                                           fold (build1 (ABS_EXPR,
5829                                                         TREE_TYPE (arg1),
5830                                                         arg1))))));
5831               default:
5832                 abort ();
5833               }
5834
5835           /* If this is A != 0 ? A : 0, this is simply A.  For ==, it is
5836              always zero.  */
5837
5838           if (integer_zerop (TREE_OPERAND (arg0, 1)) && integer_zerop (arg2))
5839             {
5840               if (comp_code == NE_EXPR)
5841                 return pedantic_non_lvalue (convert (type, arg1));
5842               else if (comp_code == EQ_EXPR)
5843                 return pedantic_non_lvalue (convert (type, integer_zero_node));
5844             }
5845
5846           /* If this is A op B ? A : B, this is either A, B, min (A, B),
5847              or max (A, B), depending on the operation.  */
5848
5849           if (operand_equal_for_comparison_p (TREE_OPERAND (arg0, 1),
5850                                               arg2, TREE_OPERAND (arg0, 0)))
5851             {
5852               tree comp_op0 = TREE_OPERAND (arg0, 0);
5853               tree comp_op1 = TREE_OPERAND (arg0, 1);
5854               tree comp_type = TREE_TYPE (comp_op0);
5855
5856               switch (comp_code)
5857                 {
5858                 case EQ_EXPR:
5859                   return pedantic_non_lvalue (convert (type, arg2));
5860                 case NE_EXPR:
5861                   return pedantic_non_lvalue (convert (type, arg1));
5862                 case LE_EXPR:
5863                 case LT_EXPR:
5864                   /* In C++ a ?: expression can be an lvalue, so put the
5865                      operand which will be used if they are equal first
5866                      so that we can convert this back to the
5867                      corresponding COND_EXPR.  */
5868                   return pedantic_non_lvalue
5869                     (convert (type, (fold (build (MIN_EXPR, comp_type,
5870                                                   (comp_code == LE_EXPR
5871                                                    ? comp_op0 : comp_op1),
5872                                                   (comp_code == LE_EXPR
5873                                                    ? comp_op1 : comp_op0))))));
5874                   break;
5875                 case GE_EXPR:
5876                 case GT_EXPR:
5877                   return pedantic_non_lvalue
5878                     (convert (type, fold (build (MAX_EXPR, comp_type,
5879                                                  (comp_code == GE_EXPR
5880                                                   ? comp_op0 : comp_op1),
5881                                                  (comp_code == GE_EXPR
5882                                                   ? comp_op1 : comp_op0)))));
5883                   break;
5884                 default:
5885                   abort ();
5886                 }
5887             }
5888
5889           /* If this is A op C1 ? A : C2 with C1 and C2 constant integers,
5890              we might still be able to simplify this.  For example,
5891              if C1 is one less or one more than C2, this might have started
5892              out as a MIN or MAX and been transformed by this function.
5893              Only good for INTEGER_TYPEs, because we need TYPE_MAX_VALUE.  */
5894
5895           if (INTEGRAL_TYPE_P (type)
5896               && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
5897               && TREE_CODE (arg2) == INTEGER_CST)
5898             switch (comp_code)
5899               {
5900               case EQ_EXPR:
5901                 /* We can replace A with C1 in this case.  */
5902                 arg1 = convert (type, TREE_OPERAND (arg0, 1));
5903                 t = build (code, type, TREE_OPERAND (t, 0), arg1,
5904                            TREE_OPERAND (t, 2));
5905                 break;
5906
5907               case LT_EXPR:
5908                 /* If C1 is C2 + 1, this is min(A, C2).  */
5909                 if (! operand_equal_p (arg2, TYPE_MAX_VALUE (type), 1)
5910                     && operand_equal_p (TREE_OPERAND (arg0, 1),
5911                                         const_binop (PLUS_EXPR, arg2,
5912                                                      integer_one_node, 0), 1))
5913                   return pedantic_non_lvalue
5914                     (fold (build (MIN_EXPR, type, arg1, arg2)));
5915                 break;
5916
5917               case LE_EXPR:
5918                 /* If C1 is C2 - 1, this is min(A, C2).  */
5919                 if (! operand_equal_p (arg2, TYPE_MIN_VALUE (type), 1)
5920                     && operand_equal_p (TREE_OPERAND (arg0, 1),
5921                                         const_binop (MINUS_EXPR, arg2,
5922                                                      integer_one_node, 0), 1))
5923                   return pedantic_non_lvalue
5924                     (fold (build (MIN_EXPR, type, arg1, arg2)));
5925                 break;
5926
5927               case GT_EXPR:
5928                 /* If C1 is C2 - 1, this is max(A, C2).  */
5929                 if (! operand_equal_p (arg2, TYPE_MIN_VALUE (type), 1)
5930                     && operand_equal_p (TREE_OPERAND (arg0, 1),
5931                                         const_binop (MINUS_EXPR, arg2,
5932                                                      integer_one_node, 0), 1))
5933                   return pedantic_non_lvalue
5934                     (fold (build (MAX_EXPR, type, arg1, arg2)));
5935                 break;
5936
5937               case GE_EXPR:
5938                 /* If C1 is C2 + 1, this is max(A, C2).  */
5939                 if (! operand_equal_p (arg2, TYPE_MAX_VALUE (type), 1)
5940                     && operand_equal_p (TREE_OPERAND (arg0, 1),
5941                                         const_binop (PLUS_EXPR, arg2,
5942                                                      integer_one_node, 0), 1))
5943                   return pedantic_non_lvalue
5944                     (fold (build (MAX_EXPR, type, arg1, arg2)));
5945                 break;
5946               case NE_EXPR:
5947                 break;
5948               default:
5949                 abort ();
5950               }
5951         }
5952
5953       /* If the second operand is simpler than the third, swap them
5954          since that produces better jump optimization results.  */
5955       if ((TREE_CONSTANT (arg1) || TREE_CODE_CLASS (TREE_CODE (arg1)) == 'd'
5956            || TREE_CODE (arg1) == SAVE_EXPR)
5957           && ! (TREE_CONSTANT (TREE_OPERAND (t, 2))
5958                 || TREE_CODE_CLASS (TREE_CODE (TREE_OPERAND (t, 2))) == 'd'
5959                 || TREE_CODE (TREE_OPERAND (t, 2)) == SAVE_EXPR))
5960         {
5961           /* See if this can be inverted.  If it can't, possibly because
5962              it was a floating-point inequality comparison, don't do
5963              anything.  */
5964           tem = invert_truthvalue (arg0);
5965
5966           if (TREE_CODE (tem) != TRUTH_NOT_EXPR)
5967             {
5968               t = build (code, type, tem,
5969                          TREE_OPERAND (t, 2), TREE_OPERAND (t, 1));
5970               arg0 = tem;
5971               arg1 = TREE_OPERAND (t, 2);
5972               STRIP_NOPS (arg1);
5973             }
5974         }
5975
5976       /* Convert A ? 1 : 0 to simply A.  */
5977       if (integer_onep (TREE_OPERAND (t, 1))
5978           && integer_zerop (TREE_OPERAND (t, 2))
5979           /* If we try to convert TREE_OPERAND (t, 0) to our type, the
5980              call to fold will try to move the conversion inside
5981              a COND, which will recurse.  In that case, the COND_EXPR
5982              is probably the best choice, so leave it alone.  */
5983           && type == TREE_TYPE (arg0))
5984         return pedantic_non_lvalue (arg0);
5985
5986       /* Look for expressions of the form A & 2 ? 2 : 0.  The result of this
5987          operation is simply A & 2.  */
5988
5989       if (integer_zerop (TREE_OPERAND (t, 2))
5990           && TREE_CODE (arg0) == NE_EXPR
5991           && integer_zerop (TREE_OPERAND (arg0, 1))
5992           && integer_pow2p (arg1)
5993           && TREE_CODE (TREE_OPERAND (arg0, 0)) == BIT_AND_EXPR
5994           && operand_equal_p (TREE_OPERAND (TREE_OPERAND (arg0, 0), 1),
5995                               arg1, 1))
5996         return pedantic_non_lvalue (convert (type, TREE_OPERAND (arg0, 0)));
5997
5998       return t;
5999
6000     case COMPOUND_EXPR:
6001       /* When pedantic, a compound expression can be neither an lvalue
6002          nor an integer constant expression.  */
6003       if (TREE_SIDE_EFFECTS (arg0) || pedantic)
6004         return t;
6005       /* Don't let (0, 0) be null pointer constant.  */
6006       if (integer_zerop (arg1))
6007         return non_lvalue (arg1);
6008       return arg1;
6009
6010     case COMPLEX_EXPR:
6011       if (wins)
6012         return build_complex (type, arg0, arg1);
6013       return t;
6014
6015     case REALPART_EXPR:
6016       if (TREE_CODE (TREE_TYPE (arg0)) != COMPLEX_TYPE)
6017         return t;
6018       else if (TREE_CODE (arg0) == COMPLEX_EXPR)
6019         return omit_one_operand (type, TREE_OPERAND (arg0, 0),
6020                                  TREE_OPERAND (arg0, 1));
6021       else if (TREE_CODE (arg0) == COMPLEX_CST)
6022         return TREE_REALPART (arg0);
6023       else if (TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MINUS_EXPR)
6024         return fold (build (TREE_CODE (arg0), type,
6025                             fold (build1 (REALPART_EXPR, type,
6026                                           TREE_OPERAND (arg0, 0))),
6027                             fold (build1 (REALPART_EXPR,
6028                                           type, TREE_OPERAND (arg0, 1)))));
6029       return t;
6030
6031     case IMAGPART_EXPR:
6032       if (TREE_CODE (TREE_TYPE (arg0)) != COMPLEX_TYPE)
6033         return convert (type, integer_zero_node);
6034       else if (TREE_CODE (arg0) == COMPLEX_EXPR)
6035         return omit_one_operand (type, TREE_OPERAND (arg0, 1),
6036                                  TREE_OPERAND (arg0, 0));
6037       else if (TREE_CODE (arg0) == COMPLEX_CST)
6038         return TREE_IMAGPART (arg0);
6039       else if (TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MINUS_EXPR)
6040         return fold (build (TREE_CODE (arg0), type,
6041                             fold (build1 (IMAGPART_EXPR, type,
6042                                           TREE_OPERAND (arg0, 0))),
6043                             fold (build1 (IMAGPART_EXPR, type,
6044                                           TREE_OPERAND (arg0, 1)))));
6045       return t;
6046
6047       /* Pull arithmetic ops out of the CLEANUP_POINT_EXPR where
6048          appropriate.  */
6049     case CLEANUP_POINT_EXPR:
6050       if (! has_cleanups (arg0))
6051         return TREE_OPERAND (t, 0);
6052
6053       {
6054         enum tree_code code0 = TREE_CODE (arg0);
6055         int kind0 = TREE_CODE_CLASS (code0);
6056         tree arg00 = TREE_OPERAND (arg0, 0);
6057         tree arg01;
6058
6059         if (kind0 == '1' || code0 == TRUTH_NOT_EXPR)
6060           return fold (build1 (code0, type,
6061                                fold (build1 (CLEANUP_POINT_EXPR,
6062                                              TREE_TYPE (arg00), arg00))));
6063
6064         if (kind0 == '<' || kind0 == '2'
6065             || code0 == TRUTH_ANDIF_EXPR || code0 == TRUTH_ORIF_EXPR
6066             || code0 == TRUTH_AND_EXPR   || code0 == TRUTH_OR_EXPR
6067             || code0 == TRUTH_XOR_EXPR)
6068           {
6069             arg01 = TREE_OPERAND (arg0, 1);
6070
6071             if (TREE_CONSTANT (arg00)
6072                 || ((code0 == TRUTH_ANDIF_EXPR || code0 == TRUTH_ORIF_EXPR)
6073                     && ! has_cleanups (arg00)))
6074               return fold (build (code0, type, arg00,
6075                                   fold (build1 (CLEANUP_POINT_EXPR,
6076                                                 TREE_TYPE (arg01), arg01))));
6077
6078             if (TREE_CONSTANT (arg01))
6079               return fold (build (code0, type,
6080                                   fold (build1 (CLEANUP_POINT_EXPR,
6081                                                 TREE_TYPE (arg00), arg00)),
6082                                   arg01));
6083           }
6084
6085         return t;
6086       }
6087
6088     default:
6089       return t;
6090     } /* switch (code) */
6091 }
6092
6093 /* Determine if first argument is a multiple of second argument.
6094    Return 0 if it is not, or is not easily determined to so be.
6095
6096    An example of the sort of thing we care about (at this point --
6097    this routine could surely be made more general, and expanded
6098    to do what the *_DIV_EXPR's fold() cases do now) is discovering
6099    that
6100
6101      SAVE_EXPR (I) * SAVE_EXPR (J * 8)
6102
6103    is a multiple of
6104
6105      SAVE_EXPR (J * 8)
6106
6107    when we know that the two `SAVE_EXPR (J * 8)' nodes are the
6108    same node (which means they will have the same value at run
6109    time, even though we don't know when they'll be assigned).
6110
6111    This code also handles discovering that
6112
6113      SAVE_EXPR (I) * SAVE_EXPR (J * 8)
6114
6115    is a multiple of
6116
6117      8
6118
6119    (of course) so we don't have to worry about dealing with a
6120    possible remainder.
6121
6122    Note that we _look_ inside a SAVE_EXPR only to determine
6123    how it was calculated; it is not safe for fold() to do much
6124    of anything else with the internals of a SAVE_EXPR, since
6125    fold() cannot know when it will be evaluated at run time.
6126    For example, the latter example above _cannot_ be implemented
6127    as
6128
6129      SAVE_EXPR (I) * J
6130
6131    or any variant thereof, since the value of J at evaluation time
6132    of the original SAVE_EXPR is not necessarily the same at the time
6133    the new expression is evaluated.  The only optimization of this
6134    sort that would be valid is changing
6135
6136      SAVE_EXPR (I) * SAVE_EXPR (SAVE_EXPR (J) * 8)
6137    divided by
6138      8
6139
6140    to
6141
6142      SAVE_EXPR (I) * SAVE_EXPR (J)
6143
6144    (where the same SAVE_EXPR (J) is used in the original and the
6145    transformed version).  */
6146
6147 static int
6148 multiple_of_p (type, top, bottom)
6149      tree type;
6150      tree top;
6151      tree bottom;
6152 {
6153   if (operand_equal_p (top, bottom, 0))
6154     return 1;
6155
6156   if (TREE_CODE (type) != INTEGER_TYPE)
6157     return 0;
6158
6159   switch (TREE_CODE (top))
6160     {
6161     case MULT_EXPR:
6162       return (multiple_of_p (type, TREE_OPERAND (top, 0), bottom)
6163               || multiple_of_p (type, TREE_OPERAND (top, 1), bottom));
6164
6165     case PLUS_EXPR:
6166     case MINUS_EXPR:
6167       return (multiple_of_p (type, TREE_OPERAND (top, 0), bottom)
6168               && multiple_of_p (type, TREE_OPERAND (top, 1), bottom));
6169
6170     case NOP_EXPR:
6171       /* Punt if conversion from non-integral or wider integral type.  */
6172       if ((TREE_CODE (TREE_TYPE (TREE_OPERAND (top, 0))) != INTEGER_TYPE)
6173           || (TYPE_PRECISION (type)
6174               < TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (top, 0)))))
6175         return 0;
6176       /* Fall through. */
6177     case SAVE_EXPR:
6178       return multiple_of_p (type, TREE_OPERAND (top, 0), bottom);
6179
6180     case INTEGER_CST:
6181       if ((TREE_CODE (bottom) != INTEGER_CST)
6182           || (tree_int_cst_sgn (top) < 0)
6183           || (tree_int_cst_sgn (bottom) < 0))
6184         return 0;
6185       return integer_zerop (const_binop (TRUNC_MOD_EXPR,
6186                                          top, bottom, 0));
6187
6188     default:
6189       return 0;
6190     }
6191 }
6192 \f