gcc/fold-const.c

   1 /* Fold a constant sub-tree into a single node for C-compiler
   2    Copyright (C) 1987, 88, 92-97, 1998 Free Software Foundation, Inc.
   3
   4 This file is part of GNU CC.
   5
   6 GNU CC is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 2, or (at your option)
   9 any later version.
  10
  11 GNU CC is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 GNU General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GNU CC; see the file COPYING.  If not, write to
  18 the Free Software Foundation, 59 Temple Place - Suite 330,
  19 Boston, MA 02111-1307, USA.  */
  20
  21 /*@@ This file should be rewritten to use an arbitrary precision
  22   @@ representation for "struct tree_int_cst" and "struct tree_real_cst".
  23   @@ Perhaps the routines could also be used for bc/dc, and made a lib.
  24   @@ The routines that translate from the ap rep should
  25   @@ warn if precision et. al. is lost.
  26   @@ This would also make life easier when this technology is used
  27   @@ for cross-compilers.  */
  28
  29
  30 /* The entry points in this file are fold, size_int_wide, size_binop
  31    and force_fit_type.
  32
  33    fold takes a tree as argument and returns a simplified tree.
  34
  35    size_binop takes a tree code for an arithmetic operation
  36    and two operands that are trees, and produces a tree for the
  37    result, assuming the type comes from `sizetype'.
  38
  39    size_int takes an integer value, and creates a tree constant
  40    with type from `sizetype'.
  41
  42    force_fit_type takes a constant and prior overflow indicator, and
  43    forces the value to fit the type.  It returns an overflow indicator.  */
  44
  45 #include "config.h"
  46 #include "system.h"
  47 #include <setjmp.h>
  48 #include "flags.h"
  49 #include "tree.h"
  50
  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      int bit_p;
