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 >= 0 && 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                    && TREE_CODE_CLASS (code) != '<'))
3761         {
3762           tree test, true_value, false_value;
3763
3764           if (TREE_CODE (arg1) == COND_EXPR)
3765             {
3766               test = TREE_OPERAND (arg1, 0);
3767               true_value = TREE_OPERAND (arg1, 1);
3768               false_value = TREE_OPERAND (arg1, 2);
3769             }
3770           else
3771             {
3772               tree testtype = TREE_TYPE (arg1);
3773               test = arg1;
3774               true_value = convert (testtype, integer_one_node);
3775               false_value = convert (testtype, integer_zero_node);
3776             }
3777
3778           /* If ARG0 is complex we want to make sure we only evaluate
3779              it once.  Though this is only required if it is volatile, it
3780              might be more efficient even if it is not.  However, if we
3781              succeed in folding one part to a constant, we do not need
3782              to make this SAVE_EXPR.  Since we do this optimization
3783              primarily to see if we do end up with constant and this
3784              SAVE_EXPR interferes with later optimizations, suppressing
3785              it when we can is important.  */
3786
3787           if (TREE_CODE (arg0) != SAVE_EXPR
3788               && ((TREE_CODE (arg0) != VAR_DECL
3789                    && TREE_CODE (arg0) != PARM_DECL)
3790                   || TREE_SIDE_EFFECTS (arg0)))
3791             {
3792               tree lhs = fold (build (code, type, arg0, true_value));
3793               tree rhs = fold (build (code, type, arg0, false_value));
3794
3795               if (TREE_CONSTANT (lhs) || TREE_CONSTANT (rhs))
3796                 return fold (build (COND_EXPR, type, test, lhs, rhs));
3797
3798               arg0 = save_expr (arg0);
3799             }
3800
3801           test = fold (build (COND_EXPR, type, test,
3802                               fold (build (code, type, arg0, true_value)),
3803                               fold (build (code, type, arg0, false_value))));
3804           if (TREE_CODE (arg0) == SAVE_EXPR)
3805             return build (COMPOUND_EXPR, type,
3806                           convert (void_type_node, arg0),
3807                           strip_compound_expr (test, arg0));
3808           else
3809             return convert (type, test);
3810         }
3811
3812       else if (TREE_CODE (arg0) == COMPOUND_EXPR)
3813         return build (COMPOUND_EXPR, type, TREE_OPERAND (arg0, 0),
3814                       fold (build (code, type, TREE_OPERAND (arg0, 1), arg1)));
3815       else if (TREE_CODE (arg0) == COND_EXPR
3816                || (TREE_CODE_CLASS (TREE_CODE (arg0)) == '<'
3817                    && TREE_CODE_CLASS (code) != '<'))
3818         {
3819           tree test, true_value, false_value;
3820
3821           if (TREE_CODE (arg0) == COND_EXPR)
3822             {
3823               test = TREE_OPERAND (arg0, 0);
3824               true_value = TREE_OPERAND (arg0, 1);
3825               false_value = TREE_OPERAND (arg0, 2);
3826             }
3827           else
3828             {
3829               tree testtype = TREE_TYPE (arg0);
3830               test = arg0;
3831               true_value = convert (testtype, integer_one_node);
3832               false_value = convert (testtype, integer_zero_node);
3833             }
3834
3835           if (TREE_CODE (arg1) != SAVE_EXPR
3836               && ((TREE_CODE (arg1) != VAR_DECL
3837                    && TREE_CODE (arg1) != PARM_DECL)
3838                   || TREE_SIDE_EFFECTS (arg1)))
3839             {
3840               tree lhs = fold (build (code, type, true_value, arg1));
3841               tree rhs = fold (build (code, type, false_value, arg1));
3842
3843               if (TREE_CONSTANT (lhs) || TREE_CONSTANT (rhs)
3844                   || TREE_CONSTANT (arg1))
3845                 return fold (build (COND_EXPR, type, test, lhs, rhs));
3846
3847               arg1 = save_expr (arg1);
3848             }
3849
3850           test = fold (build (COND_EXPR, type, test,
3851                               fold (build (code, type, true_value, arg1)),
3852                               fold (build (code, type, false_value, arg1))));
3853           if (TREE_CODE (arg1) == SAVE_EXPR)
3854             return build (COMPOUND_EXPR, type,
3855                           convert (void_type_node, arg1),
3856                           strip_compound_expr (test, arg1));
3857           else
3858             return convert (type, test);
3859         }
3860     }
3861   else if (TREE_CODE_CLASS (code) == '<'
3862            && TREE_CODE (arg0) == COMPOUND_EXPR)
3863     return build (COMPOUND_EXPR, type, TREE_OPERAND (arg0, 0),
3864                   fold (build (code, type, TREE_OPERAND (arg0, 1), arg1)));
3865   else if (TREE_CODE_CLASS (code) == '<'
3866            && TREE_CODE (arg1) == COMPOUND_EXPR)
3867     return build (COMPOUND_EXPR, type, TREE_OPERAND (arg1, 0),
3868                   fold (build (code, type, arg0, TREE_OPERAND (arg1, 1))));
3869
3870   switch (code)
3871     {
3872     case INTEGER_CST:
3873     case REAL_CST:
3874     case STRING_CST:
3875     case COMPLEX_CST:
3876     case CONSTRUCTOR:
3877       return t;
3878
3879     case CONST_DECL:
3880       return fold (DECL_INITIAL (t));
3881
3882     case NOP_EXPR:
3883     case FLOAT_EXPR:
3884     case CONVERT_EXPR:
3885     case FIX_TRUNC_EXPR:
3886       /* Other kinds of FIX are not handled properly by fold_convert.  */
3887
3888       if (TREE_TYPE (TREE_OPERAND (t, 0)) == TREE_TYPE (t))
3889         return TREE_OPERAND (t, 0);
3890
3891       /* Handle cases of two conversions in a row.  */
3892       if (TREE_CODE (TREE_OPERAND (t, 0)) == NOP_EXPR
3893           || TREE_CODE (TREE_OPERAND (t, 0)) == CONVERT_EXPR)
3894         {
3895           tree inside_type = TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 0), 0));
3896           tree inter_type = TREE_TYPE (TREE_OPERAND (t, 0));
3897           tree final_type = TREE_TYPE (t);
3898           int inside_int = INTEGRAL_TYPE_P (inside_type);
3899           int inside_ptr = POINTER_TYPE_P (inside_type);
3900           int inside_float = FLOAT_TYPE_P (inside_type);
3901           int inside_prec = TYPE_PRECISION (inside_type);
3902           int inside_unsignedp = TREE_UNSIGNED (inside_type);
3903           int inter_int = INTEGRAL_TYPE_P (inter_type);
3904           int inter_ptr = POINTER_TYPE_P (inter_type);
3905           int inter_float = FLOAT_TYPE_P (inter_type);
3906           int inter_prec = TYPE_PRECISION (inter_type);
3907           int inter_unsignedp = TREE_UNSIGNED (inter_type);
3908           int final_int = INTEGRAL_TYPE_P (final_type);
3909           int final_ptr = POINTER_TYPE_P (final_type);
3910           int final_float = FLOAT_TYPE_P (final_type);
3911           int final_prec = TYPE_PRECISION (final_type);
3912           int final_unsignedp = TREE_UNSIGNED (final_type);
3913
3914           /* In addition to the cases of two conversions in a row
3915              handled below, if we are converting something to its own
3916              type via an object of identical or wider precision, neither
3917              conversion is needed.  */
3918           if (inside_type == final_type
3919               && ((inter_int && final_int) || (inter_float && final_float))
3920               && inter_prec >= final_prec)
3921             return TREE_OPERAND (TREE_OPERAND (t, 0), 0);
3922
3923           /* Likewise, if the intermediate and final types are either both
3924              float or both integer, we don't need the middle conversion if
3925              it is wider than the final type and doesn't change the signedness
3926              (for integers).  Avoid this if the final type is a pointer
3927              since then we sometimes need the inner conversion.  Likewise if
3928              the outer has a precision not equal to the size of its mode.  */
3929           if ((((inter_int || inter_ptr) && (inside_int || inside_ptr))
3930                || (inter_float && inside_float))
3931               && inter_prec >= inside_prec
3932               && (inter_float || inter_unsignedp == inside_unsignedp)
3933               && ! (final_prec != GET_MODE_BITSIZE (TYPE_MODE (final_type))
3934                     && TYPE_MODE (final_type) == TYPE_MODE (inter_type))
3935               && ! final_ptr)
3936             return convert (final_type, TREE_OPERAND (TREE_OPERAND (t, 0), 0));
3937
3938           /* Two conversions in a row are not needed unless:
3939              - some conversion is floating-point (overstrict for now), or
3940              - the intermediate type is narrower than both initial and
3941                final, or
3942              - the intermediate type and innermost type differ in signedness,
3943                and the outermost type is wider than the intermediate, or
3944              - the initial type is a pointer type and the precisions of the
3945                intermediate and final types differ, or
3946              - the final type is a pointer type and the precisions of the
3947                initial and intermediate types differ.  */
3948           if (! inside_float && ! inter_float && ! final_float
3949               && (inter_prec > inside_prec || inter_prec > final_prec)
3950               && ! (inside_int && inter_int
3951                     && inter_unsignedp != inside_unsignedp
3952                     && inter_prec < final_prec)
3953               && ((inter_unsignedp && inter_prec > inside_prec)
3954                   == (final_unsignedp && final_prec > inter_prec))
3955               && ! (inside_ptr && inter_prec != final_prec)
3956               && ! (final_ptr && inside_prec != inter_prec)
3957               && ! (final_prec != GET_MODE_BITSIZE (TYPE_MODE (final_type))
3958                     && TYPE_MODE (final_type) == TYPE_MODE (inter_type))
3959               && ! final_ptr)
3960             return convert (final_type, TREE_OPERAND (TREE_OPERAND (t, 0), 0));
3961         }
3962
3963       if (TREE_CODE (TREE_OPERAND (t, 0)) == MODIFY_EXPR
3964           && TREE_CONSTANT (TREE_OPERAND (TREE_OPERAND (t, 0), 1))
3965           /* Detect assigning a bitfield.  */
3966           && !(TREE_CODE (TREE_OPERAND (TREE_OPERAND (t, 0), 0)) == COMPONENT_REF
3967                && DECL_BIT_FIELD (TREE_OPERAND (TREE_OPERAND (TREE_OPERAND (t, 0), 0), 1))))
3968         {
3969           /* Don't leave an assignment inside a conversion
3970              unless assigning a bitfield.  */
3971           tree prev = TREE_OPERAND (t, 0);
3972           TREE_OPERAND (t, 0) = TREE_OPERAND (prev, 1);
3973           /* First do the assignment, then return converted constant.  */
3974           t = build (COMPOUND_EXPR, TREE_TYPE (t), prev, fold (t));
3975           TREE_USED (t) = 1;
3976           return t;
3977         }
3978       if (!wins)
3979         {
3980           TREE_CONSTANT (t) = TREE_CONSTANT (arg0);
3981           return t;
3982         }
3983       return fold_convert (t, arg0);
3984
3985 #if 0  /* This loses on &"foo"[0].  */
3986     case ARRAY_REF:
3987         {
3988           int i;
3989
3990           /* Fold an expression like: "foo"[2] */
3991           if (TREE_CODE (arg0) == STRING_CST
3992               && TREE_CODE (arg1) == INTEGER_CST
3993               && !TREE_INT_CST_HIGH (arg1)
3994               && (i = TREE_INT_CST_LOW (arg1)) < TREE_STRING_LENGTH (arg0))
3995             {
3996               t = build_int_2 (TREE_STRING_POINTER (arg0)[i], 0);
3997               TREE_TYPE (t) = TREE_TYPE (TREE_TYPE (arg0));
3998               force_fit_type (t, 0);
3999             }
4000         }
4001       return t;
4002 #endif /* 0 */
4003
4004     case COMPONENT_REF:
4005       if (TREE_CODE (arg0) == CONSTRUCTOR)
4006         {
4007           tree m = purpose_member (arg1, CONSTRUCTOR_ELTS (arg0));
4008           if (m)
4009             t = TREE_VALUE (m);
4010         }
4011       return t;
4012
4013     case RANGE_EXPR:
4014       TREE_CONSTANT (t) = wins;
4015       return t;
4016
4017     case NEGATE_EXPR:
4018       if (wins)
4019         {
4020           if (TREE_CODE (arg0) == INTEGER_CST)
4021             {
4022               HOST_WIDE_INT low, high;
4023               int overflow = neg_double (TREE_INT_CST_LOW (arg0),
4024                                          TREE_INT_CST_HIGH (arg0),
4025                                          &low, &high);
4026               t = build_int_2 (low, high);
4027               TREE_TYPE (t) = type;
4028               TREE_OVERFLOW (t)
4029                 = (TREE_OVERFLOW (arg0)
4030                    | force_fit_type (t, overflow && !TREE_UNSIGNED (type)));
4031               TREE_CONSTANT_OVERFLOW (t)
4032                 = TREE_OVERFLOW (t) | TREE_CONSTANT_OVERFLOW (arg0);
4033             }
4034           else if (TREE_CODE (arg0) == REAL_CST)
4035             t = build_real (type, REAL_VALUE_NEGATE (TREE_REAL_CST (arg0)));
4036         }
4037       else if (TREE_CODE (arg0) == NEGATE_EXPR)
4038         return TREE_OPERAND (arg0, 0);
4039
4040       /* Convert - (a - b) to (b - a) for non-floating-point.  */
4041       else if (TREE_CODE (arg0) == MINUS_EXPR && ! FLOAT_TYPE_P (type))
4042         return build (MINUS_EXPR, type, TREE_OPERAND (arg0, 1),
4043                       TREE_OPERAND (arg0, 0));
4044
4045       return t;
4046
4047     case ABS_EXPR:
4048       if (wins)
4049         {
4050           if (TREE_CODE (arg0) == INTEGER_CST)
4051             {
4052               if (! TREE_UNSIGNED (type)
4053                   && TREE_INT_CST_HIGH (arg0) < 0)
4054                 {
4055                   HOST_WIDE_INT low, high;
4056                   int overflow = neg_double (TREE_INT_CST_LOW (arg0),
4057                                              TREE_INT_CST_HIGH (arg0),
4058                                              &low, &high);
4059                   t = build_int_2 (low, high);
4060                   TREE_TYPE (t) = type;
4061                   TREE_OVERFLOW (t)
4062                     = (TREE_OVERFLOW (arg0)
4063                        | force_fit_type (t, overflow));
4064                   TREE_CONSTANT_OVERFLOW (t)
4065                     = TREE_OVERFLOW (t) | TREE_CONSTANT_OVERFLOW (arg0);
4066                 }
4067             }
4068           else if (TREE_CODE (arg0) == REAL_CST)
4069             {
4070               if (REAL_VALUE_NEGATIVE (TREE_REAL_CST (arg0)))
4071                 t = build_real (type,
4072                                 REAL_VALUE_NEGATE (TREE_REAL_CST (arg0)));
4073             }
4074         }
4075       else if (TREE_CODE (arg0) == ABS_EXPR || TREE_CODE (arg0) == NEGATE_EXPR)
4076         return build1 (ABS_EXPR, type, TREE_OPERAND (arg0, 0));
4077       return t;
4078
4079     case CONJ_EXPR:
4080       if (TREE_CODE (TREE_TYPE (arg0)) != COMPLEX_TYPE)
4081         return arg0;
4082       else if (TREE_CODE (arg0) == COMPLEX_EXPR)
4083         return build (COMPLEX_EXPR, TREE_TYPE (arg0),
4084                       TREE_OPERAND (arg0, 0),
4085                       fold (build1 (NEGATE_EXPR,
4086                                     TREE_TYPE (TREE_TYPE (arg0)),
4087                                     TREE_OPERAND (arg0, 1))));
4088       else if (TREE_CODE (arg0) == COMPLEX_CST)
4089         return build_complex (type, TREE_OPERAND (arg0, 0),
4090                               fold (build1 (NEGATE_EXPR,
4091                                             TREE_TYPE (TREE_TYPE (arg0)),
4092                                             TREE_OPERAND (arg0, 1))));
4093       else if (TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MINUS_EXPR)
4094         return fold (build (TREE_CODE (arg0), type,
4095                             fold (build1 (CONJ_EXPR, type,
4096                                           TREE_OPERAND (arg0, 0))),
4097                             fold (build1 (CONJ_EXPR,
4098                                           type, TREE_OPERAND (arg0, 1)))));
4099       else if (TREE_CODE (arg0) == CONJ_EXPR)
4100         return TREE_OPERAND (arg0, 0);
4101       return t;
4102
4103     case BIT_NOT_EXPR:
4104       if (wins)
4105         {
4106           t = build_int_2 (~ TREE_INT_CST_LOW (arg0),
4107                            ~ TREE_INT_CST_HIGH (arg0));
4108           TREE_TYPE (t) = type;
4109           force_fit_type (t, 0);
4110           TREE_OVERFLOW (t) = TREE_OVERFLOW (arg0);
4111           TREE_CONSTANT_OVERFLOW (t) = TREE_CONSTANT_OVERFLOW (arg0);
4112         }
4113       else if (TREE_CODE (arg0) == BIT_NOT_EXPR)
4114         return TREE_OPERAND (arg0, 0);
4115       return t;
4116
4117     case PLUS_EXPR:
4118       /* A + (-B) -> A - B */
4119       if (TREE_CODE (arg1) == NEGATE_EXPR)
4120         return fold (build (MINUS_EXPR, type, arg0, TREE_OPERAND (arg1, 0)));
4121       else if (! FLOAT_TYPE_P (type))
4122         {
4123           if (integer_zerop (arg1))
4124             return non_lvalue (convert (type, arg0));
4125
4126           /* If we are adding two BIT_AND_EXPR's, both of which are and'ing
4127              with a constant, and the two constants have no bits in common,
4128              we should treat this as a BIT_IOR_EXPR since this may produce more
4129              simplifications.  */
4130           if (TREE_CODE (arg0) == BIT_AND_EXPR
4131               && TREE_CODE (arg1) == BIT_AND_EXPR
4132               && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
4133               && TREE_CODE (TREE_OPERAND (arg1, 1)) == INTEGER_CST
4134               && integer_zerop (const_binop (BIT_AND_EXPR,
4135                                              TREE_OPERAND (arg0, 1),
4136                                              TREE_OPERAND (arg1, 1), 0)))
4137             {
4138               code = BIT_IOR_EXPR;
4139               goto bit_ior;
4140             }
4141
4142           /* (A * C) + (B * C) -> (A+B) * C.  Since we are most concerned
4143              about the case where C is a constant, just try one of the
4144              four possibilities.  */
4145
4146           if (TREE_CODE (arg0) == MULT_EXPR && TREE_CODE (arg1) == MULT_EXPR
4147               && operand_equal_p (TREE_OPERAND (arg0, 1),
4148                                   TREE_OPERAND (arg1, 1), 0))
4149             return fold (build (MULT_EXPR, type,
4150                                 fold (build (PLUS_EXPR, type,
4151                                              TREE_OPERAND (arg0, 0),
4152                                              TREE_OPERAND (arg1, 0))),
4153                                 TREE_OPERAND (arg0, 1)));
4154         }
4155       /* In IEEE floating point, x+0 may not equal x.  */
4156       else if ((TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
4157                 || flag_fast_math)
4158                && real_zerop (arg1))
4159         return non_lvalue (convert (type, arg0));
4160     associate:
4161       /* In most languages, can't associate operations on floats
4162          through parentheses.  Rather than remember where the parentheses
4163          were, we don't associate floats at all.  It shouldn't matter much.
4164          However, associating multiplications is only very slightly
4165          inaccurate, so do that if -ffast-math is specified.  */
4166       if (FLOAT_TYPE_P (type)
4167           && ! (flag_fast_math && code == MULT_EXPR))
4168         goto binary;
4169
4170       /* The varsign == -1 cases happen only for addition and subtraction.
4171          It says that the arg that was split was really CON minus VAR.
4172          The rest of the code applies to all associative operations.  */
4173       if (!wins)
4174         {
4175           tree var, con;
4176           int varsign;
4177
4178           if (split_tree (arg0, code, &var, &con, &varsign))
4179             {
4180               if (varsign == -1)
4181                 {
4182                   /* EXPR is (CON-VAR) +- ARG1.  */
4183                   /* If it is + and VAR==ARG1, return just CONST.  */
4184                   if (code == PLUS_EXPR && operand_equal_p (var, arg1, 0))
4185                     return convert (TREE_TYPE (t), con);
4186
4187                   /* If ARG0 is a constant, don't change things around;
4188                      instead keep all the constant computations together.  */
4189
4190                   if (TREE_CONSTANT (arg0))
4191                     return t;
4192
4193                   /* Otherwise return (CON +- ARG1) - VAR.  */
4194                   t = build (MINUS_EXPR, type,
4195                              fold (build (code, type, con, arg1)), var);
4196                 }
4197               else
4198                 {
4199                   /* EXPR is (VAR+CON) +- ARG1.  */
4200                   /* If it is - and VAR==ARG1, return just CONST.  */
4201                   if (code == MINUS_EXPR && operand_equal_p (var, arg1, 0))
4202                     return convert (TREE_TYPE (t), con);
4203
4204                   /* If ARG0 is a constant, don't change things around;
4205                      instead keep all the constant computations together.  */
4206
4207                   if (TREE_CONSTANT (arg0))
4208                     return t;
4209
4210                   /* Otherwise return VAR +- (ARG1 +- CON).  */
4211                   tem = fold (build (code, type, arg1, con));
4212                   t = build (code, type, var, tem);
4213
4214                   if (integer_zerop (tem)
4215                       && (code == PLUS_EXPR || code == MINUS_EXPR))
4216                     return convert (type, var);
4217                   /* If we have x +/- (c - d) [c an explicit integer]
4218                      change it to x -/+ (d - c) since if d is relocatable
4219                      then the latter can be a single immediate insn
4220                      and the former cannot.  */
4221                   if (TREE_CODE (tem) == MINUS_EXPR
4222                       && TREE_CODE (TREE_OPERAND (tem, 0)) == INTEGER_CST)
4223                     {
4224                       tree tem1 = TREE_OPERAND (tem, 1);
4225                       TREE_OPERAND (tem, 1) = TREE_OPERAND (tem, 0);
4226                       TREE_OPERAND (tem, 0) = tem1;
4227                       TREE_SET_CODE (t,
4228                                      (code == PLUS_EXPR ? MINUS_EXPR : PLUS_EXPR));
4229                     }
4230                 }
4231               return t;
4232             }
4233
4234           if (split_tree (arg1, code, &var, &con, &varsign))
4235             {
4236               if (TREE_CONSTANT (arg1))
4237                 return t;
4238
4239               if (varsign == -1)
4240                 TREE_SET_CODE (t,
4241                                (code == PLUS_EXPR ? MINUS_EXPR : PLUS_EXPR));
4242
4243               /* EXPR is ARG0 +- (CON +- VAR).  */
4244               if (TREE_CODE (t) == MINUS_EXPR
4245                   && operand_equal_p (var, arg0, 0))
4246                 {
4247                   /* If VAR and ARG0 cancel, return just CON or -CON.  */
4248                   if (code == PLUS_EXPR)
4249                     return convert (TREE_TYPE (t), con);
4250                   return fold (build1 (NEGATE_EXPR, TREE_TYPE (t),
4251                                        convert (TREE_TYPE (t), con)));
4252                 }
4253
4254               t = build (TREE_CODE (t), type,
4255                          fold (build (code, TREE_TYPE (t), arg0, con)), var);
4256
4257               if (integer_zerop (TREE_OPERAND (t, 0))
4258                   && TREE_CODE (t) == PLUS_EXPR)
4259                 return convert (TREE_TYPE (t), var);
4260               return t;
4261             }
4262         }
4263     binary:
4264 #if defined (REAL_IS_NOT_DOUBLE) && ! defined (REAL_ARITHMETIC)
4265       if (TREE_CODE (arg1) == REAL_CST)
4266         return t;
4267 #endif /* REAL_IS_NOT_DOUBLE, and no REAL_ARITHMETIC */
4268       if (wins)
4269         t1 = const_binop (code, arg0, arg1, 0);
4270       if (t1 != NULL_TREE)
4271         {
4272           /* The return value should always have
4273              the same type as the original expression.  */
4274           if (TREE_TYPE (t1) != TREE_TYPE (t))
4275             t1 = convert (TREE_TYPE (t), t1);
4276
4277           return t1;
4278         }
4279       return t;
4280
4281     case MINUS_EXPR:
4282       if (! FLOAT_TYPE_P (type))
4283         {
4284           if (! wins && integer_zerop (arg0))
4285             return build1 (NEGATE_EXPR, type, arg1);
4286           if (integer_zerop (arg1))
4287             return non_lvalue (convert (type, arg0));
4288
4289           /* (A * C) - (B * C) -> (A-B) * C.  Since we are most concerned
4290              about the case where C is a constant, just try one of the
4291              four possibilities.  */
4292
4293           if (TREE_CODE (arg0) == MULT_EXPR && TREE_CODE (arg1) == MULT_EXPR
4294               && operand_equal_p (TREE_OPERAND (arg0, 1),
4295                                   TREE_OPERAND (arg1, 1), 0))
4296             return fold (build (MULT_EXPR, type,
4297                                 fold (build (MINUS_EXPR, type,
4298                                              TREE_OPERAND (arg0, 0),
4299                                              TREE_OPERAND (arg1, 0))),
4300                                 TREE_OPERAND (arg0, 1)));
4301         }
4302       /* Convert A - (-B) to A + B.  */
4303       else if (TREE_CODE (arg1) == NEGATE_EXPR)
4304         return fold (build (PLUS_EXPR, type, arg0, TREE_OPERAND (arg1, 0)));
4305
4306       else if (TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
4307                || flag_fast_math)
4308         {
4309           /* Except with IEEE floating point, 0-x equals -x.  */
4310           if (! wins && real_zerop (arg0))
4311             return build1 (NEGATE_EXPR, type, arg1);
4312           /* Except with IEEE floating point, x-0 equals x.  */
4313           if (real_zerop (arg1))
4314             return non_lvalue (convert (type, arg0));
4315         }
4316
4317       /* Fold &x - &x.  This can happen from &x.foo - &x.
4318          This is unsafe for certain floats even in non-IEEE formats.
4319          In IEEE, it is unsafe because it does wrong for NaNs.
4320          Also note that operand_equal_p is always false if an operand
4321          is volatile.  */
4322
4323       if ((! FLOAT_TYPE_P (type) || flag_fast_math)
4324           && operand_equal_p (arg0, arg1, 0))
4325         return convert (type, integer_zero_node);
4326
4327       goto associate;
4328
4329     case MULT_EXPR:
4330       if (! FLOAT_TYPE_P (type))
4331         {
4332           if (integer_zerop (arg1))
4333             return omit_one_operand (type, arg1, arg0);
4334           if (integer_onep (arg1))
4335             return non_lvalue (convert (type, arg0));
4336
4337           /* ((A / C) * C) is A if the division is an
4338              EXACT_DIV_EXPR.   Since C is normally a constant,
4339              just check for one of the four possibilities.  */
4340
4341           if (TREE_CODE (arg0) == EXACT_DIV_EXPR
4342               && operand_equal_p (TREE_OPERAND (arg0, 1), arg1, 0))
4343             return TREE_OPERAND (arg0, 0);
4344
4345           /* (a * (1 << b)) is (a << b)  */
4346           if (TREE_CODE (arg1) == LSHIFT_EXPR
4347               && integer_onep (TREE_OPERAND (arg1, 0)))
4348             return fold (build (LSHIFT_EXPR, type, arg0,
4349                                 TREE_OPERAND (arg1, 1)));
4350           if (TREE_CODE (arg0) == LSHIFT_EXPR
4351               && integer_onep (TREE_OPERAND (arg0, 0)))
4352             return fold (build (LSHIFT_EXPR, type, arg1,
4353                                 TREE_OPERAND (arg0, 1)));
4354         }
4355       else
4356         {
4357           /* x*0 is 0, except for IEEE floating point.  */
4358           if ((TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
4359                || flag_fast_math)
4360               && real_zerop (arg1))
4361             return omit_one_operand (type, arg1, arg0);
4362           /* In IEEE floating point, x*1 is not equivalent to x for snans.
4363              However, ANSI says we can drop signals,
4364              so we can do this anyway.  */
4365           if (real_onep (arg1))
4366             return non_lvalue (convert (type, arg0));
4367           /* x*2 is x+x */
4368           if (! wins && real_twop (arg1))
4369             {
4370               tree arg = save_expr (arg0);
4371               return build (PLUS_EXPR, type, arg, arg);
4372             }
4373         }
4374       goto associate;
4375
4376     case BIT_IOR_EXPR:
4377     bit_ior:
4378       {
4379       register enum tree_code code0, code1;
4380
4381       if (integer_all_onesp (arg1))
4382         return omit_one_operand (type, arg1, arg0);
4383       if (integer_zerop (arg1))
4384         return non_lvalue (convert (type, arg0));
4385       t1 = distribute_bit_expr (code, type, arg0, arg1);
4386       if (t1 != NULL_TREE)
4387         return t1;
4388
4389       /* (A << C1) | (A >> C2) if A is unsigned and C1+C2 is the size of A
4390          is a rotate of A by C1 bits.  */
4391       /* (A << B) | (A >> (Z - B)) if A is unsigned and Z is the size of A
4392          is a rotate of A by B bits.  */
4393
4394       code0 = TREE_CODE (arg0);
4395       code1 = TREE_CODE (arg1);
4396       if (((code0 == RSHIFT_EXPR && code1 == LSHIFT_EXPR)
4397           || (code1 == RSHIFT_EXPR && code0 == LSHIFT_EXPR))
4398           && operand_equal_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg1,0), 0)
4399           && TREE_UNSIGNED (TREE_TYPE (TREE_OPERAND (arg0, 0))))
4400         {
4401           register tree tree01, tree11;
4402           register enum tree_code code01, code11;
4403
4404           tree01 = TREE_OPERAND (arg0, 1);
4405           tree11 = TREE_OPERAND (arg1, 1);
4406           code01 = TREE_CODE (tree01);
4407           code11 = TREE_CODE (tree11);
4408           if (code01 == INTEGER_CST
4409             && code11 == INTEGER_CST
4410             && TREE_INT_CST_HIGH (tree01) == 0
4411             && TREE_INT_CST_HIGH (tree11) == 0
4412             && ((TREE_INT_CST_LOW (tree01) + TREE_INT_CST_LOW (tree11))
4413               == TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (arg0, 0)))))
4414             return build (LROTATE_EXPR, type, TREE_OPERAND (arg0, 0),
4415                       code0 == LSHIFT_EXPR ? tree01 : tree11);
4416           else if (code11 == MINUS_EXPR
4417                 && TREE_CODE (TREE_OPERAND (tree11, 0)) == INTEGER_CST
4418                 && TREE_INT_CST_HIGH (TREE_OPERAND (tree11, 0)) == 0
4419                 && TREE_INT_CST_LOW (TREE_OPERAND (tree11, 0))
4420                   == TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (arg0, 0)))
4421                 && operand_equal_p (tree01, TREE_OPERAND (tree11, 1), 0))
4422             return build (code0 == LSHIFT_EXPR ? LROTATE_EXPR : RROTATE_EXPR,
4423                         type, TREE_OPERAND (arg0, 0), tree01);
4424           else if (code01 == MINUS_EXPR
4425                 && TREE_CODE (TREE_OPERAND (tree01, 0)) == INTEGER_CST
4426                 && TREE_INT_CST_HIGH (TREE_OPERAND (tree01, 0)) == 0
4427                 && TREE_INT_CST_LOW (TREE_OPERAND (tree01, 0))
4428                   == TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (arg0, 0)))
4429                 && operand_equal_p (tree11, TREE_OPERAND (tree01, 1), 0))
4430             return build (code0 != LSHIFT_EXPR ? LROTATE_EXPR : RROTATE_EXPR,
4431                         type, TREE_OPERAND (arg0, 0), tree11);
4432         }
4433
4434       goto associate;
4435       }
4436
4437     case BIT_XOR_EXPR:
4438       if (integer_zerop (arg1))
4439         return non_lvalue (convert (type, arg0));
4440       if (integer_all_onesp (arg1))
4441         return fold (build1 (BIT_NOT_EXPR, type, arg0));
4442       goto associate;
4443
4444     case BIT_AND_EXPR:
4445     bit_and:
4446       if (integer_all_onesp (arg1))
4447         return non_lvalue (convert (type, arg0));
4448       if (integer_zerop (arg1))
4449         return omit_one_operand (type, arg1, arg0);
4450       t1 = distribute_bit_expr (code, type, arg0, arg1);
4451       if (t1 != NULL_TREE)
4452         return t1;
4453       /* Simplify ((int)c & 0x377) into (int)c, if c is unsigned char.  */
4454       if (TREE_CODE (arg0) == INTEGER_CST && TREE_CODE (arg1) == NOP_EXPR
4455           && TREE_UNSIGNED (TREE_TYPE (TREE_OPERAND (arg1, 0))))
4456         {
4457           int prec = TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (arg1, 0)));
4458           if (prec < BITS_PER_WORD && prec < HOST_BITS_PER_WIDE_INT
4459               && (~TREE_INT_CST_LOW (arg0)
4460                   & (((HOST_WIDE_INT) 1 << prec) - 1)) == 0)
4461             return build1 (NOP_EXPR, type, TREE_OPERAND (arg1, 0));
4462         }
4463       if (TREE_CODE (arg1) == INTEGER_CST && TREE_CODE (arg0) == NOP_EXPR
4464           && TREE_UNSIGNED (TREE_TYPE (TREE_OPERAND (arg0, 0))))
4465         {
4466           int prec = TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (arg0, 0)));
4467           if (prec < BITS_PER_WORD && prec < HOST_BITS_PER_WIDE_INT
4468               && (~TREE_INT_CST_LOW (arg1)
4469                   & (((HOST_WIDE_INT) 1 << prec) - 1)) == 0)
4470             return build1 (NOP_EXPR, type, TREE_OPERAND (arg0, 0));
4471         }
4472       goto associate;
4473
4474     case BIT_ANDTC_EXPR:
4475       if (integer_all_onesp (arg0))
4476         return non_lvalue (convert (type, arg1));
4477       if (integer_zerop (arg0))
4478         return omit_one_operand (type, arg0, arg1);
4479       if (TREE_CODE (arg1) == INTEGER_CST)
4480         {
4481           arg1 = fold (build1 (BIT_NOT_EXPR, type, arg1));
4482           code = BIT_AND_EXPR;
4483           goto bit_and;
4484         }
4485       goto binary;
4486
4487     case RDIV_EXPR:
4488       /* In most cases, do nothing with a divide by zero.  */
4489 #if !defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
4490 #ifndef REAL_INFINITY
4491       if (TREE_CODE (arg1) == REAL_CST && real_zerop (arg1))
4492         return t;
4493 #endif
4494 #endif /* not REAL_IS_NOT_DOUBLE, or REAL_ARITHMETIC */
4495
4496       /* In IEEE floating point, x/1 is not equivalent to x for snans.
4497          However, ANSI says we can drop signals, so we can do this anyway.  */
4498       if (real_onep (arg1))
4499         return non_lvalue (convert (type, arg0));
4500
4501       /* If ARG1 is a constant, we can convert this to a multiply by the
4502          reciprocal.  This does not have the same rounding properties,
4503          so only do this if -ffast-math.  We can actually always safely
4504          do it if ARG1 is a power of two, but it's hard to tell if it is
4505          or not in a portable manner.  */
4506       if (TREE_CODE (arg1) == REAL_CST)
4507         {
4508           if (flag_fast_math
4509               && 0 != (tem = const_binop (code, build_real (type, dconst1),
4510                                           arg1, 0)))
4511             return fold (build (MULT_EXPR, type, arg0, tem));
4512           /* Find the reciprocal if optimizing and the result is exact. */
4513           else if (optimize)
4514             {
4515               REAL_VALUE_TYPE r;
4516               r = TREE_REAL_CST (arg1);
4517               if (exact_real_inverse (TYPE_MODE(TREE_TYPE(arg0)), &r))
4518                   {
4519                     tem = build_real (type, r);
4520                     return fold (build (MULT_EXPR, type, arg0, tem));
4521                   }
4522             }
4523         }
4524       goto binary;
4525
4526     case TRUNC_DIV_EXPR:
4527     case ROUND_DIV_EXPR:
4528     case FLOOR_DIV_EXPR:
4529     case CEIL_DIV_EXPR:
4530     case EXACT_DIV_EXPR:
4531       if (integer_onep (arg1))
4532         return non_lvalue (convert (type, arg0));
4533       if (integer_zerop (arg1))
4534         return t;
4535
4536       /* If we have ((a / C1) / C2) where both division are the same type, try
4537          to simplify.  First see if C1 * C2 overflows or not.  */
4538       if (TREE_CODE (arg0) == code && TREE_CODE (arg1) == INTEGER_CST
4539           && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST)
4540         {
4541           tree new_divisor;
4542
4543           new_divisor = const_binop (MULT_EXPR, TREE_OPERAND (arg0, 1), arg1, 0);
4544           tem = const_binop (FLOOR_DIV_EXPR, new_divisor, arg1, 0);
4545
4546           if (TREE_INT_CST_LOW (TREE_OPERAND (arg0, 1)) == TREE_INT_CST_LOW (tem)
4547               && TREE_INT_CST_HIGH (TREE_OPERAND (arg0, 1)) == TREE_INT_CST_HIGH (tem))
4548             {
4549               /* If no overflow, divide by C1*C2.  */
4550               return fold (build (code, type, TREE_OPERAND (arg0, 0), new_divisor));
4551             }
4552         }
4553
4554       /* Look for ((a * C1) / C3) or (((a * C1) + C2) / C3),
4555          where C1 % C3 == 0 or C3 % C1 == 0.  We can simplify these
4556          expressions, which often appear in the offsets or sizes of
4557          objects with a varying size.  Only deal with positive divisors
4558          and multiplicands.   If C2 is negative, we must have C2 % C3 == 0.
4559
4560          Look for NOPs and SAVE_EXPRs inside.  */
4561
4562       if (TREE_CODE (arg1) == INTEGER_CST
4563           && tree_int_cst_sgn (arg1) >= 0)
4564         {
4565           int have_save_expr = 0;
4566           tree c2 = integer_zero_node;
4567           tree xarg0 = arg0;
4568
4569           if (TREE_CODE (xarg0) == SAVE_EXPR && SAVE_EXPR_RTL (xarg0) == 0)
4570             have_save_expr = 1, xarg0 = TREE_OPERAND (xarg0, 0);
4571
4572           STRIP_NOPS (xarg0);
4573
4574           if (TREE_CODE (xarg0) == PLUS_EXPR
4575               && TREE_CODE (TREE_OPERAND (xarg0, 1)) == INTEGER_CST)
4576             c2 = TREE_OPERAND (xarg0, 1), xarg0 = TREE_OPERAND (xarg0, 0);
4577           else if (TREE_CODE (xarg0) == MINUS_EXPR
4578                    && TREE_CODE (TREE_OPERAND (xarg0, 1)) == INTEGER_CST
4579                    /* If we are doing this computation unsigned, the negate
4580                       is incorrect.  */
4581                    && ! TREE_UNSIGNED (type))
4582             {
4583               c2 = fold (build1 (NEGATE_EXPR, type, TREE_OPERAND (xarg0, 1)));
4584               xarg0 = TREE_OPERAND (xarg0, 0);
4585             }
4586
4587           if (TREE_CODE (xarg0) == SAVE_EXPR && SAVE_EXPR_RTL (xarg0) == 0)
4588             have_save_expr = 1, xarg0 = TREE_OPERAND (xarg0, 0);
4589
4590           STRIP_NOPS (xarg0);
4591
4592           if (TREE_CODE (xarg0) == MULT_EXPR
4593               && TREE_CODE (TREE_OPERAND (xarg0, 1)) == INTEGER_CST
4594               && tree_int_cst_sgn (TREE_OPERAND (xarg0, 1)) >= 0
4595               && (integer_zerop (const_binop (TRUNC_MOD_EXPR,
4596                                               TREE_OPERAND (xarg0, 1), arg1, 1))
4597                   || integer_zerop (const_binop (TRUNC_MOD_EXPR, arg1,
4598                                                  TREE_OPERAND (xarg0, 1), 1)))
4599               && (tree_int_cst_sgn (c2) >= 0
4600                   || integer_zerop (const_binop (TRUNC_MOD_EXPR, c2,
4601                                                  arg1, 1))))
4602             {
4603               tree outer_div = integer_one_node;
4604               tree c1 = TREE_OPERAND (xarg0, 1);
4605               tree c3 = arg1;
4606
4607               /* If C3 > C1, set them equal and do a divide by
4608                  C3/C1 at the end of the operation.  */
4609               if (tree_int_cst_lt (c1, c3))
4610                 outer_div = const_binop (code, c3, c1, 0), c3 = c1;
4611
4612               /* The result is A * (C1/C3) + (C2/C3).  */
4613               t = fold (build (PLUS_EXPR, type,
4614                                fold (build (MULT_EXPR, type,
4615                                             TREE_OPERAND (xarg0, 0),
4616                                             const_binop (code, c1, c3, 1))),
4617                                const_binop (code, c2, c3, 1)));
4618
4619               if (! integer_onep (outer_div))
4620                 t = fold (build (code, type, t, convert (type, outer_div)));
4621
4622               if (have_save_expr)
4623                 t = save_expr (t);
4624
4625               return t;
4626             }
4627         }
4628
4629       goto binary;
4630
4631     case CEIL_MOD_EXPR:
4632     case FLOOR_MOD_EXPR:
4633     case ROUND_MOD_EXPR:
4634     case TRUNC_MOD_EXPR:
4635       if (integer_onep (arg1))
4636         return omit_one_operand (type, integer_zero_node, arg0);
4637       if (integer_zerop (arg1))
4638         return t;
4639
4640       /* Look for ((a * C1) % C3) or (((a * C1) + C2) % C3),
4641          where C1 % C3 == 0.  Handle similarly to the division case,
4642          but don't bother with SAVE_EXPRs.  */
4643
4644       if (TREE_CODE (arg1) == INTEGER_CST
4645           && ! integer_zerop (arg1))
4646         {
4647           tree c2 = integer_zero_node;
4648           tree xarg0 = arg0;
4649
4650           if (TREE_CODE (xarg0) == PLUS_EXPR
4651               && TREE_CODE (TREE_OPERAND (xarg0, 1)) == INTEGER_CST)
4652             c2 = TREE_OPERAND (xarg0, 1), xarg0 = TREE_OPERAND (xarg0, 0);
4653           else if (TREE_CODE (xarg0) == MINUS_EXPR
4654                    && TREE_CODE (TREE_OPERAND (xarg0, 1)) == INTEGER_CST
4655                    && ! TREE_UNSIGNED (type))
4656             {
4657               c2 = fold (build1 (NEGATE_EXPR, type, TREE_OPERAND (xarg0, 1)));
4658               xarg0 = TREE_OPERAND (xarg0, 0);
4659             }
4660
4661           STRIP_NOPS (xarg0);
4662
4663           if (TREE_CODE (xarg0) == MULT_EXPR
4664               && TREE_CODE (TREE_OPERAND (xarg0, 1)) == INTEGER_CST
4665               && integer_zerop (const_binop (TRUNC_MOD_EXPR,
4666                                              TREE_OPERAND (xarg0, 1),
4667                                              arg1, 1))
4668               && tree_int_cst_sgn (c2) >= 0)
4669             /* The result is (C2%C3).  */
4670             return omit_one_operand (type, const_binop (code, c2, arg1, 1),
4671                                      TREE_OPERAND (xarg0, 0));
4672         }
4673
4674       goto binary;
4675
4676     case LSHIFT_EXPR:
4677     case RSHIFT_EXPR:
4678     case LROTATE_EXPR:
4679     case RROTATE_EXPR:
4680       if (integer_zerop (arg1))
4681         return non_lvalue (convert (type, arg0));
4682       /* Since negative shift count is not well-defined,
4683          don't try to compute it in the compiler.  */
4684       if (TREE_CODE (arg1) == INTEGER_CST && tree_int_cst_sgn (arg1) < 0)
4685         return t;
4686       /* Rewrite an LROTATE_EXPR by a constant into an
4687          RROTATE_EXPR by a new constant.  */
4688       if (code == LROTATE_EXPR && TREE_CODE (arg1) == INTEGER_CST)
4689         {
4690           TREE_SET_CODE (t, RROTATE_EXPR);
4691           code = RROTATE_EXPR;
4692           TREE_OPERAND (t, 1) = arg1
4693             = const_binop
4694               (MINUS_EXPR,
4695                convert (TREE_TYPE (arg1),
4696                         build_int_2 (GET_MODE_BITSIZE (TYPE_MODE (type)), 0)),
4697                arg1, 0);
4698           if (tree_int_cst_sgn (arg1) < 0)
4699             return t;
4700         }
4701
4702       /* If we have a rotate of a bit operation with the rotate count and
4703          the second operand of the bit operation both constant,
4704          permute the two operations.  */
4705       if (code == RROTATE_EXPR && TREE_CODE (arg1) == INTEGER_CST
4706           && (TREE_CODE (arg0) == BIT_AND_EXPR
4707               || TREE_CODE (arg0) == BIT_ANDTC_EXPR
4708               || TREE_CODE (arg0) == BIT_IOR_EXPR
4709               || TREE_CODE (arg0) == BIT_XOR_EXPR)
4710           && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST)
4711         return fold (build (TREE_CODE (arg0), type,
4712                             fold (build (code, type,
4713                                          TREE_OPERAND (arg0, 0), arg1)),
4714                             fold (build (code, type,
4715                                          TREE_OPERAND (arg0, 1), arg1))));
4716
4717       /* Two consecutive rotates adding up to the width of the mode can
4718          be ignored.  */
4719       if (code == RROTATE_EXPR && TREE_CODE (arg1) == INTEGER_CST
4720           && TREE_CODE (arg0) == RROTATE_EXPR
4721           && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
4722           && TREE_INT_CST_HIGH (arg1) == 0
4723           && TREE_INT_CST_HIGH (TREE_OPERAND (arg0, 1)) == 0
4724           && ((TREE_INT_CST_LOW (arg1)
4725                + TREE_INT_CST_LOW (TREE_OPERAND (arg0, 1)))
4726               == GET_MODE_BITSIZE (TYPE_MODE (type))))
4727         return TREE_OPERAND (arg0, 0);
4728
4729       goto binary;
4730
4731     case MIN_EXPR:
4732       if (operand_equal_p (arg0, arg1, 0))
4733         return arg0;
4734       if (INTEGRAL_TYPE_P (type)
4735           && operand_equal_p (arg1, TYPE_MIN_VALUE (type), 1))
4736         return omit_one_operand (type, arg1, arg0);
4737       goto associate;
4738
4739     case MAX_EXPR:
4740       if (operand_equal_p (arg0, arg1, 0))
4741         return arg0;
4742       if (INTEGRAL_TYPE_P (type)
4743           && operand_equal_p (arg1, TYPE_MAX_VALUE (type), 1))
4744         return omit_one_operand (type, arg1, arg0);
4745       goto associate;
4746
4747     case TRUTH_NOT_EXPR:
4748       /* Note that the operand of this must be an int
4749          and its values must be 0 or 1.
4750          ("true" is a fixed value perhaps depending on the language,
4751          but we don't handle values other than 1 correctly yet.)  */
4752       tem = invert_truthvalue (arg0);
4753       /* Avoid infinite recursion.  */
4754       if (TREE_CODE (tem) == TRUTH_NOT_EXPR)
4755         return t;
4756       return convert (type, tem);
4757
4758     case TRUTH_ANDIF_EXPR:
4759       /* Note that the operands of this must be ints
4760          and their values must be 0 or 1.
4761          ("true" is a fixed value perhaps depending on the language.)  */
4762       /* If first arg is constant zero, return it.  */
4763       if (integer_zerop (arg0))
4764         return arg0;
4765     case TRUTH_AND_EXPR:
4766       /* If either arg is constant true, drop it.  */
4767       if (TREE_CODE (arg0) == INTEGER_CST && ! integer_zerop (arg0))
4768         return non_lvalue (arg1);
4769       if (TREE_CODE (arg1) == INTEGER_CST && ! integer_zerop (arg1))
4770         return non_lvalue (arg0);
4771       /* If second arg is constant zero, result is zero, but first arg
4772          must be evaluated.  */
4773       if (integer_zerop (arg1))
4774         return omit_one_operand (type, arg1, arg0);
4775       /* Likewise for first arg, but note that only the TRUTH_AND_EXPR
4776          case will be handled here.  */
4777       if (integer_zerop (arg0))
4778         return omit_one_operand (type, arg0, arg1);
4779
4780     truth_andor:
4781       /* We only do these simplifications if we are optimizing.  */
4782       if (!optimize)
4783         return t;
4784
4785       /* Check for things like (A || B) && (A || C).  We can convert this
4786          to A || (B && C).  Note that either operator can be any of the four
4787          truth and/or operations and the transformation will still be
4788          valid.   Also note that we only care about order for the
4789          ANDIF and ORIF operators.  */
4790       if (TREE_CODE (arg0) == TREE_CODE (arg1)
4791           && (TREE_CODE (arg0) == TRUTH_ANDIF_EXPR
4792               || TREE_CODE (arg0) == TRUTH_ORIF_EXPR
4793               || TREE_CODE (arg0) == TRUTH_AND_EXPR
4794               || TREE_CODE (arg0) == TRUTH_OR_EXPR))
4795         {
4796           tree a00 = TREE_OPERAND (arg0, 0);
4797           tree a01 = TREE_OPERAND (arg0, 1);
4798           tree a10 = TREE_OPERAND (arg1, 0);
4799           tree a11 = TREE_OPERAND (arg1, 1);
4800           int commutative = ((TREE_CODE (arg0) == TRUTH_OR_EXPR
4801                               || TREE_CODE (arg0) == TRUTH_AND_EXPR)
4802                              && (code == TRUTH_AND_EXPR
4803                                  || code == TRUTH_OR_EXPR));
4804
4805           if (operand_equal_p (a00, a10, 0))
4806             return fold (build (TREE_CODE (arg0), type, a00,
4807                                 fold (build (code, type, a01, a11))));
4808           else if (commutative && operand_equal_p (a00, a11, 0))
4809             return fold (build (TREE_CODE (arg0), type, a00,
4810                                 fold (build (code, type, a01, a10))));
4811           else if (commutative && operand_equal_p (a01, a10, 0))
4812             return fold (build (TREE_CODE (arg0), type, a01,
4813                                 fold (build (code, type, a00, a11))));
4814
4815           /* This case if tricky because we must either have commutative
4816              operators or else A10 must not have side-effects.  */
4817
4818           else if ((commutative || ! TREE_SIDE_EFFECTS (a10))
4819                    && operand_equal_p (a01, a11, 0))
4820             return fold (build (TREE_CODE (arg0), type,
4821                                 fold (build (code, type, a00, a10)),
4822                                 a01));
4823         }
4824
4825       /* See if we can build a range comparison.  */
4826       if (0 != (tem = fold_range_test (t)))
4827         return tem;
4828
4829       /* Check for the possibility of merging component references.  If our
4830          lhs is another similar operation, try to merge its rhs with our
4831          rhs.  Then try to merge our lhs and rhs.  */
4832       if (TREE_CODE (arg0) == code
4833           && 0 != (tem = fold_truthop (code, type,
4834                                        TREE_OPERAND (arg0, 1), arg1)))
4835         return fold (build (code, type, TREE_OPERAND (arg0, 0), tem));
4836
4837       if ((tem = fold_truthop (code, type, arg0, arg1)) != 0)
4838         return tem;
4839
4840       return t;
4841
4842     case TRUTH_ORIF_EXPR:
4843       /* Note that the operands of this must be ints
4844          and their values must be 0 or true.
4845          ("true" is a fixed value perhaps depending on the language.)  */
4846       /* If first arg is constant true, return it.  */
4847       if (TREE_CODE (arg0) == INTEGER_CST && ! integer_zerop (arg0))
4848         return arg0;
4849     case TRUTH_OR_EXPR:
4850       /* If either arg is constant zero, drop it.  */
4851       if (TREE_CODE (arg0) == INTEGER_CST && integer_zerop (arg0))
4852         return non_lvalue (arg1);
4853       if (TREE_CODE (arg1) == INTEGER_CST && integer_zerop (arg1))
4854         return non_lvalue (arg0);
4855       /* If second arg is constant true, result is true, but we must
4856          evaluate first arg.  */
4857       if (TREE_CODE (arg1) == INTEGER_CST && ! integer_zerop (arg1))
4858         return omit_one_operand (type, arg1, arg0);
4859       /* Likewise for first arg, but note this only occurs here for
4860          TRUTH_OR_EXPR.  */
4861       if (TREE_CODE (arg0) == INTEGER_CST && ! integer_zerop (arg0))
4862         return omit_one_operand (type, arg0, arg1);
4863       goto truth_andor;
4864
4865     case TRUTH_XOR_EXPR:
4866       /* If either arg is constant zero, drop it.  */
4867       if (integer_zerop (arg0))
4868         return non_lvalue (arg1);
4869       if (integer_zerop (arg1))
4870         return non_lvalue (arg0);
4871       /* If either arg is constant true, this is a logical inversion.  */
4872       if (integer_onep (arg0))
4873         return non_lvalue (invert_truthvalue (arg1));
4874       if (integer_onep (arg1))
4875         return non_lvalue (invert_truthvalue (arg0));
4876       return t;
4877
4878     case EQ_EXPR:
4879     case NE_EXPR:
4880     case LT_EXPR:
4881     case GT_EXPR:
4882     case LE_EXPR:
4883     case GE_EXPR:
4884       /* If one arg is a constant integer, put it last.  */
4885       if (TREE_CODE (arg0) == INTEGER_CST
4886           && TREE_CODE (arg1) != INTEGER_CST)
4887         {
4888           TREE_OPERAND (t, 0) = arg1;
4889           TREE_OPERAND (t, 1) = arg0;
4890           arg0 = TREE_OPERAND (t, 0);
4891           arg1 = TREE_OPERAND (t, 1);
4892           code = swap_tree_comparison (code);
4893           TREE_SET_CODE (t, code);
4894         }
4895
4896       /* Convert foo++ == CONST into ++foo == CONST + INCR.
4897          First, see if one arg is constant; find the constant arg
4898          and the other one.  */
4899       {
4900         tree constop = 0, varop;
4901         int constopnum = -1;
4902
4903         if (TREE_CONSTANT (arg1))
4904           constopnum = 1, constop = arg1, varop = arg0;
4905         if (TREE_CONSTANT (arg0))
4906           constopnum = 0, constop = arg0, varop = arg1;
4907
4908         if (constop && TREE_CODE (varop) == POSTINCREMENT_EXPR)
4909           {
4910             /* This optimization is invalid for ordered comparisons
4911                if CONST+INCR overflows or if foo+incr might overflow.
4912                This optimization is invalid for floating point due to rounding.
4913                For pointer types we assume overflow doesn't happen.  */
4914             if (TREE_CODE (TREE_TYPE (varop)) == POINTER_TYPE
4915                 || (! FLOAT_TYPE_P (TREE_TYPE (varop))
4916                     && (code == EQ_EXPR || code == NE_EXPR)))
4917               {
4918                 tree newconst
4919                   = fold (build (PLUS_EXPR, TREE_TYPE (varop),
4920                                  constop, TREE_OPERAND (varop, 1)));
4921                 TREE_SET_CODE (varop, PREINCREMENT_EXPR);
4922
4923                 /* If VAROP is a reference to a bitfield, we must mask
4924                    the constant by the width of the field.  */
4925                 if (TREE_CODE (TREE_OPERAND (varop, 0)) == COMPONENT_REF
4926                     && DECL_BIT_FIELD(TREE_OPERAND
4927                                       (TREE_OPERAND (varop, 0), 1)))
4928                   {
4929                     int size
4930                       = TREE_INT_CST_LOW (DECL_SIZE
4931                                           (TREE_OPERAND
4932                                            (TREE_OPERAND (varop, 0), 1)));
4933
4934                     newconst = fold (build (BIT_AND_EXPR,
4935                                             TREE_TYPE (varop), newconst,
4936                                             convert (TREE_TYPE (varop),
4937                                                      build_int_2 (size, 0))));
4938                   }
4939
4940
4941                 t = build (code, type, TREE_OPERAND (t, 0),
4942                            TREE_OPERAND (t, 1));
4943                 TREE_OPERAND (t, constopnum) = newconst;
4944                 return t;
4945               }
4946           }
4947         else if (constop && TREE_CODE (varop) == POSTDECREMENT_EXPR)
4948           {
4949             if (TREE_CODE (TREE_TYPE (varop)) == POINTER_TYPE
4950                 || (! FLOAT_TYPE_P (TREE_TYPE (varop))
4951                     && (code == EQ_EXPR || code == NE_EXPR)))
4952               {
4953                 tree newconst
4954                   = fold (build (MINUS_EXPR, TREE_TYPE (varop),
4955                                  constop, TREE_OPERAND (varop, 1)));
4956                 TREE_SET_CODE (varop, PREDECREMENT_EXPR);
4957
4958                 if (TREE_CODE (TREE_OPERAND (varop, 0)) == COMPONENT_REF
4959                     && DECL_BIT_FIELD(TREE_OPERAND
4960                                       (TREE_OPERAND (varop, 0), 1)))
4961                   {
4962                     int size
4963                       = TREE_INT_CST_LOW (DECL_SIZE
4964                                           (TREE_OPERAND
4965                                            (TREE_OPERAND (varop, 0), 1)));
4966
4967                     newconst = fold (build (BIT_AND_EXPR,
4968                                             TREE_TYPE (varop), newconst,
4969                                             convert (TREE_TYPE (varop),
4970                                                      build_int_2 (size, 0))));
4971                   }
4972
4973
4974                 t = build (code, type, TREE_OPERAND (t, 0),
4975                            TREE_OPERAND (t, 1));
4976                 TREE_OPERAND (t, constopnum) = newconst;
4977                 return t;
4978               }
4979           }
4980       }
4981
4982       /* Change X >= CST to X > (CST - 1) if CST is positive.  */
4983       if (TREE_CODE (arg1) == INTEGER_CST
4984           && TREE_CODE (arg0) != INTEGER_CST
4985           && tree_int_cst_sgn (arg1) > 0)
4986         {
4987           switch (TREE_CODE (t))
4988             {
4989             case GE_EXPR:
4990               code = GT_EXPR;
4991               arg1 = const_binop (MINUS_EXPR, arg1, integer_one_node, 0);
4992               t = build (code, type, TREE_OPERAND (t, 0), arg1);
4993               break;
4994
4995             case LT_EXPR:
4996               code = LE_EXPR;
4997               arg1 = const_binop (MINUS_EXPR, arg1, integer_one_node, 0);
4998               t = build (code, type, TREE_OPERAND (t, 0), arg1);
4999               break;
5000             }
5001         }
5002
5003       /* If this is an EQ or NE comparison with zero and ARG0 is
5004          (1 << foo) & bar, convert it to (bar >> foo) & 1.  Both require
5005          two operations, but the latter can be done in one less insn
5006          one machine that have only two-operand insns or on which a
5007          constant cannot be the first operand.  */
5008       if (integer_zerop (arg1) && (code == EQ_EXPR || code == NE_EXPR)
5009           && TREE_CODE (arg0) == BIT_AND_EXPR)
5010         {
5011           if (TREE_CODE (TREE_OPERAND (arg0, 0)) == LSHIFT_EXPR
5012               && integer_onep (TREE_OPERAND (TREE_OPERAND (arg0, 0), 0)))
5013             return
5014               fold (build (code, type,
5015                            build (BIT_AND_EXPR, TREE_TYPE (arg0),
5016                                   build (RSHIFT_EXPR,
5017                                          TREE_TYPE (TREE_OPERAND (arg0, 0)),
5018                                          TREE_OPERAND (arg0, 1),
5019                                          TREE_OPERAND (TREE_OPERAND (arg0, 0), 1)),
5020                                   convert (TREE_TYPE (arg0),
5021                                            integer_one_node)),
5022                            arg1));
5023           else if (TREE_CODE (TREE_OPERAND (arg0, 1)) == LSHIFT_EXPR
5024                    && integer_onep (TREE_OPERAND (TREE_OPERAND (arg0, 1), 0)))
5025             return
5026               fold (build (code, type,
5027                            build (BIT_AND_EXPR, TREE_TYPE (arg0),
5028                                   build (RSHIFT_EXPR,
5029                                          TREE_TYPE (TREE_OPERAND (arg0, 1)),
5030                                          TREE_OPERAND (arg0, 0),
5031                                          TREE_OPERAND (TREE_OPERAND (arg0, 1), 1)),
5032                                   convert (TREE_TYPE (arg0),
5033                                            integer_one_node)),
5034                            arg1));
5035         }
5036
5037       /* If this is an NE or EQ comparison of zero against the result of a
5038          signed MOD operation whose second operand is a power of 2, make
5039          the MOD operation unsigned since it is simpler and equivalent.  */
5040       if ((code == NE_EXPR || code == EQ_EXPR)
5041           && integer_zerop (arg1)
5042           && ! TREE_UNSIGNED (TREE_TYPE (arg0))
5043           && (TREE_CODE (arg0) == TRUNC_MOD_EXPR
5044               || TREE_CODE (arg0) == CEIL_MOD_EXPR
5045               || TREE_CODE (arg0) == FLOOR_MOD_EXPR
5046               || TREE_CODE (arg0) == ROUND_MOD_EXPR)
5047           && integer_pow2p (TREE_OPERAND (arg0, 1)))
5048         {
5049           tree newtype = unsigned_type (TREE_TYPE (arg0));
5050           tree newmod = build (TREE_CODE (arg0), newtype,
5051                                convert (newtype, TREE_OPERAND (arg0, 0)),
5052                                convert (newtype, TREE_OPERAND (arg0, 1)));
5053
5054           return build (code, type, newmod, convert (newtype, arg1));
5055         }
5056
5057       /* If this is an NE comparison of zero with an AND of one, remove the
5058          comparison since the AND will give the correct value.  */
5059       if (code == NE_EXPR && integer_zerop (arg1)
5060           && TREE_CODE (arg0) == BIT_AND_EXPR
5061           && integer_onep (TREE_OPERAND (arg0, 1)))
5062         return convert (type, arg0);
5063
5064       /* If we have (A & C) == C where C is a power of 2, convert this into
5065          (A & C) != 0.  Similarly for NE_EXPR.  */
5066       if ((code == EQ_EXPR || code == NE_EXPR)
5067           && TREE_CODE (arg0) == BIT_AND_EXPR
5068           && integer_pow2p (TREE_OPERAND (arg0, 1))
5069           && operand_equal_p (TREE_OPERAND (arg0, 1), arg1, 0))
5070         return build (code == EQ_EXPR ? NE_EXPR : EQ_EXPR, type,
5071                       arg0, integer_zero_node);
5072
5073       /* If X is unsigned, convert X < (1 << Y) into X >> Y == 0
5074          and similarly for >= into !=.  */
5075       if ((code == LT_EXPR || code == GE_EXPR)
5076           && TREE_UNSIGNED (TREE_TYPE (arg0))
5077           && TREE_CODE (arg1) == LSHIFT_EXPR
5078           && integer_onep (TREE_OPERAND (arg1, 0)))
5079         return build (code == LT_EXPR ? EQ_EXPR : NE_EXPR, type,
5080                       build (RSHIFT_EXPR, TREE_TYPE (arg0), arg0,
5081                              TREE_OPERAND (arg1, 1)),
5082                       convert (TREE_TYPE (arg0), integer_zero_node));
5083
5084       else if ((code == LT_EXPR || code == GE_EXPR)
5085                && TREE_UNSIGNED (TREE_TYPE (arg0))
5086                && (TREE_CODE (arg1) == NOP_EXPR
5087                    || TREE_CODE (arg1) == CONVERT_EXPR)
5088                && TREE_CODE (TREE_OPERAND (arg1, 0)) == LSHIFT_EXPR
5089                && integer_onep (TREE_OPERAND (TREE_OPERAND (arg1, 0), 0)))
5090         return
5091           build (code == LT_EXPR ? EQ_EXPR : NE_EXPR, type,
5092                  convert (TREE_TYPE (arg0),
5093                           build (RSHIFT_EXPR, TREE_TYPE (arg0), arg0,
5094                                  TREE_OPERAND (TREE_OPERAND (arg1, 0), 1))),
5095                  convert (TREE_TYPE (arg0), integer_zero_node));
5096
5097       /* Simplify comparison of something with itself.  (For IEEE
5098          floating-point, we can only do some of these simplifications.)  */
5099       if (operand_equal_p (arg0, arg1, 0))
5100         {
5101           switch (code)
5102             {
5103             case EQ_EXPR:
5104             case GE_EXPR:
5105             case LE_EXPR:
5106               if (INTEGRAL_TYPE_P (TREE_TYPE (arg0)))
5107                 {
5108                   if (type == integer_type_node)
5109                     return integer_one_node;
5110
5111                   t = build_int_2 (1, 0);
5112                   TREE_TYPE (t) = type;
5113                   return t;
5114                 }
5115               code = EQ_EXPR;
5116               TREE_SET_CODE (t, code);
5117               break;
5118
5119             case NE_EXPR:
5120               /* For NE, we can only do this simplification if integer.  */
5121               if (! INTEGRAL_TYPE_P (TREE_TYPE (arg0)))
5122                 break;
5123               /* ... fall through ...  */
5124             case GT_EXPR:
5125             case LT_EXPR:
5126               if (type == integer_type_node)
5127                 return integer_zero_node;
5128
5129               t = build_int_2 (0, 0);
5130               TREE_TYPE (t) = type;
5131               return t;
5132             }
5133         }
5134
5135       /* An unsigned comparison against 0 can be simplified.  */
5136       if (integer_zerop (arg1)
5137           && (INTEGRAL_TYPE_P (TREE_TYPE (arg1))
5138               || TREE_CODE (TREE_TYPE (arg1)) == POINTER_TYPE)
5139           && TREE_UNSIGNED (TREE_TYPE (arg1)))
5140         {
5141           switch (TREE_CODE (t))
5142             {
5143             case GT_EXPR:
5144               code = NE_EXPR;
5145               TREE_SET_CODE (t, NE_EXPR);
5146               break;
5147             case LE_EXPR:
5148               code = EQ_EXPR;
5149               TREE_SET_CODE (t, EQ_EXPR);
5150               break;
5151             case GE_EXPR:
5152               return omit_one_operand (type,
5153                                        convert (type, integer_one_node),
5154                                        arg0);
5155             case LT_EXPR:
5156               return omit_one_operand (type,
5157                                        convert (type, integer_zero_node),
5158                                        arg0);
5159             }
5160         }
5161
5162       /* If we are comparing an expression that just has comparisons
5163          of two integer values, arithmetic expressions of those comparisons,
5164          and constants, we can simplify it.  There are only three cases
5165          to check: the two values can either be equal, the first can be
5166          greater, or the second can be greater.  Fold the expression for
5167          those three values.  Since each value must be 0 or 1, we have
5168          eight possibilities, each of which corresponds to the constant 0
5169          or 1 or one of the six possible comparisons.
5170
5171          This handles common cases like (a > b) == 0 but also handles
5172          expressions like  ((x > y) - (y > x)) > 0, which supposedly
5173          occur in macroized code.  */
5174
5175       if (TREE_CODE (arg1) == INTEGER_CST && TREE_CODE (arg0) != INTEGER_CST)
5176         {
5177           tree cval1 = 0, cval2 = 0;
5178           int save_p = 0;
5179
5180           if (twoval_comparison_p (arg0, &cval1, &cval2, &save_p)
5181               /* Don't handle degenerate cases here; they should already
5182                  have been handled anyway.  */
5183               && cval1 != 0 && cval2 != 0
5184               && ! (TREE_CONSTANT (cval1) && TREE_CONSTANT (cval2))
5185               && TREE_TYPE (cval1) == TREE_TYPE (cval2)
5186               && INTEGRAL_TYPE_P (TREE_TYPE (cval1))
5187               && ! operand_equal_p (TYPE_MIN_VALUE (TREE_TYPE (cval1)),
5188                                     TYPE_MAX_VALUE (TREE_TYPE (cval2)), 0))
5189             {
5190               tree maxval = TYPE_MAX_VALUE (TREE_TYPE (cval1));
5191               tree minval = TYPE_MIN_VALUE (TREE_TYPE (cval1));
5192
5193               /* We can't just pass T to eval_subst in case cval1 or cval2
5194                  was the same as ARG1.  */
5195
5196               tree high_result
5197                 = fold (build (code, type,
5198                                eval_subst (arg0, cval1, maxval, cval2, minval),
5199                                arg1));
5200               tree equal_result
5201                 = fold (build (code, type,
5202                                eval_subst (arg0, cval1, maxval, cval2, maxval),
5203                                arg1));
5204               tree low_result
5205                 = fold (build (code, type,
5206                                eval_subst (arg0, cval1, minval, cval2, maxval),
5207                                arg1));
5208
5209               /* All three of these results should be 0 or 1.  Confirm they
5210                  are.  Then use those values to select the proper code
5211                  to use.  */
5212
5213               if ((integer_zerop (high_result)
5214                    || integer_onep (high_result))
5215                   && (integer_zerop (equal_result)
5216                       || integer_onep (equal_result))
5217                   && (integer_zerop (low_result)
5218                       || integer_onep (low_result)))
5219                 {
5220                   /* Make a 3-bit mask with the high-order bit being the
5221                      value for `>', the next for '=', and the low for '<'.  */
5222                   switch ((integer_onep (high_result) * 4)
5223                           + (integer_onep (equal_result) * 2)
5224                           + integer_onep (low_result))
5225                     {
5226                     case 0:
5227                       /* Always false.  */
5228                       return omit_one_operand (type, integer_zero_node, arg0);
5229                     case 1:
5230                       code = LT_EXPR;
5231                       break;
5232                     case 2:
5233                       code = EQ_EXPR;
5234                       break;
5235                     case 3:
5236                       code = LE_EXPR;
5237                       break;
5238                     case 4:
5239                       code = GT_EXPR;
5240                       break;
5241                     case 5:
5242                       code = NE_EXPR;
5243                       break;
5244                     case 6:
5245                       code = GE_EXPR;
5246                       break;
5247                     case 7:
5248                       /* Always true.  */
5249                       return omit_one_operand (type, integer_one_node, arg0);
5250                     }
5251
5252                   t = build (code, type, cval1, cval2);
5253                   if (save_p)
5254                     return save_expr (t);
5255                   else
5256                     return fold (t);
5257                 }
5258             }
5259         }
5260
5261       /* If this is a comparison of a field, we may be able to simplify it.  */
5262       if ((TREE_CODE (arg0) == COMPONENT_REF
5263            || TREE_CODE (arg0) == BIT_FIELD_REF)
5264           && (code == EQ_EXPR || code == NE_EXPR)
5265           /* Handle the constant case even without -O
5266              to make sure the warnings are given.  */
5267           && (optimize || TREE_CODE (arg1) == INTEGER_CST))
5268         {
5269           t1 = optimize_bit_field_compare (code, type, arg0, arg1);
5270           return t1 ? t1 : t;
5271         }
5272
5273       /* If this is a comparison of complex values and either or both
5274          sizes are a COMPLEX_EXPR, it is best to split up the comparisons
5275          and join them with a TRUTH_ANDIF_EXPR or TRUTH_ORIF_EXPR.  This
5276          may prevent needless evaluations.  */
5277       if ((code == EQ_EXPR || code == NE_EXPR)
5278           && TREE_CODE (TREE_TYPE (arg0)) == COMPLEX_TYPE
5279           && (TREE_CODE (arg0) == COMPLEX_EXPR
5280               || TREE_CODE (arg1) == COMPLEX_EXPR))
5281         {
5282           tree subtype = TREE_TYPE (TREE_TYPE (arg0));
5283           tree real0 = fold (build1 (REALPART_EXPR, subtype, arg0));
5284           tree imag0 = fold (build1 (IMAGPART_EXPR, subtype, arg0));
5285           tree real1 = fold (build1 (REALPART_EXPR, subtype, arg1));
5286           tree imag1 = fold (build1 (IMAGPART_EXPR, subtype, arg1));
5287
5288           return fold (build ((code == EQ_EXPR ? TRUTH_ANDIF_EXPR
5289                                : TRUTH_ORIF_EXPR),
5290                               type,
5291                               fold (build (code, type, real0, real1)),
5292                               fold (build (code, type, imag0, imag1))));
5293         }
5294
5295       /* From here on, the only cases we handle are when the result is
5296          known to be a constant.
5297
5298          To compute GT, swap the arguments and do LT.
5299          To compute GE, do LT and invert the result.
5300          To compute LE, swap the arguments, do LT and invert the result.
5301          To compute NE, do EQ and invert the result.
5302
5303          Therefore, the code below must handle only EQ and LT.  */
5304
5305       if (code == LE_EXPR || code == GT_EXPR)
5306         {
5307           tem = arg0, arg0 = arg1, arg1 = tem;
5308           code = swap_tree_comparison (code);
5309         }
5310
5311       /* Note that it is safe to invert for real values here because we
5312          will check below in the one case that it matters.  */
5313
5314       invert = 0;
5315       if (code == NE_EXPR || code == GE_EXPR)
5316         {
5317           invert = 1;
5318           code = invert_tree_comparison (code);
5319         }
5320
5321       /* Compute a result for LT or EQ if args permit;
5322          otherwise return T.  */
5323       if (TREE_CODE (arg0) == INTEGER_CST && TREE_CODE (arg1) == INTEGER_CST)
5324         {
5325           if (code == EQ_EXPR)
5326             t1 = build_int_2 ((TREE_INT_CST_LOW (arg0)
5327                                == TREE_INT_CST_LOW (arg1))
5328                               && (TREE_INT_CST_HIGH (arg0)
5329                                   == TREE_INT_CST_HIGH (arg1)),
5330                               0);
5331           else
5332             t1 = build_int_2 ((TREE_UNSIGNED (TREE_TYPE (arg0))
5333                                ? INT_CST_LT_UNSIGNED (arg0, arg1)
5334                                : INT_CST_LT (arg0, arg1)),
5335                               0);
5336         }
5337
5338 #if 0 /* This is no longer useful, but breaks some real code.  */
5339       /* Assume a nonexplicit constant cannot equal an explicit one,
5340          since such code would be undefined anyway.
5341          Exception: on sysvr4, using #pragma weak,
5342          a label can come out as 0.  */
5343       else if (TREE_CODE (arg1) == INTEGER_CST
5344                && !integer_zerop (arg1)
5345                && TREE_CONSTANT (arg0)
5346                && TREE_CODE (arg0) == ADDR_EXPR
5347                && code == EQ_EXPR)
5348         t1 = build_int_2 (0, 0);
5349 #endif
5350       /* Two real constants can be compared explicitly.  */
5351       else if (TREE_CODE (arg0) == REAL_CST && TREE_CODE (arg1) == REAL_CST)
5352         {
5353           /* If either operand is a NaN, the result is false with two
5354              exceptions: First, an NE_EXPR is true on NaNs, but that case
5355              is already handled correctly since we will be inverting the
5356              result for NE_EXPR.  Second, if we had inverted a LE_EXPR
5357              or a GE_EXPR into a LT_EXPR, we must return true so that it
5358              will be inverted into false.  */
5359
5360           if (REAL_VALUE_ISNAN (TREE_REAL_CST (arg0))
5361               || REAL_VALUE_ISNAN (TREE_REAL_CST (arg1)))
5362             t1 = build_int_2 (invert && code == LT_EXPR, 0);
5363
5364           else if (code == EQ_EXPR)
5365             t1 = build_int_2 (REAL_VALUES_EQUAL (TREE_REAL_CST (arg0),
5366                                                  TREE_REAL_CST (arg1)),
5367                               0);
5368           else
5369             t1 = build_int_2 (REAL_VALUES_LESS (TREE_REAL_CST (arg0),
5370                                                 TREE_REAL_CST (arg1)),
5371                               0);
5372         }
5373
5374       if (t1 == NULL_TREE)
5375         return t;
5376
5377       if (invert)
5378         TREE_INT_CST_LOW (t1) ^= 1;
5379
5380       TREE_TYPE (t1) = type;
5381       return t1;
5382
5383     case COND_EXPR:
5384       /* Pedantic ANSI C says that a conditional expression is never an lvalue,
5385          so all simple results must be passed through pedantic_non_lvalue.  */
5386       if (TREE_CODE (arg0) == INTEGER_CST)
5387         return pedantic_non_lvalue
5388           (TREE_OPERAND (t, (integer_zerop (arg0) ? 2 : 1)));
5389       else if (operand_equal_p (arg1, TREE_OPERAND (expr, 2), 0))
5390         return pedantic_omit_one_operand (type, arg1, arg0);
5391
5392       /* If the second operand is zero, invert the comparison and swap
5393          the second and third operands.  Likewise if the second operand
5394          is constant and the third is not or if the third operand is
5395          equivalent to the first operand of the comparison.  */
5396
5397       if (integer_zerop (arg1)
5398           || (TREE_CONSTANT (arg1) && ! TREE_CONSTANT (TREE_OPERAND (t, 2)))
5399           || (TREE_CODE_CLASS (TREE_CODE (arg0)) == '<'
5400               && operand_equal_for_comparison_p (TREE_OPERAND (arg0, 0),
5401                                                  TREE_OPERAND (t, 2),
5402                                                  TREE_OPERAND (arg0, 1))))
5403         {
5404           /* See if this can be inverted.  If it can't, possibly because
5405              it was a floating-point inequality comparison, don't do
5406              anything.  */
5407           tem = invert_truthvalue (arg0);
5408
5409           if (TREE_CODE (tem) != TRUTH_NOT_EXPR)
5410             {
5411               t = build (code, type, tem,
5412                          TREE_OPERAND (t, 2), TREE_OPERAND (t, 1));
5413               arg0 = tem;
5414               arg1 = TREE_OPERAND (t, 2);
5415               STRIP_NOPS (arg1);
5416             }
5417         }
5418
5419       /* If we have A op B ? A : C, we may be able to convert this to a
5420          simpler expression, depending on the operation and the values
5421          of B and C.  IEEE floating point prevents this though,
5422          because A or B might be -0.0 or a NaN.  */
5423
5424       if (TREE_CODE_CLASS (TREE_CODE (arg0)) == '<'
5425           && (TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
5426               || ! FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (arg0, 0)))
5427               || flag_fast_math)
5428           && operand_equal_for_comparison_p (TREE_OPERAND (arg0, 0),
5429                                              arg1, TREE_OPERAND (arg0, 1)))
5430         {
5431           tree arg2 = TREE_OPERAND (t, 2);
5432           enum tree_code comp_code = TREE_CODE (arg0);
5433
5434           STRIP_NOPS (arg2);
5435
5436           /* If we have A op 0 ? A : -A, this is A, -A, abs (A), or abs (-A),
5437              depending on the comparison operation.  */
5438           if ((FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (arg0, 1)))
5439                ? real_zerop (TREE_OPERAND (arg0, 1))
5440                : integer_zerop (TREE_OPERAND (arg0, 1)))
5441               && TREE_CODE (arg2) == NEGATE_EXPR
5442               && operand_equal_p (TREE_OPERAND (arg2, 0), arg1, 0))
5443             switch (comp_code)
5444               {
5445               case EQ_EXPR:
5446                 return pedantic_non_lvalue
5447                   (fold (build1 (NEGATE_EXPR, type, arg1)));
5448               case NE_EXPR:
5449                 return pedantic_non_lvalue (convert (type, arg1));
5450               case GE_EXPR:
5451               case GT_EXPR:
5452                 return pedantic_non_lvalue
5453                   (convert (type, fold (build1 (ABS_EXPR,
5454                                                 TREE_TYPE (arg1), arg1))));
5455               case LE_EXPR:
5456               case LT_EXPR:
5457                 return pedantic_non_lvalue
5458                   (fold (build1 (NEGATE_EXPR, type,
5459                                  convert (type,
5460                                           fold (build1 (ABS_EXPR,
5461                                                         TREE_TYPE (arg1),
5462                                                         arg1))))));
5463               }
5464
5465           /* If this is A != 0 ? A : 0, this is simply A.  For ==, it is
5466              always zero.  */
5467
5468           if (integer_zerop (TREE_OPERAND (arg0, 1)) && integer_zerop (arg2))
5469             {
5470               if (comp_code == NE_EXPR)
5471                 return pedantic_non_lvalue (convert (type, arg1));
5472               else if (comp_code == EQ_EXPR)
5473                 return pedantic_non_lvalue (convert (type, integer_zero_node));
5474             }
5475
5476           /* If this is A op B ? A : B, this is either A, B, min (A, B),
5477              or max (A, B), depending on the operation.  */
5478
5479           if (operand_equal_for_comparison_p (TREE_OPERAND (arg0, 1),
5480                                               arg2, TREE_OPERAND (arg0, 0)))
5481             {
5482               tree comp_op0 = TREE_OPERAND (arg0, 0);
5483               tree comp_op1 = TREE_OPERAND (arg0, 1);
5484               tree comp_type = TREE_TYPE (comp_op0);
5485
5486               switch (comp_code)
5487                 {
5488                 case EQ_EXPR:
5489                   return pedantic_non_lvalue (convert (type, arg2));
5490                 case NE_EXPR:
5491                   return pedantic_non_lvalue (convert (type, arg1));
5492                 case LE_EXPR:
5493                 case LT_EXPR:
5494                   return pedantic_non_lvalue
5495                     (convert (type, (fold (build (MIN_EXPR, comp_type,
5496                                                   comp_op0, comp_op1)))));
5497                 case GE_EXPR:
5498                 case GT_EXPR:
5499                   return pedantic_non_lvalue
5500                     (convert (type, fold (build (MAX_EXPR, comp_type,
5501                                                  comp_op0, comp_op1))));
5502                 }
5503             }
5504
5505           /* If this is A op C1 ? A : C2 with C1 and C2 constant integers,
5506              we might still be able to simplify this.  For example,
5507              if C1 is one less or one more than C2, this might have started
5508              out as a MIN or MAX and been transformed by this function.
5509              Only good for INTEGER_TYPEs, because we need TYPE_MAX_VALUE.  */
5510
5511           if (INTEGRAL_TYPE_P (type)
5512               && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
5513               && TREE_CODE (arg2) == INTEGER_CST)
5514             switch (comp_code)
5515               {
5516               case EQ_EXPR:
5517                 /* We can replace A with C1 in this case.  */
5518                 arg1 = convert (type, TREE_OPERAND (arg0, 1));
5519                 t = build (code, type, TREE_OPERAND (t, 0), arg1,
5520                            TREE_OPERAND (t, 2));
5521                 break;
5522
5523               case LT_EXPR:
5524                 /* If C1 is C2 + 1, this is min(A, C2).  */
5525                 if (! operand_equal_p (arg2, TYPE_MAX_VALUE (type), 1)
5526                     && operand_equal_p (TREE_OPERAND (arg0, 1),
5527                                         const_binop (PLUS_EXPR, arg2,
5528                                                      integer_one_node, 0), 1))
5529                   return pedantic_non_lvalue
5530                     (fold (build (MIN_EXPR, type, arg1, arg2)));
5531                 break;
5532
5533               case LE_EXPR:
5534                 /* If C1 is C2 - 1, this is min(A, C2).  */
5535                 if (! operand_equal_p (arg2, TYPE_MIN_VALUE (type), 1)
5536                     && operand_equal_p (TREE_OPERAND (arg0, 1),
5537                                         const_binop (MINUS_EXPR, arg2,
5538                                                      integer_one_node, 0), 1))
5539                   return pedantic_non_lvalue
5540                     (fold (build (MIN_EXPR, type, arg1, arg2)));
5541                 break;
5542
5543               case GT_EXPR:
5544                 /* If C1 is C2 - 1, this is max(A, C2).  */
5545                 if (! operand_equal_p (arg2, TYPE_MIN_VALUE (type), 1)
5546                     && operand_equal_p (TREE_OPERAND (arg0, 1),
5547                                         const_binop (MINUS_EXPR, arg2,
5548                                                      integer_one_node, 0), 1))
5549                   return pedantic_non_lvalue
5550                     (fold (build (MAX_EXPR, type, arg1, arg2)));
5551                 break;
5552
5553               case GE_EXPR:
5554                 /* If C1 is C2 + 1, this is max(A, C2).  */
5555                 if (! operand_equal_p (arg2, TYPE_MAX_VALUE (type), 1)
5556                     && operand_equal_p (TREE_OPERAND (arg0, 1),
5557                                         const_binop (PLUS_EXPR, arg2,
5558                                                      integer_one_node, 0), 1))
5559                   return pedantic_non_lvalue
5560                     (fold (build (MAX_EXPR, type, arg1, arg2)));
5561                 break;
5562               }
5563         }
5564
5565       /* If the second operand is simpler than the third, swap them
5566          since that produces better jump optimization results.  */
5567       if ((TREE_CONSTANT (arg1) || TREE_CODE_CLASS (TREE_CODE (arg1)) == 'd'
5568            || TREE_CODE (arg1) == SAVE_EXPR)
5569           && ! (TREE_CONSTANT (TREE_OPERAND (t, 2))
5570                 || TREE_CODE_CLASS (TREE_CODE (TREE_OPERAND (t, 2))) == 'd'
5571                 || TREE_CODE (TREE_OPERAND (t, 2)) == SAVE_EXPR))
5572         {
5573           /* See if this can be inverted.  If it can't, possibly because
5574              it was a floating-point inequality comparison, don't do
5575              anything.  */
5576           tem = invert_truthvalue (arg0);
5577
5578           if (TREE_CODE (tem) != TRUTH_NOT_EXPR)
5579             {
5580               t = build (code, type, tem,
5581                          TREE_OPERAND (t, 2), TREE_OPERAND (t, 1));
5582               arg0 = tem;
5583               arg1 = TREE_OPERAND (t, 2);
5584               STRIP_NOPS (arg1);
5585             }
5586         }
5587
5588       /* Convert A ? 1 : 0 to simply A.  */
5589       if (integer_onep (TREE_OPERAND (t, 1))
5590           && integer_zerop (TREE_OPERAND (t, 2))
5591           /* If we try to convert TREE_OPERAND (t, 0) to our type, the
5592              call to fold will try to move the conversion inside
5593              a COND, which will recurse.  In that case, the COND_EXPR
5594              is probably the best choice, so leave it alone.  */
5595           && type == TREE_TYPE (arg0))
5596         return pedantic_non_lvalue (arg0);
5597
5598       /* Look for expressions of the form A & 2 ? 2 : 0.  The result of this
5599          operation is simply A & 2.  */
5600
5601       if (integer_zerop (TREE_OPERAND (t, 2))
5602           && TREE_CODE (arg0) == NE_EXPR
5603           && integer_zerop (TREE_OPERAND (arg0, 1))
5604           && integer_pow2p (arg1)
5605           && TREE_CODE (TREE_OPERAND (arg0, 0)) == BIT_AND_EXPR
5606           && operand_equal_p (TREE_OPERAND (TREE_OPERAND (arg0, 0), 1),
5607                               arg1, 1))
5608         return pedantic_non_lvalue (convert (type, TREE_OPERAND (arg0, 0)));
5609
5610       return t;
5611
5612     case COMPOUND_EXPR:
5613       /* When pedantic, a compound expression can be neither an lvalue
5614          nor an integer constant expression.  */
5615       if (TREE_SIDE_EFFECTS (arg0) || pedantic)
5616         return t;
5617       /* Don't let (0, 0) be null pointer constant.  */
5618       if (integer_zerop (arg1))
5619         return non_lvalue (arg1);
5620       return arg1;
5621
5622     case COMPLEX_EXPR:
5623       if (wins)
5624         return build_complex (type, arg0, arg1);
5625       return t;
5626
5627     case REALPART_EXPR:
5628       if (TREE_CODE (TREE_TYPE (arg0)) != COMPLEX_TYPE)
5629         return t;
5630       else if (TREE_CODE (arg0) == COMPLEX_EXPR)
5631         return omit_one_operand (type, TREE_OPERAND (arg0, 0),
5632                                  TREE_OPERAND (arg0, 1));
5633       else if (TREE_CODE (arg0) == COMPLEX_CST)
5634         return TREE_REALPART (arg0);
5635       else if (TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MINUS_EXPR)
5636         return fold (build (TREE_CODE (arg0), type,
5637                             fold (build1 (REALPART_EXPR, type,
5638                                           TREE_OPERAND (arg0, 0))),
5639                             fold (build1 (REALPART_EXPR,
5640                                           type, TREE_OPERAND (arg0, 1)))));
5641       return t;
5642
5643     case IMAGPART_EXPR:
5644       if (TREE_CODE (TREE_TYPE (arg0)) != COMPLEX_TYPE)
5645         return convert (type, integer_zero_node);
5646       else if (TREE_CODE (arg0) == COMPLEX_EXPR)
5647         return omit_one_operand (type, TREE_OPERAND (arg0, 1),
5648                                  TREE_OPERAND (arg0, 0));
5649       else if (TREE_CODE (arg0) == COMPLEX_CST)
5650         return TREE_IMAGPART (arg0);
5651       else if (TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MINUS_EXPR)
5652         return fold (build (TREE_CODE (arg0), type,
5653                             fold (build1 (IMAGPART_EXPR, type,
5654                                           TREE_OPERAND (arg0, 0))),
5655                             fold (build1 (IMAGPART_EXPR, type,
5656                                           TREE_OPERAND (arg0, 1)))));
5657       return t;
5658
5659       /* Pull arithmetic ops out of the CLEANUP_POINT_EXPR where
5660          appropriate.  */
5661     case CLEANUP_POINT_EXPR:
5662       if (! TREE_SIDE_EFFECTS (arg0))
5663         return TREE_OPERAND (t, 0);
5664
5665       {
5666         enum tree_code code0 = TREE_CODE (arg0);
5667         int kind0 = TREE_CODE_CLASS (code0);
5668         tree arg00 = TREE_OPERAND (arg0, 0);
5669         tree arg01;
5670
5671         if (kind0 == '1' || code0 == TRUTH_NOT_EXPR)
5672           return fold (build1 (code0, type,
5673                                fold (build1 (CLEANUP_POINT_EXPR,
5674                                              TREE_TYPE (arg00), arg00))));
5675
5676         if (kind0 == '<' || kind0 == '2'
5677             || code0 == TRUTH_ANDIF_EXPR || code0 == TRUTH_ORIF_EXPR
5678             || code0 == TRUTH_AND_EXPR   || code0 == TRUTH_OR_EXPR
5679             || code0 == TRUTH_XOR_EXPR)
5680           {
5681             arg01 = TREE_OPERAND (arg0, 1);
5682
5683             if (! TREE_SIDE_EFFECTS (arg00))
5684               return fold (build (code0, type, arg00,
5685                                   fold (build1 (CLEANUP_POINT_EXPR,
5686                                                 TREE_TYPE (arg01), arg01))));
5687
5688             if (! TREE_SIDE_EFFECTS (arg01))
5689               return fold (build (code0, type,
5690                                   fold (build1 (CLEANUP_POINT_EXPR,
5691                                                 TREE_TYPE (arg00), arg00)),
5692                                   arg01));
5693           }
5694
5695         return t;
5696       }
5697
5698     default:
5699       return t;
5700     } /* switch (code) */
5701 }