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