gcc/fold-const.c

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