1433 {
1434   register tree t;
1435   /* Type-size nodes already made for small sizes.  */
1436   static tree size_table[2*HOST_BITS_PER_WIDE_INT + 1][2];
1437
1438   if (number < 2*HOST_BITS_PER_WIDE_INT + 1 && ! high
1439       && size_table[number][bit_p] != 0)
1440     return size_table[number][bit_p];
1441   if (number < 2*HOST_BITS_PER_WIDE_INT + 1 && ! high)
1442     {
1443       push_obstacks_nochange ();
1444       /* Make this a permanent node.  */
1445       end_temporary_allocation ();
1446       t = build_int_2 (number, 0);
1447       TREE_TYPE (t) = sizetype_tab[bit_p];
1448       size_table[number][bit_p] = t;
1449       pop_obstacks ();
1450     }
1451   else
1452     {
1453       t = build_int_2 (number, high);
1454       TREE_TYPE (t) = sizetype_tab[bit_p];
1455       TREE_OVERFLOW (t) = TREE_CONSTANT_OVERFLOW (t) = force_fit_type (t, 0);
1456     }
1457   return t;
1458 }
1459
1460 /* Combine operands OP1 and OP2 with arithmetic operation CODE.
1461    CODE is a tree code.  Data type is taken from `sizetype',
1462    If the operands are constant, so is the result.  */
1463
1464 tree
1465 size_binop (code, arg0, arg1)
1466      enum tree_code code;
1467      tree arg0, arg1;
1468 {
1469   /* Handle the special case of two integer constants faster.  */
1470   if (TREE_CODE (arg0) == INTEGER_CST && TREE_CODE (arg1) == INTEGER_CST)
1471     {
1472       /* And some specific cases even faster than that.  */
1473       if (code == PLUS_EXPR && integer_zerop (arg0))
1474         return arg1;
1475       else if ((code == MINUS_EXPR || code == PLUS_EXPR)
1476                && integer_zerop (arg1))
1477         return arg0;
1478       else if (code == MULT_EXPR && integer_onep (arg0))
1479         return arg1;
1480
1481       /* Handle general case of two integer constants.  */
1482       return int_const_binop (code, arg0, arg1, 0, 1);
1483     }
1484
1485   if (arg0 == error_mark_node || arg1 == error_mark_node)
1486     return error_mark_node;
1487
1488   return fold (build (code, sizetype, arg0, arg1));
1489 }
1490 \f
1491 /* Given T, a tree representing type conversion of ARG1, a constant,
1492    return a constant tree representing the result of conversion.  */
1493
1494 static tree
1495 fold_convert (t, arg1)
1496      register tree t;
1497      register tree arg1;
1498 {
1499   register tree type = TREE_TYPE (t);
1500   int overflow = 0;
1501
1502   if (TREE_CODE (type) == POINTER_TYPE || INTEGRAL_TYPE_P (type))
1503     {
1504       if (TREE_CODE (arg1) == INTEGER_CST)
1505         {
1506           /* If we would build a constant wider than GCC supports,
1507              leave the conversion unfolded.  */
1508           if (TYPE_PRECISION (type) > 2 * HOST_BITS_PER_WIDE_INT)
1509             return t;
1510
1511           /* Given an integer constant, make new constant with new type,
1512              appropriately sign-extended or truncated.  */
1513           t = build_int_2 (TREE_INT_CST_LOW (arg1),
1514                            TREE_INT_CST_HIGH (arg1));
1515           TREE_TYPE (t) = type;
1516           /* Indicate an overflow if (1) ARG1 already overflowed,
1517              or (2) force_fit_type indicates an overflow.
1518              Tell force_fit_type that an overflow has already occurred
1519              if ARG1 is a too-large unsigned value and T is signed.
1520              But don't indicate an overflow if converting a pointer.  */
1521           TREE_OVERFLOW (t)
1522             = (TREE_OVERFLOW (arg1)
1523                || (force_fit_type (t,
1524                                   (TREE_INT_CST_HIGH (arg1) < 0
1525                                    && (TREE_UNSIGNED (type)
1526                                      < TREE_UNSIGNED (TREE_TYPE (arg1)))))
1527                    && TREE_CODE (TREE_TYPE (arg1)) != POINTER_TYPE));
1528           TREE_CONSTANT_OVERFLOW (t)
1529             = TREE_OVERFLOW (t) | TREE_CONSTANT_OVERFLOW (arg1);
1530         }
1531 #if !defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
1532       else if (TREE_CODE (arg1) == REAL_CST)
1533         {
1534           /* Don't initialize these, use assignments.
1535              Initialized local aggregates don't work on old compilers.  */
1536           REAL_VALUE_TYPE x;
1537           REAL_VALUE_TYPE l;
1538           REAL_VALUE_TYPE u;
1539           tree type1 = TREE_TYPE (arg1);
1540           int no_upper_bound;
1541
1542           x = TREE_REAL_CST (arg1);
1543           l = real_value_from_int_cst (type1, TYPE_MIN_VALUE (type));
1544
1545           no_upper_bound = (TYPE_MAX_VALUE (type) == NULL);
1546           if (!no_upper_bound)
1547             u = real_value_from_int_cst (type1, TYPE_MAX_VALUE (type));
1548
1549           /* See if X will be in range after truncation towards 0.
1550              To compensate for truncation, move the bounds away from 0,
1551              but reject if X exactly equals the adjusted bounds.  */
1552 #ifdef REAL_ARITHMETIC
1553           REAL_ARITHMETIC (l, MINUS_EXPR, l, dconst1);
1554           if (!no_upper_bound)
1555             REAL_ARITHMETIC (u, PLUS_EXPR, u, dconst1);
1556 #else
1557           l--;
1558           if (!no_upper_bound)
1559             u++;
1560 #endif
1561           /* If X is a NaN, use zero instead and show we have an overflow.
1562              Otherwise, range check.  */
1563           if (REAL_VALUE_ISNAN (x))
1564             overflow = 1, x = dconst0;
1565           else if (! (REAL_VALUES_LESS (l, x)
1566                       && !no_upper_bound
1567                       && REAL_VALUES_LESS (x, u)))
1568             overflow = 1;
1569
1570 #ifndef REAL_ARITHMETIC
1571           {
1572             HOST_WIDE_INT low, high;
1573             HOST_WIDE_INT half_word
1574               = (HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT / 2);
1575
1576             if (x < 0)
1577               x = -x;
1578
1579             high = (HOST_WIDE_INT) (x / half_word / half_word);
1580             x -= (REAL_VALUE_TYPE) high * half_word * half_word;
1581             if (x >= (REAL_VALUE_TYPE) half_word * half_word / 2)
1582               {
1583                 low = x - (REAL_VALUE_TYPE) half_word * half_word / 2;
1584                 low |= (HOST_WIDE_INT) -1 << (HOST_BITS_PER_WIDE_INT - 1);
1585               }
1586             else
1587               low = (HOST_WIDE_INT) x;
1588             if (TREE_REAL_CST (arg1) < 0)
1589               neg_double (low, high, &low, &high);
1590             t = build_int_2 (low, high);
1591           }
1592 #else
1593           {
1594             HOST_WIDE_INT low, high;
1595             REAL_VALUE_TO_INT (&low, &high, x);
1596             t = build_int_2 (low, high);
1597           }
1598 #endif
1599           TREE_TYPE (t) = type;
1600           TREE_OVERFLOW (t)
1601             = TREE_OVERFLOW (arg1) | force_fit_type (t, overflow);
1602           TREE_CONSTANT_OVERFLOW (t)
1603             = TREE_OVERFLOW (t) | TREE_CONSTANT_OVERFLOW (arg1);
1604         }
1605 #endif /* not REAL_IS_NOT_DOUBLE, or REAL_ARITHMETIC */
1606       TREE_TYPE (t) = type;
1607     }
1608   else if (TREE_CODE (type) == REAL_TYPE)
1609     {
1610 #if !defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
1611       if (TREE_CODE (arg1) == INTEGER_CST)
1612         return build_real_from_int_cst (type, arg1);
1613 #endif /* not REAL_IS_NOT_DOUBLE, or REAL_ARITHMETIC */
1614       if (TREE_CODE (arg1) == REAL_CST)
1615         {
1616           if (REAL_VALUE_ISNAN (TREE_REAL_CST (arg1)))
1617             {
1618               t = arg1;
1619               TREE_TYPE (arg1) = type;
1620               return t;
1621             }
1622           else if (setjmp (float_error))
1623             {
1624               overflow = 1;
1625               t = copy_node (arg1);
1626               goto got_it;
1627             }
1628           set_float_handler (float_error);
1629
1630           t = build_real (type, real_value_truncate (TYPE_MODE (type),
1631                                                      TREE_REAL_CST (arg1)));
1632           set_float_handler (NULL_PTR);
1633
1634         got_it:
1635           TREE_OVERFLOW (t)
1636             = TREE_OVERFLOW (arg1) | force_fit_type (t, overflow);
1637           TREE_CONSTANT_OVERFLOW (t)
1638             = TREE_OVERFLOW (t) | TREE_CONSTANT_OVERFLOW (arg1);
1639           return t;
1640         }
1641     }
1642   TREE_CONSTANT (t) = 1;
1643   return t;
1644 }
1645 \f
1646 /* Return an expr equal to X but certainly not valid as an lvalue.
1647    Also make sure it is not valid as an null pointer constant.  */
1648
1649 tree
1650 non_lvalue (x)
1651      tree x;
1652 {
1653   tree result;
1654
1655   /* These things are certainly not lvalues.  */
1656   if (TREE_CODE (x) == NON_LVALUE_EXPR
1657       || TREE_CODE (x) == INTEGER_CST
1658       || TREE_CODE (x) == REAL_CST
1659       || TREE_CODE (x) == STRING_CST
1660       || TREE_CODE (x) == ADDR_EXPR)
1661     {
1662       if (TREE_CODE (x) == INTEGER_CST && integer_zerop (x))
1663         {
1664           /* Use NOP_EXPR instead of NON_LVALUE_EXPR
1665              so convert_for_assignment won't strip it.
1666              This is so this 0 won't be treated as a null pointer constant.  */
1667           result = build1 (NOP_EXPR, TREE_TYPE (x), x);
1668           TREE_CONSTANT (result) = TREE_CONSTANT (x);
1669           return result;
1670         }
1671       return x;
1672     }
1673
1674   result = build1 (NON_LVALUE_EXPR, TREE_TYPE (x), x);
1675   TREE_CONSTANT (result) = TREE_CONSTANT (x);
1676   return result;
1677 }
1678
1679 /* Nonzero means lvalues are limited to those valid in pedantic ANSI C.
1680    Zero means allow extended lvalues.  */
1681
1682 int pedantic_lvalues;
1683
1684 /* When pedantic, return an expr equal to X but certainly not valid as a
1685    pedantic lvalue.  Otherwise, return X.  */
1686
1687 tree
1688 pedantic_non_lvalue (x)
1689      tree x;
1690 {
1691   if (pedantic_lvalues)
1692     return non_lvalue (x);
1693   else
1694     return x;
1695 }
1696 \f
1697 /* Given a tree comparison code, return the code that is the logical inverse
1698    of the given code.  It is not safe to do this for floating-point
1699    comparisons, except for NE_EXPR and EQ_EXPR.  */
1700
1701 static enum tree_code
1702 invert_tree_comparison (code)
1703      enum tree_code code;
1704 {
1705   switch (code)
1706     {
1707     case EQ_EXPR:
1708       return NE_EXPR;
1709     case NE_EXPR:
1710       return EQ_EXPR;
1711     case GT_EXPR:
1712       return LE_EXPR;
1713     case GE_EXPR:
1714       return LT_EXPR;
1715     case LT_EXPR:
1716       return GE_EXPR;
1717     case LE_EXPR:
1718       return GT_EXPR;
1719     default:
1720       abort ();
1721     }
1722 }
1723
1724 /* Similar, but return the comparison that results if the operands are
1725    swapped.  This is safe for floating-point.  */
1726
1727 static enum tree_code
1728 swap_tree_comparison (code)
1729      enum tree_code code;
1730 {
1731   switch (code)
1732     {
1733     case EQ_EXPR:
1734     case NE_EXPR:
1735       return code;
1736     case GT_EXPR:
1737       return LT_EXPR;
1738     case GE_EXPR:
1739       return LE_EXPR;
1740     case LT_EXPR:
1741       return GT_EXPR;
1742     case LE_EXPR:
1743       return GE_EXPR;
1744     default:
1745       abort ();
1746     }
1747 }
1748
1749 /* Return nonzero if CODE is a tree code that represents a truth value.  */
1750
1751 static int
1752 truth_value_p (code)
1753      enum tree_code code;
1754 {
1755   return (TREE_CODE_CLASS (code) == '<'
1756           || code == TRUTH_AND_EXPR || code == TRUTH_ANDIF_EXPR
1757           || code == TRUTH_OR_EXPR || code == TRUTH_ORIF_EXPR
1758           || code == TRUTH_XOR_EXPR || code == TRUTH_NOT_EXPR);
1759 }
1760 \f
1761 /* Return nonzero if two operands are necessarily equal.
1762    If ONLY_CONST is non-zero, only return non-zero for constants.
1763    This function tests whether the operands are indistinguishable;
1764    it does not test whether they are equal using C's == operation.
1765    The distinction is important for IEEE floating point, because
1766    (1) -0.0 and 0.0 are distinguishable, but -0.0==0.0, and
1767    (2) two NaNs may be indistinguishable, but NaN!=NaN.  */
1768
1769 int
1770 operand_equal_p (arg0, arg1, only_const)
1771      tree arg0, arg1;
1772      int only_const;
1773 {
1774   /* If both types don't have the same signedness, then we can't consider
1775      them equal.  We must check this before the STRIP_NOPS calls
1776      because they may change the signedness of the arguments.  */
1777   if (TREE_UNSIGNED (TREE_TYPE (arg0)) != TREE_UNSIGNED (TREE_TYPE (arg1)))
1778     return 0;
1779
1780   STRIP_NOPS (arg0);
1781   STRIP_NOPS (arg1);
1782
1783   if (TREE_CODE (arg0) != TREE_CODE (arg1)
1784       /* This is needed for conversions and for COMPONENT_REF.
1785          Might as well play it safe and always test this.  */
1786       || TYPE_MODE (TREE_TYPE (arg0)) != TYPE_MODE (TREE_TYPE (arg1)))
1787     return 0;
1788
1789   /* If ARG0 and ARG1 are the same SAVE_EXPR, they are necessarily equal.
1790      We don't care about side effects in that case because the SAVE_EXPR
1791      takes care of that for us. In all other cases, two expressions are
1792      equal if they have no side effects.  If we have two identical
1793      expressions with side effects that should be treated the same due
1794      to the only side effects being identical SAVE_EXPR's, that will
1795      be detected in the recursive calls below.  */
1796   if (arg0 == arg1 && ! only_const
1797       && (TREE_CODE (arg0) == SAVE_EXPR
1798           || (! TREE_SIDE_EFFECTS (arg0) && ! TREE_SIDE_EFFECTS (arg1))))
1799     return 1;
1800
1801   /* Next handle constant cases, those for which we can return 1 even
1802      if ONLY_CONST is set.  */
1803   if (TREE_CONSTANT (arg0) && TREE_CONSTANT (arg1))
1804     switch (TREE_CODE (arg0))
1805       {
1806       case INTEGER_CST:
1807         return (! TREE_CONSTANT_OVERFLOW (arg0)
1808                 && ! TREE_CONSTANT_OVERFLOW (arg1)
1809                 && TREE_INT_CST_LOW (arg0) == TREE_INT_CST_LOW (arg1)
1810                 && TREE_INT_CST_HIGH (arg0) == TREE_INT_CST_HIGH (arg1));
1811
1812       case REAL_CST:
1813         return (! TREE_CONSTANT_OVERFLOW (arg0)
1814                 && ! TREE_CONSTANT_OVERFLOW (arg1)
1815                 && REAL_VALUES_IDENTICAL (TREE_REAL_CST (arg0),
1816                                           TREE_REAL_CST (arg1)));
1817
1818       case COMPLEX_CST:
1819         return (operand_equal_p (TREE_REALPART (arg0), TREE_REALPART (arg1),
1820                                  only_const)
1821                 && operand_equal_p (TREE_IMAGPART (arg0), TREE_IMAGPART (arg1),
1822                                     only_const));
1823
1824       case STRING_CST:
1825         return (TREE_STRING_LENGTH (arg0) == TREE_STRING_LENGTH (arg1)
1826                 && ! strncmp (TREE_STRING_POINTER (arg0),
1827                               TREE_STRING_POINTER (arg1),
1828                               TREE_STRING_LENGTH (arg0)));
1829
1830       case ADDR_EXPR:
1831         return operand_equal_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg1, 0),
1832                                 0);
1833       default:
1834         break;
1835       }
1836
1837   if (only_const)
1838     return 0;
1839
1840   switch (TREE_CODE_CLASS (TREE_CODE (arg0)))
1841     {
1842     case '1':
1843       /* Two conversions are equal only if signedness and modes match.  */
1844       if ((TREE_CODE (arg0) == NOP_EXPR || TREE_CODE (arg0) == CONVERT_EXPR)
1845           && (TREE_UNSIGNED (TREE_TYPE (arg0))
1846               != TREE_UNSIGNED (TREE_TYPE (arg1))))
1847         return 0;
1848
1849       return operand_equal_p (TREE_OPERAND (arg0, 0),
1850                               TREE_OPERAND (arg1, 0), 0);
1851
1852     case '<':
1853     case '2':
1854       if (operand_equal_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg1, 0), 0)
1855           && operand_equal_p (TREE_OPERAND (arg0, 1), TREE_OPERAND (arg1, 1),
1856                               0))
1857         return 1;
1858
1859       /* For commutative ops, allow the other order.  */
1860       return ((TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MULT_EXPR
1861                || TREE_CODE (arg0) == MIN_EXPR || TREE_CODE (arg0) == MAX_EXPR
1862                || TREE_CODE (arg0) == BIT_IOR_EXPR
1863                || TREE_CODE (arg0) == BIT_XOR_EXPR
1864                || TREE_CODE (arg0) == BIT_AND_EXPR
1865                || TREE_CODE (arg0) == NE_EXPR || TREE_CODE (arg0) == EQ_EXPR)
1866               && operand_equal_p (TREE_OPERAND (arg0, 0),
1867                                   TREE_OPERAND (arg1, 1), 0)
1868               && operand_equal_p (TREE_OPERAND (arg0, 1),
1869                                   TREE_OPERAND (arg1, 0), 0));
1870
1871     case 'r':
1872       switch (TREE_CODE (arg0))
1873         {
1874         case INDIRECT_REF:
1875           return operand_equal_p (TREE_OPERAND (arg0, 0),
1876                                   TREE_OPERAND (arg1, 0), 0);
1877
1878         case COMPONENT_REF:
1879         case ARRAY_REF:
1880           return (operand_equal_p (TREE_OPERAND (arg0, 0),
1881                                    TREE_OPERAND (arg1, 0), 0)
1882                   && operand_equal_p (TREE_OPERAND (arg0, 1),
1883                                       TREE_OPERAND (arg1, 1), 0));
1884
1885         case BIT_FIELD_REF:
1886           return (operand_equal_p (TREE_OPERAND (arg0, 0),
1887                                    TREE_OPERAND (arg1, 0), 0)
1888                   && operand_equal_p (TREE_OPERAND (arg0, 1),
1889                                       TREE_OPERAND (arg1, 1), 0)
1890                   && operand_equal_p (TREE_OPERAND (arg0, 2),
1891                                       TREE_OPERAND (arg1, 2), 0));
1892         default:
1893           return 0;
1894         }
1895
1896     default:
1897       return 0;
1898     }
1899 }
1900 \f
1901 /* Similar to operand_equal_p, but see if ARG0 might have been made by
1902    shorten_compare from ARG1 when ARG1 was being compared with OTHER.
1903
1904    When in doubt, return 0.  */
1905
1906 static int
1907 operand_equal_for_comparison_p (arg0, arg1, other)
1908      tree arg0, arg1;
1909      tree other;
1910 {
1911   int unsignedp1, unsignedpo;
1912   tree primarg1, primother;
1913   unsigned correct_width;
1914
1915   if (operand_equal_p (arg0, arg1, 0))
1916     return 1;
1917
1918   if (! INTEGRAL_TYPE_P (TREE_TYPE (arg0))
1919       || ! INTEGRAL_TYPE_P (TREE_TYPE (arg1)))
1920     return 0;
1921
1922   /* Duplicate what shorten_compare does to ARG1 and see if that gives the
1923      actual comparison operand, ARG0.
1924
1925      First throw away any conversions to wider types
1926      already present in the operands.  */
1927
1928   primarg1 = get_narrower (arg1, &unsignedp1);
1929   primother = get_narrower (other, &unsignedpo);
1930
1931   correct_width = TYPE_PRECISION (TREE_TYPE (arg1));
1932   if (unsignedp1 == unsignedpo
1933       && TYPE_PRECISION (TREE_TYPE (primarg1)) < correct_width
1934       && TYPE_PRECISION (TREE_TYPE (primother)) < correct_width)
1935     {
1936       tree type = TREE_TYPE (arg0);
1937
1938       /* Make sure shorter operand is extended the right way
1939          to match the longer operand.  */
1940       primarg1 = convert (signed_or_unsigned_type (unsignedp1,
1941                                                   TREE_TYPE (primarg1)),
1942                          primarg1);
1943
1944       if (operand_equal_p (arg0, convert (type, primarg1), 0))
1945         return 1;
1946     }
1947
1948   return 0;
1949 }
1950 \f
1951 /* See if ARG is an expression that is either a comparison or is performing
1952    arithmetic on comparisons.  The comparisons must only be comparing
1953    two different values, which will be stored in *CVAL1 and *CVAL2; if
1954    they are non-zero it means that some operands have already been found.
1955    No variables may be used anywhere else in the expression except in the
1956    comparisons.  If SAVE_P is true it means we removed a SAVE_EXPR around
1957    the expression and save_expr needs to be called with CVAL1 and CVAL2.
1958
1959    If this is true, return 1.  Otherwise, return zero.  */
1960
1961 static int
1962 twoval_comparison_p (arg, cval1, cval2, save_p)
1963      tree arg;
1964      tree *cval1, *cval2;
1965      int *save_p;
1966 {
1967   enum tree_code code = TREE_CODE (arg);
1968   char class = TREE_CODE_CLASS (code);
1969
1970   /* We can handle some of the 'e' cases here.  */
1971   if (class == 'e' && code == TRUTH_NOT_EXPR)
1972     class = '1';
1973   else if (class == 'e'
1974            && (code == TRUTH_ANDIF_EXPR || code == TRUTH_ORIF_EXPR
1975                || code == COMPOUND_EXPR))
1976     class = '2';
1977
1978   /* ??? Disable this since the SAVE_EXPR might already be in use outside
1979      the expression.  There may be no way to make this work, but it needs
1980      to be looked at again for 2.6.  */
1981 #if 0
1982   else if (class == 'e' && code == SAVE_EXPR && SAVE_EXPR_RTL (arg) == 0)
1983     {
1984       /* If we've already found a CVAL1 or CVAL2, this expression is
1985          two complex to handle.  */
1986       if (*cval1 || *cval2)
1987         return 0;
1988
1989       class = '1';
1990       *save_p = 1;
1991     }
1992 #endif
1993
1994   switch (class)
1995     {
1996     case '1':
1997       return twoval_comparison_p (TREE_OPERAND (arg, 0), cval1, cval2, save_p);
1998
1999     case '2':
2000       return (twoval_comparison_p (TREE_OPERAND (arg, 0), cval1, cval2, save_p)
2001               && twoval_comparison_p (TREE_OPERAND (arg, 1),
2002                                       cval1, cval2, save_p));
2003
2004     case 'c':
2005       return 1;
2006
2007     case 'e':
2008       if (code == COND_EXPR)
2009         return (twoval_comparison_p (TREE_OPERAND (arg, 0),
2010                                      cval1, cval2, save_p)
2011                 && twoval_comparison_p (TREE_OPERAND (arg, 1),
2012                                         cval1, cval2, save_p)
2013                 && twoval_comparison_p (TREE_OPERAND (arg, 2),
2014                                         cval1, cval2, save_p));
2015       return 0;
2016
2017     case '<':
2018       /* First see if we can handle the first operand, then the second.  For
2019          the second operand, we know *CVAL1 can't be zero.  It must be that
2020          one side of the comparison is each of the values; test for the
2021          case where this isn't true by failing if the two operands
2022          are the same.  */
2023
2024       if (operand_equal_p (TREE_OPERAND (arg, 0),
2025                            TREE_OPERAND (arg, 1), 0))
2026         return 0;
2027
2028       if (*cval1 == 0)
2029         *cval1 = TREE_OPERAND (arg, 0);
2030       else if (operand_equal_p (*cval1, TREE_OPERAND (arg, 0), 0))
2031         ;
2032       else if (*cval2 == 0)
2033         *cval2 = TREE_OPERAND (arg, 0);
2034       else if (operand_equal_p (*cval2, TREE_OPERAND (arg, 0), 0))
2035         ;
2036       else
2037         return 0;
2038
2039       if (operand_equal_p (*cval1, TREE_OPERAND (arg, 1), 0))
2040         ;
2041       else if (*cval2 == 0)
2042         *cval2 = TREE_OPERAND (arg, 1);
2043       else if (operand_equal_p (*cval2, TREE_OPERAND (arg, 1), 0))
2044         ;
2045       else
2046         return 0;
2047
2048       return 1;
2049
2050     default:
2051       return 0;
2052     }
2053 }
2054 \f
2055 /* ARG is a tree that is known to contain just arithmetic operations and
2056    comparisons.  Evaluate the operations in the tree substituting NEW0 for
2057    any occurrence of OLD0 as an operand of a comparison and likewise for
2058    NEW1 and OLD1.  */
2059
2060 static tree
2061 eval_subst (arg, old0, new0, old1, new1)
2062      tree arg;
2063      tree old0, new0, old1, new1;
2064 {
2065   tree type = TREE_TYPE (arg);
2066   enum tree_code code = TREE_CODE (arg);
2067   char class = TREE_CODE_CLASS (code);
2068
2069   /* We can handle some of the 'e' cases here.  */
2070   if (class == 'e' && code == TRUTH_NOT_EXPR)
2071     class = '1';
2072   else if (class == 'e'
2073            && (code == TRUTH_ANDIF_EXPR || code == TRUTH_ORIF_EXPR))
2074     class = '2';
2075
2076   switch (class)
2077     {
2078     case '1':
2079       return fold (build1 (code, type,
2080                            eval_subst (TREE_OPERAND (arg, 0),
2081                                        old0, new0, old1, new1)));
2082
2083     case '2':
2084       return fold (build (code, type,
2085                           eval_subst (TREE_OPERAND (arg, 0),
2086                                       old0, new0, old1, new1),
2087                           eval_subst (TREE_OPERAND (arg, 1),
2088                                       old0, new0, old1, new1)));
2089
2090     case 'e':
2091       switch (code)
2092         {
2093         case SAVE_EXPR:
2094           return eval_subst (TREE_OPERAND (arg, 0), old0, new0, old1, new1);
2095
2096         case COMPOUND_EXPR:
2097           return eval_subst (TREE_OPERAND (arg, 1), old0, new0, old1, new1);
2098
2099         case COND_EXPR:
2100           return fold (build (code, type,
2101                               eval_subst (TREE_OPERAND (arg, 0),
2102                                           old0, new0, old1, new1),
2103                               eval_subst (TREE_OPERAND (arg, 1),
2104                                           old0, new0, old1, new1),
2105                               eval_subst (TREE_OPERAND (arg, 2),
2106                                           old0, new0, old1, new1)));
2107         default:
2108           break;
2109         }
2110       /* fall through (???) */
2111
2112     case '<':
2113       {
2114         tree arg0 = TREE_OPERAND (arg, 0);
2115         tree arg1 = TREE_OPERAND (arg, 1);
2116
2117         /* We need to check both for exact equality and tree equality.  The
2118            former will be true if the operand has a side-effect.  In that
2119            case, we know the operand occurred exactly once.  */
2120
2121         if (arg0 == old0 || operand_equal_p (arg0, old0, 0))
2122           arg0 = new0;
2123         else if (arg0 == old1 || operand_equal_p (arg0, old1, 0))
2124           arg0 = new1;
2125
2126         if (arg1 == old0 || operand_equal_p (arg1, old0, 0))
2127           arg1 = new0;
2128         else if (arg1 == old1 || operand_equal_p (arg1, old1, 0))
2129           arg1 = new1;
2130
2131         return fold (build (code, type, arg0, arg1));
2132       }
2133
2134     default:
2135       return arg;
2136     }
2137 }
2138 \f
2139 /* Return a tree for the case when the result of an expression is RESULT
2140    converted to TYPE and OMITTED was previously an operand of the expression
2141    but is now not needed (e.g., we folded OMITTED * 0).
2142
2143    If OMITTED has side effects, we must evaluate it.  Otherwise, just do
2144    the conversion of RESULT to TYPE.  */
2145
2146 static tree
2147 omit_one_operand (type, result, omitted)
2148      tree type, result, omitted;
2149 {
2150   tree t = convert (type, result);
2151
2152   if (TREE_SIDE_EFFECTS (omitted))
2153     return build (COMPOUND_EXPR, type, omitted, t);
2154
2155   return non_lvalue (t);
2156 }
2157
2158 /* Similar, but call pedantic_non_lvalue instead of non_lvalue.  */
2159
2160 static tree
2161 pedantic_omit_one_operand (type, result, omitted)
2162      tree type, result, omitted;
2163 {
2164   tree t = convert (type, result);
2165
2166   if (TREE_SIDE_EFFECTS (omitted))
2167     return build (COMPOUND_EXPR, type, omitted, t);
2168
2169   return pedantic_non_lvalue (t);
2170 }
2171
2172
2173 \f
2174 /* Return a simplified tree node for the truth-negation of ARG.  This
2175    never alters ARG itself.  We assume that ARG is an operation that
2176    returns a truth value (0 or 1).  */
2177
2178 tree
2179 invert_truthvalue (arg)
2180      tree arg;
2181 {
2182   tree type = TREE_TYPE (arg);
2183   enum tree_code code = TREE_CODE (arg);
2184
2185   if (code == ERROR_MARK)
2186     return arg;
2187
2188   /* If this is a comparison, we can simply invert it, except for
2189      floating-point non-equality comparisons, in which case we just
2190      enclose a TRUTH_NOT_EXPR around what we have.  */
2191
2192   if (TREE_CODE_CLASS (code) == '<')
2193     {
2194       if (FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (arg, 0)))
2195           && code != NE_EXPR && code != EQ_EXPR)
2196         return build1 (TRUTH_NOT_EXPR, type, arg);
2197       else
2198         return build (invert_tree_comparison (code), type,
2199                       TREE_OPERAND (arg, 0), TREE_OPERAND (arg, 1));
2200     }
2201
2202   switch (code)
2203     {
2204     case INTEGER_CST:
2205       return convert (type, build_int_2 (TREE_INT_CST_LOW (arg) == 0
2206                                          && TREE_INT_CST_HIGH (arg) == 0, 0));
2207
2208     case TRUTH_AND_EXPR:
2209       return build (TRUTH_OR_EXPR, type,
2210                     invert_truthvalue (TREE_OPERAND (arg, 0)),
2211                     invert_truthvalue (TREE_OPERAND (arg, 1)));
2212
2213     case TRUTH_OR_EXPR:
2214       return build (TRUTH_AND_EXPR, type,
2215                     invert_truthvalue (TREE_OPERAND (arg, 0)),
2216                     invert_truthvalue (TREE_OPERAND (arg, 1)));
2217
2218     case TRUTH_XOR_EXPR:
2219       /* Here we can invert either operand.  We invert the first operand
2220          unless the second operand is a TRUTH_NOT_EXPR in which case our
2221          result is the XOR of the first operand with the inside of the
2222          negation of the second operand.  */
2223
2224       if (TREE_CODE (TREE_OPERAND (arg, 1)) == TRUTH_NOT_EXPR)
2225         return build (TRUTH_XOR_EXPR, type, TREE_OPERAND (arg, 0),
2226                       TREE_OPERAND (TREE_OPERAND (arg, 1), 0));
2227       else
2228         return build (TRUTH_XOR_EXPR, type,
2229                       invert_truthvalue (TREE_OPERAND (arg, 0)),
2230                       TREE_OPERAND (arg, 1));
2231
2232     case TRUTH_ANDIF_EXPR:
2233       return build (TRUTH_ORIF_EXPR, type,
2234                     invert_truthvalue (TREE_OPERAND (arg, 0)),
2235                     invert_truthvalue (TREE_OPERAND (arg, 1)));
2236
2237     case TRUTH_ORIF_EXPR:
2238       return build (TRUTH_ANDIF_EXPR, type,
2239                     invert_truthvalue (TREE_OPERAND (arg, 0)),
2240                     invert_truthvalue (TREE_OPERAND (arg, 1)));
2241
2242     case TRUTH_NOT_EXPR:
2243       return TREE_OPERAND (arg, 0);
2244
2245     case COND_EXPR:
2246       return build (COND_EXPR, type, TREE_OPERAND (arg, 0),
2247                     invert_truthvalue (TREE_OPERAND (arg, 1)),
2248                     invert_truthvalue (TREE_OPERAND (arg, 2)));
2249
2250     case COMPOUND_EXPR:
2251       return build (COMPOUND_EXPR, type, TREE_OPERAND (arg, 0),
2252                     invert_truthvalue (TREE_OPERAND (arg, 1)));
2253
2254     case NON_LVALUE_EXPR:
2255       return invert_truthvalue (TREE_OPERAND (arg, 0));
2256
2257     case NOP_EXPR:
2258     case CONVERT_EXPR:
2259     case FLOAT_EXPR:
2260       return build1 (TREE_CODE (arg), type,
2261                      invert_truthvalue (TREE_OPERAND (arg, 0)));
2262
2263     case BIT_AND_EXPR:
2264       if (!integer_onep (TREE_OPERAND (arg, 1)))
2265         break;
2266       return build (EQ_EXPR, type, arg, convert (type, integer_zero_node));
2267
2268     case SAVE_EXPR:
2269       return build1 (TRUTH_NOT_EXPR, type, arg);
2270
2271     case CLEANUP_POINT_EXPR:
2272       return build1 (CLEANUP_POINT_EXPR, type,
2273                      invert_truthvalue (TREE_OPERAND (arg, 0)));
2274
2275     default:
2276       break;
2277     }
2278   if (TREE_CODE (TREE_TYPE (arg)) != BOOLEAN_TYPE)
2279     abort ();
2280   return build1 (TRUTH_NOT_EXPR, type, arg);
2281 }
2282
2283 /* Given a bit-wise operation CODE applied to ARG0 and ARG1, see if both
2284    operands are another bit-wise operation with a common input.  If so,
2285    distribute the bit operations to save an operation and possibly two if
2286    constants are involved.  For example, convert
2287         (A | B) & (A | C) into A | (B & C)
2288    Further simplification will occur if B and C are constants.
2289
2290    If this optimization cannot be done, 0 will be returned.  */
2291
2292 static tree
2293 distribute_bit_expr (code, type, arg0, arg1)
2294      enum tree_code code;
2295      tree type;
2296      tree arg0, arg1;
2297 {
2298   tree common;
2299   tree left, right;
2300
2301   if (TREE_CODE (arg0) != TREE_CODE (arg1)
2302       || TREE_CODE (arg0) == code
2303       || (TREE_CODE (arg0) != BIT_AND_EXPR
2304           && TREE_CODE (arg0) != BIT_IOR_EXPR))
2305     return 0;
2306
2307   if (operand_equal_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg1, 0), 0))
2308     {
2309       common = TREE_OPERAND (arg0, 0);
2310       left = TREE_OPERAND (arg0, 1);
2311       right = TREE_OPERAND (arg1, 1);
2312     }
2313   else if (operand_equal_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg1, 1), 0))
2314     {
2315       common = TREE_OPERAND (arg0, 0);
2316       left = TREE_OPERAND (arg0, 1);
2317       right = TREE_OPERAND (arg1, 0);
2318     }
2319   else if (operand_equal_p (TREE_OPERAND (arg0, 1), TREE_OPERAND (arg1, 0), 0))
2320     {
2321       common = TREE_OPERAND (arg0, 1);
2322       left = TREE_OPERAND (arg0, 0);
2323       right = TREE_OPERAND (arg1, 1);
2324     }
2325   else if (operand_equal_p (TREE_OPERAND (arg0, 1), TREE_OPERAND (arg1, 1), 0))
2326     {
2327       common = TREE_OPERAND (arg0, 1);
2328       left = TREE_OPERAND (arg0, 0);
2329       right = TREE_OPERAND (arg1, 0);
2330     }
2331   else
2332     return 0;
2333
2334   return fold (build (TREE_CODE (arg0), type, common,
2335                       fold (build (code, type, left, right))));
2336 }
2337 \f
2338 /* Return a BIT_FIELD_REF of type TYPE to refer to BITSIZE bits of INNER
2339    starting at BITPOS.  The field is unsigned if UNSIGNEDP is non-zero.  */
2340
2341 static tree
2342 make_bit_field_ref (inner, type, bitsize, bitpos, unsignedp)
2343      tree inner;
2344      tree type;
2345      int bitsize, bitpos;
2346      int unsignedp;
2347 {
2348   tree result = build (BIT_FIELD_REF, type, inner,
2349                        size_int (bitsize), bitsize_int (bitpos, 0L));
2350
2351   TREE_UNSIGNED (result) = unsignedp;
2352
2353   return result;
2354 }
2355
2356 /* Optimize a bit-field compare.
2357
2358    There are two cases:  First is a compare against a constant and the
2359    second is a comparison of two items where the fields are at the same
2360    bit position relative to the start of a chunk (byte, halfword, word)
2361    large enough to contain it.  In these cases we can avoid the shift
2362    implicit in bitfield extractions.
2363
2364    For constants, we emit a compare of the shifted constant with the
2365    BIT_AND_EXPR of a mask and a byte, halfword, or word of the operand being
2366    compared.  For two fields at the same position, we do the ANDs with the
2367    similar mask and compare the result of the ANDs.
2368
2369    CODE is the comparison code, known to be either NE_EXPR or EQ_EXPR.
2370    COMPARE_TYPE is the type of the comparison, and LHS and RHS
2371    are the left and right operands of the comparison, respectively.
2372
2373    If the optimization described above can be done, we return the resulting
2374    tree.  Otherwise we return zero.  */
2375
2376 static tree
2377 optimize_bit_field_compare (code, compare_type, lhs, rhs)
2378      enum tree_code code;
2379      tree compare_type;
2380      tree lhs, rhs;
2381 {
2382   int lbitpos, lbitsize, rbitpos, rbitsize;
2383   int lnbitpos, lnbitsize, rnbitpos, rnbitsize;
2384   tree type = TREE_TYPE (lhs);
2385   tree signed_type, unsigned_type;
2386   int const_p = TREE_CODE (rhs) == INTEGER_CST;
2387   enum machine_mode lmode, rmode, lnmode, rnmode;
2388   int lunsignedp, runsignedp;
2389   int lvolatilep = 0, rvolatilep = 0;
2390   int alignment;
2391   tree linner, rinner;
2392   tree mask;
2393   tree offset;
2394
2395   /* Get all the information about the extractions being done.  If the bit size
2396      if the same as the size of the underlying object, we aren't doing an
2397      extraction at all and so can do nothing.  */
2398   linner = get_inner_reference (lhs, &lbitsize, &lbitpos, &offset, &lmode,
2399                                 &lunsignedp, &lvolatilep, &alignment);
2400   if (linner == lhs || lbitsize == GET_MODE_BITSIZE (lmode) || lbitsize < 0
2401       || offset != 0)
2402     return 0;
2403
2404  if (!const_p)
2405    {
2406      /* If this is not a constant, we can only do something if bit positions,
2407         sizes, and signedness are the same.   */
2408      rinner = get_inner_reference (rhs, &rbitsize, &rbitpos, &offset, &rmode,
2409                                    &runsignedp, &rvolatilep, &alignment);
2410
2411      if (rinner == rhs || lbitpos != rbitpos || lbitsize != rbitsize
2412          || lunsignedp != runsignedp || offset != 0)
2413        return 0;
2414    }
2415
2416   /* See if we can find a mode to refer to this field.  We should be able to,
2417      but fail if we can't.  */
2418   lnmode = get_best_mode (lbitsize, lbitpos,
2419                           TYPE_ALIGN (TREE_TYPE (linner)), word_mode,
2420                           lvolatilep);
2421   if (lnmode == VOIDmode)
2422     return 0;
2423
2424   /* Set signed and unsigned types of the precision of this mode for the
2425      shifts below.  */
2426   signed_type = type_for_mode (lnmode, 0);
2427   unsigned_type = type_for_mode (lnmode, 1);
2428
2429   if (! const_p)
2430     {
2431       rnmode = get_best_mode (rbitsize, rbitpos,
2432                               TYPE_ALIGN (TREE_TYPE (rinner)), word_mode,
2433                               rvolatilep);
2434       if (rnmode == VOIDmode)
2435         return 0;
2436     }
2437
2438   /* Compute the bit position and size for the new reference and our offset
2439      within it. If the new reference is the same size as the original, we
2440      won't optimize anything, so return zero.  */
2441   lnbitsize = GET_MODE_BITSIZE (lnmode);
2442   lnbitpos = lbitpos & ~ (lnbitsize - 1);
2443   lbitpos -= lnbitpos;
2444   if (lnbitsize == lbitsize)
2445     return 0;
2446
2447   if (! const_p)
2448     {
2449       rnbitsize = GET_MODE_BITSIZE (rnmode);
2450       rnbitpos = rbitpos & ~ (rnbitsize - 1);
2451       rbitpos -= rnbitpos;
2452       if (rnbitsize == rbitsize)
2453         return 0;
2454     }
2455
2456   if (BYTES_BIG_ENDIAN)
2457     lbitpos = lnbitsize - lbitsize - lbitpos;
2458
2459   /* Make the mask to be used against the extracted field.  */
2460   mask = build_int_2 (~0, ~0);
2461   TREE_TYPE (mask) = unsigned_type;
2462   force_fit_type (mask, 0);
2463   mask = convert (unsigned_type, mask);
2464   mask = const_binop (LSHIFT_EXPR, mask, size_int (lnbitsize - lbitsize), 0);
2465   mask = const_binop (RSHIFT_EXPR, mask,
2466                       size_int (lnbitsize - lbitsize - lbitpos), 0);
2467
2468   if (! const_p)
2469     /* If not comparing with constant, just rework the comparison
2470        and return.  */
2471     return build (code, compare_type,
2472                   build (BIT_AND_EXPR, unsigned_type,
2473                          make_bit_field_ref (linner, unsigned_type,
2474                                              lnbitsize, lnbitpos, 1),
2475                          mask),
2476                   build (BIT_AND_EXPR, unsigned_type,
2477                          make_bit_field_ref (rinner, unsigned_type,
2478                                              rnbitsize, rnbitpos, 1),
2479                          mask));
2480
2481   /* Otherwise, we are handling the constant case. See if the constant is too
2482      big for the field.  Warn and return a tree of for 0 (false) if so.  We do
2483      this not only for its own sake, but to avoid having to test for this
2484      error case below.  If we didn't, we might generate wrong code.
2485
2486      For unsigned fields, the constant shifted right by the field length should
2487      be all zero.  For signed fields, the high-order bits should agree with
2488      the sign bit.  */
2489
2490   if (lunsignedp)
2491     {
2492       if (! integer_zerop (const_binop (RSHIFT_EXPR,
2493                                         convert (unsigned_type, rhs),
2494                                         size_int (lbitsize), 0)))
2495         {
2496           warning ("comparison is always %s due to width of bitfield",
2497                    code == NE_EXPR ? "one" : "zero");
2498           return convert (compare_type,
2499                           (code == NE_EXPR
2500                            ? integer_one_node : integer_zero_node));
2501         }
2502     }
2503   else
2504     {
2505       tree tem = const_binop (RSHIFT_EXPR, convert (signed_type, rhs),
2506                               size_int (lbitsize - 1), 0);
2507       if (! integer_zerop (tem) && ! integer_all_onesp (tem))
2508         {
2509           warning ("comparison is always %s due to width of bitfield",
2510                    code == NE_EXPR ? "one" : "zero");
2511           return convert (compare_type,
2512                           (code == NE_EXPR
2513                            ? integer_one_node : integer_zero_node));
2514         }
2515     }
2516
2517   /* Single-bit compares should always be against zero.  */
2518   if (lbitsize == 1 && ! integer_zerop (rhs))
2519     {
2520       code = code == EQ_EXPR ? NE_EXPR : EQ_EXPR;
2521       rhs = convert (type, integer_zero_node);
2522     }
2523
2524   /* Make a new bitfield reference, shift the constant over the
2525      appropriate number of bits and mask it with the computed mask
2526      (in case this was a signed field).  If we changed it, make a new one.  */
2527   lhs = make_bit_field_ref (linner, unsigned_type, lnbitsize, lnbitpos, 1);
2528   if (lvolatilep)
2529     {
2530       TREE_SIDE_EFFECTS (lhs) = 1;
2531       TREE_THIS_VOLATILE (lhs) = 1;
2532     }
2533
2534   rhs = fold (const_binop (BIT_AND_EXPR,
2535                            const_binop (LSHIFT_EXPR,
2536                                         convert (unsigned_type, rhs),
2537                                         size_int (lbitpos), 0),
2538                            mask, 0));
2539
2540   return build (code, compare_type,
2541                 build (BIT_AND_EXPR, unsigned_type, lhs, mask),
2542                 rhs);
2543 }
2544 \f
2545 /* Subroutine for fold_truthop: decode a field reference.
2546
2547    If EXP is a comparison reference, we return the innermost reference.
2548
2549    *PBITSIZE is set to the number of bits in the reference, *PBITPOS is
2550    set to the starting bit number.
2551
2552    If the innermost field can be completely contained in a mode-sized
2553    unit, *PMODE is set to that mode.  Otherwise, it is set to VOIDmode.
2554
2555    *PVOLATILEP is set to 1 if the any expression encountered is volatile;
2556    otherwise it is not changed.
2557
2558    *PUNSIGNEDP is set to the signedness of the field.
2559
2560    *PMASK is set to the mask used.  This is either contained in a
2561    BIT_AND_EXPR or derived from the width of the field.
2562
2563    *PAND_MASK is set the the mask found in a BIT_AND_EXPR, if any.
2564
2565    Return 0 if this is not a component reference or is one that we can't
2566    do anything with.  */
2567
2568 static tree
2569 decode_field_reference (exp, pbitsize, pbitpos, pmode, punsignedp,
2570                         pvolatilep, pmask, pand_mask)
2571      tree exp;
2572      int *pbitsize, *pbitpos;
2573      enum machine_mode *pmode;
2574      int *punsignedp, *pvolatilep;
2575      tree *pmask;
2576      tree *pand_mask;
2577 {
2578   tree and_mask = 0;
2579   tree mask, inner, offset;
2580   tree unsigned_type;
2581   int precision;
2582   int alignment;
2583
2584   /* All the optimizations using this function assume integer fields.
2585      There are problems with FP fields since the type_for_size call
2586      below can fail for, e.g., XFmode.  */
2587   if (! INTEGRAL_TYPE_P (TREE_TYPE (exp)))
2588     return 0;
2589
2590   STRIP_NOPS (exp);
2591
2592   if (TREE_CODE (exp) == BIT_AND_EXPR)
2593     {
2594       and_mask = TREE_OPERAND (exp, 1);
2595       exp = TREE_OPERAND (exp, 0);
2596       STRIP_NOPS (exp); STRIP_NOPS (and_mask);
2597       if (TREE_CODE (and_mask) != INTEGER_CST)
2598         return 0;
2599     }
2600
2601
2602   inner = get_inner_reference (exp, pbitsize, pbitpos, &offset, pmode,
2603                                punsignedp, pvolatilep, &alignment);
2604   if ((inner == exp && and_mask == 0)
2605       || *pbitsize < 0 || offset != 0)
2606     return 0;
2607
2608   /* Compute the mask to access the bitfield.  */
2609   unsigned_type = type_for_size (*pbitsize, 1);
2610   precision = TYPE_PRECISION (unsigned_type);
2611
2612   mask = build_int_2 (~0, ~0);
2613   TREE_TYPE (mask) = unsigned_type;
2614   force_fit_type (mask, 0);
2615   mask = const_binop (LSHIFT_EXPR, mask, size_int (precision - *pbitsize), 0);
2616   mask = const_binop (RSHIFT_EXPR, mask, size_int (precision - *pbitsize), 0);
2617
2618   /* Merge it with the mask we found in the BIT_AND_EXPR, if any.  */
2619   if (and_mask != 0)
2620     mask = fold (build (BIT_AND_EXPR, unsigned_type,
2621                         convert (unsigned_type, and_mask), mask));
2622
2623   *pmask = mask;
2624   *pand_mask = and_mask;
2625   return inner;
2626 }
2627
2628 /* Return non-zero if MASK represents a mask of SIZE ones in the low-order
2629    bit positions.  */
2630
2631 static int
2632 all_ones_mask_p (mask, size)
2633      tree mask;
2634      int size;
2635 {
2636   tree type = TREE_TYPE (mask);
2637   int precision = TYPE_PRECISION (type);
2638   tree tmask;
2639
2640   tmask = build_int_2 (~0, ~0);
2641   TREE_TYPE (tmask) = signed_type (type);
2642   force_fit_type (tmask, 0);
2643   return
2644     tree_int_cst_equal (mask,
2645                         const_binop (RSHIFT_EXPR,
2646                                      const_binop (LSHIFT_EXPR, tmask,
2647                                                   size_int (precision - size),
2648                                                   0),
2649                                      size_int (precision - size), 0));
2650 }
2651
2652 /* Subroutine for fold_truthop: determine if an operand is simple enough
2653    to be evaluated unconditionally.  */
2654
2655 static int
2656 simple_operand_p (exp)
2657      tree exp;
2658 {
2659   /* Strip any conversions that don't change the machine mode.  */
2660   while ((TREE_CODE (exp) == NOP_EXPR
2661           || TREE_CODE (exp) == CONVERT_EXPR)
2662          && (TYPE_MODE (TREE_TYPE (exp))
2663              == TYPE_MODE (TREE_TYPE (TREE_OPERAND (exp, 0)))))
2664     exp = TREE_OPERAND (exp, 0);
2665
2666   return (TREE_CODE_CLASS (TREE_CODE (exp)) == 'c'
2667           || (TREE_CODE_CLASS (TREE_CODE (exp)) == 'd'
2668               && ! TREE_ADDRESSABLE (exp)
2669               && ! TREE_THIS_VOLATILE (exp)
2670               && ! DECL_NONLOCAL (exp)
2671               /* Don't regard global variables as simple.  They may be
2672                  allocated in ways unknown to the compiler (shared memory,
2673                  #pragma weak, etc).  */
2674               && ! TREE_PUBLIC (exp)
2675               && ! DECL_EXTERNAL (exp)
2676               /* Loading a static variable is unduly expensive, but global
2677                  registers aren't expensive.  */
2678               && (! TREE_STATIC (exp) || DECL_REGISTER (exp))));
2679 }
2680 \f
2681 /* The following functions are subroutines to fold_range_test and allow it to
2682    try to change a logical combination of comparisons into a range test.
2683
2684    For example, both
2685         X == 2 && X == 3 && X == 4 && X == 5
2686    and
2687         X >= 2 && X <= 5
2688    are converted to
2689         (unsigned) (X - 2) <= 3
2690
2691    We describe each set of comparisons as being either inside or outside
2692    a range, using a variable named like IN_P, and then describe the
2693    range with a lower and upper bound.  If one of the bounds is omitted,
2694    it represents either the highest or lowest value of the type.
2695
2696    In the comments below, we represent a range by two numbers in brackets
2697    preceded by a "+" to designate being inside that range, or a "-" to
2698    designate being outside that range, so the condition can be inverted by
2699    flipping the prefix.  An omitted bound is represented by a "-".  For
2700    example, "- [-, 10]" means being outside the range starting at the lowest
2701    possible value and ending at 10, in other words, being greater than 10.
2702    The range "+ [-, -]" is always true and hence the range "- [-, -]" is
2703    always false.
2704
2705    We set up things so that the missing bounds are handled in a consistent
2706    manner so neither a missing bound nor "true" and "false" need to be
2707    handled using a special case.  */
2708
2709 /* Return the result of applying CODE to ARG0 and ARG1, but handle the case
2710    of ARG0 and/or ARG1 being omitted, meaning an unlimited range. UPPER0_P
2711    and UPPER1_P are nonzero if the respective argument is an upper bound
2712    and zero for a lower.  TYPE, if nonzero, is the type of the result; it
2713    must be specified for a comparison.  ARG1 will be converted to ARG0's
2714    type if both are specified.  */
2715
2716 static tree
2717 range_binop (code, type, arg0, upper0_p, arg1, upper1_p)
2718      enum tree_code code;
2719      tree type;
2720      tree arg0, arg1;
2721      int upper0_p, upper1_p;
2722 {
2723   tree tem;
2724   int result;
2725   int sgn0, sgn1;
2726
2727   /* If neither arg represents infinity, do the normal operation.
2728      Else, if not a comparison, return infinity.  Else handle the special
2729      comparison rules. Note that most of the cases below won't occur, but
2730      are handled for consistency.  */
2731
2732   if (arg0 != 0 && arg1 != 0)
2733     {
2734       tem = fold (build (code, type != 0 ? type : TREE_TYPE (arg0),
2735                          arg0, convert (TREE_TYPE (arg0), arg1)));
2736       STRIP_NOPS (tem);
2737       return TREE_CODE (tem) == INTEGER_CST ? tem : 0;
2738     }
2739
2740   if (TREE_CODE_CLASS (code) != '<')
2741     return 0;
2742
2743   /* Set SGN[01] to -1 if ARG[01] is a lower bound, 1 for upper, and 0
2744      for neither.  Then compute our result treating them as never equal
2745      and comparing bounds to non-bounds as above.  */
2746   sgn0 = arg0 != 0 ? 0 : (upper0_p ? 1 : -1);
2747   sgn1 = arg1 != 0 ? 0 : (upper1_p ? 1 : -1);
2748   switch (code)
2749     {
2750     case EQ_EXPR:  case NE_EXPR:
2751       result = (code == NE_EXPR);
2752       break;
2753     case LT_EXPR:  case LE_EXPR:
2754       result = sgn0 < sgn1;
2755       break;
2756     case GT_EXPR:  case GE_EXPR:
2757       result = sgn0 > sgn1;
2758       break;
2759     default:
2760       abort ();
2761     }
2762
2763   return convert (type, result ? integer_one_node : integer_zero_node);
2764 }
2765 \f
2766 /* Given EXP, a logical expression, set the range it is testing into
2767    variables denoted by PIN_P, PLOW, and PHIGH.  Return the expression
2768    actually being tested.  *PLOW and *PHIGH will have be made the same type
2769    as the returned expression.  If EXP is not a comparison, we will most
2770    likely not be returning a useful value and range.  */
2771
2772 static tree
2773 make_range (exp, pin_p, plow, phigh)
2774      tree exp;
2775      int *pin_p;
2776      tree *plow, *phigh;
2777 {
2778   enum tree_code code;
2779   tree arg0, arg1, type;
2780   int in_p, n_in_p;
2781   tree low, high, n_low, n_high;
2782
2783   /* Start with simply saying "EXP != 0" and then look at the code of EXP
2784      and see if we can refine the range.  Some of the cases below may not
2785      happen, but it doesn't seem worth worrying about this.  We "continue"
2786      the outer loop when we've changed something; otherwise we "break"
2787      the switch, which will "break" the while.  */
2788
2789   in_p = 0, low = high = convert (TREE_TYPE (exp), integer_zero_node);
2790
2791   while (1)
2792     {
2793       code = TREE_CODE (exp);
2794       arg0 = TREE_OPERAND (exp, 0), arg1 = TREE_OPERAND (exp, 1);
2795       if (TREE_CODE_CLASS (code) == '<' || TREE_CODE_CLASS (code) == '1'
2796           || TREE_CODE_CLASS (code) == '2')
2797         type = TREE_TYPE (arg0);
2798
2799       switch (code)
2800         {
2801         case TRUTH_NOT_EXPR:
2802           in_p = ! in_p, exp = arg0;
2803           continue;
2804
2805         case EQ_EXPR: case NE_EXPR:
2806         case LT_EXPR: case LE_EXPR: case GE_EXPR: case GT_EXPR:
2807           /* We can only do something if the range is testing for zero
2808              and if the second operand is an integer constant.  Note that
2809              saying something is "in" the range we make is done by
2810              complementing IN_P since it will set in the initial case of
2811              being not equal to zero; "out" is leaving it alone.  */
2812           if (low == 0 || high == 0
2813               || ! integer_zerop (low) || ! integer_zerop (high)
2814               || TREE_CODE (arg1) != INTEGER_CST)
2815             break;
2816
2817           switch (code)
2818             {
2819             case NE_EXPR:  /* - [c, c]  */
2820               low = high = arg1;
2821               break;
2822             case EQ_EXPR:  /* + [c, c]  */
2823               in_p = ! in_p, low = high = arg1;
2824               break;
2825             case GT_EXPR:  /* - [-, c] */
2826               low = 0, high = arg1;
2827               break;
2828             case GE_EXPR:  /* + [c, -] */
2829               in_p = ! in_p, low = arg1, high = 0;
2830               break;
2831             case LT_EXPR:  /* - [c, -] */
2832               low = arg1, high = 0;
2833               break;
2834             case LE_EXPR:  /* + [-, c] */
2835               in_p = ! in_p, low = 0, high = arg1;
2836               break;
2837             default:
2838               abort ();
2839             }
2840
2841           exp = arg0;
2842
2843           /* If this is an unsigned comparison, we also know that EXP is
2844              greater than or equal to zero.  We base the range tests we make
2845              on that fact, so we record it here so we can parse existing
2846              range tests.  */
2847           if (TREE_UNSIGNED (type) && (low == 0 || high == 0))
2848             {
2849               if (! merge_ranges (&n_in_p, &n_low, &n_high, in_p, low, high,
2850                                   1, convert (type, integer_zero_node),
2851                                   NULL_TREE))
2852                 break;
2853
2854               in_p = n_in_p, low = n_low, high = n_high;
2855
2856               /* If the high bound is missing, reverse the range so it
2857                  goes from zero to the low bound minus 1.  */
2858               if (high == 0)
2859                 {
2860                   in_p = ! in_p;
2861                   high = range_binop (MINUS_EXPR, NULL_TREE, low, 0,
2862                                       integer_one_node, 0);
2863                   low = convert (type, integer_zero_node);
2864                 }
2865             }
2866           continue;
2867
2868         case NEGATE_EXPR:
2869           /* (-x) IN [a,b] -> x in [-b, -a]  */
2870           n_low = range_binop (MINUS_EXPR, type,
2871                                convert (type, integer_zero_node), 0, high, 1);
2872           n_high = range_binop (MINUS_EXPR, type,
2873                                 convert (type, integer_zero_node), 0, low, 0);
2874           low = n_low, high = n_high;
2875           exp = arg0;
2876           continue;
2877
2878         case BIT_NOT_EXPR:
2879           /* ~ X -> -X - 1  */
2880           exp = build (MINUS_EXPR, type, build1 (NEGATE_EXPR, type, arg0),
2881                        convert (type, integer_one_node));
2882           continue;
2883
2884         case PLUS_EXPR:  case MINUS_EXPR:
2885           if (TREE_CODE (arg1) != INTEGER_CST)
2886             break;
2887
2888           /* If EXP is signed, any overflow in the computation is undefined,
2889              so we don't worry about it so long as our computations on
2890              the bounds don't overflow.  For unsigned, overflow is defined
2891              and this is exactly the right thing.  */
2892           n_low = range_binop (code == MINUS_EXPR ? PLUS_EXPR : MINUS_EXPR,
2893                                type, low, 0, arg1, 0);
2894           n_high = range_binop (code == MINUS_EXPR ? PLUS_EXPR : MINUS_EXPR,
2895                                 type, high, 1, arg1, 0);
2896           if ((n_low != 0 && TREE_OVERFLOW (n_low))
2897               || (n_high != 0 && TREE_OVERFLOW (n_high)))
2898             break;
2899
2900           /* Check for an unsigned range which has wrapped around the maximum
2901              value thus making n_high < n_low, and normalize it.  */
2902           if (n_low && n_high && tree_int_cst_lt (n_high, n_low))
2903             {
2904               low = range_binop (PLUS_EXPR, type, n_high, 0,
2905                                  integer_one_node, 0);
2906               high = range_binop (MINUS_EXPR, type, n_low, 0,
2907                                  integer_one_node, 0);
2908               in_p = ! in_p;
2909             }
2910           else
2911             low = n_low, high = n_high;
2912
2913           exp = arg0;
2914           continue;
2915
2916         case NOP_EXPR:  case NON_LVALUE_EXPR:  case CONVERT_EXPR:
2917           if (! INTEGRAL_TYPE_P (type)
2918               || (low != 0 && ! int_fits_type_p (low, type))
2919               || (high != 0 && ! int_fits_type_p (high, type)))
2920             break;
2921
2922           n_low = low, n_high = high;
2923
2924           if (n_low != 0)
2925             n_low = convert (type, n_low);
2926
2927           if (n_high != 0)
2928             n_high = convert (type, n_high);
2929
2930           /* If we're converting from an unsigned to a signed type,
2931              we will be doing the comparison as unsigned.  The tests above
2932              have already verified that LOW and HIGH are both positive.
2933
2934              So we have to make sure that the original unsigned value will
2935              be interpreted as positive.  */
2936           if (TREE_UNSIGNED (type) && ! TREE_UNSIGNED (TREE_TYPE (exp)))
2937             {
2938               tree equiv_type = type_for_mode (TYPE_MODE (type), 1);
2939               tree high_positive;
2940
2941               /* A range without an upper bound is, naturally, unbounded.
2942                  Since convert would have cropped a very large value, use
2943                   the max value for the destination type.  */
2944
2945               high_positive = TYPE_MAX_VALUE (equiv_type);
2946               if (!high_positive)
2947                 {
2948                   high_positive = TYPE_MAX_VALUE (type);
2949                   if (!high_positive)
2950                     abort();
2951                 }
2952               high_positive = fold (build (RSHIFT_EXPR, type,
2953                                            convert (type, high_positive),
2954                                            convert (type, integer_one_node)));
2955
2956               /* If the low bound is specified, "and" the range with the
2957                  range for which the original unsigned value will be
2958                  positive.  */
2959               if (low != 0)
2960                 {
2961                   if (! merge_ranges (&n_in_p, &n_low, &n_high,
2962                                       1, n_low, n_high,
2963                                       1, convert (type, integer_zero_node),
2964                                       high_positive))
2965                     break;
2966
2967                   in_p = (n_in_p == in_p);
2968                 }
2969               else
2970                 {
2971                   /* Otherwise, "or" the range with the range of the input
2972                      that will be interpreted as negative.  */
2973                   if (! merge_ranges (&n_in_p, &n_low, &n_high,
2974                                       0, n_low, n_high,
2975                                       1, convert (type, integer_zero_node),
2976                                       high_positive))
2977                     break;
2978
2979                   in_p = (in_p != n_in_p);
2980                 }
2981             }
2982
2983           exp = arg0;
2984           low = n_low, high = n_high;
2985           continue;
2986
2987         default:
2988           break;
2989         }
2990
2991       break;
2992     }
2993
2994   /* If EXP is a constant, we can evaluate whether this is true or false.  */
2995   if (TREE_CODE (exp) == INTEGER_CST)
2996     {
2997       in_p = in_p == (integer_onep (range_binop (GE_EXPR, integer_type_node,
2998                                                  exp, 0, low, 0))
2999                       && integer_onep (range_binop (LE_EXPR, integer_type_node,
3000                                                     exp, 1, high, 1)));
3001       low = high = 0;
3002       exp = 0;
3003     }
3004
3005   *pin_p = in_p, *plow = low, *phigh = high;
3006   return exp;
3007 }
3008 \f
3009 /* Given a range, LOW, HIGH, and IN_P, an expression, EXP, and a result
3010    type, TYPE, return an expression to test if EXP is in (or out of, depending
3011    on IN_P) the range.  */
3012
3013 static tree
3014 build_range_check (type, exp, in_p, low, high)
3015      tree type;
3016      tree exp;
3017      int in_p;
3018      tree low, high;
3019 {
3020   tree etype = TREE_TYPE (exp);
3021   tree utype, value;
3022
3023   if (! in_p
3024       && (0 != (value = build_range_check (type, exp, 1, low, high))))
3025     return invert_truthvalue (value);
3026
3027   else if (low == 0 && high == 0)
3028     return convert (type, integer_one_node);
3029
3030   else if (low == 0)
3031     return fold (build (LE_EXPR, type, exp, high));
3032
3033   else if (high == 0)
3034     return fold (build (GE_EXPR, type, exp, low));
3035
3036   else if (operand_equal_p (low, high, 0))
3037     return fold (build (EQ_EXPR, type, exp, low));
3038
3039   else if (TREE_UNSIGNED (etype) && integer_zerop (low))
3040     return build_range_check (type, exp, 1, 0, high);
3041
3042   else if (integer_zerop (low))
3043     {
3044       utype = unsigned_type (etype);
3045       return build_range_check (type, convert (utype, exp), 1, 0,
3046                                 convert (utype, high));
3047     }
3048
3049   else if (0 != (value = const_binop (MINUS_EXPR, high, low, 0))
3050            && ! TREE_OVERFLOW (value))
3051     return build_range_check (type,
3052                               fold (build (MINUS_EXPR, etype, exp, low)),
3053                               1, convert (etype, integer_zero_node), value);
3054   else
3055     return 0;
3056 }
3057 \f
3058 /* Given two ranges, see if we can merge them into one.  Return 1 if we
3059    can, 0 if we can't.  Set the output range into the specified parameters.  */
3060
3061 static int
3062 merge_ranges (pin_p, plow, phigh, in0_p, low0, high0, in1_p, low1, high1)
3063      int *pin_p;
3064      tree *plow, *phigh;
3065      int in0_p, in1_p;
3066      tree low0, high0, low1, high1;
3067 {
3068   int no_overlap;
3069   int subset;
3070   int temp;
3071   tree tem;
3072   int in_p;
3073   tree low, high;
3074   int lowequal = ((low0 == 0 && low1 == 0)
3075                   || integer_onep (range_binop (EQ_EXPR, integer_type_node,
3076                                                 low0, 0, low1, 0)));
3077   int highequal = ((high0 == 0 && high1 == 0)
3078                    || integer_onep (range_binop (EQ_EXPR, integer_type_node,
3079                                                  high0, 1, high1, 1)));
3080
3081   /* Make range 0 be the range that starts first, or ends last if they
3082      start at the same value.  Swap them if it isn't.  */
3083   if (integer_onep (range_binop (GT_EXPR, integer_type_node,
3084                                  low0, 0, low1, 0))
3085       || (lowequal
3086           && integer_onep (range_binop (GT_EXPR, integer_type_node,
3087                                         high1, 1, high0, 1))))
3088     {
3089       temp = in0_p, in0_p = in1_p, in1_p = temp;
3090       tem = low0, low0 = low1, low1 = tem;
3091       tem = high0, high0 = high1, high1 = tem;
3092     }
3093
3094   /* Now flag two cases, whether the ranges are disjoint or whether the
3095      second range is totally subsumed in the first.  Note that the tests
3096      below are simplified by the ones above.  */
3097   no_overlap = integer_onep (range_binop (LT_EXPR, integer_type_node,
3098                                           high0, 1, low1, 0));
3099   subset = integer_onep (range_binop (LE_EXPR, integer_type_node,
3100                                       high1, 1, high0, 1));
3101
3102   /* We now have four cases, depending on whether we are including or
3103      excluding the two ranges.  */
3104   if (in0_p && in1_p)
3105     {
3106       /* If they don't overlap, the result is false.  If the second range
3107          is a subset it is the result.  Otherwise, the range is from the start
3108          of the second to the end of the first.  */
3109       if (no_overlap)
3110         in_p = 0, low = high = 0;
3111       else if (subset)
3112         in_p = 1, low = low1, high = high1;
3113       else
3114         in_p = 1, low = low1, high = high0;
3115     }
3116
3117   else if (in0_p && ! in1_p)
3118     {
3119       /* If they don't overlap, the result is the first range.  If they are
3120          equal, the result is false.  If the second range is a subset of the
3121          first, and the ranges begin at the same place, we go from just after
3122          the end of the first range to the end of the second.  If the second
3123          range is not a subset of the first, or if it is a subset and both
3124          ranges end at the same place, the range starts at the start of the
3125          first range and ends just before the second range.
3126          Otherwise, we can't describe this as a single range.  */
3127       if (no_overlap)
3128         in_p = 1, low = low0, high = high0;
3129       else if (lowequal && highequal)
3130         in_p = 0, low = high = 0;
3131       else if (subset && lowequal)
3132         {
3133           in_p = 1, high = high0;
3134           low = range_binop (PLUS_EXPR, NULL_TREE, high1, 0,
3135                              integer_one_node, 0);
3136         }
3137       else if (! subset || highequal)
3138         {
3139           in_p = 1, low = low0;
3140           high = range_binop (MINUS_EXPR, NULL_TREE, low1, 0,
3141                               integer_one_node, 0);
3142         }
3143       else
3144         return 0;
3145     }
3146
3147   else if (! in0_p && in1_p)
3148     {
3149       /* If they don't overlap, the result is the second range.  If the second
3150          is a subset of the first, the result is false.  Otherwise,
3151          the range starts just after the first range and ends at the
3152          end of the second.  */
3153       if (no_overlap)
3154         in_p = 1, low = low1, high = high1;
3155       else if (subset)
3156         in_p = 0, low = high = 0;
3157       else
3158         {
3159           in_p = 1, high = high1;
3160           low = range_binop (PLUS_EXPR, NULL_TREE, high0, 1,
3161                              integer_one_node, 0);
3162         }
3163     }
3164
3165   else
3166     {
3167       /* The case where we are excluding both ranges.  Here the complex case
3168          is if they don't overlap.  In that case, the only time we have a
3169          range is if they are adjacent.  If the second is a subset of the
3170          first, the result is the first.  Otherwise, the range to exclude
3171          starts at the beginning of the first range and ends at the end of the
3172          second.  */
3173       if (no_overlap)
3174         {
3175           if (integer_onep (range_binop (EQ_EXPR, integer_type_node,
3176                                          range_binop (PLUS_EXPR, NULL_TREE,
3177                                                       high0, 1,
3178                                                       integer_one_node, 1),
3179                                          1, low1, 0)))
3180             in_p = 0, low = low0, high = high1;
3181           else
3182             return 0;
3183         }
3184       else if (subset)
3185         in_p = 0, low = low0, high = high0;
3186       else
3187         in_p = 0, low = low0, high = high1;
3188     }
3189
3190   *pin_p = in_p, *plow = low, *phigh = high;
3191   return 1;
3192 }
3193 \f
3194 /* EXP is some logical combination of boolean tests.  See if we can
3195    merge it into some range test.  Return the new tree if so.  */
3196
3197 static tree
3198 fold_range_test (exp)
3199      tree exp;
3200 {
3201   int or_op = (TREE_CODE (exp) == TRUTH_ORIF_EXPR
3202                || TREE_CODE (exp) == TRUTH_OR_EXPR);
3203   int in0_p, in1_p, in_p;
3204   tree low0, low1, low, high0, high1, high;
3205   tree lhs = make_range (TREE_OPERAND (exp, 0), &in0_p, &low0, &high0);
3206   tree rhs = make_range (TREE_OPERAND (exp, 1), &in1_p, &low1, &high1);
3207   tree tem;
3208
3209   /* If this is an OR operation, invert both sides; we will invert
3210      again at the end.  */
3211   if (or_op)
3212     in0_p = ! in0_p, in1_p = ! in1_p;
3213
3214   /* If both expressions are the same, if we can merge the ranges, and we
3215      can build the range test, return it or it inverted.  If one of the
3216      ranges is always true or always false, consider it to be the same
3217      expression as the other.  */
3218   if ((lhs == 0 || rhs == 0 || operand_equal_p (lhs, rhs, 0))
3219       && merge_ranges (&in_p, &low, &high, in0_p, low0, high0,
3220                        in1_p, low1, high1)
3221       && 0 != (tem = (build_range_check (TREE_TYPE (exp),
3222                                          lhs != 0 ? lhs
3223                                          : rhs != 0 ? rhs : integer_zero_node,
3224                                          in_p, low, high))))
3225     return or_op ? invert_truthvalue (tem) : tem;
3226
3227   /* On machines where the branch cost is expensive, if this is a
3228      short-circuited branch and the underlying object on both sides
3229      is the same, make a non-short-circuit operation.  */
3230   else if (BRANCH_COST >= 2
3231            && (TREE_CODE (exp) == TRUTH_ANDIF_EXPR
3232                || TREE_CODE (exp) == TRUTH_ORIF_EXPR)
3233            && operand_equal_p (lhs, rhs, 0))
3234     {
3235       /* If simple enough, just rewrite.  Otherwise, make a SAVE_EXPR
3236          unless we are at top level, in which case we can't do this.  */
3237       if (simple_operand_p (lhs))
3238         return build (TREE_CODE (exp) == TRUTH_ANDIF_EXPR
3239                       ? TRUTH_AND_EXPR : TRUTH_OR_EXPR,
3240                       TREE_TYPE (exp), TREE_OPERAND (exp, 0),
3241                       TREE_OPERAND (exp, 1));
3242
3243       else if (current_function_decl != 0)
3244         {
3245           tree common = save_expr (lhs);
3246
3247           if (0 != (lhs = build_range_check (TREE_TYPE (exp), common,
3248                                              or_op ? ! in0_p : in0_p,
3249                                              low0, high0))
3250               && (0 != (rhs = build_range_check (TREE_TYPE (exp), common,
3251                                                  or_op ? ! in1_p : in1_p,
3252                                                  low1, high1))))
3253             return build (TREE_CODE (exp) == TRUTH_ANDIF_EXPR
3254                           ? TRUTH_AND_EXPR : TRUTH_OR_EXPR,
3255                           TREE_TYPE (exp), lhs, rhs);
3256         }
3257     }
3258   else
3259     return 0;
3260 }
3261 \f
3262 /* Subroutine for fold_truthop: C is an INTEGER_CST interpreted as a P
3263    bit value.  Arrange things so the extra bits will be set to zero if and
3264    only if C is signed-extended to its full width.  If MASK is nonzero,
3265    it is an INTEGER_CST that should be AND'ed with the extra bits.  */
3266
3267 static tree
3268 unextend (c, p, unsignedp, mask)
3269      tree c;
3270      int p;
3271      int unsignedp;
3272      tree mask;
3273 {
3274   tree type = TREE_TYPE (c);
3275   int modesize = GET_MODE_BITSIZE (TYPE_MODE (type));
3276   tree temp;
3277
3278   if (p == modesize || unsignedp)
3279     return c;
3280
3281   /* We work by getting just the sign bit into the low-order bit, then
3282      into the high-order bit, then sign-extend.  We then XOR that value
3283      with C.  */
3284   temp = const_binop (RSHIFT_EXPR, c, size_int (p - 1), 0);
3285   temp = const_binop (BIT_AND_EXPR, temp, size_int (1), 0);
3286
3287   /* We must use a signed type in order to get an arithmetic right shift.
3288      However, we must also avoid introducing accidental overflows, so that
3289      a subsequent call to integer_zerop will work.  Hence we must
3290      do the type conversion here.  At this point, the constant is either
3291      zero or one, and the conversion to a signed type can never overflow.
3292      We could get an overflow if this conversion is done anywhere else.  */
3293   if (TREE_UNSIGNED (type))
3294     temp = convert (signed_type (type), temp);
3295
3296   temp = const_binop (LSHIFT_EXPR, temp, size_int (modesize - 1), 0);
3297   temp = const_binop (RSHIFT_EXPR, temp, size_int (modesize - p - 1), 0);
3298   if (mask != 0)
3299     temp = const_binop (BIT_AND_EXPR, temp, convert (TREE_TYPE (c), mask), 0);
3300   /* If necessary, convert the type back to match the type of C.  */
3301   if (TREE_UNSIGNED (type))
3302     temp = convert (type, temp);
3303
3304   return convert (type, const_binop (BIT_XOR_EXPR, c, temp, 0));
3305 }
3306 \f
3307 /* Find ways of folding logical expressions of LHS and RHS:
3308    Try to merge two comparisons to the same innermost item.
3309    Look for range tests like "ch >= '0' && ch <= '9'".
3310    Look for combinations of simple terms on machines with expensive branches
3311    and evaluate the RHS unconditionally.
3312
3313    For example, if we have p->a == 2 && p->b == 4 and we can make an
3314    object large enough to span both A and B, we can do this with a comparison
3315    against the object ANDed with the a mask.
3316
3317    If we have p->a == q->a && p->b == q->b, we may be able to use bit masking
3318    operations to do this with one comparison.
3319
3320    We check for both normal comparisons and the BIT_AND_EXPRs made this by
3321    function and the one above.
3322
3323    CODE is the logical operation being done.  It can be TRUTH_ANDIF_EXPR,
3324    TRUTH_AND_EXPR, TRUTH_ORIF_EXPR, or TRUTH_OR_EXPR.
3325
3326    TRUTH_TYPE is the type of the logical operand and LHS and RHS are its
3327    two operands.
3328
3329    We return the simplified tree or 0 if no optimization is possible.  */
3330
3331 static tree
3332 fold_truthop (code, truth_type, lhs, rhs)
3333      enum tree_code code;
3334      tree truth_type, lhs, rhs;
3335 {
3336   /* If this is the "or" of two comparisons, we can do something if we
3337      the comparisons are NE_EXPR.  If this is the "and", we can do something
3338      if the comparisons are EQ_EXPR.  I.e.,
3339         (a->b == 2 && a->c == 4) can become (a->new == NEW).
3340
3341      WANTED_CODE is this operation code.  For single bit fields, we can
3342      convert EQ_EXPR to NE_EXPR so we need not reject the "wrong"
3343      comparison for one-bit fields.  */
3344
3345   enum tree_code wanted_code;
3346   enum tree_code lcode, rcode;
3347   tree ll_arg, lr_arg, rl_arg, rr_arg;
3348   tree ll_inner, lr_inner, rl_inner, rr_inner;
3349   int ll_bitsize, ll_bitpos, lr_bitsize, lr_bitpos;
3350   int rl_bitsize, rl_bitpos, rr_bitsize, rr_bitpos;
3351   int xll_bitpos, xlr_bitpos, xrl_bitpos, xrr_bitpos;
3352   int lnbitsize, lnbitpos, rnbitsize, rnbitpos;
3353   int ll_unsignedp, lr_unsignedp, rl_unsignedp, rr_unsignedp;
3354   enum machine_mode ll_mode, lr_mode, rl_mode, rr_mode;
3355   enum machine_mode lnmode, rnmode;
3356   tree ll_mask, lr_mask, rl_mask, rr_mask;
3357   tree ll_and_mask, lr_and_mask, rl_and_mask, rr_and_mask;
3358   tree l_const, r_const;
3359   tree type, result;
3360   int first_bit, end_bit;
3361   int volatilep;
3362
3363   /* Start by getting the comparison codes.  Fail if anything is volatile.
3364      If one operand is a BIT_AND_EXPR with the constant one, treat it as if
3365      it were surrounded with a NE_EXPR.  */
3366
3367   if (TREE_SIDE_EFFECTS (lhs) || TREE_SIDE_EFFECTS (rhs))
3368     return 0;
3369
3370   lcode = TREE_CODE (lhs);
3371   rcode = TREE_CODE (rhs);
3372
3373   if (lcode == BIT_AND_EXPR && integer_onep (TREE_OPERAND (lhs, 1)))
3374     lcode = NE_EXPR, lhs = build (NE_EXPR, truth_type, lhs, integer_zero_node);
3375
3376   if (rcode == BIT_AND_EXPR && integer_onep (TREE_OPERAND (rhs, 1)))
3377     rcode = NE_EXPR, rhs = build (NE_EXPR, truth_type, rhs, integer_zero_node);
3378
3379   if (TREE_CODE_CLASS (lcode) != '<' || TREE_CODE_CLASS (rcode) != '<')
3380     return 0;
3381
3382   code = ((code == TRUTH_AND_EXPR || code == TRUTH_ANDIF_EXPR)
3383           ? TRUTH_AND_EXPR : TRUTH_OR_EXPR);
3384
3385   ll_arg = TREE_OPERAND (lhs, 0);
3386   lr_arg = TREE_OPERAND (lhs, 1);
3387   rl_arg = TREE_OPERAND (rhs, 0);
3388   rr_arg = TREE_OPERAND (rhs, 1);
3389
3390   /* If the RHS can be evaluated unconditionally and its operands are
3391      simple, it wins to evaluate the RHS unconditionally on machines
3392      with expensive branches.  In this case, this isn't a comparison
3393      that can be merged.  */
3394
3395   /* @@ I'm not sure it wins on the m88110 to do this if the comparisons
3396      are with zero (tmw).  */
3397
3398   if (BRANCH_COST >= 2
3399       && INTEGRAL_TYPE_P (TREE_TYPE (rhs))
3400       && simple_operand_p (rl_arg)
3401       && simple_operand_p (rr_arg))
3402     return build (code, truth_type, lhs, rhs);
3403
3404   /* See if the comparisons can be merged.  Then get all the parameters for
3405      each side.  */
3406
3407   if ((lcode != EQ_EXPR && lcode != NE_EXPR)
3408       || (rcode != EQ_EXPR && rcode != NE_EXPR))
3409     return 0;
3410
3411   volatilep = 0;
3412   ll_inner = decode_field_reference (ll_arg,
3413                                      &ll_bitsize, &ll_bitpos, &ll_mode,
3414                                      &ll_unsignedp, &volatilep, &ll_mask,
3415                                      &ll_and_mask);
3416   lr_inner = decode_field_reference (lr_arg,
3417                                      &lr_bitsize, &lr_bitpos, &lr_mode,
3418                                      &lr_unsignedp, &volatilep, &lr_mask,
3419                                      &lr_and_mask);
3420   rl_inner = decode_field_reference (rl_arg,
3421                                      &rl_bitsize, &rl_bitpos, &rl_mode,
3422                                      &rl_unsignedp, &volatilep, &rl_mask,
3423                                      &rl_and_mask);
3424   rr_inner = decode_field_reference (rr_arg,
3425                                      &rr_bitsize, &rr_bitpos, &rr_mode,
3426                                      &rr_unsignedp, &volatilep, &rr_mask,
3427                                      &rr_and_mask);
3428
3429   /* It must be true that the inner operation on the lhs of each
3430      comparison must be the same if we are to be able to do anything.
3431      Then see if we have constants.  If not, the same must be true for
3432      the rhs's.  */
3433   if (volatilep || ll_inner == 0 || rl_inner == 0
3434       || ! operand_equal_p (ll_inner, rl_inner, 0))
3435     return 0;
3436
3437   if (TREE_CODE (lr_arg) == INTEGER_CST
3438       && TREE_CODE (rr_arg) == INTEGER_CST)
3439     l_const = lr_arg, r_const = rr_arg;
3440   else if (lr_inner == 0 || rr_inner == 0
3441            || ! operand_equal_p (lr_inner, rr_inner, 0))
3442     return 0;
3443   else
3444     l_const = r_const = 0;
3445
3446   /* If either comparison code is not correct for our logical operation,
3447      fail.  However, we can convert a one-bit comparison against zero into
3448      the opposite comparison against that bit being set in the field.  */
3449
3450   wanted_code = (code == TRUTH_AND_EXPR ? EQ_EXPR : NE_EXPR);
3451   if (lcode != wanted_code)
3452     {
3453       if (l_const && integer_zerop (l_const) && integer_pow2p (ll_mask))
3454         {
3455           if (ll_unsignedp || tree_log2 (ll_mask) + 1 < ll_bitsize)
3456             l_const = ll_mask;
3457         else
3458           /* Since ll_arg is a single bit bit mask, we can sign extend
3459              it appropriately with a NEGATE_EXPR.
3460              l_const is made a signed value here, but since for l_const != NULL
3461              lr_unsignedp is not used, we don't need to clear the latter.  */
3462           l_const = fold (build1 (NEGATE_EXPR, TREE_TYPE (ll_arg),
3463                                   convert (TREE_TYPE (ll_arg), ll_mask)));
3464         }
3465       else
3466         return 0;
3467     }
3468
3469   if (rcode != wanted_code)
3470     {
3471       if (r_const && integer_zerop (r_const) && integer_pow2p (rl_mask))
3472         {
3473           if (rl_unsignedp || tree_log2 (rl_mask) + 1 < rl_bitsize)
3474             r_const = rl_mask;
3475         else
3476           /* This is analogous to the code for l_const above.  */
3477           r_const = fold (build1 (NEGATE_EXPR, TREE_TYPE (rl_arg),
3478                                   convert (TREE_TYPE (rl_arg), rl_mask)));
3479         }
3480       else
3481         return 0;
3482     }
3483
3484   /* See if we can find a mode that contains both fields being compared on
3485      the left.  If we can't, fail.  Otherwise, update all constants and masks
3486      to be relative to a field of that size.  */
3487   first_bit = MIN (ll_bitpos, rl_bitpos);
3488   end_bit = MAX (ll_bitpos + ll_bitsize, rl_bitpos + rl_bitsize);
3489   lnmode = get_best_mode (end_bit - first_bit, first_bit,
3490                           TYPE_ALIGN (TREE_TYPE (ll_inner)), word_mode,
3491                           volatilep);
3492   if (lnmode == VOIDmode)
3493     return 0;
3494
3495   lnbitsize = GET_MODE_BITSIZE (lnmode);
3496   lnbitpos = first_bit & ~ (lnbitsize - 1);
3497   type = type_for_size (lnbitsize, 1);
3498   xll_bitpos = ll_bitpos - lnbitpos, xrl_bitpos = rl_bitpos - lnbitpos;
3499
3500   if (BYTES_BIG_ENDIAN)
3501     {
3502       xll_bitpos = lnbitsize - xll_bitpos - ll_bitsize;
3503       xrl_bitpos = lnbitsize - xrl_bitpos - rl_bitsize;
3504     }
3505
3506   ll_mask = const_binop (LSHIFT_EXPR, convert (type, ll_mask),
3507                          size_int (xll_bitpos), 0);
3508   rl_mask = const_binop (LSHIFT_EXPR, convert (type, rl_mask),
3509                          size_int (xrl_bitpos), 0);
3510
3511   if (l_const)
3512     {
3513       l_const = convert (type, l_const);
3514       l_const = unextend (l_const,  ll_bitsize, ll_unsignedp, ll_and_mask);
3515       l_const = const_binop (LSHIFT_EXPR, l_const, size_int (xll_bitpos), 0);
3516       if (! integer_zerop (const_binop (BIT_AND_EXPR, l_const,
3517                                         fold (build1 (BIT_NOT_EXPR,
3518                                                       type, ll_mask)),
3519                                         0)))
3520         {
3521           warning ("comparison is always %s",
3522                    wanted_code == NE_EXPR ? "one" : "zero");
3523
3524           return convert (truth_type,
3525                           wanted_code == NE_EXPR
3526                           ? integer_one_node : integer_zero_node);
3527         }
3528     }
3529   if (r_const)
3530     {
3531       r_const = convert (type, r_const);
3532       r_const = unextend (r_const, rl_bitsize, rl_unsignedp, rl_and_mask);
3533       r_const = const_binop (LSHIFT_EXPR, r_const, size_int (xrl_bitpos), 0);
3534       if (! integer_zerop (const_binop (BIT_AND_EXPR, r_const,
3535                                         fold (build1 (BIT_NOT_EXPR,
3536                                                       type, rl_mask)),
3537                                         0)))
3538         {
3539           warning ("comparison is always %s",
3540                    wanted_code == NE_EXPR ? "one" : "zero");
3541
3542           return convert (truth_type,
3543                           wanted_code == NE_EXPR
3544                           ? integer_one_node : integer_zero_node);
3545         }
3546     }
3547
3548   /* If the right sides are not constant, do the same for it.  Also,
3549      disallow this optimization if a size or signedness mismatch occurs
3550      between the left and right sides.  */
3551   if (l_const == 0)
3552     {
3553       if (ll_bitsize != lr_bitsize || rl_bitsize != rr_bitsize
3554           || ll_unsignedp != lr_unsignedp || rl_unsignedp != rr_unsignedp
3555           /* Make sure the two fields on the right
3556              correspond to the left without being swapped.  */
3557           || ll_bitpos - rl_bitpos != lr_bitpos - rr_bitpos)
3558         return 0;
3559
3560       first_bit = MIN (lr_bitpos, rr_bitpos);
3561       end_bit = MAX (lr_bitpos + lr_bitsize, rr_bitpos + rr_bitsize);
3562       rnmode = get_best_mode (end_bit - first_bit, first_bit,
3563                               TYPE_ALIGN (TREE_TYPE (lr_inner)), word_mode,
3564                               volatilep);
3565       if (rnmode == VOIDmode)
3566         return 0;
3567
3568       rnbitsize = GET_MODE_BITSIZE (rnmode);
3569       rnbitpos = first_bit & ~ (rnbitsize - 1);
3570       xlr_bitpos = lr_bitpos - rnbitpos, xrr_bitpos = rr_bitpos - rnbitpos;
3571
3572       if (BYTES_BIG_ENDIAN)
3573         {
3574           xlr_bitpos = rnbitsize - xlr_bitpos - lr_bitsize;
3575           xrr_bitpos = rnbitsize - xrr_bitpos - rr_bitsize;
3576         }
3577
3578       lr_mask = const_binop (LSHIFT_EXPR, convert (type, lr_mask),
3579                              size_int (xlr_bitpos), 0);
3580       rr_mask = const_binop (LSHIFT_EXPR, convert (type, rr_mask),
3581                              size_int (xrr_bitpos), 0);
3582
3583       /* Make a mask that corresponds to both fields being compared.
3584          Do this for both items being compared.  If the masks agree,
3585          we can do this by masking both and comparing the masked
3586          results.  */
3587       ll_mask = const_binop (BIT_IOR_EXPR, ll_mask, rl_mask, 0);
3588       lr_mask = const_binop (BIT_IOR_EXPR, lr_mask, rr_mask, 0);
3589       if (operand_equal_p (ll_mask, lr_mask, 0) && lnbitsize == rnbitsize)
3590         {
3591           lhs = make_bit_field_ref (ll_inner, type, lnbitsize, lnbitpos,
3592                                     ll_unsignedp || rl_unsignedp);
3593           rhs = make_bit_field_ref (lr_inner, type, rnbitsize, rnbitpos,
3594                                     lr_unsignedp || rr_unsignedp);
3595           if (! all_ones_mask_p (ll_mask, lnbitsize))
3596             {
3597               lhs = build (BIT_AND_EXPR, type, lhs, ll_mask);
3598               rhs = build (BIT_AND_EXPR, type, rhs, ll_mask);
3599             }
3600           return build (wanted_code, truth_type, lhs, rhs);
3601         }
3602
3603       /* There is still another way we can do something:  If both pairs of
3604          fields being compared are adjacent, we may be able to make a wider
3605          field containing them both.  */
3606       if ((ll_bitsize + ll_bitpos == rl_bitpos
3607            && lr_bitsize + lr_bitpos == rr_bitpos)
3608           || (ll_bitpos == rl_bitpos + rl_bitsize
3609               && lr_bitpos == rr_bitpos + rr_bitsize))
3610         return build (wanted_code, truth_type,
3611                       make_bit_field_ref (ll_inner, type,
3612                                           ll_bitsize + rl_bitsize,
3613                                           MIN (ll_bitpos, rl_bitpos),
3614                                           ll_unsignedp),
3615                       make_bit_field_ref (lr_inner, type,
3616                                           lr_bitsize + rr_bitsize,
3617                                           MIN (lr_bitpos, rr_bitpos),
3618                                           lr_unsignedp));
3619
3620       return 0;
3621     }
3622
3623   /* Handle the case of comparisons with constants.  If there is something in
3624      common between the masks, those bits of the constants must be the same.
3625      If not, the condition is always false.  Test for this to avoid generating
3626      incorrect code below.  */
3627   result = const_binop (BIT_AND_EXPR, ll_mask, rl_mask, 0);
3628   if (! integer_zerop (result)
3629       && simple_cst_equal (const_binop (BIT_AND_EXPR, result, l_const, 0),
3630                            const_binop (BIT_AND_EXPR, result, r_const, 0)) != 1)
3631     {
3632       if (wanted_code == NE_EXPR)
3633         {
3634           warning ("`or' of unmatched not-equal tests is always 1");
3635           return convert (truth_type, integer_one_node);
3636         }
3637       else
3638         {
3639           warning ("`and' of mutually exclusive equal-tests is always zero");
3640           return convert (truth_type, integer_zero_node);
3641         }
3642     }
3643
3644   /* Construct the expression we will return.  First get the component
3645      reference we will make.  Unless the mask is all ones the width of
3646      that field, perform the mask operation.  Then compare with the
3647      merged constant.  */
3648   result = make_bit_field_ref (ll_inner, type, lnbitsize, lnbitpos,
3649                                ll_unsignedp || rl_unsignedp);
3650
3651   ll_mask = const_binop (BIT_IOR_EXPR, ll_mask, rl_mask, 0);
3652   if (! all_ones_mask_p (ll_mask, lnbitsize))
3653     result = build (BIT_AND_EXPR, type, result, ll_mask);
3654
3655   return build (wanted_code, truth_type, result,
3656                 const_binop (BIT_IOR_EXPR, l_const, r_const, 0));
3657 }
3658 \f
3659 /* If T contains a COMPOUND_EXPR which was inserted merely to evaluate
3660    S, a SAVE_EXPR, return the expression actually being evaluated.   Note
3661    that we may sometimes modify the tree.  */
3662
3663 static tree
3664 strip_compound_expr (t, s)
3665      tree t;
3666      tree s;
3667 {
3668   enum tree_code code = TREE_CODE (t);
3669
3670   /* See if this is the COMPOUND_EXPR we want to eliminate.  */
3671   if (code == COMPOUND_EXPR && TREE_CODE (TREE_OPERAND (t, 0)) == CONVERT_EXPR
3672       && TREE_OPERAND (TREE_OPERAND (t, 0), 0) == s)
3673     return TREE_OPERAND (t, 1);
3674
3675   /* See if this is a COND_EXPR or a simple arithmetic operator.   We
3676      don't bother handling any other types.  */
3677   else if (code == COND_EXPR)
3678     {
3679       TREE_OPERAND (t, 0) = strip_compound_expr (TREE_OPERAND (t, 0), s);
3680       TREE_OPERAND (t, 1) = strip_compound_expr (TREE_OPERAND (t, 1), s);
3681       TREE_OPERAND (t, 2) = strip_compound_expr (TREE_OPERAND (t, 2), s);
3682     }
3683   else if (TREE_CODE_CLASS (code) == '1')
3684     TREE_OPERAND (t, 0) = strip_compound_expr (TREE_OPERAND (t, 0), s);
3685   else if (TREE_CODE_CLASS (code) == '<'
3686            || TREE_CODE_CLASS (code) == '2')
3687     {
3688       TREE_OPERAND (t, 0) = strip_compound_expr (TREE_OPERAND (t, 0), s);
3689       TREE_OPERAND (t, 1) = strip_compound_expr (TREE_OPERAND (t, 1), s);
3690     }
3691
3692   return t;
3693 }
3694 \f
3695 /* Perform constant folding and related simplification of EXPR.
3696    The related simplifications include x*1 => x, x*0 => 0, etc.,
3697    and application of the associative law.
3698    NOP_EXPR conversions may be removed freely (as long as we
3699    are careful not to change the C type of the overall expression)
3700    We cannot simplify through a CONVERT_EXPR, FIX_EXPR or FLOAT_EXPR,
3701    but we can constant-fold them if they have constant operands.  */
3702
3703 tree
3704 fold (expr)
3705      tree expr;
3706 {
3707   register tree t = expr;
3708   tree t1 = NULL_TREE;
3709   tree tem;
3710   tree type = TREE_TYPE (expr);
3711   register tree arg0, arg1;
3712   register enum tree_code code = TREE_CODE (t);
3713   register int kind;
3714   int invert;
3715
3716   /* WINS will be nonzero when the switch is done
3717      if all operands are constant.  */
3718
3719   int wins = 1;
3720
3721   /* Don't try to process an RTL_EXPR since its operands aren't trees.
3722      Likewise for a SAVE_EXPR that's already been evaluated.  */
3723   if (code == RTL_EXPR || (code == SAVE_EXPR && SAVE_EXPR_RTL (t)) != 0)
3724     return t;
3725
3726   /* Return right away if already constant.  */
3727   if (TREE_CONSTANT (t))
3728     {
3729       if (code == CONST_DECL)
3730         return DECL_INITIAL (t);
3731       return t;
3732     }
3733
3734   kind = TREE_CODE_CLASS (code);
3735   if (code == NOP_EXPR || code == FLOAT_EXPR || code == CONVERT_EXPR)
3736     {
3737       tree subop;
3738
3739       /* Special case for conversion ops that can have fixed point args.  */
3740       arg0 = TREE_OPERAND (t, 0);
3741
3742       /* Don't use STRIP_NOPS, because signedness of argument type matters.  */
3743       if (arg0 != 0)
3744         STRIP_TYPE_NOPS (arg0);
3745
3746       if (arg0 != 0 && TREE_CODE (arg0) == COMPLEX_CST)
3747         subop = TREE_REALPART (arg0);
3748       else
3749         subop = arg0;
3750
3751       if (subop != 0 && TREE_CODE (subop) != INTEGER_CST
3752 #if ! defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
3753           && TREE_CODE (subop) != REAL_CST
3754 #endif /* not REAL_IS_NOT_DOUBLE, or REAL_ARITHMETIC */
3755           )
3756         /* Note that TREE_CONSTANT isn't enough:
3757            static var addresses are constant but we can't
3758            do arithmetic on them.  */
3759         wins = 0;
3760     }
3761   else if (kind == 'e' || kind == '<'
3762            || kind == '1' || kind == '2' || kind == 'r')
3763     {
3764       register int len = tree_code_length[(int) code];
3765       register int i;
3766       for (i = 0; i < len; i++)
3767         {
3768           tree op = TREE_OPERAND (t, i);
3769           tree subop;
3770
3771           if (op == 0)
3772             continue;           /* Valid for CALL_EXPR, at least.  */
3773
3774           if (kind == '<' || code == RSHIFT_EXPR)
3775             {
3776               /* Signedness matters here.  Perhaps we can refine this
3777                  later.  */
3778               STRIP_TYPE_NOPS (op);
3779             }
3780           else
3781             {
3782               /* Strip any conversions that don't change the mode.  */
3783               STRIP_NOPS (op);
3784             }
3785
3786           if (TREE_CODE (op) == COMPLEX_CST)
3787             subop = TREE_REALPART (op);
3788           else
3789             subop = op;
3790
3791           if (TREE_CODE (subop) != INTEGER_CST
3792 #if ! defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
3793               && TREE_CODE (subop) != REAL_CST
3794 #endif /* not REAL_IS_NOT_DOUBLE, or REAL_ARITHMETIC */
3795               )
3796             /* Note that TREE_CONSTANT isn't enough:
3797                static var addresses are constant but we can't
3798                do arithmetic on them.  */
3799             wins = 0;
3800
3801           if (i == 0)
3802             arg0 = op;
3803           else if (i == 1)
3804             arg1 = op;
3805         }
3806     }
3807
3808   /* If this is a commutative operation, and ARG0 is a constant, move it
3809      to ARG1 to reduce the number of tests below.  */
3810   if ((code == PLUS_EXPR || code == MULT_EXPR || code == MIN_EXPR
3811        || code == MAX_EXPR || code == BIT_IOR_EXPR || code == BIT_XOR_EXPR
3812        || code == BIT_AND_EXPR)
3813       && (TREE_CODE (arg0) == INTEGER_CST || TREE_CODE (arg0) == REAL_CST))
3814     {
3815       tem = arg0; arg0 = arg1; arg1 = tem;
3816
3817       tem = TREE_OPERAND (t, 0); TREE_OPERAND (t, 0) = TREE_OPERAND (t, 1);
3818       TREE_OPERAND (t, 1) = tem;
3819     }
3820
3821   /* Now WINS is set as described above,
3822      ARG0 is the first operand of EXPR,
3823      and ARG1 is the second operand (if it has more than one operand).
3824
3825      First check for cases where an arithmetic operation is applied to a
3826      compound, conditional, or comparison operation.  Push the arithmetic
3827      operation inside the compound or conditional to see if any folding
3828      can then be done.  Convert comparison to conditional for this purpose.
3829      The also optimizes non-constant cases that used to be done in
3830      expand_expr.
3831
3832      Before we do that, see if this is a BIT_AND_EXPR or a BIT_OR_EXPR,
3833      one of the operands is a comparison and the other is a comparison, a
3834      BIT_AND_EXPR with the constant 1, or a truth value.  In that case, the
3835      code below would make the expression more complex.  Change it to a
3836      TRUTH_{AND,OR}_EXPR.  Likewise, convert a similar NE_EXPR to
3837      TRUTH_XOR_EXPR and an EQ_EXPR to the inversion of a TRUTH_XOR_EXPR.  */
3838
3839   if ((code == BIT_AND_EXPR || code == BIT_IOR_EXPR
3840        || code == EQ_EXPR || code == NE_EXPR)
3841       && ((truth_value_p (TREE_CODE (arg0))
3842            && (truth_value_p (TREE_CODE (arg1))
3843                || (TREE_CODE (arg1) == BIT_AND_EXPR
3844                    && integer_onep (TREE_OPERAND (arg1, 1)))))
3845           || (truth_value_p (TREE_CODE (arg1))
3846               && (truth_value_p (TREE_CODE (arg0))
3847                   || (TREE_CODE (arg0) == BIT_AND_EXPR
3848                       && integer_onep (TREE_OPERAND (arg0, 1)))))))
3849     {
3850       t = fold (build (code == BIT_AND_EXPR ? TRUTH_AND_EXPR
3851                        : code == BIT_IOR_EXPR ? TRUTH_OR_EXPR
3852                        : TRUTH_XOR_EXPR,
3853                        type, arg0, arg1));
3854
3855       if (code == EQ_EXPR)
3856         t = invert_truthvalue (t);
3857
3858       return t;
3859     }
3860
3861   if (TREE_CODE_CLASS (code) == '1')
3862     {
3863       if (TREE_CODE (arg0) == COMPOUND_EXPR)
3864         return build (COMPOUND_EXPR, type, TREE_OPERAND (arg0, 0),
3865                       fold (build1 (code, type, TREE_OPERAND (arg0, 1))));
3866       else if (TREE_CODE (arg0) == COND_EXPR)
3867         {
3868           t = fold (build (COND_EXPR, type, TREE_OPERAND (arg0, 0),
3869                            fold (build1 (code, type, TREE_OPERAND (arg0, 1))),
3870                            fold (build1 (code, type, TREE_OPERAND (arg0, 2)))));
3871
3872           /* If this was a conversion, and all we did was to move into
3873              inside the COND_EXPR, bring it back out.  But leave it if
3874              it is a conversion from integer to integer and the
3875              result precision is no wider than a word since such a
3876              conversion is cheap and may be optimized away by combine,
3877              while it couldn't if it were outside the COND_EXPR.  Then return
3878              so we don't get into an infinite recursion loop taking the
3879              conversion out and then back in.  */
3880
3881           if ((code == NOP_EXPR || code == CONVERT_EXPR
3882                || code == NON_LVALUE_EXPR)
3883               && TREE_CODE (t) == COND_EXPR
3884               && TREE_CODE (TREE_OPERAND (t, 1)) == code
3885               && TREE_CODE (TREE_OPERAND (t, 2)) == code
3886               && (TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 1), 0))
3887                   == TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 2), 0)))
3888               && ! (INTEGRAL_TYPE_P (TREE_TYPE (t))
3889                     && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 1), 0)))
3890                     && TYPE_PRECISION (TREE_TYPE (t)) <= BITS_PER_WORD))
3891             t = build1 (code, type,
3892                         build (COND_EXPR,
3893                                TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 1), 0)),
3894                                TREE_OPERAND (t, 0),
3895                                TREE_OPERAND (TREE_OPERAND (t, 1), 0),
3896                                TREE_OPERAND (TREE_OPERAND (t, 2), 0)));
3897           return t;
3898         }
3899       else if (TREE_CODE_CLASS (TREE_CODE (arg0)) == '<')
3900         return fold (build (COND_EXPR, type, arg0,
3901                             fold (build1 (code, type, integer_one_node)),
3902                             fold (build1 (code, type, integer_zero_node))));
3903    }
3904   else if (TREE_CODE_CLASS (code) == '2'
3905            || TREE_CODE_CLASS (code) == '<')
3906     {
3907       if (TREE_CODE (arg1) == COMPOUND_EXPR)
3908         return build (COMPOUND_EXPR, type, TREE_OPERAND (arg1, 0),
3909                       fold (build (code, type,
3910                                    arg0, TREE_OPERAND (arg1, 1))));
3911       else if ((TREE_CODE (arg1) == COND_EXPR
3912                 || (TREE_CODE_CLASS (TREE_CODE (arg1)) == '<'
3913                     && TREE_CODE_CLASS (code) != '<'))
3914                && (! TREE_SIDE_EFFECTS (arg0) || current_function_decl != 0))
3915         {
3916           tree test, true_value, false_value;
3917
3918           if (TREE_CODE (arg1) == COND_EXPR)
3919             {
3920               test = TREE_OPERAND (arg1, 0);
3921               true_value = TREE_OPERAND (arg1, 1);
3922               false_value = TREE_OPERAND (arg1, 2);
3923             }
3924           else
3925             {
3926               tree testtype = TREE_TYPE (arg1);
3927               test = arg1;
3928               true_value = convert (testtype, integer_one_node);
3929               false_value = convert (testtype, integer_zero_node);
3930             }
3931
3932           /* If ARG0 is complex we want to make sure we only evaluate
3933              it once.  Though this is only required if it is volatile, it
3934              might be more efficient even if it is not.  However, if we
3935              succeed in folding one part to a constant, we do not need
3936              to make this SAVE_EXPR.  Since we do this optimization
3937              primarily to see if we do end up with constant and this
3938              SAVE_EXPR interferes with later optimizations, suppressing
3939              it when we can is important.  */
3940
3941           if (TREE_CODE (arg0) != SAVE_EXPR
3942               && ((TREE_CODE (arg0) != VAR_DECL
3943                    && TREE_CODE (arg0) != PARM_DECL)
3944                   || TREE_SIDE_EFFECTS (arg0)))
3945             {
3946               tree lhs = fold (build (code, type, arg0, true_value));
3947               tree rhs = fold (build (code, type, arg0, false_value));
3948
3949               if (TREE_CONSTANT (lhs) || TREE_CONSTANT (rhs))
3950                 return fold (build (COND_EXPR, type, test, lhs, rhs));
3951
3952               if (current_function_decl != 0)
3953                 arg0 = save_expr (arg0);
3954             }
3955
3956           test = fold (build (COND_EXPR, type, test,
3957                               fold (build (code, type, arg0, true_value)),
3958                               fold (build (code, type, arg0, false_value))));
3959           if (TREE_CODE (arg0) == SAVE_EXPR)
3960             return build (COMPOUND_EXPR, type,
3961                           convert (void_type_node, arg0),
3962                           strip_compound_expr (test, arg0));
3963           else
3964             return convert (type, test);
3965         }
3966
3967       else if (TREE_CODE (arg0) == COMPOUND_EXPR)
3968         return build (COMPOUND_EXPR, type, TREE_OPERAND (arg0, 0),
3969                       fold (build (code, type, TREE_OPERAND (arg0, 1), arg1)));
3970       else if ((TREE_CODE (arg0) == COND_EXPR
3971                 || (TREE_CODE_CLASS (TREE_CODE (arg0)) == '<'
3972                     && TREE_CODE_CLASS (code) != '<'))
3973                && (! TREE_SIDE_EFFECTS (arg1) || current_function_decl != 0))
3974         {
3975           tree test, true_value, false_value;
3976
3977           if (TREE_CODE (arg0) == COND_EXPR)
3978             {
3979               test = TREE_OPERAND (arg0, 0);
3980               true_value = TREE_OPERAND (arg0, 1);
3981               false_value = TREE_OPERAND (arg0, 2);
3982             }
3983           else
3984             {
3985               tree testtype = TREE_TYPE (arg0);
3986               test = arg0;
3987               true_value = convert (testtype, integer_one_node);
3988               false_value = convert (testtype, integer_zero_node);
3989             }
3990
3991           if (TREE_CODE (arg1) != SAVE_EXPR
3992               && ((TREE_CODE (arg1) != VAR_DECL
3993                    && TREE_CODE (arg1) != PARM_DECL)
3994                   || TREE_SIDE_EFFECTS (arg1)))
3995             {
3996               tree lhs = fold (build (code, type, true_value, arg1));
3997               tree rhs = fold (build (code, type, false_value, arg1));
3998
3999               if (TREE_CONSTANT (lhs) || TREE_CONSTANT (rhs)
4000                   || TREE_CONSTANT (arg1))
4001                 return fold (build (COND_EXPR, type, test, lhs, rhs));
4002
4003               if (current_function_decl != 0)
4004                 arg1 = save_expr (arg1);
4005             }
4006
4007           test = fold (build (COND_EXPR, type, test,
4008                               fold (build (code, type, true_value, arg1)),
4009                               fold (build (code, type, false_value, arg1))));
4010           if (TREE_CODE (arg1) == SAVE_EXPR)
4011             return build (COMPOUND_EXPR, type,
4012                           convert (void_type_node, arg1),
4013                           strip_compound_expr (test, arg1));
4014           else
4015             return convert (type, test);
4016         }
4017     }
4018   else if (TREE_CODE_CLASS (code) == '<'
4019            && TREE_CODE (arg0) == COMPOUND_EXPR)
4020     return build (COMPOUND_EXPR, type, TREE_OPERAND (arg0, 0),
4021                   fold (build (code, type, TREE_OPERAND (arg0, 1), arg1)));
4022   else if (TREE_CODE_CLASS (code) == '<'
4023            && TREE_CODE (arg1) == COMPOUND_EXPR)
4024     return build (COMPOUND_EXPR, type, TREE_OPERAND (arg1, 0),
4025                   fold (build (code, type, arg0, TREE_OPERAND (arg1, 1))));
4026
4027   switch (code)
4028     {
4029     case INTEGER_CST:
4030     case REAL_CST:
4031     case STRING_CST:
4032     case COMPLEX_CST:
4033     case CONSTRUCTOR:
4034       return t;
4035
4036     case CONST_DECL:
4037       return fold (DECL_INITIAL (t));
4038
4039     case NOP_EXPR:
4040     case FLOAT_EXPR:
4041     case CONVERT_EXPR:
4042     case FIX_TRUNC_EXPR:
4043       /* Other kinds of FIX are not handled properly by fold_convert.  */
4044
4045       if (TREE_TYPE (TREE_OPERAND (t, 0)) == TREE_TYPE (t))
4046         return TREE_OPERAND (t, 0);
4047
4048       /* Handle cases of two conversions in a row.  */
4049       if (TREE_CODE (TREE_OPERAND (t, 0)) == NOP_EXPR
4050           || TREE_CODE (TREE_OPERAND (t, 0)) == CONVERT_EXPR)
4051         {
4052           tree inside_type = TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 0), 0));
4053           tree inter_type = TREE_TYPE (TREE_OPERAND (t, 0));
4054           tree final_type = TREE_TYPE (t);
4055           int inside_int = INTEGRAL_TYPE_P (inside_type);
4056           int inside_ptr = POINTER_TYPE_P (inside_type);
4057           int inside_float = FLOAT_TYPE_P (inside_type);
4058           int inside_prec = TYPE_PRECISION (inside_type);
4059           int inside_unsignedp = TREE_UNSIGNED (inside_type);
4060           int inter_int = INTEGRAL_TYPE_P (inter_type);
4061           int inter_ptr = POINTER_TYPE_P (inter_type);
4062           int inter_float = FLOAT_TYPE_P (inter_type);
4063           int inter_prec = TYPE_PRECISION (inter_type);
4064           int inter_unsignedp = TREE_UNSIGNED (inter_type);
4065           int final_int = INTEGRAL_TYPE_P (final_type);
4066           int final_ptr = POINTER_TYPE_P (final_type);
4067           int final_float = FLOAT_TYPE_P (final_type);
4068           int final_prec = TYPE_PRECISION (final_type);
4069           int final_unsignedp = TREE_UNSIGNED (final_type);
4070
4071           /* In addition to the cases of two conversions in a row
4072              handled below, if we are converting something to its own
4073              type via an object of identical or wider precision, neither
4074              conversion is needed.  */
4075           if (inside_type == final_type
4076               && ((inter_int && final_int) || (inter_float && final_float))
4077               && inter_prec >= final_prec)
4078             return TREE_OPERAND (TREE_OPERAND (t, 0), 0);
4079
4080           /* Likewise, if the intermediate and final types are either both
4081              float or both integer, we don't need the middle conversion if
4082              it is wider than the final type and doesn't change the signedness
4083              (for integers).  Avoid this if the final type is a pointer
4084              since then we sometimes need the inner conversion.  Likewise if
4085              the outer has a precision not equal to the size of its mode.  */
4086           if ((((inter_int || inter_ptr) && (inside_int || inside_ptr))
4087                || (inter_float && inside_float))
4088               && inter_prec >= inside_prec
4089               && (inter_float || inter_unsignedp == inside_unsignedp)
4090               && ! (final_prec != GET_MODE_BITSIZE (TYPE_MODE (final_type))
4091                     && TYPE_MODE (final_type) == TYPE_MODE (inter_type))
4092               && ! final_ptr)
4093             return convert (final_type, TREE_OPERAND (TREE_OPERAND (t, 0), 0));
4094
4095           /* Two conversions in a row are not needed unless:
4096              - some conversion is floating-point (overstrict for now), or
4097              - the intermediate type is narrower than both initial and
4098                final, or
4099              - the intermediate type and innermost type differ in signedness,
4100                and the outermost type is wider than the intermediate, or
4101              - the initial type is a pointer type and the precisions of the
4102                intermediate and final types differ, or
4103              - the final type is a pointer type and the precisions of the
4104                initial and intermediate types differ.  */
4105           if (! inside_float && ! inter_float && ! final_float
4106               && (inter_prec > inside_prec || inter_prec > final_prec)
4107               && ! (inside_int && inter_int
4108                     && inter_unsignedp != inside_unsignedp
4109                     && inter_prec < final_prec)
4110               && ((inter_unsignedp && inter_prec > inside_prec)
4111                   == (final_unsignedp && final_prec > inter_prec))
4112               && ! (inside_ptr && inter_prec != final_prec)
4113               && ! (final_ptr && inside_prec != inter_prec)
4114               && ! (final_prec != GET_MODE_BITSIZE (TYPE_MODE (final_type))
4115                     && TYPE_MODE (final_type) == TYPE_MODE (inter_type))
4116               && ! final_ptr)
4117             return convert (final_type, TREE_OPERAND (TREE_OPERAND (t, 0), 0));
4118         }
4119
4120       if (TREE_CODE (TREE_OPERAND (t, 0)) == MODIFY_EXPR
4121           && TREE_CONSTANT (TREE_OPERAND (TREE_OPERAND (t, 0), 1))
4122           /* Detect assigning a bitfield.  */
4123           && !(TREE_CODE (TREE_OPERAND (TREE_OPERAND (t, 0), 0)) == COMPONENT_REF
4124                && DECL_BIT_FIELD (TREE_OPERAND (TREE_OPERAND (TREE_OPERAND (t, 0), 0), 1))))
4125         {
4126           /* Don't leave an assignment inside a conversion
4127              unless assigning a bitfield.  */
4128           tree prev = TREE_OPERAND (t, 0);
4129           TREE_OPERAND (t, 0) = TREE_OPERAND (prev, 1);
4130           /* First do the assignment, then return converted constant.  */
4131           t = build (COMPOUND_EXPR, TREE_TYPE (t), prev, fold (t));
4132           TREE_USED (t) = 1;
4133           return t;
4134         }
4135       if (!wins)
4136         {
4137           TREE_CONSTANT (t) = TREE_CONSTANT (arg0);
4138           return t;
4139         }
4140       return fold_convert (t, arg0);
4141
4142 #if 0  /* This loses on &"foo"[0].  */
4143     case ARRAY_REF:
4144         {
4145           int i;
4146
4147           /* Fold an expression like: "foo"[2] */
4148           if (TREE_CODE (arg0) == STRING_CST
4149               && TREE_CODE (arg1) == INTEGER_CST
4150               && !TREE_INT_CST_HIGH (arg1)
4151               && (i = TREE_INT_CST_LOW (arg1)) < TREE_STRING_LENGTH (arg0))
4152             {
4153               t = build_int_2 (TREE_STRING_POINTER (arg0)[i], 0);
4154               TREE_TYPE (t) = TREE_TYPE (TREE_TYPE (arg0));
4155               force_fit_type (t, 0);
4156             }
4157         }
4158       return t;
4159 #endif /* 0 */
4160
4161     case COMPONENT_REF:
4162       if (TREE_CODE (arg0) == CONSTRUCTOR)
4163         {
4164           tree m = purpose_member (arg1, CONSTRUCTOR_ELTS (arg0));
4165           if (m)
4166             t = TREE_VALUE (m);
4167         }
4168       return t;
4169
4170     case RANGE_EXPR:
4171       TREE_CONSTANT (t) = wins;
4172       return t;
4173
4174     case NEGATE_EXPR:
4175       if (wins)
4176         {
4177           if (TREE_CODE (arg0) == INTEGER_CST)
4178             {
4179               HOST_WIDE_INT low, high;
4180               int overflow = neg_double (TREE_INT_CST_LOW (arg0),
4181                                          TREE_INT_CST_HIGH (arg0),
4182                                          &low, &high);
4183               t = build_int_2 (low, high);
4184               TREE_TYPE (t) = type;
4185               TREE_OVERFLOW (t)
4186                 = (TREE_OVERFLOW (arg0)
4187                    | force_fit_type (t, overflow && !TREE_UNSIGNED (type)));
4188               TREE_CONSTANT_OVERFLOW (t)
4189                 = TREE_OVERFLOW (t) | TREE_CONSTANT_OVERFLOW (arg0);
4190             }
4191           else if (TREE_CODE (arg0) == REAL_CST)
4192             t = build_real (type, REAL_VALUE_NEGATE (TREE_REAL_CST (arg0)));
4193         }
4194       else if (TREE_CODE (arg0) == NEGATE_EXPR)
4195         return TREE_OPERAND (arg0, 0);
4196
4197       /* Convert - (a - b) to (b - a) for non-floating-point.  */
4198       else if (TREE_CODE (arg0) == MINUS_EXPR && ! FLOAT_TYPE_P (type))
4199         return build (MINUS_EXPR, type, TREE_OPERAND (arg0, 1),
4200                       TREE_OPERAND (arg0, 0));
4201
4202       return t;
4203
4204     case ABS_EXPR:
4205       if (wins)
4206         {
4207           if (TREE_CODE (arg0) == INTEGER_CST)
4208             {
4209               if (! TREE_UNSIGNED (type)
4210                   && TREE_INT_CST_HIGH (arg0) < 0)
4211                 {
4212                   HOST_WIDE_INT low, high;
4213                   int overflow = neg_double (TREE_INT_CST_LOW (arg0),
4214                                              TREE_INT_CST_HIGH (arg0),
4215                                              &low, &high);
4216                   t = build_int_2 (low, high);
4217                   TREE_TYPE (t) = type;
4218                   TREE_OVERFLOW (t)
4219                     = (TREE_OVERFLOW (arg0)
4220                        | force_fit_type (t, overflow));
4221                   TREE_CONSTANT_OVERFLOW (t)
4222                     = TREE_OVERFLOW (t) | TREE_CONSTANT_OVERFLOW (arg0);
4223                 }
4224             }
4225           else if (TREE_CODE (arg0) == REAL_CST)
4226             {
4227               if (REAL_VALUE_NEGATIVE (TREE_REAL_CST (arg0)))
4228                 t = build_real (type,
4229                                 REAL_VALUE_NEGATE (TREE_REAL_CST (arg0)));
4230             }
4231         }
4232       else if (TREE_CODE (arg0) == ABS_EXPR || TREE_CODE (arg0) == NEGATE_EXPR)
4233         return build1 (ABS_EXPR, type, TREE_OPERAND (arg0, 0));
4234       return t;
4235
4236     case CONJ_EXPR:
4237       if (TREE_CODE (TREE_TYPE (arg0)) != COMPLEX_TYPE)
4238         return arg0;
4239       else if (TREE_CODE (arg0) == COMPLEX_EXPR)
4240         return build (COMPLEX_EXPR, TREE_TYPE (arg0),
4241                       TREE_OPERAND (arg0, 0),
4242                       fold (build1 (NEGATE_EXPR,
4243                                     TREE_TYPE (TREE_TYPE (arg0)),
4244                                     TREE_OPERAND (arg0, 1))));
4245       else if (TREE_CODE (arg0) == COMPLEX_CST)
4246         return build_complex (type, TREE_OPERAND (arg0, 0),
4247                               fold (build1 (NEGATE_EXPR,
4248                                             TREE_TYPE (TREE_TYPE (arg0)),
4249                                             TREE_OPERAND (arg0, 1))));
4250       else if (TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MINUS_EXPR)
4251         return fold (build (TREE_CODE (arg0), type,
4252                             fold (build1 (CONJ_EXPR, type,
4253                                           TREE_OPERAND (arg0, 0))),
4254                             fold (build1 (CONJ_EXPR,
4255                                           type, TREE_OPERAND (arg0, 1)))));
4256       else if (TREE_CODE (arg0) == CONJ_EXPR)
4257         return TREE_OPERAND (arg0, 0);
4258       return t;
4259
4260     case BIT_NOT_EXPR:
4261       if (wins)
4262         {
4263           t = build_int_2 (~ TREE_INT_CST_LOW (arg0),
4264                            ~ TREE_INT_CST_HIGH (arg0));
4265           TREE_TYPE (t) = type;
4266           force_fit_type (t, 0);
4267           TREE_OVERFLOW (t) = TREE_OVERFLOW (arg0);
4268           TREE_CONSTANT_OVERFLOW (t) = TREE_CONSTANT_OVERFLOW (arg0);
4269         }
4270       else if (TREE_CODE (arg0) == BIT_NOT_EXPR)
4271         return TREE_OPERAND (arg0, 0);
4272       return t;
4273
4274     case PLUS_EXPR:
4275       /* A + (-B) -> A - B */
4276       if (TREE_CODE (arg1) == NEGATE_EXPR)
4277         return fold (build (MINUS_EXPR, type, arg0, TREE_OPERAND (arg1, 0)));
4278       else if (! FLOAT_TYPE_P (type))
4279         {
4280           if (integer_zerop (arg1))
4281             return non_lvalue (convert (type, arg0));
4282
4283           /* If we are adding two BIT_AND_EXPR's, both of which are and'ing
4284              with a constant, and the two constants have no bits in common,
4285              we should treat this as a BIT_IOR_EXPR since this may produce more
4286              simplifications.  */
4287           if (TREE_CODE (arg0) == BIT_AND_EXPR
4288               && TREE_CODE (arg1) == BIT_AND_EXPR
4289               && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
4290               && TREE_CODE (TREE_OPERAND (arg1, 1)) == INTEGER_CST
4291               && integer_zerop (const_binop (BIT_AND_EXPR,
4292                                              TREE_OPERAND (arg0, 1),
4293                                              TREE_OPERAND (arg1, 1), 0)))
4294             {
4295               code = BIT_IOR_EXPR;
4296               goto bit_ior;
4297             }
4298
4299           /* (A * C) + (B * C) -> (A+B) * C.  Since we are most concerned
4300              about the case where C is a constant, just try one of the
4301              four possibilities.  */
4302
4303           if (TREE_CODE (arg0) == MULT_EXPR && TREE_CODE (arg1) == MULT_EXPR
4304               && operand_equal_p (TREE_OPERAND (arg0, 1),
4305                                   TREE_OPERAND (arg1, 1), 0))
4306             return fold (build (MULT_EXPR, type,
4307                                 fold (build (PLUS_EXPR, type,
4308                                              TREE_OPERAND (arg0, 0),
4309                                              TREE_OPERAND (arg1, 0))),
4310                                 TREE_OPERAND (arg0, 1)));
4311         }
4312       /* In IEEE floating point, x+0 may not equal x.  */
4313       else if ((TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
4314                 || flag_fast_math)
4315                && real_zerop (arg1))
4316         return non_lvalue (convert (type, arg0));
4317     associate:
4318       /* In most languages, can't associate operations on floats
4319          through parentheses.  Rather than remember where the parentheses
4320          were, we don't associate floats at all.  It shouldn't matter much.
4321          However, associating multiplications is only very slightly
4322          inaccurate, so do that if -ffast-math is specified.  */
4323       if (FLOAT_TYPE_P (type)
4324           && ! (flag_fast_math && code == MULT_EXPR))
4325         goto binary;
4326
4327       /* The varsign == -1 cases happen only for addition and subtraction.
4328          It says that the arg that was split was really CON minus VAR.
4329          The rest of the code applies to all associative operations.  */
4330       if (!wins)
4331         {
4332           tree var, con;
4333           int varsign;
4334
4335           if (split_tree (arg0, code, &var, &con, &varsign))
4336             {
4337               if (varsign == -1)
4338                 {
4339                   /* EXPR is (CON-VAR) +- ARG1.  */
4340                   /* If it is + and VAR==ARG1, return just CONST.  */
4341                   if (code == PLUS_EXPR && operand_equal_p (var, arg1, 0))
4342                     return convert (TREE_TYPE (t), con);
4343
4344                   /* If ARG0 is a constant, don't change things around;
4345                      instead keep all the constant computations together.  */
4346
4347                   if (TREE_CONSTANT (arg0))
4348                     return t;
4349
4350                   /* Otherwise return (CON +- ARG1) - VAR.  */
4351                   t = build (MINUS_EXPR, type,
4352                              fold (build (code, type, con, arg1)), var);
4353                 }
4354               else
4355                 {
4356                   /* EXPR is (VAR+CON) +- ARG1.  */
4357                   /* If it is - and VAR==ARG1, return just CONST.  */
4358                   if (code == MINUS_EXPR && operand_equal_p (var, arg1, 0))
4359                     return convert (TREE_TYPE (t), con);
4360
4361                   /* If ARG0 is a constant, don't change things around;
4362                      instead keep all the constant computations together.  */
4363
4364                   if (TREE_CONSTANT (arg0))
4365                     return t;
4366
4367                   /* Otherwise return VAR +- (ARG1 +- CON).  */
4368                   tem = fold (build (code, type, arg1, con));
4369                   t = build (code, type, var, tem);
4370
4371                   if (integer_zerop (tem)
4372                       && (code == PLUS_EXPR || code == MINUS_EXPR))
4373                     return convert (type, var);
4374                   /* If we have x +/- (c - d) [c an explicit integer]
4375                      change it to x -/+ (d - c) since if d is relocatable
4376                      then the latter can be a single immediate insn
4377                      and the former cannot.  */
4378                   if (TREE_CODE (tem) == MINUS_EXPR
4379                       && TREE_CODE (TREE_OPERAND (tem, 0)) == INTEGER_CST)
4380                     {
4381                       tree tem1 = TREE_OPERAND (tem, 1);
4382                       TREE_OPERAND (tem, 1) = TREE_OPERAND (tem, 0);
4383                       TREE_OPERAND (tem, 0) = tem1;
4384                       TREE_SET_CODE (t,
4385                                      (code == PLUS_EXPR ? MINUS_EXPR : PLUS_EXPR));
4386                     }
4387                 }
4388               return t;
4389             }
4390
4391           if (split_tree (arg1, code, &var, &con, &varsign))
4392             {
4393               if (TREE_CONSTANT (arg1))
4394                 return t;
4395
4396               if (varsign == -1)
4397                 TREE_SET_CODE (t,
4398                                (code == PLUS_EXPR ? MINUS_EXPR : PLUS_EXPR));
4399
4400               /* EXPR is ARG0 +- (CON +- VAR).  */
4401               if (TREE_CODE (t) == MINUS_EXPR
4402                   && operand_equal_p (var, arg0, 0))
4403                 {
4404                   /* If VAR and ARG0 cancel, return just CON or -CON.  */
4405                   if (code == PLUS_EXPR)
4406                     return convert (TREE_TYPE (t), con);
4407                   return fold (build1 (NEGATE_EXPR, TREE_TYPE (t),
4408                                        convert (TREE_TYPE (t), con)));
4409                 }
4410
4411               t = build (TREE_CODE (t), type,
4412                          fold (build (code, TREE_TYPE (t), arg0, con)), var);
4413
4414               if (integer_zerop (TREE_OPERAND (t, 0))
4415                   && TREE_CODE (t) == PLUS_EXPR)
4416                 return convert (TREE_TYPE (t), var);
4417               return t;
4418             }
4419         }
4420     binary:
4421 #if defined (REAL_IS_NOT_DOUBLE) && ! defined (REAL_ARITHMETIC)
4422       if (TREE_CODE (arg1) == REAL_CST)
4423         return t;
4424 #endif /* REAL_IS_NOT_DOUBLE, and no REAL_ARITHMETIC */
4425       if (wins)
4426         t1 = const_binop (code, arg0, arg1, 0);
4427       if (t1 != NULL_TREE)
4428         {
4429           /* The return value should always have
4430              the same type as the original expression.  */
4431           if (TREE_TYPE (t1) != TREE_TYPE (t))
4432             t1 = convert (TREE_TYPE (t), t1);
4433
4434           return t1;
4435         }
4436       return t;
4437
4438     case MINUS_EXPR:
4439       if (! FLOAT_TYPE_P (type))
4440         {
4441           if (! wins && integer_zerop (arg0))
4442             return build1 (NEGATE_EXPR, type, arg1);
4443           if (integer_zerop (arg1))
4444             return non_lvalue (convert (type, arg0));
4445
4446           /* (A * C) - (B * C) -> (A-B) * C.  Since we are most concerned
4447              about the case where C is a constant, just try one of the
4448              four possibilities.  */
4449
4450           if (TREE_CODE (arg0) == MULT_EXPR && TREE_CODE (arg1) == MULT_EXPR
4451               && operand_equal_p (TREE_OPERAND (arg0, 1),
4452                                   TREE_OPERAND (arg1, 1), 0))
4453             return fold (build (MULT_EXPR, type,
4454                                 fold (build (MINUS_EXPR, type,
4455                                              TREE_OPERAND (arg0, 0),
4456                                              TREE_OPERAND (arg1, 0))),
4457                                 TREE_OPERAND (arg0, 1)));
4458         }
4459       /* Convert A - (-B) to A + B.  */
4460       else if (TREE_CODE (arg1) == NEGATE_EXPR)
4461         return fold (build (PLUS_EXPR, type, arg0, TREE_OPERAND (arg1, 0)));
4462
4463       else if (TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
4464                || flag_fast_math)
4465         {
4466           /* Except with IEEE floating point, 0-x equals -x.  */
4467           if (! wins && real_zerop (arg0))
4468             return build1 (NEGATE_EXPR, type, arg1);
4469           /* Except with IEEE floating point, x-0 equals x.  */
4470           if (real_zerop (arg1))
4471             return non_lvalue (convert (type, arg0));
4472         }
4473
4474       /* Fold &x - &x.  This can happen from &x.foo - &x.
4475          This is unsafe for certain floats even in non-IEEE formats.
4476          In IEEE, it is unsafe because it does wrong for NaNs.
4477          Also note that operand_equal_p is always false if an operand
4478          is volatile.  */
4479
4480       if ((! FLOAT_TYPE_P (type) || flag_fast_math)
4481           && operand_equal_p (arg0, arg1, 0))
4482         return convert (type, integer_zero_node);
4483
4484       goto associate;
4485
4486     case MULT_EXPR:
4487       if (! FLOAT_TYPE_P (type))
4488         {
4489           if (integer_zerop (arg1))
4490             return omit_one_operand (type, arg1, arg0);
4491           if (integer_onep (arg1))
4492             return non_lvalue (convert (type, arg0));
4493
4494           /* ((A / C) * C) is A if the division is an
4495              EXACT_DIV_EXPR.   Since C is normally a constant,
4496              just check for one of the four possibilities.  */
4497
4498           if (TREE_CODE (arg0) == EXACT_DIV_EXPR
4499               && operand_equal_p (TREE_OPERAND (arg0, 1), arg1, 0))
4500             return TREE_OPERAND (arg0, 0);
4501
4502           /* (a * (1 << b)) is (a << b)  */
4503           if (TREE_CODE (arg1) == LSHIFT_EXPR
4504               && integer_onep (TREE_OPERAND (arg1, 0)))
4505             return fold (build (LSHIFT_EXPR, type, arg0,
4506                                 TREE_OPERAND (arg1, 1)));
4507           if (TREE_CODE (arg0) == LSHIFT_EXPR
4508               && integer_onep (TREE_OPERAND (arg0, 0)))
4509             return fold (build (LSHIFT_EXPR, type, arg1,
4510                                 TREE_OPERAND (arg0, 1)));
4511         }
4512       else
4513         {
4514           /* x*0 is 0, except for IEEE floating point.  */
4515           if ((TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
4516                || flag_fast_math)
4517               && real_zerop (arg1))
4518             return omit_one_operand (type, arg1, arg0);
4519           /* In IEEE floating point, x*1 is not equivalent to x for snans.
4520              However, ANSI says we can drop signals,
4521              so we can do this anyway.  */
4522           if (real_onep (arg1))
4523             return non_lvalue (convert (type, arg0));
4524           /* x*2 is x+x */
4525           if (! wins && real_twop (arg1) && current_function_decl != 0)
4526             {
4527               tree arg = save_expr (arg0);
4528               return build (PLUS_EXPR, type, arg, arg);
4529             }
4530         }
4531       goto associate;
4532
4533     case BIT_IOR_EXPR:
4534     bit_ior:
4535       {
4536       register enum tree_code code0, code1;
4537
4538       if (integer_all_onesp (arg1))
4539         return omit_one_operand (type, arg1, arg0);
4540       if (integer_zerop (arg1))
4541         return non_lvalue (convert (type, arg0));
4542       t1 = distribute_bit_expr (code, type, arg0, arg1);
4543       if (t1 != NULL_TREE)
4544         return t1;
4545
4546       /* (A << C1) | (A >> C2) if A is unsigned and C1+C2 is the size of A
4547          is a rotate of A by C1 bits.  */
4548       /* (A << B) | (A >> (Z - B)) if A is unsigned and Z is the size of A
4549          is a rotate of A by B bits.  */
4550
4551       code0 = TREE_CODE (arg0);
4552       code1 = TREE_CODE (arg1);
4553       if (((code0 == RSHIFT_EXPR && code1 == LSHIFT_EXPR)
4554           || (code1 == RSHIFT_EXPR && code0 == LSHIFT_EXPR))
4555           && operand_equal_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg1,0), 0)
4556           && TREE_UNSIGNED (TREE_TYPE (TREE_OPERAND (arg0, 0))))
4557         {
4558           register tree tree01, tree11;
4559           register enum tree_code code01, code11;
4560
4561           tree01 = TREE_OPERAND (arg0, 1);
4562           tree11 = TREE_OPERAND (arg1, 1);
4563           code01 = TREE_CODE (tree01);
4564           code11 = TREE_CODE (tree11);
4565           if (code01 == INTEGER_CST
4566             && code11 == INTEGER_CST
4567             && TREE_INT_CST_HIGH (tree01) == 0
4568             && TREE_INT_CST_HIGH (tree11) == 0
4569             && ((TREE_INT_CST_LOW (tree01) + TREE_INT_CST_LOW (tree11))
4570               == TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (arg0, 0)))))
4571             return build (LROTATE_EXPR, type, TREE_OPERAND (arg0, 0),
4572                       code0 == LSHIFT_EXPR ? tree01 : tree11);
4573           else if (code11 == MINUS_EXPR
4574                 && TREE_CODE (TREE_OPERAND (tree11, 0)) == INTEGER_CST
4575                 && TREE_INT_CST_HIGH (TREE_OPERAND (tree11, 0)) == 0
4576                 && TREE_INT_CST_LOW (TREE_OPERAND (tree11, 0))
4577                   == TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (arg0, 0)))
4578                 && operand_equal_p (tree01, TREE_OPERAND (tree11, 1), 0))
4579             return build (code0 == LSHIFT_EXPR ? LROTATE_EXPR : RROTATE_EXPR,
4580                         type, TREE_OPERAND (arg0, 0), tree01);
4581           else if (code01 == MINUS_EXPR
4582                 && TREE_CODE (TREE_OPERAND (tree01, 0)) == INTEGER_CST
4583                 && TREE_INT_CST_HIGH (TREE_OPERAND (tree01, 0)) == 0
4584                 && TREE_INT_CST_LOW (TREE_OPERAND (tree01, 0))
4585                   == TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (arg0, 0)))
4586                 && operand_equal_p (tree11, TREE_OPERAND (tree01, 1), 0))
4587             return build (code0 != LSHIFT_EXPR ? LROTATE_EXPR : RROTATE_EXPR,
4588                         type, TREE_OPERAND (arg0, 0), tree11);
4589         }
4590
4591       goto associate;
4592       }
4593
4594     case BIT_XOR_EXPR:
4595       if (integer_zerop (arg1))
4596         return non_lvalue (convert (type, arg0));
4597       if (integer_all_onesp (arg1))
4598         return fold (build1 (BIT_NOT_EXPR, type, arg0));
4599       goto associate;
4600
4601     case BIT_AND_EXPR:
4602     bit_and:
4603       if (integer_all_onesp (arg1))
4604         return non_lvalue (convert (type, arg0));
4605       if (integer_zerop (arg1))
4606         return omit_one_operand (type, arg1, arg0);
4607       t1 = distribute_bit_expr (code, type, arg0, arg1);
4608       if (t1 != NULL_TREE)
4609         return t1;
4610       /* Simplify ((int)c & 0x377) into (int)c, if c is unsigned char.  */
4611       if (TREE_CODE (arg0) == INTEGER_CST && TREE_CODE (arg1) == NOP_EXPR
4612           && TREE_UNSIGNED (TREE_TYPE (TREE_OPERAND (arg1, 0))))
4613         {
4614           int prec = TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (arg1, 0)));
4615           if (prec < BITS_PER_WORD && prec < HOST_BITS_PER_WIDE_INT
4616               && (~TREE_INT_CST_LOW (arg0)
4617                   & (((HOST_WIDE_INT) 1 << prec) - 1)) == 0)
4618             return build1 (NOP_EXPR, type, TREE_OPERAND (arg1, 0));
4619         }
4620       if (TREE_CODE (arg1) == INTEGER_CST && TREE_CODE (arg0) == NOP_EXPR
4621           && TREE_UNSIGNED (TREE_TYPE (TREE_OPERAND (arg0, 0))))
4622         {
4623           int prec = TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (arg0, 0)));
4624           if (prec < BITS_PER_WORD && prec < HOST_BITS_PER_WIDE_INT
4625               && (~TREE_INT_CST_LOW (arg1)
4626                   & (((HOST_WIDE_INT) 1 << prec) - 1)) == 0)
4627             return build1 (NOP_EXPR, type, TREE_OPERAND (arg0, 0));
4628         }
4629       goto associate;
4630
4631     case BIT_ANDTC_EXPR:
4632       if (integer_all_onesp (arg0))
4633         return non_lvalue (convert (type, arg1));
4634       if (integer_zerop (arg0))
4635         return omit_one_operand (type, arg0, arg1);
4636       if (TREE_CODE (arg1) == INTEGER_CST)
4637         {
4638           arg1 = fold (build1 (BIT_NOT_EXPR, type, arg1));
4639           code = BIT_AND_EXPR;
4640           goto bit_and;
4641         }
4642       goto binary;
4643
4644     case RDIV_EXPR:
4645       /* In most cases, do nothing with a divide by zero.  */
4646 #if !defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
4647 #ifndef REAL_INFINITY
4648       if (TREE_CODE (arg1) == REAL_CST && real_zerop (arg1))
4649         return t;
4650 #endif
4651 #endif /* not REAL_IS_NOT_DOUBLE, or REAL_ARITHMETIC */
4652
4653       /* In IEEE floating point, x/1 is not equivalent to x for snans.
4654          However, ANSI says we can drop signals, so we can do this anyway.  */
4655       if (real_onep (arg1))
4656         return non_lvalue (convert (type, arg0));
4657
4658       /* If ARG1 is a constant, we can convert this to a multiply by the
4659          reciprocal.  This does not have the same rounding properties,
4660          so only do this if -ffast-math.  We can actually always safely
4661          do it if ARG1 is a power of two, but it's hard to tell if it is
4662          or not in a portable manner.  */
4663       if (TREE_CODE (arg1) == REAL_CST)
4664         {
4665           if (flag_fast_math
4666               && 0 != (tem = const_binop (code, build_real (type, dconst1),
4667                                           arg1, 0)))
4668             return fold (build (MULT_EXPR, type, arg0, tem));
4669           /* Find the reciprocal if optimizing and the result is exact. */
4670           else if (optimize)
4671             {
4672               REAL_VALUE_TYPE r;
4673               r = TREE_REAL_CST (arg1);
4674               if (exact_real_inverse (TYPE_MODE(TREE_TYPE(arg0)), &r))
4675                   {
4676                     tem = build_real (type, r);
4677                     return fold (build (MULT_EXPR, type, arg0, tem));
4678                   }
4679             }
4680         }
4681       goto binary;
4682
4683     case TRUNC_DIV_EXPR:
4684     case ROUND_DIV_EXPR:
4685     case FLOOR_DIV_EXPR:
4686     case CEIL_DIV_EXPR:
4687     case EXACT_DIV_EXPR:
4688       if (integer_onep (arg1))
4689         return non_lvalue (convert (type, arg0));
4690       if (integer_zerop (arg1))
4691         return t;
4692
4693       /* If arg0 is a multiple of arg1, then rewrite to the fastest div
4694          operation, EXACT_DIV_EXPR.
4695
4696          Note that only CEIL_DIV_EXPR and FLOOR_DIV_EXPR are rewritten now.
4697          At one time others generated faster code, it's not clear if they do
4698          after the last round to changes to the DIV code in expmed.c.  */
4699       if ((code == CEIL_DIV_EXPR || code == FLOOR_DIV_EXPR)
4700           && multiple_of_p (type, arg0, arg1))
4701         return fold (build (EXACT_DIV_EXPR, type, arg0, arg1));
4702
4703       /* If we have ((a / C1) / C2) where both division are the same type, try
4704          to simplify.  First see if C1 * C2 overflows or not.  */
4705       if (TREE_CODE (arg0) == code && TREE_CODE (arg1) == INTEGER_CST
4706           && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST)
4707         {
4708           tree new_divisor;
4709
4710           new_divisor = const_binop (MULT_EXPR, TREE_OPERAND (arg0, 1), arg1, 0);
4711           tem = const_binop (FLOOR_DIV_EXPR, new_divisor, arg1, 0);
4712
4713           if (TREE_INT_CST_LOW (TREE_OPERAND (arg0, 1)) == TREE_INT_CST_LOW (tem)
4714               && TREE_INT_CST_HIGH (TREE_OPERAND (arg0, 1)) == TREE_INT_CST_HIGH (tem))
4715             {
4716               /* If no overflow, divide by C1*C2.  */
4717               return fold (build (code, type, TREE_OPERAND (arg0, 0), new_divisor));
4718             }
4719         }
4720
4721       /* Look for ((a * C1) / C3) or (((a * C1) + C2) / C3),
4722          where C1 % C3 == 0 or C3 % C1 == 0.  We can simplify these
4723          expressions, which often appear in the offsets or sizes of
4724          objects with a varying size.  Only deal with positive divisors
4725          and multiplicands.   If C2 is negative, we must have C2 % C3 == 0.
4726
4727          Look for NOPs and SAVE_EXPRs inside.  */
4728
4729       if (TREE_CODE (arg1) == INTEGER_CST
4730           && tree_int_cst_sgn (arg1) >= 0)
4731         {
4732           int have_save_expr = 0;
4733           tree c2 = integer_zero_node;
4734           tree xarg0 = arg0;
4735
4736           if (TREE_CODE (xarg0) == SAVE_EXPR && SAVE_EXPR_RTL (xarg0) == 0)
4737             have_save_expr = 1, xarg0 = TREE_OPERAND (xarg0, 0);
4738
4739           STRIP_NOPS (xarg0);
4740
4741           /* Look inside the dividend and simplify using EXACT_DIV_EXPR
4742              if possible.  */
4743           if (TREE_CODE (xarg0) == MULT_EXPR
4744               && multiple_of_p (type, TREE_OPERAND (xarg0, 0), arg1))
4745             {
4746               tree t;
4747
4748               t = fold (build (MULT_EXPR, type,
4749                                fold (build (EXACT_DIV_EXPR, type,
4750                                             TREE_OPERAND (xarg0, 0), arg1)),
4751                                TREE_OPERAND (xarg0, 1)));
4752               if (have_save_expr)
4753                 t = save_expr (t);
4754               return t;
4755
4756             }
4757
4758           if (TREE_CODE (xarg0) == MULT_EXPR
4759               && multiple_of_p (type, TREE_OPERAND (xarg0, 1), arg1))
4760             {
4761               tree t;
4762
4763               t = fold (build (MULT_EXPR, type,
4764                                fold (build (EXACT_DIV_EXPR, type,
4765                                             TREE_OPERAND (xarg0, 1), arg1)),
4766                                TREE_OPERAND (xarg0, 0)));
4767               if (have_save_expr)
4768                 t = save_expr (t);
4769               return t;
4770             }
4771
4772           if (TREE_CODE (xarg0) == PLUS_EXPR
4773               && TREE_CODE (TREE_OPERAND (xarg0, 1)) == INTEGER_CST)
4774             c2 = TREE_OPERAND (xarg0, 1), xarg0 = TREE_OPERAND (xarg0, 0);
4775           else if (TREE_CODE (xarg0) == MINUS_EXPR
4776                    && TREE_CODE (TREE_OPERAND (xarg0, 1)) == INTEGER_CST
4777                    /* If we are doing this computation unsigned, the negate
4778                       is incorrect.  */
4779                    && ! TREE_UNSIGNED (type))
4780             {
4781               c2 = fold (build1 (NEGATE_EXPR, type, TREE_OPERAND (xarg0, 1)));
4782               xarg0 = TREE_OPERAND (xarg0, 0);
4783             }
4784
4785           if (TREE_CODE (xarg0) == SAVE_EXPR && SAVE_EXPR_RTL (xarg0) == 0)
4786             have_save_expr = 1, xarg0 = TREE_OPERAND (xarg0, 0);
4787
4788           STRIP_NOPS (xarg0);
4789
4790           if (TREE_CODE (xarg0) == MULT_EXPR
4791               && TREE_CODE (TREE_OPERAND (xarg0, 1)) == INTEGER_CST
4792               && tree_int_cst_sgn (TREE_OPERAND (xarg0, 1)) >= 0
4793               && (integer_zerop (const_binop (TRUNC_MOD_EXPR,
4794                                               TREE_OPERAND (xarg0, 1), arg1, 1))
4795                   || integer_zerop (const_binop (TRUNC_MOD_EXPR, arg1,
4796                                                  TREE_OPERAND (xarg0, 1), 1)))
4797               && (tree_int_cst_sgn (c2) >= 0
4798                   || integer_zerop (const_binop (TRUNC_MOD_EXPR, c2,
4799                                                  arg1, 1))))
4800             {
4801               tree outer_div = integer_one_node;
4802               tree c1 = TREE_OPERAND (xarg0, 1);
4803               tree c3 = arg1;
4804
4805               /* If C3 > C1, set them equal and do a divide by
4806                  C3/C1 at the end of the operation.  */
4807               if (tree_int_cst_lt (c1, c3))
4808                 outer_div = const_binop (code, c3, c1, 0), c3 = c1;
4809
4810               /* The result is A * (C1/C3) + (C2/C3).  */
4811               t = fold (build (PLUS_EXPR, type,
4812                                fold (build (MULT_EXPR, type,
4813                                             TREE_OPERAND (xarg0, 0),
4814                                             const_binop (code, c1, c3, 1))),
4815                                const_binop (code, c2, c3, 1)));
4816
4817               if (! integer_onep (outer_div))
4818                 t = fold (build (code, type, t, convert (type, outer_div)));
4819
4820               if (have_save_expr)
4821                 t = save_expr (t);
4822
4823               return t;
4824             }
4825         }
4826
4827       goto binary;
4828
4829     case CEIL_MOD_EXPR:
4830     case FLOOR_MOD_EXPR:
4831     case ROUND_MOD_EXPR:
4832     case TRUNC_MOD_EXPR:
4833       if (integer_onep (arg1))
4834         return omit_one_operand (type, integer_zero_node, arg0);
4835       if (integer_zerop (arg1))
4836         return t;
4837
4838       /* Look for ((a * C1) % C3) or (((a * C1) + C2) % C3),
4839          where C1 % C3 == 0.  Handle similarly to the division case,
4840          but don't bother with SAVE_EXPRs.  */
4841
4842       if (TREE_CODE (arg1) == INTEGER_CST
4843           && ! integer_zerop (arg1))
4844         {
4845           tree c2 = integer_zero_node;
4846           tree xarg0 = arg0;
4847
4848           if (TREE_CODE (xarg0) == PLUS_EXPR
4849               && TREE_CODE (TREE_OPERAND (xarg0, 1)) == INTEGER_CST)
4850             c2 = TREE_OPERAND (xarg0, 1), xarg0 = TREE_OPERAND (xarg0, 0);
4851           else if (TREE_CODE (xarg0) == MINUS_EXPR
4852                    && TREE_CODE (TREE_OPERAND (xarg0, 1)) == INTEGER_CST
4853                    && ! TREE_UNSIGNED (type))
4854             {
4855               c2 = fold (build1 (NEGATE_EXPR, type, TREE_OPERAND (xarg0, 1)));
4856               xarg0 = TREE_OPERAND (xarg0, 0);
4857             }
4858
4859           STRIP_NOPS (xarg0);
4860
4861           if (TREE_CODE (xarg0) == MULT_EXPR
4862               && TREE_CODE (TREE_OPERAND (xarg0, 1)) == INTEGER_CST
4863               && integer_zerop (const_binop (TRUNC_MOD_EXPR,
4864                                              TREE_OPERAND (xarg0, 1),
4865                                              arg1, 1))
4866               && tree_int_cst_sgn (c2) >= 0)
4867             /* The result is (C2%C3).  */
4868             return omit_one_operand (type, const_binop (code, c2, arg1, 1),
4869                                      TREE_OPERAND (xarg0, 0));
4870         }
4871
4872       goto binary;
4873
4874     case LSHIFT_EXPR:
4875     case RSHIFT_EXPR:
4876     case LROTATE_EXPR:
4877     case RROTATE_EXPR:
4878       if (integer_zerop (arg1))
4879         return non_lvalue (convert (type, arg0));
4880       /* Since negative shift count is not well-defined,
4881          don't try to compute it in the compiler.  */
4882       if (TREE_CODE (arg1) == INTEGER_CST && tree_int_cst_sgn (arg1) < 0)
4883         return t;
4884       /* Rewrite an LROTATE_EXPR by a constant into an
4885          RROTATE_EXPR by a new constant.  */
4886       if (code == LROTATE_EXPR && TREE_CODE (arg1) == INTEGER_CST)
4887         {
4888           TREE_SET_CODE (t, RROTATE_EXPR);
4889           code = RROTATE_EXPR;
4890           TREE_OPERAND (t, 1) = arg1
4891             = const_binop
4892               (MINUS_EXPR,
4893                convert (TREE_TYPE (arg1),
4894                         build_int_2 (GET_MODE_BITSIZE (TYPE_MODE (type)), 0)),
4895                arg1, 0);
4896           if (tree_int_cst_sgn (arg1) < 0)
4897             return t;
4898         }
4899
4900       /* If we have a rotate of a bit operation with the rotate count and
4901          the second operand of the bit operation both constant,
4902          permute the two operations.  */
4903       if (code == RROTATE_EXPR && TREE_CODE (arg1) == INTEGER_CST
4904           && (TREE_CODE (arg0) == BIT_AND_EXPR
4905               || TREE_CODE (arg0) == BIT_ANDTC_EXPR
4906               || TREE_CODE (arg0) == BIT_IOR_EXPR
4907               || TREE_CODE (arg0) == BIT_XOR_EXPR)
4908           && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST)
4909         return fold (build (TREE_CODE (arg0), type,
4910                             fold (build (code, type,
4911                                          TREE_OPERAND (arg0, 0), arg1)),
4912                             fold (build (code, type,
4913                                          TREE_OPERAND (arg0, 1), arg1))));
4914
4915       /* Two consecutive rotates adding up to the width of the mode can
4916          be ignored.  */
4917       if (code == RROTATE_EXPR && TREE_CODE (arg1) == INTEGER_CST
4918           && TREE_CODE (arg0) == RROTATE_EXPR
4919           && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
4920           && TREE_INT_CST_HIGH (arg1) == 0
4921           && TREE_INT_CST_HIGH (TREE_OPERAND (arg0, 1)) == 0
4922           && ((TREE_INT_CST_LOW (arg1)
4923                + TREE_INT_CST_LOW (TREE_OPERAND (arg0, 1)))
4924               == GET_MODE_BITSIZE (TYPE_MODE (type))))
4925         return TREE_OPERAND (arg0, 0);
4926
4927       goto binary;
4928
4929     case MIN_EXPR:
4930       if (operand_equal_p (arg0, arg1, 0))
4931         return arg0;
4932       if (INTEGRAL_TYPE_P (type)
4933           && operand_equal_p (arg1, TYPE_MIN_VALUE (type), 1))
4934         return omit_one_operand (type, arg1, arg0);
4935       goto associate;
4936
4937     case MAX_EXPR:
4938       if (operand_equal_p (arg0, arg1, 0))
4939         return arg0;
4940       if (INTEGRAL_TYPE_P (type)
4941           && TYPE_MAX_VALUE (type)
4942           && operand_equal_p (arg1, TYPE_MAX_VALUE (type), 1))
4943         return omit_one_operand (type, arg1, arg0);
4944       goto associate;
4945
4946     case TRUTH_NOT_EXPR:
4947       /* Note that the operand of this must be an int
4948          and its values must be 0 or 1.
4949          ("true" is a fixed value perhaps depending on the language,
4950          but we don't handle values other than 1 correctly yet.)  */
4951       tem = invert_truthvalue (arg0);
4952       /* Avoid infinite recursion.  */
4953       if (TREE_CODE (tem) == TRUTH_NOT_EXPR)
4954         return t;
4955       return convert (type, tem);
4956
4957     case TRUTH_ANDIF_EXPR:
4958       /* Note that the operands of this must be ints
4959          and their values must be 0 or 1.
4960          ("true" is a fixed value perhaps depending on the language.)  */
4961       /* If first arg is constant zero, return it.  */
4962       if (integer_zerop (arg0))
4963         return arg0;
4964     case TRUTH_AND_EXPR:
4965       /* If either arg is constant true, drop it.  */
4966       if (TREE_CODE (arg0) == INTEGER_CST && ! integer_zerop (arg0))
4967         return non_lvalue (arg1);
4968       if (TREE_CODE (arg1) == INTEGER_CST && ! integer_zerop (arg1))
4969         return non_lvalue (arg0);
4970       /* If second arg is constant zero, result is zero, but first arg
4971          must be evaluated.  */
4972       if (integer_zerop (arg1))
4973         return omit_one_operand (type, arg1, arg0);
4974       /* Likewise for first arg, but note that only the TRUTH_AND_EXPR
4975          case will be handled here.  */
4976       if (integer_zerop (arg0))
4977         return omit_one_operand (type, arg0, arg1);
4978
4979     truth_andor:
4980       /* We only do these simplifications if we are optimizing.  */
4981       if (!optimize)
4982         return t;
4983
4984       /* Check for things like (A || B) && (A || C).  We can convert this
4985          to A || (B && C).  Note that either operator can be any of the four
4986          truth and/or operations and the transformation will still be
4987          valid.   Also note that we only care about order for the
4988          ANDIF and ORIF operators.  If B contains side effects, this
4989          might change the truth-value of A. */
4990       if (TREE_CODE (arg0) == TREE_CODE (arg1)
4991           && (TREE_CODE (arg0) == TRUTH_ANDIF_EXPR
4992               || TREE_CODE (arg0) == TRUTH_ORIF_EXPR
4993               || TREE_CODE (arg0) == TRUTH_AND_EXPR
4994               || TREE_CODE (arg0) == TRUTH_OR_EXPR)
4995           && ! TREE_SIDE_EFFECTS (TREE_OPERAND (arg0, 1)))
4996         {
4997           tree a00 = TREE_OPERAND (arg0, 0);
4998           tree a01 = TREE_OPERAND (arg0, 1);
4999           tree a10 = TREE_OPERAND (arg1, 0);
5000           tree a11 = TREE_OPERAND (arg1, 1);
5001           int commutative = ((TREE_CODE (arg0) == TRUTH_OR_EXPR
5002                               || TREE_CODE (arg0) == TRUTH_AND_EXPR)
5003                              && (code == TRUTH_AND_EXPR
5004                                  || code == TRUTH_OR_EXPR));
5005
5006           if (operand_equal_p (a00, a10, 0))
5007             return fold (build (TREE_CODE (arg0), type, a00,
5008                                 fold (build (code, type, a01, a11))));
5009           else if (commutative && operand_equal_p (a00, a11, 0))
5010             return fold (build (TREE_CODE (arg0), type, a00,
5011                                 fold (build (code, type, a01, a10))));
5012           else if (commutative && operand_equal_p (a01, a10, 0))
5013             return fold (build (TREE_CODE (arg0), type, a01,
5014                                 fold (build (code, type, a00, a11))));
5015
5016           /* This case if tricky because we must either have commutative
5017              operators or else A10 must not have side-effects.  */
5018
5019           else if ((commutative || ! TREE_SIDE_EFFECTS (a10))
5020                    && operand_equal_p (a01, a11, 0))
5021             return fold (build (TREE_CODE (arg0), type,
5022                                 fold (build (code, type, a00, a10)),
5023                                 a01));
5024         }
5025
5026       /* See if we can build a range comparison.  */
5027       if (0 != (tem = fold_range_test (t)))
5028         return tem;
5029
5030       /* Check for the possibility of merging component references.  If our
5031          lhs is another similar operation, try to merge its rhs with our
5032          rhs.  Then try to merge our lhs and rhs.  */
5033       if (TREE_CODE (arg0) == code
5034           && 0 != (tem = fold_truthop (code, type,
5035                                        TREE_OPERAND (arg0, 1), arg1)))
5036         return fold (build (code, type, TREE_OPERAND (arg0, 0), tem));
5037
5038       if ((tem = fold_truthop (code, type, arg0, arg1)) != 0)
5039         return tem;
5040
5041       return t;
5042
5043     case TRUTH_ORIF_EXPR:
5044       /* Note that the operands of this must be ints
5045          and their values must be 0 or true.
5046          ("true" is a fixed value perhaps depending on the language.)  */
5047       /* If first arg is constant true, return it.  */
5048       if (TREE_CODE (arg0) == INTEGER_CST && ! integer_zerop (arg0))
5049         return arg0;
5050     case TRUTH_OR_EXPR:
5051       /* If either arg is constant zero, drop it.  */
5052       if (TREE_CODE (arg0) == INTEGER_CST && integer_zerop (arg0))
5053         return non_lvalue (arg1);
5054       if (TREE_CODE (arg1) == INTEGER_CST && integer_zerop (arg1))
5055         return non_lvalue (arg0);
5056       /* If second arg is constant true, result is true, but we must
5057          evaluate first arg.  */
5058       if (TREE_CODE (arg1) == INTEGER_CST && ! integer_zerop (arg1))
5059         return omit_one_operand (type, arg1, arg0);
5060       /* Likewise for first arg, but note this only occurs here for
5061          TRUTH_OR_EXPR.  */
5062       if (TREE_CODE (arg0) == INTEGER_CST && ! integer_zerop (arg0))
5063         return omit_one_operand (type, arg0, arg1);
5064       goto truth_andor;
5065
5066     case TRUTH_XOR_EXPR:
5067       /* If either arg is constant zero, drop it.  */
5068       if (integer_zerop (arg0))
5069         return non_lvalue (arg1);
5070       if (integer_zerop (arg1))
5071         return non_lvalue (arg0);
5072       /* If either arg is constant true, this is a logical inversion.  */
5073       if (integer_onep (arg0))
5074         return non_lvalue (invert_truthvalue (arg1));
5075       if (integer_onep (arg1))
5076         return non_lvalue (invert_truthvalue (arg0));
5077       return t;
5078
5079     case EQ_EXPR:
5080     case NE_EXPR:
5081     case LT_EXPR:
5082     case GT_EXPR:
5083     case LE_EXPR:
5084     case GE_EXPR:
5085       /* If one arg is a constant integer, put it last.  */
5086       if (TREE_CODE (arg0) == INTEGER_CST
5087           && TREE_CODE (arg1) != INTEGER_CST)
5088         {
5089           TREE_OPERAND (t, 0) = arg1;
5090           TREE_OPERAND (t, 1) = arg0;
5091           arg0 = TREE_OPERAND (t, 0);
5092           arg1 = TREE_OPERAND (t, 1);
5093           code = swap_tree_comparison (code);
5094           TREE_SET_CODE (t, code);
5095         }
5096
5097       /* Convert foo++ == CONST into ++foo == CONST + INCR.
5098          First, see if one arg is constant; find the constant arg
5099          and the other one.  */
5100       {
5101         tree constop = 0, varop;
5102         int constopnum = -1;
5103
5104         if (TREE_CONSTANT (arg1))
5105           constopnum = 1, constop = arg1, varop = arg0;
5106         if (TREE_CONSTANT (arg0))
5107           constopnum = 0, constop = arg0, varop = arg1;
5108
5109         if (constop && TREE_CODE (varop) == POSTINCREMENT_EXPR)
5110           {
5111             /* This optimization is invalid for ordered comparisons
5112                if CONST+INCR overflows or if foo+incr might overflow.
5113                This optimization is invalid for floating point due to rounding.
5114                For pointer types we assume overflow doesn't happen.  */
5115             if (TREE_CODE (TREE_TYPE (varop)) == POINTER_TYPE
5116                 || (! FLOAT_TYPE_P (TREE_TYPE (varop))
5117                     && (code == EQ_EXPR || code == NE_EXPR)))
5118               {
5119                 tree newconst
5120                   = fold (build (PLUS_EXPR, TREE_TYPE (varop),
5121                                  constop, TREE_OPERAND (varop, 1)));
5122                 TREE_SET_CODE (varop, PREINCREMENT_EXPR);
5123
5124                 /* If VAROP is a reference to a bitfield, we must mask
5125                    the constant by the width of the field.  */
5126                 if (TREE_CODE (TREE_OPERAND (varop, 0)) == COMPONENT_REF
5127                     && DECL_BIT_FIELD(TREE_OPERAND
5128                                       (TREE_OPERAND (varop, 0), 1)))
5129                   {
5130                     int size
5131                       = TREE_INT_CST_LOW (DECL_SIZE
5132                                           (TREE_OPERAND
5133                                            (TREE_OPERAND (varop, 0), 1)));
5134
5135                     newconst = fold (build (BIT_AND_EXPR,
5136                                             TREE_TYPE (varop), newconst,
5137                                             convert (TREE_TYPE (varop),
5138                                                      build_int_2 (size, 0))));
5139                   }
5140
5141
5142                 t = build (code, type, TREE_OPERAND (t, 0),
5143                            TREE_OPERAND (t, 1));
5144                 TREE_OPERAND (t, constopnum) = newconst;
5145                 return t;
5146               }
5147           }
5148         else if (constop && TREE_CODE (varop) == POSTDECREMENT_EXPR)
5149           {
5150             if (TREE_CODE (TREE_TYPE (varop)) == POINTER_TYPE
5151                 || (! FLOAT_TYPE_P (TREE_TYPE (varop))
5152                     && (code == EQ_EXPR || code == NE_EXPR)))
5153               {
5154                 tree newconst
5155                   = fold (build (MINUS_EXPR, TREE_TYPE (varop),
5156                                  constop, TREE_OPERAND (varop, 1)));
5157                 TREE_SET_CODE (varop, PREDECREMENT_EXPR);
5158
5159                 if (TREE_CODE (TREE_OPERAND (varop, 0)) == COMPONENT_REF
5160                     && DECL_BIT_FIELD(TREE_OPERAND
5161                                       (TREE_OPERAND (varop, 0), 1)))
5162                   {
5163                     int size
5164                       = TREE_INT_CST_LOW (DECL_SIZE
5165                                           (TREE_OPERAND
5166                                            (TREE_OPERAND (varop, 0), 1)));
5167
5168                     newconst = fold (build (BIT_AND_EXPR,
5169                                             TREE_TYPE (varop), newconst,
5170                                             convert (TREE_TYPE (varop),
5171                                                      build_int_2 (size, 0))));
5172                   }
5173
5174
5175                 t = build (code, type, TREE_OPERAND (t, 0),
5176                            TREE_OPERAND (t, 1));
5177                 TREE_OPERAND (t, constopnum) = newconst;
5178                 return t;
5179               }
5180           }
5181       }
5182
5183       /* Change X >= CST to X > (CST - 1) if CST is positive.  */
5184       if (TREE_CODE (arg1) == INTEGER_CST
5185           && TREE_CODE (arg0) != INTEGER_CST
5186           && tree_int_cst_sgn (arg1) > 0)
5187         {
5188           switch (TREE_CODE (t))
5189             {
5190             case GE_EXPR:
5191               code = GT_EXPR;
5192               arg1 = const_binop (MINUS_EXPR, arg1, integer_one_node, 0);
5193               t = build (code, type, TREE_OPERAND (t, 0), arg1);
5194               break;
5195
5196             case LT_EXPR:
5197               code = LE_EXPR;
5198               arg1 = const_binop (MINUS_EXPR, arg1, integer_one_node, 0);
5199               t = build (code, type, TREE_OPERAND (t, 0), arg1);
5200               break;
5201
5202             default:
5203               break;
5204             }
5205         }
5206
5207       /* If this is an EQ or NE comparison with zero and ARG0 is
5208          (1 << foo) & bar, convert it to (bar >> foo) & 1.  Both require
5209          two operations, but the latter can be done in one less insn
5210          on machines that have only two-operand insns or on which a
5211          constant cannot be the first operand.  */
5212       if (integer_zerop (arg1) && (code == EQ_EXPR || code == NE_EXPR)
5213           && TREE_CODE (arg0) == BIT_AND_EXPR)
5214         {
5215           if (TREE_CODE (TREE_OPERAND (arg0, 0)) == LSHIFT_EXPR
5216               && integer_onep (TREE_OPERAND (TREE_OPERAND (arg0, 0), 0)))
5217             return
5218               fold (build (code, type,
5219                            build (BIT_AND_EXPR, TREE_TYPE (arg0),
5220                                   build (RSHIFT_EXPR,
5221                                          TREE_TYPE (TREE_OPERAND (arg0, 0)),
5222                                          TREE_OPERAND (arg0, 1),
5223                                          TREE_OPERAND (TREE_OPERAND (arg0, 0), 1)),
5224                                   convert (TREE_TYPE (arg0),
5225                                            integer_one_node)),
5226                            arg1));
5227           else if (TREE_CODE (TREE_OPERAND (arg0, 1)) == LSHIFT_EXPR
5228                    && integer_onep (TREE_OPERAND (TREE_OPERAND (arg0, 1), 0)))
5229             return
5230               fold (build (code, type,
5231                            build (BIT_AND_EXPR, TREE_TYPE (arg0),
5232                                   build (RSHIFT_EXPR,
5233                                          TREE_TYPE (TREE_OPERAND (arg0, 1)),
5234                                          TREE_OPERAND (arg0, 0),
5235                                          TREE_OPERAND (TREE_OPERAND (arg0, 1), 1)),
5236                                   convert (TREE_TYPE (arg0),
5237                                            integer_one_node)),
5238                            arg1));
5239         }
5240
5241       /* If this is an NE or EQ comparison of zero against the result of a
5242          signed MOD operation whose second operand is a power of 2, make
5243          the MOD operation unsigned since it is simpler and equivalent.  */
5244       if ((code == NE_EXPR || code == EQ_EXPR)
5245           && integer_zerop (arg1)
5246           && ! TREE_UNSIGNED (TREE_TYPE (arg0))
5247           && (TREE_CODE (arg0) == TRUNC_MOD_EXPR
5248               || TREE_CODE (arg0) == CEIL_MOD_EXPR
5249               || TREE_CODE (arg0) == FLOOR_MOD_EXPR
5250               || TREE_CODE (arg0) == ROUND_MOD_EXPR)
5251           && integer_pow2p (TREE_OPERAND (arg0, 1)))
5252         {
5253           tree newtype = unsigned_type (TREE_TYPE (arg0));
5254           tree newmod = build (TREE_CODE (arg0), newtype,
5255                                convert (newtype, TREE_OPERAND (arg0, 0)),
5256                                convert (newtype, TREE_OPERAND (arg0, 1)));
5257
5258           return build (code, type, newmod, convert (newtype, arg1));
5259         }
5260
5261       /* If this is an NE comparison of zero with an AND of one, remove the
5262          comparison since the AND will give the correct value.  */
5263       if (code == NE_EXPR && integer_zerop (arg1)
5264           && TREE_CODE (arg0) == BIT_AND_EXPR
5265           && integer_onep (TREE_OPERAND (arg0, 1)))
5266         return convert (type, arg0);
5267
5268       /* If we have (A & C) == C where C is a power of 2, convert this into
5269          (A & C) != 0.  Similarly for NE_EXPR.  */
5270       if ((code == EQ_EXPR || code == NE_EXPR)
5271           && TREE_CODE (arg0) == BIT_AND_EXPR
5272           && integer_pow2p (TREE_OPERAND (arg0, 1))
5273           && operand_equal_p (TREE_OPERAND (arg0, 1), arg1, 0))
5274         return build (code == EQ_EXPR ? NE_EXPR : EQ_EXPR, type,
5275                       arg0, integer_zero_node);
5276
5277       /* If X is unsigned, convert X < (1 << Y) into X >> Y == 0
5278          and similarly for >= into !=.  */
5279       if ((code == LT_EXPR || code == GE_EXPR)
5280           && TREE_UNSIGNED (TREE_TYPE (arg0))
5281           && TREE_CODE (arg1) == LSHIFT_EXPR
5282           && integer_onep (TREE_OPERAND (arg1, 0)))
5283         return build (code == LT_EXPR ? EQ_EXPR : NE_EXPR, type,
5284                       build (RSHIFT_EXPR, TREE_TYPE (arg0), arg0,
5285                              TREE_OPERAND (arg1, 1)),
5286                       convert (TREE_TYPE (arg0), integer_zero_node));
5287
5288       else if ((code == LT_EXPR || code == GE_EXPR)
5289                && TREE_UNSIGNED (TREE_TYPE (arg0))
5290                && (TREE_CODE (arg1) == NOP_EXPR
5291                    || TREE_CODE (arg1) == CONVERT_EXPR)
5292                && TREE_CODE (TREE_OPERAND (arg1, 0)) == LSHIFT_EXPR
5293                && integer_onep (TREE_OPERAND (TREE_OPERAND (arg1, 0), 0)))
5294         return
5295           build (code == LT_EXPR ? EQ_EXPR : NE_EXPR, type,
5296                  convert (TREE_TYPE (arg0),
5297                           build (RSHIFT_EXPR, TREE_TYPE (arg0), arg0,
5298                                  TREE_OPERAND (TREE_OPERAND (arg1, 0), 1))),
5299                  convert (TREE_TYPE (arg0), integer_zero_node));
5300
5301       /* Simplify comparison of something with itself.  (For IEEE
5302          floating-point, we can only do some of these simplifications.)  */
5303       if (operand_equal_p (arg0, arg1, 0))
5304         {
5305           switch (code)
5306             {
5307             case EQ_EXPR:
5308             case GE_EXPR:
5309             case LE_EXPR:
5310               if (INTEGRAL_TYPE_P (TREE_TYPE (arg0)))
5311                 {
5312                   if (type == integer_type_node)
5313                     return integer_one_node;
5314
5315                   t = build_int_2 (1, 0);
5316                   TREE_TYPE (t) = type;
5317                   return t;
5318                 }
5319               code = EQ_EXPR;
5320               TREE_SET_CODE (t, code);
5321               break;
5322
5323             case NE_EXPR:
5324               /* For NE, we can only do this simplification if integer.  */
5325               if (! INTEGRAL_TYPE_P (TREE_TYPE (arg0)))
5326                 break;
5327               /* ... fall through ...  */
5328             case GT_EXPR:
5329             case LT_EXPR:
5330               if (type == integer_type_node)
5331                 return integer_zero_node;
5332
5333               t = build_int_2 (0, 0);
5334               TREE_TYPE (t) = type;
5335               return t;
5336             default:
5337               abort ();
5338             }
5339         }
5340
5341       /* An unsigned comparison against 0 can be simplified.  */
5342       if (integer_zerop (arg1)
5343           && (INTEGRAL_TYPE_P (TREE_TYPE (arg1))
5344               || TREE_CODE (TREE_TYPE (arg1)) == POINTER_TYPE)
5345           && TREE_UNSIGNED (TREE_TYPE (arg1)))
5346         {
5347           switch (TREE_CODE (t))
5348             {
5349             case GT_EXPR:
5350               code = NE_EXPR;
5351               TREE_SET_CODE (t, NE_EXPR);
5352               break;
5353             case LE_EXPR:
5354               code = EQ_EXPR;
5355               TREE_SET_CODE (t, EQ_EXPR);
5356               break;
5357             case GE_EXPR:
5358               return omit_one_operand (type,
5359                                        convert (type, integer_one_node),
5360                                        arg0);
5361             case LT_EXPR:
5362               return omit_one_operand (type,
5363                                        convert (type, integer_zero_node),
5364                                        arg0);
5365             default:
5366               break;
5367             }
5368         }
5369
5370       /* An unsigned <= 0x7fffffff can be simplified.  */
5371       {
5372         int width = TYPE_PRECISION (TREE_TYPE (arg1));
5373         if (TREE_CODE (arg1) == INTEGER_CST
5374             && ! TREE_CONSTANT_OVERFLOW (arg1)
5375             && width <= HOST_BITS_PER_WIDE_INT
5376             && TREE_INT_CST_LOW (arg1) == ((HOST_WIDE_INT) 1 << (width - 1)) - 1
5377             && TREE_INT_CST_HIGH (arg1) == 0
5378             && (INTEGRAL_TYPE_P (TREE_TYPE (arg1))
5379                 || TREE_CODE (TREE_TYPE (arg1)) == POINTER_TYPE)
5380             && TREE_UNSIGNED (TREE_TYPE (arg1)))
5381           {
5382             switch (TREE_CODE (t))
5383               {
5384               case LE_EXPR:
5385                 return fold (build (GE_EXPR, type,
5386                                     convert (signed_type (TREE_TYPE (arg0)),
5387                                              arg0),
5388                                     convert (signed_type (TREE_TYPE (arg1)),
5389                                              integer_zero_node)));
5390               case GT_EXPR:
5391                 return fold (build (LT_EXPR, type,
5392                                     convert (signed_type (TREE_TYPE (arg0)),
5393                                              arg0),
5394                                     convert (signed_type (TREE_TYPE (arg1)),
5395                                              integer_zero_node)));
5396               default:
5397                 break;
5398               }
5399           }
5400       }
5401
5402       /* If we are comparing an expression that just has comparisons
5403          of two integer values, arithmetic expressions of those comparisons,
5404          and constants, we can simplify it.  There are only three cases
5405          to check: the two values can either be equal, the first can be
5406          greater, or the second can be greater.  Fold the expression for
5407          those three values.  Since each value must be 0 or 1, we have
5408          eight possibilities, each of which corresponds to the constant 0
5409          or 1 or one of the six possible comparisons.
5410
5411          This handles common cases like (a > b) == 0 but also handles
5412          expressions like  ((x > y) - (y > x)) > 0, which supposedly
5413          occur in macroized code.  */
5414
5415       if (TREE_CODE (arg1) == INTEGER_CST && TREE_CODE (arg0) != INTEGER_CST)
5416         {
5417           tree cval1 = 0, cval2 = 0;
5418           int save_p = 0;
5419
5420           if (twoval_comparison_p (arg0, &cval1, &cval2, &save_p)
5421               /* Don't handle degenerate cases here; they should already
5422                  have been handled anyway.  */
5423               && cval1 != 0 && cval2 != 0
5424               && ! (TREE_CONSTANT (cval1) && TREE_CONSTANT (cval2))
5425               && TREE_TYPE (cval1) == TREE_TYPE (cval2)
5426               && INTEGRAL_TYPE_P (TREE_TYPE (cval1))
5427               && TYPE_MAX_VALUE (TREE_TYPE (cval1))
5428               && TYPE_MAX_VALUE (TREE_TYPE (cval2))
5429               && ! operand_equal_p (TYPE_MIN_VALUE (TREE_TYPE (cval1)),
5430                                     TYPE_MAX_VALUE (TREE_TYPE (cval2)), 0))
5431             {
5432               tree maxval = TYPE_MAX_VALUE (TREE_TYPE (cval1));
5433               tree minval = TYPE_MIN_VALUE (TREE_TYPE (cval1));
5434
5435               /* We can't just pass T to eval_subst in case cval1 or cval2
5436                  was the same as ARG1.  */
5437
5438               tree high_result
5439                 = fold (build (code, type,
5440                                eval_subst (arg0, cval1, maxval, cval2, minval),
5441                                arg1));
5442               tree equal_result
5443                 = fold (build (code, type,
5444                                eval_subst (arg0, cval1, maxval, cval2, maxval),
5445                                arg1));
5446               tree low_result
5447                 = fold (build (code, type,
5448                                eval_subst (arg0, cval1, minval, cval2, maxval),
5449                                arg1));
5450
5451               /* All three of these results should be 0 or 1.  Confirm they
5452                  are.  Then use those values to select the proper code
5453                  to use.  */
5454
5455               if ((integer_zerop (high_result)
5456                    || integer_onep (high_result))
5457                   && (integer_zerop (equal_result)
5458                       || integer_onep (equal_result))
5459                   && (integer_zerop (low_result)
5460                       || integer_onep (low_result)))
5461                 {
5462                   /* Make a 3-bit mask with the high-order bit being the
5463                      value for `>', the next for '=', and the low for '<'.  */
5464                   switch ((integer_onep (high_result) * 4)
5465                           + (integer_onep (equal_result) * 2)
5466                           + integer_onep (low_result))
5467                     {
5468                     case 0:
5469                       /* Always false.  */
5470                       return omit_one_operand (type, integer_zero_node, arg0);
5471                     case 1:
5472                       code = LT_EXPR;
5473                       break;
5474                     case 2:
5475                       code = EQ_EXPR;
5476                       break;
5477                     case 3:
5478                       code = LE_EXPR;
5479                       break;
5480                     case 4:
5481                       code = GT_EXPR;
5482                       break;
5483                     case 5:
5484                       code = NE_EXPR;
5485                       break;
5486                     case 6:
5487                       code = GE_EXPR;
5488                       break;
5489                     case 7:
5490                       /* Always true.  */
5491                       return omit_one_operand (type, integer_one_node, arg0);
5492                     }
5493
5494                   t = build (code, type, cval1, cval2);
5495                   if (save_p)
5496                     return save_expr (t);
5497                   else
5498                     return fold (t);
5499                 }
5500             }
5501         }
5502
5503       /* If this is a comparison of a field, we may be able to simplify it.  */
5504       if ((TREE_CODE (arg0) == COMPONENT_REF
5505            || TREE_CODE (arg0) == BIT_FIELD_REF)
5506           && (code == EQ_EXPR || code == NE_EXPR)
5507           /* Handle the constant case even without -O
5508              to make sure the warnings are given.  */
5509           && (optimize || TREE_CODE (arg1) == INTEGER_CST))
5510         {
5511           t1 = optimize_bit_field_compare (code, type, arg0, arg1);
5512           return t1 ? t1 : t;
5513         }
5514
5515       /* If this is a comparison of complex values and either or both
5516          sizes are a COMPLEX_EXPR, it is best to split up the comparisons
5517          and join them with a TRUTH_ANDIF_EXPR or TRUTH_ORIF_EXPR.  This
5518          may prevent needless evaluations.  */
5519       if ((code == EQ_EXPR || code == NE_EXPR)
5520           && TREE_CODE (TREE_TYPE (arg0)) == COMPLEX_TYPE
5521           && (TREE_CODE (arg0) == COMPLEX_EXPR
5522               || TREE_CODE (arg1) == COMPLEX_EXPR))
5523         {
5524           tree subtype = TREE_TYPE (TREE_TYPE (arg0));
5525           tree real0 = fold (build1 (REALPART_EXPR, subtype, arg0));
5526           tree imag0 = fold (build1 (IMAGPART_EXPR, subtype, arg0));
5527           tree real1 = fold (build1 (REALPART_EXPR, subtype, arg1));
5528           tree imag1 = fold (build1 (IMAGPART_EXPR, subtype, arg1));
5529
5530           return fold (build ((code == EQ_EXPR ? TRUTH_ANDIF_EXPR
5531                                : TRUTH_ORIF_EXPR),
5532                               type,
5533                               fold (build (code, type, real0, real1)),
5534                               fold (build (code, type, imag0, imag1))));
5535         }
5536
5537       /* From here on, the only cases we handle are when the result is
5538          known to be a constant.
5539
5540          To compute GT, swap the arguments and do LT.
5541          To compute GE, do LT and invert the result.
5542          To compute LE, swap the arguments, do LT and invert the result.
5543          To compute NE, do EQ and invert the result.
5544
5545          Therefore, the code below must handle only EQ and LT.  */
5546
5547       if (code == LE_EXPR || code == GT_EXPR)
5548         {
5549           tem = arg0, arg0 = arg1, arg1 = tem;
5550           code = swap_tree_comparison (code);
5551         }
5552
5553       /* Note that it is safe to invert for real values here because we
5554          will check below in the one case that it matters.  */
5555
5556       invert = 0;
5557       if (code == NE_EXPR || code == GE_EXPR)
5558         {
5559           invert = 1;
5560           code = invert_tree_comparison (code);
5561         }
5562
5563       /* Compute a result for LT or EQ if args permit;
5564          otherwise return T.  */
5565       if (TREE_CODE (arg0) == INTEGER_CST && TREE_CODE (arg1) == INTEGER_CST)
5566         {
5567           if (code == EQ_EXPR)
5568             t1 = build_int_2 ((TREE_INT_CST_LOW (arg0)
5569                                == TREE_INT_CST_LOW (arg1))
5570                               && (TREE_INT_CST_HIGH (arg0)
5571                                   == TREE_INT_CST_HIGH (arg1)),
5572                               0);
5573           else
5574             t1 = build_int_2 ((TREE_UNSIGNED (TREE_TYPE (arg0))
5575                                ? INT_CST_LT_UNSIGNED (arg0, arg1)
5576                                : INT_CST_LT (arg0, arg1)),
5577                               0);
5578         }
5579
5580 #if 0 /* This is no longer useful, but breaks some real code.  */
5581       /* Assume a nonexplicit constant cannot equal an explicit one,
5582          since such code would be undefined anyway.
5583          Exception: on sysvr4, using #pragma weak,
5584          a label can come out as 0.  */
5585       else if (TREE_CODE (arg1) == INTEGER_CST
5586                && !integer_zerop (arg1)
5587                && TREE_CONSTANT (arg0)
5588                && TREE_CODE (arg0) == ADDR_EXPR
5589                && code == EQ_EXPR)
5590         t1 = build_int_2 (0, 0);
5591 #endif
5592       /* Two real constants can be compared explicitly.  */
5593       else if (TREE_CODE (arg0) == REAL_CST && TREE_CODE (arg1) == REAL_CST)
5594         {
5595           /* If either operand is a NaN, the result is false with two
5596              exceptions: First, an NE_EXPR is true on NaNs, but that case
5597              is already handled correctly since we will be inverting the
5598              result for NE_EXPR.  Second, if we had inverted a LE_EXPR
5599              or a GE_EXPR into a LT_EXPR, we must return true so that it
5600              will be inverted into false.  */
5601
5602           if (REAL_VALUE_ISNAN (TREE_REAL_CST (arg0))
5603               || REAL_VALUE_ISNAN (TREE_REAL_CST (arg1)))
5604             t1 = build_int_2 (invert && code == LT_EXPR, 0);
5605
5606           else if (code == EQ_EXPR)
5607             t1 = build_int_2 (REAL_VALUES_EQUAL (TREE_REAL_CST (arg0),
5608                                                  TREE_REAL_CST (arg1)),
5609                               0);
5610           else
5611             t1 = build_int_2 (REAL_VALUES_LESS (TREE_REAL_CST (arg0),
5612                                                 TREE_REAL_CST (arg1)),
5613                               0);
5614         }
5615
5616       if (t1 == NULL_TREE)
5617         return t;
5618
5619       if (invert)
5620         TREE_INT_CST_LOW (t1) ^= 1;
5621
5622       TREE_TYPE (t1) = type;
5623       return t1;
5624
5625     case COND_EXPR:
5626       /* Pedantic ANSI C says that a conditional expression is never an lvalue,
5627          so all simple results must be passed through pedantic_non_lvalue.  */
5628       if (TREE_CODE (arg0) == INTEGER_CST)
5629         return pedantic_non_lvalue
5630           (TREE_OPERAND (t, (integer_zerop (arg0) ? 2 : 1)));
5631       else if (operand_equal_p (arg1, TREE_OPERAND (expr, 2), 0))
5632         return pedantic_omit_one_operand (type, arg1, arg0);
5633
5634       /* If the second operand is zero, invert the comparison and swap
5635          the second and third operands.  Likewise if the second operand
5636          is constant and the third is not or if the third operand is
5637          equivalent to the first operand of the comparison.  */
5638
5639       if (integer_zerop (arg1)
5640           || (TREE_CONSTANT (arg1) && ! TREE_CONSTANT (TREE_OPERAND (t, 2)))
5641           || (TREE_CODE_CLASS (TREE_CODE (arg0)) == '<'
5642               && operand_equal_for_comparison_p (TREE_OPERAND (arg0, 0),
5643                                                  TREE_OPERAND (t, 2),
5644                                                  TREE_OPERAND (arg0, 1))))
5645         {
5646           /* See if this can be inverted.  If it can't, possibly because
5647              it was a floating-point inequality comparison, don't do
5648              anything.  */
5649           tem = invert_truthvalue (arg0);
5650
5651           if (TREE_CODE (tem) != TRUTH_NOT_EXPR)
5652             {
5653               t = build (code, type, tem,
5654                          TREE_OPERAND (t, 2), TREE_OPERAND (t, 1));
5655               arg0 = tem;
5656               arg1 = TREE_OPERAND (t, 2);
5657               STRIP_NOPS (arg1);
5658             }
5659         }
5660
5661       /* If we have A op B ? A : C, we may be able to convert this to a
5662          simpler expression, depending on the operation and the values
5663          of B and C.  IEEE floating point prevents this though,
5664          because A or B might be -0.0 or a NaN.  */
5665
5666       if (TREE_CODE_CLASS (TREE_CODE (arg0)) == '<'
5667           && (TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
5668               || ! FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (arg0, 0)))
5669               || flag_fast_math)
5670           && operand_equal_for_comparison_p (TREE_OPERAND (arg0, 0),
5671                                              arg1, TREE_OPERAND (arg0, 1)))
5672         {
5673           tree arg2 = TREE_OPERAND (t, 2);
5674           enum tree_code comp_code = TREE_CODE (arg0);
5675
5676           STRIP_NOPS (arg2);
5677
5678           /* If we have A op 0 ? A : -A, this is A, -A, abs (A), or abs (-A),
5679              depending on the comparison operation.  */
5680           if ((FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (arg0, 1)))
5681                ? real_zerop (TREE_OPERAND (arg0, 1))
5682                : integer_zerop (TREE_OPERAND (arg0, 1)))
5683               && TREE_CODE (arg2) == NEGATE_EXPR
5684               && operand_equal_p (TREE_OPERAND (arg2, 0), arg1, 0))
5685             switch (comp_code)
5686               {
5687               case EQ_EXPR:
5688                 return pedantic_non_lvalue
5689                   (fold (build1 (NEGATE_EXPR, type, arg1)));
5690               case NE_EXPR:
5691                 return pedantic_non_lvalue (convert (type, arg1));
5692               case GE_EXPR:
5693               case GT_EXPR:
5694                 return pedantic_non_lvalue
5695                   (convert (type, fold (build1 (ABS_EXPR,
5696                                                 TREE_TYPE (arg1), arg1))));
5697               case LE_EXPR:
5698               case LT_EXPR:
5699                 return pedantic_non_lvalue
5700                   (fold (build1 (NEGATE_EXPR, type,
5701                                  convert (type,
5702                                           fold (build1 (ABS_EXPR,
5703                                                         TREE_TYPE (arg1),
5704                                                         arg1))))));
5705               default:
5706                 abort ();
5707               }
5708
5709           /* If this is A != 0 ? A : 0, this is simply A.  For ==, it is
5710              always zero.  */
5711
5712           if (integer_zerop (TREE_OPERAND (arg0, 1)) && integer_zerop (arg2))
5713             {
5714               if (comp_code == NE_EXPR)
5715                 return pedantic_non_lvalue (convert (type, arg1));
5716               else if (comp_code == EQ_EXPR)
5717                 return pedantic_non_lvalue (convert (type, integer_zero_node));
5718             }
5719
5720           /* If this is A op B ? A : B, this is either A, B, min (A, B),
5721              or max (A, B), depending on the operation.  */
5722
5723           if (operand_equal_for_comparison_p (TREE_OPERAND (arg0, 1),
5724                                               arg2, TREE_OPERAND (arg0, 0)))
5725             {
5726               tree comp_op0 = TREE_OPERAND (arg0, 0);
5727               tree comp_op1 = TREE_OPERAND (arg0, 1);
5728               tree comp_type = TREE_TYPE (comp_op0);
5729
5730               switch (comp_code)
5731                 {
5732                 case EQ_EXPR:
5733                   return pedantic_non_lvalue (convert (type, arg2));
5734                 case NE_EXPR:
5735                   return pedantic_non_lvalue (convert (type, arg1));
5736                 case LE_EXPR:
5737                 case LT_EXPR:
5738                   /* In C++ a ?: expression can be an lvalue, so put the
5739                      operand which will be used if they are equal first
5740                      so that we can convert this back to the
5741                      corresponding COND_EXPR.  */
5742                   return pedantic_non_lvalue
5743                     (convert (type, (fold (build (MIN_EXPR, comp_type,
5744                                                   (comp_code == LE_EXPR
5745                                                    ? comp_op0 : comp_op1),
5746                                                   (comp_code == LE_EXPR
5747                                                    ? comp_op1 : comp_op0))))));
5748                   break;
5749                 case GE_EXPR:
5750                 case GT_EXPR:
5751                   return pedantic_non_lvalue
5752                     (convert (type, fold (build (MAX_EXPR, comp_type,
5753                                                  (comp_code == GE_EXPR
5754                                                   ? comp_op0 : comp_op1),
5755                                                  (comp_code == GE_EXPR
5756                                                   ? comp_op1 : comp_op0)))));
5757                   break;
5758                 default:
5759                   abort ();
5760                 }
5761             }
5762
5763           /* If this is A op C1 ? A : C2 with C1 and C2 constant integers,
5764              we might still be able to simplify this.  For example,
5765              if C1 is one less or one more than C2, this might have started
5766              out as a MIN or MAX and been transformed by this function.
5767              Only good for INTEGER_TYPEs, because we need TYPE_MAX_VALUE.  */
5768
5769           if (INTEGRAL_TYPE_P (type)
5770               && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
5771               && TREE_CODE (arg2) == INTEGER_CST)
5772             switch (comp_code)
5773               {
5774               case EQ_EXPR:
5775                 /* We can replace A with C1 in this case.  */
5776                 arg1 = convert (type, TREE_OPERAND (arg0, 1));
5777                 t = build (code, type, TREE_OPERAND (t, 0), arg1,
5778                            TREE_OPERAND (t, 2));
5779                 break;
5780
5781               case LT_EXPR:
5782                 /* If C1 is C2 + 1, this is min(A, C2).  */
5783                 if (! operand_equal_p (arg2, TYPE_MAX_VALUE (type), 1)
5784                     && operand_equal_p (TREE_OPERAND (arg0, 1),
5785                                         const_binop (PLUS_EXPR, arg2,
5786                                                      integer_one_node, 0), 1))
5787                   return pedantic_non_lvalue
5788                     (fold (build (MIN_EXPR, type, arg1, arg2)));
5789                 break;
5790
5791               case LE_EXPR:
5792                 /* If C1 is C2 - 1, this is min(A, C2).  */
5793                 if (! operand_equal_p (arg2, TYPE_MIN_VALUE (type), 1)
5794                     && operand_equal_p (TREE_OPERAND (arg0, 1),
5795                                         const_binop (MINUS_EXPR, arg2,
5796                                                      integer_one_node, 0), 1))
5797                   return pedantic_non_lvalue
5798                     (fold (build (MIN_EXPR, type, arg1, arg2)));
5799                 break;
5800
5801               case GT_EXPR:
5802                 /* If C1 is C2 - 1, this is max(A, C2).  */
5803                 if (! operand_equal_p (arg2, TYPE_MIN_VALUE (type), 1)
5804                     && operand_equal_p (TREE_OPERAND (arg0, 1),
5805                                         const_binop (MINUS_EXPR, arg2,
5806                                                      integer_one_node, 0), 1))
5807                   return pedantic_non_lvalue
5808                     (fold (build (MAX_EXPR, type, arg1, arg2)));
5809                 break;
5810
5811               case GE_EXPR:
5812                 /* If C1 is C2 + 1, this is max(A, C2).  */
5813                 if (! operand_equal_p (arg2, TYPE_MAX_VALUE (type), 1)
5814                     && operand_equal_p (TREE_OPERAND (arg0, 1),
5815                                         const_binop (PLUS_EXPR, arg2,
5816                                                      integer_one_node, 0), 1))
5817                   return pedantic_non_lvalue
5818                     (fold (build (MAX_EXPR, type, arg1, arg2)));
5819                 break;
5820               case NE_EXPR:
5821                 break;
5822               default:
5823                 abort ();
5824               }
5825         }
5826
5827       /* If the second operand is simpler than the third, swap them
5828          since that produces better jump optimization results.  */
5829       if ((TREE_CONSTANT (arg1) || TREE_CODE_CLASS (TREE_CODE (arg1)) == 'd'
5830            || TREE_CODE (arg1) == SAVE_EXPR)
5831           && ! (TREE_CONSTANT (TREE_OPERAND (t, 2))
5832                 || TREE_CODE_CLASS (TREE_CODE (TREE_OPERAND (t, 2))) == 'd'
5833                 || TREE_CODE (TREE_OPERAND (t, 2)) == SAVE_EXPR))
5834         {
5835           /* See if this can be inverted.  If it can't, possibly because
5836              it was a floating-point inequality comparison, don't do
5837              anything.  */
5838           tem = invert_truthvalue (arg0);
5839
5840           if (TREE_CODE (tem) != TRUTH_NOT_EXPR)
5841             {
5842               t = build (code, type, tem,
5843                          TREE_OPERAND (t, 2), TREE_OPERAND (t, 1));
5844               arg0 = tem;
5845               arg1 = TREE_OPERAND (t, 2);
5846               STRIP_NOPS (arg1);
5847             }
5848         }
5849
5850       /* Convert A ? 1 : 0 to simply A.  */
5851       if (integer_onep (TREE_OPERAND (t, 1))
5852           && integer_zerop (TREE_OPERAND (t, 2))
5853           /* If we try to convert TREE_OPERAND (t, 0) to our type, the
5854              call to fold will try to move the conversion inside
5855              a COND, which will recurse.  In that case, the COND_EXPR
5856              is probably the best choice, so leave it alone.  */
5857           && type == TREE_TYPE (arg0))
5858         return pedantic_non_lvalue (arg0);
5859
5860       /* Look for expressions of the form A & 2 ? 2 : 0.  The result of this
5861          operation is simply A & 2.  */
5862
5863       if (integer_zerop (TREE_OPERAND (t, 2))
5864           && TREE_CODE (arg0) == NE_EXPR
5865           && integer_zerop (TREE_OPERAND (arg0, 1))
5866           && integer_pow2p (arg1)
5867           && TREE_CODE (TREE_OPERAND (arg0, 0)) == BIT_AND_EXPR
5868           && operand_equal_p (TREE_OPERAND (TREE_OPERAND (arg0, 0), 1),
5869                               arg1, 1))
5870         return pedantic_non_lvalue (convert (type, TREE_OPERAND (arg0, 0)));
5871
5872       return t;
5873
5874     case COMPOUND_EXPR:
5875       /* When pedantic, a compound expression can be neither an lvalue
5876          nor an integer constant expression.  */
5877       if (TREE_SIDE_EFFECTS (arg0) || pedantic)
5878         return t;
5879       /* Don't let (0, 0) be null pointer constant.  */
5880       if (integer_zerop (arg1))
5881         return non_lvalue (arg1);
5882       return arg1;
5883
5884     case COMPLEX_EXPR:
5885       if (wins)
5886         return build_complex (type, arg0, arg1);
5887       return t;
5888
5889     case REALPART_EXPR:
5890       if (TREE_CODE (TREE_TYPE (arg0)) != COMPLEX_TYPE)
5891         return t;
5892       else if (TREE_CODE (arg0) == COMPLEX_EXPR)
5893         return omit_one_operand (type, TREE_OPERAND (arg0, 0),
5894                                  TREE_OPERAND (arg0, 1));
5895       else if (TREE_CODE (arg0) == COMPLEX_CST)
5896         return TREE_REALPART (arg0);
5897       else if (TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MINUS_EXPR)
5898         return fold (build (TREE_CODE (arg0), type,
5899                             fold (build1 (REALPART_EXPR, type,
5900                                           TREE_OPERAND (arg0, 0))),
5901                             fold (build1 (REALPART_EXPR,
5902                                           type, TREE_OPERAND (arg0, 1)))));
5903       return t;
5904
5905     case IMAGPART_EXPR:
5906       if (TREE_CODE (TREE_TYPE (arg0)) != COMPLEX_TYPE)
5907         return convert (type, integer_zero_node);
5908       else if (TREE_CODE (arg0) == COMPLEX_EXPR)
5909         return omit_one_operand (type, TREE_OPERAND (arg0, 1),
5910                                  TREE_OPERAND (arg0, 0));
5911       else if (TREE_CODE (arg0) == COMPLEX_CST)
5912         return TREE_IMAGPART (arg0);
5913       else if (TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MINUS_EXPR)
5914         return fold (build (TREE_CODE (arg0), type,
5915                             fold (build1 (IMAGPART_EXPR, type,
5916                                           TREE_OPERAND (arg0, 0))),
5917                             fold (build1 (IMAGPART_EXPR, type,
5918                                           TREE_OPERAND (arg0, 1)))));
5919       return t;
5920
5921       /* Pull arithmetic ops out of the CLEANUP_POINT_EXPR where
5922          appropriate.  */
5923     case CLEANUP_POINT_EXPR:
5924       if (! has_cleanups (arg0))
5925         return TREE_OPERAND (t, 0);
5926
5927       {
5928         enum tree_code code0 = TREE_CODE (arg0);
5929         int kind0 = TREE_CODE_CLASS (code0);
5930         tree arg00 = TREE_OPERAND (arg0, 0);
5931         tree arg01;
5932
5933         if (kind0 == '1' || code0 == TRUTH_NOT_EXPR)
5934           return fold (build1 (code0, type,
5935                                fold (build1 (CLEANUP_POINT_EXPR,
5936                                              TREE_TYPE (arg00), arg00))));
5937
5938         if (kind0 == '<' || kind0 == '2'
5939             || code0 == TRUTH_ANDIF_EXPR || code0 == TRUTH_ORIF_EXPR
5940             || code0 == TRUTH_AND_EXPR   || code0 == TRUTH_OR_EXPR
5941             || code0 == TRUTH_XOR_EXPR)
5942           {
5943             arg01 = TREE_OPERAND (arg0, 1);
5944
5945             if (TREE_CONSTANT (arg00)
5946                 || ((code0 == TRUTH_ANDIF_EXPR || code0 == TRUTH_ORIF_EXPR)
5947                     && ! has_cleanups (arg00)))
5948               return fold (build (code0, type, arg00,
5949                                   fold (build1 (CLEANUP_POINT_EXPR,
5950                                                 TREE_TYPE (arg01), arg01))));
5951
5952             if (TREE_CONSTANT (arg01))
5953               return fold (build (code0, type,
5954                                   fold (build1 (CLEANUP_POINT_EXPR,
5955                                                 TREE_TYPE (arg00), arg00)),
5956                                   arg01));
5957           }
5958
5959         return t;
5960       }
5961
5962     default:
5963       return t;
5964     } /* switch (code) */
5965 }
5966
5967 /* Determine if first argument is a multiple of second argument.
5968    Return 0 if it is not, or is not easily determined to so be.
5969
5970    An example of the sort of thing we care about (at this point --
5971    this routine could surely be made more general, and expanded
5972    to do what the *_DIV_EXPR's fold() cases do now) is discovering
5973    that
5974
5975      SAVE_EXPR (I) * SAVE_EXPR (J * 8)
5976
5977    is a multiple of
5978
5979      SAVE_EXPR (J * 8)
5980
5981    when we know that the two `SAVE_EXPR (J * 8)' nodes are the
5982    same node (which means they will have the same value at run
5983    time, even though we don't know when they'll be assigned).
5984
5985    This code also handles discovering that
5986
5987      SAVE_EXPR (I) * SAVE_EXPR (J * 8)
5988
5989    is a multiple of
5990
5991      8
5992
5993    (of course) so we don't have to worry about dealing with a
5994    possible remainder.
5995
5996    Note that we _look_ inside a SAVE_EXPR only to determine
5997    how it was calculated; it is not safe for fold() to do much
5998    of anything else with the internals of a SAVE_EXPR, since
5999    fold() cannot know when it will be evaluated at run time.
6000    For example, the latter example above _cannot_ be implemented
6001    as
6002
6003      SAVE_EXPR (I) * J
6004
6005    or any variant thereof, since the value of J at evaluation time
6006    of the original SAVE_EXPR is not necessarily the same at the time
6007    the new expression is evaluated.  The only optimization of this
6008    sort that would be valid is changing
6009
6010      SAVE_EXPR (I) * SAVE_EXPR (SAVE_EXPR (J) * 8)
6011    divided by
6012      8
6013
6014    to
6015
6016      SAVE_EXPR (I) * SAVE_EXPR (J)
6017
6018    (where the same SAVE_EXPR (J) is used in the original and the
6019    transformed version).  */
6020
6021 static int
6022 multiple_of_p (type, top, bottom)
6023      tree type;
6024      tree top;
6025      tree bottom;
6026 {
6027   if (operand_equal_p (top, bottom, 0))
6028     return 1;
6029
6030   if (TREE_CODE (type) != INTEGER_TYPE)
6031     return 0;
6032
6033   switch (TREE_CODE (top))
6034     {
6035     case MULT_EXPR:
6036       return (multiple_of_p (type, TREE_OPERAND (top, 0), bottom)
6037               || multiple_of_p (type, TREE_OPERAND (top, 1), bottom));
6038
6039     case PLUS_EXPR:
6040     case MINUS_EXPR:
6041       return (multiple_of_p (type, TREE_OPERAND (top, 0), bottom)
6042               && multiple_of_p (type, TREE_OPERAND (top, 1), bottom));
6043
6044     case NOP_EXPR:
6045       /* Punt if conversion from non-integral or wider integral type.  */
6046       if ((TREE_CODE (TREE_TYPE (TREE_OPERAND (top, 0))) != INTEGER_TYPE)
6047           || (TYPE_PRECISION (type)
6048               < TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (top, 0)))))
6049         return 0;
6050       /* Fall through. */
6051     case SAVE_EXPR:
6052       return multiple_of_p (type, TREE_OPERAND (top, 0), bottom);
6053
6054     case INTEGER_CST:
6055       if ((TREE_CODE (bottom) != INTEGER_CST)
6056           || (tree_int_cst_sgn (top) < 0)
6057           || (tree_int_cst_sgn (bottom) < 0))
6058         return 0;
6059       return integer_zerop (const_binop (TRUNC_MOD_EXPR,
6060                                          top, bottom, 0));
6061
6062     default:
6063       return 0;
6064     }
6065 }
6066 \f