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