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