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