gcc/fold-const.c

   1 /* Fold a constant sub-tree into a single node for C-compiler
   2    Copyright (C) 1987, 1988, 1992 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, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  19
  20 /*@@ Fix lossage on folding division of big integers.  */
  21
  22 /*@@ This file should be rewritten to use an arbitrary precision
  23   @@ representation for "struct tree_int_cst" and "struct tree_real_cst".
  24   @@ Perhaps the routines could also be used for bc/dc, and made a lib.
  25   @@ The routines that translate from the ap rep should
  26   @@ warn if precision et. al. is lost.
  27   @@ This would also make life easier when this technology is used
  28   @@ for cross-compilers.  */
  29
  30
  31 /* The entry points in this file are fold, size_int and size_binop.
  32
  33    fold takes a tree as argument and returns a simplified tree.
  34
  35    size_binop takes a tree code for an arithmetic operation
  36    and two operands that are trees, and produces a tree for the
  37    result, assuming the type comes from `sizetype'.
  38
  39    size_int takes an integer value, and creates a tree constant
  40    with type from `sizetype'.  */
  41
  42 #include <stdio.h>
  43 #include <setjmp.h>
  44 #include "config.h"
  45 #include "flags.h"
  46 #include "tree.h"
  47
  48 /* Handle floating overflow for `const_binop'.  */
  49 static jmp_buf float_error;
  50
  51 void lshift_double ();
  52 void rshift_double ();
  53 void lrotate_double ();
  54 void rrotate_double ();
  55 static tree const_binop ();
  56
  57 #ifndef BRANCH_COST
  58 #define BRANCH_COST 1
  59 #endif
  60
  61 /* Yield nonzero if a signed left shift of A by B bits overflows.  */
  62 #define left_shift_overflows(a, b)  ((a)  !=  ((a) << (b)) >> (b))
  63
  64 /* Suppose A1 + B1 = SUM1, using 2's complement arithmetic ignoring overflow.
  65    Suppose A, B and SUM have the same respective signs as A1, B1, and SUM1.
  66    Then this yields nonzero if overflow occurred during the addition.
  67    Overflow occurs if A and B have the same sign, but A and SUM differ in sign.
  68    Use `^' to test whether signs differ, and `< 0' to isolate the sign.  */
  69 #define overflow_sum_sign(a, b, sum) ((~((a) ^ (b)) & ((a) ^ (sum))) < 0)
  70 \f
  71 /* To do constant folding on INTEGER_CST nodes requires two-word arithmetic.
  72    We do that by representing the two-word integer as MAX_SHORTS shorts,
  73    with only 8 bits stored in each short, as a positive number.  */
  74
  75 /* Unpack a two-word integer into MAX_SHORTS shorts.
  76    LOW and HI are the integer, as two `HOST_WIDE_INT' pieces.
  77    SHORTS points to the array of shorts.  */
  78
  79 static void
  80 encode (shorts, low, hi)
  81      short *shorts;
  82      HOST_WIDE_INT low, hi;
  83 {
  84   register int i;
  85
  86   for (i = 0; i < MAX_SHORTS / 2; i++)
  87     {
  88       shorts[i] = (low >> (i * 8)) & 0xff;
  89       shorts[i + MAX_SHORTS / 2] = (hi >> (i * 8) & 0xff);
  90     }
  91 }
  92
  93 /* Pack an array of MAX_SHORTS shorts into a two-word integer.
  94    SHORTS points to the array of shorts.
  95    The integer is stored into *LOW and *HI as two `HOST_WIDE_INT' pieces.  */
  96
  97 static void
  98 decode (shorts, low, hi)
  99      short *shorts;
 100      HOST_WIDE_INT *low, *hi;
 101 {
 102   register int i;
 103   HOST_WIDE_INT lv = 0, hv = 0;
 104
 105   for (i = 0; i < MAX_SHORTS / 2; i++)
 106     {
 107       lv |= (HOST_WIDE_INT) shorts[i] << (i * 8);
 108       hv |= (HOST_WIDE_INT) shorts[i + MAX_SHORTS / 2] << (i * 8);
 109     }
 110
 111   *low = lv, *hi = hv;
 112 }
 113 \f
 114 /* Make the integer constant T valid for its type
 115    by setting to 0 or 1 all the bits in the constant
 116    that don't belong in the type.
 117    Yield 1 if a signed overflow occurs, 0 otherwise.
 118    If OVERFLOW is nonzero, a signed overflow has already occurred
 119    in calculating T, so propagate it.  */
 120
 121 int
 122 force_fit_type (t, overflow)
 123      tree t;
 124      int overflow;
 125 {
 126   HOST_WIDE_INT low, high;
 127   register int prec;
 128
 129   if (TREE_CODE (t) != INTEGER_CST)
 130     return overflow;
 131
 132   low = TREE_INT_CST_LOW (t);
 133   high = TREE_INT_CST_HIGH (t);
 134
 135   if (TREE_CODE (TREE_TYPE (t)) == POINTER_TYPE)
 136     prec = POINTER_SIZE;
 137   else
 138     prec = TYPE_PRECISION (TREE_TYPE (t));
 139
 140   /* First clear all bits that are beyond the type's precision.  */
 141
 142   if (prec == 2 * HOST_BITS_PER_WIDE_INT)
 143     ;
 144   else if (prec > HOST_BITS_PER_WIDE_INT)
 145     {
 146       TREE_INT_CST_HIGH (t)
 147         &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
 148     }
 149   else
 150     {
 151       TREE_INT_CST_HIGH (t) = 0;
 152       if (prec < HOST_BITS_PER_WIDE_INT)
 153         TREE_INT_CST_LOW (t) &= ~((HOST_WIDE_INT) (-1) << prec);
 154     }
 155
 156   /* Unsigned types do not suffer sign extension or overflow.  */
 157   if (TREE_UNSIGNED (TREE_TYPE (t)))
 158     return 0;
 159
 160   /* If the value's sign bit is set, extend the sign.  */
 161   if (prec != 2 * HOST_BITS_PER_WIDE_INT
 162       && (prec > HOST_BITS_PER_WIDE_INT
 163           ? (TREE_INT_CST_HIGH (t)
 164              & ((HOST_WIDE_INT) 1 << (prec - HOST_BITS_PER_WIDE_INT - 1)))
 165           : TREE_INT_CST_LOW (t) & ((HOST_WIDE_INT) 1 << (prec - 1))))
 166     {
 167       /* Value is negative:
 168          set to 1 all the bits that are outside this type's precision.  */
 169       if (prec > HOST_BITS_PER_WIDE_INT)
 170         {
 171           TREE_INT_CST_HIGH (t)
 172             |= ((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
 173         }
 174       else
 175         {
 176           TREE_INT_CST_HIGH (t) = -1;
 177           if (prec < HOST_BITS_PER_WIDE_INT)
 178             TREE_INT_CST_LOW (t) |= ((HOST_WIDE_INT) (-1) << prec);
 179         }
 180     }
 181
 182   /* Yield nonzero if signed overflow occurred.  */
 183   return
 184     ((overflow | (low ^ TREE_INT_CST_LOW (t)) | (high ^ TREE_INT_CST_HIGH (t)))
 185      != 0);
 186 }
 187 \f
 188 /* Add two doubleword integers with doubleword result.
 189    Each argument is given as two `HOST_WIDE_INT' pieces.
 190    One argument is L1 and H1; the other, L2 and H2.
 191    The value is stored as two `HOST_WIDE_INT' pieces in *LV and *HV.
 192    We use the 8-shorts representation internally.  */
 193
 194 int
 195 add_double (l1, h1, l2, h2, lv, hv)
 196      HOST_WIDE_INT l1, h1, l2, h2;
 197      HOST_WIDE_INT *lv, *hv;
 198 {
 199   short arg1[MAX_SHORTS];
 200   short arg2[MAX_SHORTS];
 201   register int carry = 0;
 202   register int i;
 203
 204   encode (arg1, l1, h1);
 205   encode (arg2, l2, h2);
 206
 207   for (i = 0; i < MAX_SHORTS; i++)
 208     {
 209       carry += arg1[i] + arg2[i];
 210       arg1[i] = carry & 0xff;
 211       carry >>= 8;
 212     }
 213
 214   decode (arg1, lv, hv);
 215   return overflow_sum_sign (h1, h2, *hv);
 216 }
 217
 218 /* Negate a doubleword integer with doubleword result.
 219    Return nonzero if the operation overflows, assuming it's signed.
 220    The argument is given as two `HOST_WIDE_INT' pieces in L1 and H1.
 221    The value is stored as two `HOST_WIDE_INT' pieces in *LV and *HV.
 222    We use the 8-shorts representation internally.  */
 223
 224 int
 225 neg_double (l1, h1, lv, hv)
 226      HOST_WIDE_INT l1, h1;
 227      HOST_WIDE_INT *lv, *hv;
 228 {
 229   if (l1 == 0)
 230     {
 231       *lv = 0;
 232       *hv = - h1;
 233       return (*hv & h1) < 0;
 234     }
 235   else
 236     {
 237       *lv = - l1;
 238       *hv = ~ h1;
 239       return 0;
 240     }
 241 }
 242 \f
 243 /* Multiply two doubleword integers with doubleword result.
 244    Return nonzero if the operation overflows, assuming it's signed.
 245    Each argument is given as two `HOST_WIDE_INT' pieces.
 246    One argument is L1 and H1; the other, L2 and H2.
 247    The value is stored as two `HOST_WIDE_INT' pieces in *LV and *HV.
 248    We use the 8-shorts representation internally.  */
 249
 250 int
 251 mul_double (l1, h1, l2, h2, lv, hv)
 252      HOST_WIDE_INT l1, h1, l2, h2;
 253      HOST_WIDE_INT *lv, *hv;
 254 {
 255   short arg1[MAX_SHORTS];
 256   short arg2[MAX_SHORTS];
 257   short prod[MAX_SHORTS * 2];
 258   register int carry = 0;
 259   register int i, j, k;
 260   HOST_WIDE_INT toplow, tophigh, neglow, neghigh;
 261
 262   /* These cases are used extensively, arising from pointer combinations.  */
 263   if (h2 == 0)
 264     {
 265       if (l2 == 2)
 266         {
 267           int overflow = left_shift_overflows (h1, 1);
 268           unsigned HOST_WIDE_INT temp = l1 + l1;
 269           *hv = (h1 << 1) + (temp < l1);
 270           *lv = temp;
 271           return overflow;
 272         }
 273       if (l2 == 4)
 274         {
 275           int overflow = left_shift_overflows (h1, 2);
 276           unsigned HOST_WIDE_INT temp = l1 + l1;
 277           h1 = (h1 << 2) + ((temp < l1) << 1);
 278           l1 = temp;
 279           temp += temp;
 280           h1 += (temp < l1);
 281           *lv = temp;
 282           *hv = h1;
 283           return overflow;
 284         }
 285       if (l2 == 8)
 286         {
 287           int overflow = left_shift_overflows (h1, 3);
 288           unsigned HOST_WIDE_INT temp = l1 + l1;
 289           h1 = (h1 << 3) + ((temp < l1) << 2);
 290           l1 = temp;
 291           temp += temp;
 292           h1 += (temp < l1) << 1;
 293           l1 = temp;
 294           temp += temp;
 295           h1 += (temp < l1);
 296           *lv = temp;
 297           *hv = h1;
 298           return overflow;
 299         }
 300     }
 301
 302   encode (arg1, l1, h1);
 303   encode (arg2, l2, h2);
 304
 305   bzero (prod, sizeof prod);
 306
 307   for (i = 0; i < MAX_SHORTS; i++)
 308     for (j = 0; j < MAX_SHORTS; j++)
 309       {
 310         k = i + j;
 311         carry = arg1[i] * arg2[j];
 312         while (carry)
 313           {
 314             carry += prod[k];
 315             prod[k] = carry & 0xff;
 316             carry >>= 8;
 317             k++;
 318           }
 319       }
 320
 321   decode (prod, lv, hv);        /* This ignores
 322                                    prod[MAX_SHORTS] -> prod[MAX_SHORTS*2-1] */
 323
 324   /* Check for overflow by calculating the top half of the answer in full;
 325      it should agree with the low half's sign bit.  */
 326   decode (prod+MAX_SHORTS, &toplow, &tophigh);
 327   if (h1 < 0)
 328     {
 329       neg_double (l2, h2, &neglow, &neghigh);
 330       add_double (neglow, neghigh, toplow, tophigh, &toplow, &tophigh);
 331     }
 332   if (h2 < 0)
 333     {
 334       neg_double (l1, h1, &neglow, &neghigh);
 335       add_double (neglow, neghigh, toplow, tophigh, &toplow, &tophigh);
 336     }
 337   return (*hv < 0 ? ~(toplow & tophigh) : toplow | tophigh) != 0;
 338 }
 339 \f
 340 /* Shift the doubleword integer in L1, H1 left by COUNT places
 341    keeping only PREC bits of result.
 342    Shift right if COUNT is negative.
 343    ARITH nonzero specifies arithmetic shifting; otherwise use logical shift.
 344    Store the value as two `HOST_WIDE_INT' pieces in *LV and *HV.  */
 345
 346 void
 347 lshift_double (l1, h1, count, prec, lv, hv, arith)
 348      HOST_WIDE_INT l1, h1;
 349      int count, prec;
 350      HOST_WIDE_INT *lv, *hv;
 351      int arith;
 352 {
 353   short arg1[MAX_SHORTS];
 354   register int i;
 355   register int carry;
 356
 357   if (count < 0)
 358     {
 359       rshift_double (l1, h1, - count, prec, lv, hv, arith);
 360       return;
 361     }
 362
 363   encode (arg1, l1, h1);
 364
 365   if (count > prec)
 366     count = prec;
 367
 368   while (count > 0)
 369     {
 370       carry = 0;
 371       for (i = 0; i < MAX_SHORTS; i++)
 372         {
 373           carry += arg1[i] << 1;
 374           arg1[i] = carry & 0xff;
 375           carry >>= 8;
 376         }
 377       count--;
 378     }
 379
 380   decode (arg1, lv, hv);
 381 }
 382
 383 /* Shift the doubleword integer in L1, H1 right by COUNT places
 384    keeping only PREC bits of result.  COUNT must be positive.
 385    ARITH nonzero specifies arithmetic shifting; otherwise use logical shift.
 386    Store the value as two `HOST_WIDE_INT' pieces in *LV and *HV.  */
 387
 388 void
 389 rshift_double (l1, h1, count, prec, lv, hv, arith)
 390      HOST_WIDE_INT l1, h1, count, prec;
 391      HOST_WIDE_INT *lv, *hv;
 392      int arith;
 393 {
 394   short arg1[MAX_SHORTS];
 395   register int i;
 396   register int carry;
 397
 398   encode (arg1, l1, h1);
 399
 400   if (count > prec)
 401     count = prec;
 402
 403   while (count > 0)
 404     {
 405       carry = arith && arg1[7] >> 7;
 406       for (i = MAX_SHORTS - 1; i >= 0; i--)
 407         {
 408           carry <<= 8;
 409           carry += arg1[i];
 410           arg1[i] = (carry >> 1) & 0xff;
 411         }
 412       count--;
 413     }
 414
 415   decode (arg1, lv, hv);
 416 }
 417 \f
 418 /* Rotate the doubldword integer in L1, H1 left by COUNT places
 419    keeping only PREC bits of result.
 420    Rotate right if COUNT is negative.
 421    Store the value as two `HOST_WIDE_INT' pieces in *LV and *HV.  */
 422
 423 void
 424 lrotate_double (l1, h1, count, prec, lv, hv)
 425      HOST_WIDE_INT l1, h1, count, prec;
 426      HOST_WIDE_INT *lv, *hv;
 427 {
 428   short arg1[MAX_SHORTS];
 429   register int i;
 430   register int carry;
 431
 432   if (count < 0)
 433     {
 434       rrotate_double (l1, h1, - count, prec, lv, hv);
 435       return;
 436     }
 437
 438   encode (arg1, l1, h1);
 439
 440   if (count > prec)
 441     count = prec;
 442
 443   carry = arg1[MAX_SHORTS - 1] >> 7;
 444   while (count > 0)
 445     {
 446       for (i = 0; i < MAX_SHORTS; i++)
 447         {
 448           carry += arg1[i] << 1;
 449           arg1[i] = carry & 0xff;
 450           carry >>= 8;
 451         }
 452       count--;
 453     }
 454
 455   decode (arg1, lv, hv);
 456 }
 457
 458 /* Rotate the doubleword integer in L1, H1 left by COUNT places
 459    keeping only PREC bits of result.  COUNT must be positive.
 460    Store the value as two `HOST_WIDE_INT' pieces in *LV and *HV.  */
 461
 462 void
 463 rrotate_double (l1, h1, count, prec, lv, hv)
 464      HOST_WIDE_INT l1, h1, count, prec;
 465      HOST_WIDE_INT *lv, *hv;
 466 {
 467   short arg1[MAX_SHORTS];
 468   register int i;
 469   register int carry;
 470
 471   encode (arg1, l1, h1);
 472
 473   if (count > prec)
 474     count = prec;
 475
 476   carry = arg1[0] & 1;
 477   while (count > 0)
 478     {
 479       for (i = MAX_SHORTS - 1; i >= 0; i--)
 480         {
 481           carry <<= 8;
 482           carry += arg1[i];
 483           arg1[i] = (carry >> 1) & 0xff;
 484         }
 485       count--;
 486     }
 487
 488   decode (arg1, lv, hv);
 489 }
 490 \f
 491 /* Divide doubleword integer LNUM, HNUM by doubleword integer LDEN, HDEN
 492    for a quotient (stored in *LQUO, *HQUO) and remainder (in *LREM, *HREM).
 493    CODE is a tree code for a kind of division, one of
 494    TRUNC_DIV_EXPR, FLOOR_DIV_EXPR, CEIL_DIV_EXPR, ROUND_DIV_EXPR
 495    or EXACT_DIV_EXPR
 496    It controls how the quotient is rounded to a integer.
 497    Return nonzero if the operation overflows.
 498    UNS nonzero says do unsigned division.  */
 499
 500 static int
 501 div_and_round_double (code, uns,
 502                       lnum_orig, hnum_orig, lden_orig, hden_orig,
 503                       lquo, hquo, lrem, hrem)
 504      enum tree_code code;
 505      int uns;
 506      HOST_WIDE_INT lnum_orig, hnum_orig; /* num == numerator == dividend */
 507      HOST_WIDE_INT lden_orig, hden_orig; /* den == denominator == divisor */
 508      HOST_WIDE_INT *lquo, *hquo, *lrem, *hrem;
 509 {
 510   int quo_neg = 0;
 511   short num[MAX_SHORTS + 1];    /* extra element for scaling.  */
 512   short den[MAX_SHORTS], quo[MAX_SHORTS];
 513   register int i, j, work;
 514   register int carry = 0;
 515   unsigned HOST_WIDE_INT lnum = lnum_orig;
 516   HOST_WIDE_INT hnum = hnum_orig;
 517   unsigned HOST_WIDE_INT lden = lden_orig;
 518   HOST_WIDE_INT hden = hden_orig;
 519   int overflow = 0;
 520
 521   if ((hden == 0) && (lden == 0))
 522     abort ();
 523
 524   /* calculate quotient sign and convert operands to unsigned.  */
 525   if (!uns)
 526     {
 527       if (hnum < 0)
 528         {
 529           quo_neg = ~ quo_neg;
 530           /* (minimum integer) / (-1) is the only overflow case.  */
 531           if (neg_double (lnum, hnum, &lnum, &hnum) && (lden & hden) == -1)
 532             overflow = 1;
 533         }
 534       if (hden < 0)
 535         {
 536           quo_neg = ~ quo_neg;
 537           neg_double (lden, hden, &lden, &hden);
 538         }
 539     }
 540
 541   if (hnum == 0 && hden == 0)
 542     {                           /* single precision */
 543       *hquo = *hrem = 0;
 544       *lquo = lnum / lden;      /* rounds toward zero since positive args */
 545       goto finish_up;
 546     }
 547
 548   if (hnum == 0)
 549     {                           /* trivial case: dividend < divisor */
 550       /* hden != 0 already checked.  */
 551       *hquo = *lquo = 0;
 552       *hrem = hnum;
 553       *lrem = lnum;
 554       goto finish_up;
 555     }
 556
 557   bzero (quo, sizeof quo);
 558
 559   bzero (num, sizeof num);      /* to zero 9th element */
 560   bzero (den, sizeof den);
 561
 562   encode (num, lnum, hnum);
 563   encode (den, lden, hden);
 564
 565   /* This code requires more than just hden == 0.
 566      We also have to require that we don't need more than three bytes
 567      to hold CARRY.  If we ever did need four bytes to hold it, we
 568      would lose part of it when computing WORK on the next round.  */
 569   if (hden == 0 && ((lden << 8) >> 8) == lden)
 570     {                           /* simpler algorithm */
 571       /* hnum != 0 already checked.  */
 572       for (i = MAX_SHORTS - 1; i >= 0; i--)
 573         {
 574           work = num[i] + (carry << 8);
 575           quo[i] = work / lden;
 576           carry = work % lden;
 577         }
 578     }
 579   else {                        /* full double precision,
 580                                    with thanks to Don Knuth's
 581                                    "Seminumerical Algorithms".  */
 582 #define BASE 256
 583     int quo_est, scale, num_hi_sig, den_hi_sig, quo_hi_sig;
 584
 585     /* Find the highest non-zero divisor digit.  */
 586     for (i = MAX_SHORTS - 1; ; i--)
 587       if (den[i] != 0) {
 588         den_hi_sig = i;
 589         break;
 590       }
 591     for (i = MAX_SHORTS - 1; ; i--)
 592       if (num[i] != 0) {
 593         num_hi_sig = i;
 594         break;
 595       }
 596     quo_hi_sig = num_hi_sig - den_hi_sig + 1;
 597
 598     /* Insure that the first digit of the divisor is at least BASE/2.
 599        This is required by the quotient digit estimation algorithm.  */
 600
 601     scale = BASE / (den[den_hi_sig] + 1);
 602     if (scale > 1) {            /* scale divisor and dividend */
 603       carry = 0;
 604       for (i = 0; i <= MAX_SHORTS - 1; i++) {
 605         work = (num[i] * scale) + carry;
 606         num[i] = work & 0xff;
 607         carry = work >> 8;
 608         if (num[i] != 0) num_hi_sig = i;
 609       }
 610       carry = 0;
 611       for (i = 0; i <= MAX_SHORTS - 1; i++) {
 612         work = (den[i] * scale) + carry;
 613         den[i] = work & 0xff;
 614         carry = work >> 8;
 615         if (den[i] != 0) den_hi_sig = i;
 616       }
 617     }
 618
 619     /* Main loop */
 620     for (i = quo_hi_sig; i > 0; i--) {
 621       /* guess the next quotient digit, quo_est, by dividing the first
 622          two remaining dividend digits by the high order quotient digit.
 623          quo_est is never low and is at most 2 high.  */
 624
 625       int num_hi;               /* index of highest remaining dividend digit */
 626
 627       num_hi = i + den_hi_sig;
 628
 629       work = (num[num_hi] * BASE) + (num_hi > 0 ? num[num_hi - 1] : 0);
 630       if (num[num_hi] != den[den_hi_sig]) {
 631         quo_est = work / den[den_hi_sig];
 632       }
 633       else {
 634         quo_est = BASE - 1;
 635       }
 636
 637       /* refine quo_est so it's usually correct, and at most one high.   */
 638       while ((den[den_hi_sig - 1] * quo_est)
 639              > (((work - (quo_est * den[den_hi_sig])) * BASE)
 640                  + ((num_hi - 1) > 0 ? num[num_hi - 2] : 0)))
 641         quo_est--;
 642
 643       /* Try QUO_EST as the quotient digit, by multiplying the
 644          divisor by QUO_EST and subtracting from the remaining dividend.
 645          Keep in mind that QUO_EST is the I - 1st digit.  */
 646
 647       carry = 0;
 648
 649       for (j = 0; j <= den_hi_sig; j++)
 650         {
 651           int digit;
 652
 653           work = num[i + j - 1] - (quo_est * den[j]) + carry;
 654           digit = work & 0xff;
 655           carry = work >> 8;
 656           if (digit < 0)
 657             {
 658               digit += BASE;
 659               carry--;
 660             }
 661           num[i + j - 1] = digit;
 662         }
 663
 664       /* if quo_est was high by one, then num[i] went negative and
 665          we need to correct things.  */
 666
 667       if (num[num_hi] < 0)
 668         {
 669           quo_est--;
 670           carry = 0;            /* add divisor back in */
 671           for (j = 0; j <= den_hi_sig; j++)
 672             {
 673               work = num[i + j - 1] + den[j] + carry;
 674               if (work > BASE)
 675                 {
 676                   work -= BASE;
 677                   carry = 1;
 678                 }
 679               else
 680                 {
 681                   carry = 0;
 682                 }
 683               num[i + j - 1] = work;
 684             }
 685           num [num_hi] += carry;
 686         }
 687
 688       /* store the quotient digit.  */
 689       quo[i - 1] = quo_est;
 690     }
 691   }
 692
 693   decode (quo, lquo, hquo);
 694
 695  finish_up:
 696   /* if result is negative, make it so.  */
 697   if (quo_neg)
 698     neg_double (*lquo, *hquo, lquo, hquo);
 699
 700   /* compute trial remainder:  rem = num - (quo * den)  */
 701   mul_double (*lquo, *hquo, lden_orig, hden_orig, lrem, hrem);
 702   neg_double (*lrem, *hrem, lrem, hrem);
 703   add_double (lnum_orig, hnum_orig, *lrem, *hrem, lrem, hrem);
 704
 705   switch (code)
 706     {
 707     case TRUNC_DIV_EXPR:
 708     case TRUNC_MOD_EXPR:        /* round toward zero */
 709     case EXACT_DIV_EXPR:        /* for this one, it shouldn't matter */
 710       return overflow;
 711
 712     case FLOOR_DIV_EXPR:
 713     case FLOOR_MOD_EXPR:        /* round toward negative infinity */
 714       if (quo_neg && (*lrem != 0 || *hrem != 0))   /* ratio < 0 && rem != 0 */
 715         {
 716           /* quo = quo - 1;  */
 717           add_double (*lquo, *hquo, (HOST_WIDE_INT) -1, (HOST_WIDE_INT)  -1,
 718                       lquo, hquo);
 719         }
 720       else return overflow;
 721       break;
 722
 723     case CEIL_DIV_EXPR:
 724     case CEIL_MOD_EXPR:         /* round toward positive infinity */
 725       if (!quo_neg && (*lrem != 0 || *hrem != 0))  /* ratio > 0 && rem != 0 */
 726         {
 727           add_double (*lquo, *hquo, (HOST_WIDE_INT) 1, (HOST_WIDE_INT) 0,
 728                       lquo, hquo);
 729         }
 730       else return overflow;
 731       break;
 732
 733     case ROUND_DIV_EXPR:
 734     case ROUND_MOD_EXPR:        /* round to closest integer */
 735       {
 736         HOST_WIDE_INT labs_rem = *lrem, habs_rem = *hrem;
 737         HOST_WIDE_INT labs_den = lden, habs_den = hden, ltwice, htwice;
 738
 739         /* get absolute values */
 740         if (*hrem < 0) neg_double (*lrem, *hrem, &labs_rem, &habs_rem);
 741         if (hden < 0) neg_double (lden, hden, &labs_den, &habs_den);
 742
 743         /* if (2 * abs (lrem) >= abs (lden)) */
 744         mul_double ((HOST_WIDE_INT) 2, (HOST_WIDE_INT) 0,
 745                     labs_rem, habs_rem, &ltwice, &htwice);
 746         if (((unsigned HOST_WIDE_INT) habs_den
 747              < (unsigned HOST_WIDE_INT) htwice)
 748             || (((unsigned HOST_WIDE_INT) habs_den
 749                  == (unsigned HOST_WIDE_INT) htwice)
 750                 && ((HOST_WIDE_INT unsigned) labs_den
 751                     < (unsigned HOST_WIDE_INT) ltwice)))
 752           {
 753             if (*hquo < 0)
 754               /* quo = quo - 1;  */
 755               add_double (*lquo, *hquo,
 756                           (HOST_WIDE_INT) -1, (HOST_WIDE_INT) -1, lquo, hquo);
 757             else
 758               /* quo = quo + 1; */
 759               add_double (*lquo, *hquo, (HOST_WIDE_INT) 1, (HOST_WIDE_INT) 0,
 760                           lquo, hquo);
 761           }
 762         else return overflow;
 763       }
 764       break;
 765
 766     default:
 767       abort ();
 768     }
 769
 770   /* compute true remainder:  rem = num - (quo * den)  */
 771   mul_double (*lquo, *hquo, lden_orig, hden_orig, lrem, hrem);
 772   neg_double (*lrem, *hrem, lrem, hrem);
 773   add_double (lnum_orig, hnum_orig, *lrem, *hrem, lrem, hrem);
 774   return overflow;
 775 }
 776 \f
 777 /* Effectively truncate a real value to represent
 778    the nearest possible value in a narrower mode.
 779    The result is actually represented in the same data type as the argument,
 780    but its value is usually different.  */
 781
 782 REAL_VALUE_TYPE
 783 real_value_truncate (mode, arg)
 784      enum machine_mode mode;
 785      REAL_VALUE_TYPE arg;
 786 {
 787 #ifdef __STDC__
 788   /* Make sure the value is actually stored in memory before we turn off
 789      the handler.  */
 790   volatile
 791 #endif
 792     REAL_VALUE_TYPE value;
 793   jmp_buf handler, old_handler;
 794   int handled;
 795
 796   if (setjmp (handler))
 797     {
 798       error ("floating overflow");
 799       return dconst0;
 800     }
 801   handled = push_float_handler (handler, old_handler);
 802   value = REAL_VALUE_TRUNCATE (mode, arg);
 803   pop_float_handler (handled, old_handler);
 804   return value;
 805 }
 806
 807 #if TARGET_FLOAT_FORMAT == IEEE_FLOAT_FORMAT
 808
 809 /* Check for infinity in an IEEE double precision number.  */
 810
 811 int
 812 target_isinf (x)
 813      REAL_VALUE_TYPE x;
 814 {
 815   /* The IEEE 64-bit double format.  */
 816   union {
 817     REAL_VALUE_TYPE d;
 818     struct {
 819       unsigned sign      :  1;
 820       unsigned exponent  : 11;
 821       unsigned mantissa1 : 20;
 822       unsigned mantissa2;
 823     } little_endian;
 824     struct {
 825       unsigned mantissa2;
 826       unsigned mantissa1 : 20;
 827       unsigned exponent  : 11;
 828       unsigned sign      :  1;
 829     } big_endian;
 830   } u;
 831
 832   u.d = dconstm1;
 833   if (u.big_endian.sign == 1)
 834     {
 835       u.d = x;
 836       return (u.big_endian.exponent == 2047
 837               && u.big_endian.mantissa1 == 0
 838               && u.big_endian.mantissa2 == 0);
 839     }
 840   else
 841     {
 842       u.d = x;
 843       return (u.little_endian.exponent == 2047
 844               && u.little_endian.mantissa1 == 0
 845               && u.little_endian.mantissa2 == 0);
 846     }
 847 }
 848
 849 /* Check whether an IEEE double precision number is a NaN.  */
 850
 851 int
 852 target_isnan (x)
 853      REAL_VALUE_TYPE x;
 854 {
 855   /* The IEEE 64-bit double format.  */
 856   union {
 857     REAL_VALUE_TYPE d;
 858     struct {
 859       unsigned sign      :  1;
 860       unsigned exponent  : 11;
 861       unsigned mantissa1 : 20;
 862       unsigned mantissa2;
 863     } little_endian;
 864     struct {
 865       unsigned mantissa2;
 866       unsigned mantissa1 : 20;
 867       unsigned exponent  : 11;
 868       unsigned sign      :  1;
 869     } big_endian;
 870   } u;
 871
 872   u.d = dconstm1;
 873   if (u.big_endian.sign == 1)
 874     {
 875       u.d = x;
 876       return (u.big_endian.exponent == 2047
 877               && (u.big_endian.mantissa1 != 0
 878                   || u.big_endian.mantissa2 != 0));
 879     }
 880   else
 881     {
 882       u.d = x;
 883       return (u.little_endian.exponent == 2047
 884               && (u.little_endian.mantissa1 != 0
 885                   || u.little_endian.mantissa2 != 0));
 886     }
 887 }
 888
 889 /* Check for a negative IEEE double precision number.  */
 890
 891 int
 892 target_negative (x)
 893      REAL_VALUE_TYPE x;
 894 {
 895   /* The IEEE 64-bit double format.  */
 896   union {
 897     REAL_VALUE_TYPE d;
 898     struct {
 899       unsigned sign      :  1;
 900       unsigned exponent  : 11;
 901       unsigned mantissa1 : 20;
 902       unsigned mantissa2;
 903     } little_endian;
 904     struct {
 905       unsigned mantissa2;
 906       unsigned mantissa1 : 20;
 907       unsigned exponent  : 11;
 908       unsigned sign      :  1;
 909     } big_endian;
 910   } u;
 911
 912   u.d = dconstm1;
 913   if (u.big_endian.sign == 1)
 914     {
 915       u.d = x;
 916       return u.big_endian.sign;
 917     }
 918   else
 919     {
 920       u.d = x;
 921       return u.little_endian.sign;
 922     }
 923 }
 924 #else /* Target not IEEE */
 925
 926 /* Let's assume other float formats don't have infinity.
 927    (This can be overridden by redefining REAL_VALUE_ISINF.)  */
 928
 929 target_isinf (x)
 930      REAL_VALUE_TYPE x;
 931 {
 932   return 0;
 933 }
 934
 935 /* Let's assume other float formats don't have NaNs.
 936    (This can be overridden by redefining REAL_VALUE_ISNAN.)  */
 937
 938 target_isnan (x)
 939      REAL_VALUE_TYPE x;
 940 {
 941   return 0;
 942 }
 943
 944 /* Let's assume other float formats don't have minus zero.
 945    (This can be overridden by redefining REAL_VALUE_NEGATIVE.)  */
 946
 947 target_negative (x)
 948      REAL_VALUE_TYPE x;
 949 {
 950   return x < 0;
 951 }
 952 #endif /* Target not IEEE */
 953 \f
 954 /* Split a tree IN into a constant and a variable part
 955    that could be combined with CODE to make IN.
 956    CODE must be a commutative arithmetic operation.
 957    Store the constant part into *CONP and the variable in &VARP.
 958    Return 1 if this was done; zero means the tree IN did not decompose
 959    this way.
 960
 961    If CODE is PLUS_EXPR we also split trees that use MINUS_EXPR.
 962    Therefore, we must tell the caller whether the variable part
 963    was subtracted.  We do this by storing 1 or -1 into *VARSIGNP.
 964    The value stored is the coefficient for the variable term.
 965    The constant term we return should always be added;
 966    we negate it if necessary.  */
 967
 968 static int
 969 split_tree (in, code, varp, conp, varsignp)
 970      tree in;
 971      enum tree_code code;
 972      tree *varp, *conp;
 973      int *varsignp;
 974 {
 975   register tree outtype = TREE_TYPE (in);
 976   *varp = 0;
 977   *conp = 0;
 978
 979   /* Strip any conversions that don't change the machine mode.  */
 980   while ((TREE_CODE (in) == NOP_EXPR
 981           || TREE_CODE (in) == CONVERT_EXPR)
 982          && (TYPE_MODE (TREE_TYPE (in))
 983              == TYPE_MODE (TREE_TYPE (TREE_OPERAND (in, 0)))))
 984     in = TREE_OPERAND (in, 0);
 985
 986   if (TREE_CODE (in) == code
 987       || (TREE_CODE (TREE_TYPE (in)) != REAL_TYPE
 988           /* We can associate addition and subtraction together
 989              (even though the C standard doesn't say so)
 990              for integers because the value is not affected.
 991              For reals, the value might be affected, so we can't.  */
 992           &&
 993           ((code == PLUS_EXPR && TREE_CODE (in) == MINUS_EXPR)
 994            || (code == MINUS_EXPR && TREE_CODE (in) == PLUS_EXPR))))
 995     {
 996       enum tree_code code = TREE_CODE (TREE_OPERAND (in, 0));
 997       if (code == INTEGER_CST)
 998         {
 999           *conp = TREE_OPERAND (in, 0);
1000           *varp = TREE_OPERAND (in, 1);
1001           if (TYPE_MODE (TREE_TYPE (*varp)) != TYPE_MODE (outtype)
1002               && TREE_TYPE (*varp) != outtype)
1003             *varp = convert (outtype, *varp);
1004           *varsignp = (TREE_CODE (in) == MINUS_EXPR) ? -1 : 1;
1005           return 1;
1006         }
1007       if (TREE_CONSTANT (TREE_OPERAND (in, 1)))
1008         {
1009           *conp = TREE_OPERAND (in, 1);
1010           *varp = TREE_OPERAND (in, 0);
1011           *varsignp = 1;
1012           if (TYPE_MODE (TREE_TYPE (*varp)) != TYPE_MODE (outtype)
1013               && TREE_TYPE (*varp) != outtype)
1014             *varp = convert (outtype, *varp);
1015           if (TREE_CODE (in) == MINUS_EXPR)
1016             {
1017               /* If operation is subtraction and constant is second,
1018                  must negate it to get an additive constant.
1019                  And this cannot be done unless it is a manifest constant.
1020                  It could also be the address of a static variable.
1021                  We cannot negate that, so give up.  */
1022               if (TREE_CODE (*conp) == INTEGER_CST)
1023                 /* Subtracting from integer_zero_node loses for long long.  */
1024                 *conp = fold (build1 (NEGATE_EXPR, TREE_TYPE (*conp), *conp));
1025               else
1026                 return 0;
1027             }
1028           return 1;
1029         }
1030       if (TREE_CONSTANT (TREE_OPERAND (in, 0)))
1031         {
1032           *conp = TREE_OPERAND (in, 0);
1033           *varp = TREE_OPERAND (in, 1);
1034           if (TYPE_MODE (TREE_TYPE (*varp)) != TYPE_MODE (outtype)
1035               && TREE_TYPE (*varp) != outtype)
1036             *varp = convert (outtype, *varp);
1037           *varsignp = (TREE_CODE (in) == MINUS_EXPR) ? -1 : 1;
1038           return 1;
1039         }
1040     }
1041   return 0;
1042 }
1043 \f
1044 /* Combine two constants NUM and ARG2 under operation CODE
1045    to produce a new constant.
1046    We assume ARG1 and ARG2 have the same data type,
1047    or at least are the same kind of constant and the same machine mode.
1048
1049    If NOTRUNC is nonzero, do not truncate the result to fit the data type.  */
1050
1051 static tree
1052 const_binop (code, arg1, arg2, notrunc)
1053      enum tree_code code;
1054      register tree arg1, arg2;
1055      int notrunc;
1056 {
1057   if (TREE_CODE (arg1) == INTEGER_CST)
1058     {
1059       register HOST_WIDE_INT int1l = TREE_INT_CST_LOW (arg1);
1060       register HOST_WIDE_INT int1h = TREE_INT_CST_HIGH (arg1);
1061       HOST_WIDE_INT int2l = TREE_INT_CST_LOW (arg2);
1062       HOST_WIDE_INT int2h = TREE_INT_CST_HIGH (arg2);
1063       HOST_WIDE_INT low, hi;
1064       HOST_WIDE_INT garbagel, garbageh;
1065       register tree t;
1066       int uns = TREE_UNSIGNED (TREE_TYPE (arg1));
1067       int overflow = 0;
1068
1069       switch (code)
1070         {
1071         case BIT_IOR_EXPR:
1072           t = build_int_2 (int1l | int2l, int1h | int2h);
1073           break;
1074
1075         case BIT_XOR_EXPR:
1076           t = build_int_2 (int1l ^ int2l, int1h ^ int2h);
1077           break;
1078
1079         case BIT_AND_EXPR:
1080           t = build_int_2 (int1l & int2l, int1h & int2h);
1081           break;
1082
1083         case BIT_ANDTC_EXPR:
1084           t = build_int_2 (int1l & ~int2l, int1h & ~int2h);
1085           break;
1086
1087         case RSHIFT_EXPR:
1088           int2l = - int2l;
1089         case LSHIFT_EXPR:
1090           /* It's unclear from the C standard whether shifts can overflow.
1091              The following code ignores overflow; perhaps a C standard
1092              interpretation ruling is needed.  */
1093           lshift_double (int1l, int1h, int2l,
1094                          TYPE_PRECISION (TREE_TYPE (arg1)),
1095                          &low, &hi,
1096                          !uns);
1097           t = build_int_2 (low, hi);
1098           TREE_TYPE (t) = TREE_TYPE (arg1);
1099           if (!notrunc)
1100             force_fit_type (t, 0);
1101           TREE_CONSTANT_OVERFLOW (t)
1102             = TREE_CONSTANT_OVERFLOW (arg1) | TREE_CONSTANT_OVERFLOW (arg2);
1103           return t;
1104
1105         case RROTATE_EXPR:
1106           int2l = - int2l;
1107         case LROTATE_EXPR:
1108           lrotate_double (int1l, int1h, int2l,
1109                           TYPE_PRECISION (TREE_TYPE (arg1)),
1110                           &low, &hi);
1111           t = build_int_2 (low, hi);
1112           break;
1113
1114         case PLUS_EXPR:
1115           if (int1h == 0)
1116             {
1117               int2l += int1l;
1118               if ((unsigned HOST_WIDE_INT) int2l < int1l)
1119                 {
1120                   hi = int2h++;
1121                   overflow = int2h < hi;
1122                 }
1123               t = build_int_2 (int2l, int2h);
1124               break;
1125             }
1126           if (int2h == 0)
1127             {
1128               int1l += int2l;
1129               if ((unsigned HOST_WIDE_INT) int1l < int2l)
1130                 {
1131                   hi = int1h++;
1132                   overflow = int1h < hi;
1133                 }
1134               t = build_int_2 (int1l, int1h);
1135               break;
1136             }
1137           overflow = add_double (int1l, int1h, int2l, int2h, &low, &hi);
1138           t = build_int_2 (low, hi);
1139           break;
1140
1141         case MINUS_EXPR:
1142           if (int2h == 0 && int2l == 0)
1143             {
1144               t = build_int_2 (int1l, int1h);
1145               break;
1146             }
1147           neg_double (int2l, int2h, &low, &hi);
1148           add_double (int1l, int1h, low, hi, &low, &hi);
1149           overflow = overflow_sum_sign (hi, int2h, int1h);
1150           t = build_int_2 (low, hi);
1151           break;
1152
1153         case MULT_EXPR:
1154           /* Optimize simple cases.  */
1155           if (int1h == 0)
1156             {
1157               unsigned HOST_WIDE_INT temp;
1158
1159               switch (int1l)
1160                 {
1161                 case 0:
1162                   t = build_int_2 (0, 0);
1163                   goto got_it;
1164                 case 1:
1165                   t = build_int_2 (int2l, int2h);
1166                   goto got_it;
1167                 case 2:
1168                   overflow = left_shift_overflows (int2h, 1);
1169                   temp = int2l + int2l;
1170                   int2h = (int2h << 1) + (temp < int2l);
1171                   t = build_int_2 (temp, int2h);
1172                   goto got_it;
1173 #if 0 /* This code can lose carries.  */
1174                 case 3:
1175                   temp = int2l + int2l + int2l;
1176                   int2h = int2h * 3 + (temp < int2l);
1177                   t = build_int_2 (temp, int2h);
1178                   goto got_it;
1179 #endif
1180                 case 4:
1181                   overflow = left_shift_overflows (int2h, 2);
1182                   temp = int2l + int2l;
1183                   int2h = (int2h << 2) + ((temp < int2l) << 1);
1184                   int2l = temp;
1185                   temp += temp;
1186                   int2h += (temp < int2l);
1187                   t = build_int_2 (temp, int2h);
1188                   goto got_it;
1189                 case 8:
1190                   overflow = left_shift_overflows (int2h, 3);
1191                   temp = int2l + int2l;
1192                   int2h = (int2h << 3) + ((temp < int2l) << 2);
1193                   int2l = temp;
1194                   temp += temp;
1195                   int2h += (temp < int2l) << 1;
1196                   int2l = temp;
1197                   temp += temp;
1198                   int2h += (temp < int2l);
1199                   t = build_int_2 (temp, int2h);
1200                   goto got_it;
1201                 default:
1202                   break;
1203                 }
1204             }
1205
1206           if (int2h == 0)
1207             {
1208               if (int2l == 0)
1209                 {
1210                   t = build_int_2 (0, 0);
1211                   break;
1212                 }
1213               if (int2l == 1)
1214                 {
1215                   t = build_int_2 (int1l, int1h);
1216                   break;
1217                 }
1218             }
1219
1220           overflow = mul_double (int1l, int1h, int2l, int2h, &low, &hi);
1221           t = build_int_2 (low, hi);
1222           break;
1223
1224         case TRUNC_DIV_EXPR:
1225         case FLOOR_DIV_EXPR: case CEIL_DIV_EXPR:
1226         case EXACT_DIV_EXPR:
1227           /* This is a shortcut for a common special case.
1228              It reduces the number of tree nodes generated
1229              and saves time.  */
1230           if (int2h == 0 && int2l > 0
1231               && TREE_TYPE (arg1) == sizetype
1232               && int1h == 0 && int1l >= 0)
1233             {
1234               if (code == CEIL_DIV_EXPR)
1235                 int1l += int2l-1;
1236               return size_int (int1l / int2l);
1237             }
1238         case ROUND_DIV_EXPR:
1239           if (int2h == 0 && int2l == 1)
1240             {
1241               t = build_int_2 (int1l, int1h);
1242               break;
1243             }
1244           if (int1l == int2l && int1h == int2h)
1245             {
1246               if ((int1l | int1h) == 0)
1247                 abort ();
1248               t = build_int_2 (1, 0);
1249               break;
1250             }
1251           overflow = div_and_round_double (code, uns,
1252                                            int1l, int1h, int2l, int2h,
1253                                            &low, &hi, &garbagel, &garbageh);
1254           t = build_int_2 (low, hi);
1255           break;
1256
1257         case TRUNC_MOD_EXPR: case ROUND_MOD_EXPR:
1258         case FLOOR_MOD_EXPR: case CEIL_MOD_EXPR:
1259           overflow = div_and_round_double (code, uns,
1260                                            int1l, int1h, int2l, int2h,
1261                                            &garbagel, &garbageh, &low, &hi);
1262           t = build_int_2 (low, hi);
1263           break;
1264
1265         case MIN_EXPR:
1266         case MAX_EXPR:
1267           if (uns)
1268             {
1269               low = (((unsigned HOST_WIDE_INT) int1h
1270                       < (unsigned HOST_WIDE_INT) int2h)
1271                      || (((unsigned HOST_WIDE_INT) int1h
1272                           == (unsigned HOST_WIDE_INT) int2h)
1273                          && ((unsigned HOST_WIDE_INT) int1l
1274                              < (unsigned HOST_WIDE_INT) int2l)));
1275             }
1276           else
1277             {
1278               low = ((int1h < int2h)
1279                      || ((int1h == int2h)
1280                          && ((unsigned HOST_WIDE_INT) int1l
1281                              < (unsigned HOST_WIDE_INT) int2l)));
1282             }
1283           if (low == (code == MIN_EXPR))
1284             t = build_int_2 (int1l, int1h);
1285           else
1286             t = build_int_2 (int2l, int2h);
1287           break;
1288
1289         default:
1290           abort ();
1291         }
1292     got_it:
1293       TREE_TYPE (t) = TREE_TYPE (arg1);
1294       TREE_CONSTANT_OVERFLOW (t)
1295         = ((notrunc ? !uns && overflow : force_fit_type (t, overflow))
1296            | TREE_CONSTANT_OVERFLOW (arg1)
1297            | TREE_CONSTANT_OVERFLOW (arg2));
1298       return t;
1299     }
1300 #if ! defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
1301   if (TREE_CODE (arg1) == REAL_CST)
1302     {
1303       register REAL_VALUE_TYPE d1;
1304       register REAL_VALUE_TYPE d2;
1305       register REAL_VALUE_TYPE value;
1306       tree t;
1307
1308       d1 = TREE_REAL_CST (arg1);
1309       d2 = TREE_REAL_CST (arg2);
1310       if (setjmp (float_error))
1311         {
1312           pedwarn ("floating overflow in constant expression");
1313           return build (code, TREE_TYPE (arg1), arg1, arg2);
1314         }
1315       set_float_handler (float_error);
1316
1317 #ifdef REAL_ARITHMETIC
1318       REAL_ARITHMETIC (value, code, d1, d2);
1319 #else
1320       switch (code)
1321         {
1322         case PLUS_EXPR:
1323           value = d1 + d2;
1324           break;
1325
1326         case MINUS_EXPR:
1327           value = d1 - d2;
1328           break;
1329
1330         case MULT_EXPR:
1331           value = d1 * d2;
1332           break;
1333
1334         case RDIV_EXPR:
1335 #ifndef REAL_INFINITY
1336           if (d2 == 0)
1337             abort ();
1338 #endif
1339
1340           value = d1 / d2;
1341           break;
1342
1343         case MIN_EXPR:
1344           value = MIN (d1, d2);
1345           break;
1346
1347         case MAX_EXPR:
1348           value = MAX (d1, d2);
1349           break;
1350
1351         default:
1352           abort ();
1353         }
1354 #endif /* no REAL_ARITHMETIC */
1355       t = build_real (TREE_TYPE (arg1),
1356                       real_value_truncate (TYPE_MODE (TREE_TYPE (arg1)), value));
1357       set_float_handler (NULL_PTR);
1358       return t;
1359     }
1360 #endif /* not REAL_IS_NOT_DOUBLE, or REAL_ARITHMETIC */
1361   if (TREE_CODE (arg1) == COMPLEX_CST)
1362     {
1363       register tree r1 = TREE_REALPART (arg1);
1364       register tree i1 = TREE_IMAGPART (arg1);
1365       register tree r2 = TREE_REALPART (arg2);
1366       register tree i2 = TREE_IMAGPART (arg2);
1367       register tree t;
1368
1369       switch (code)
1370         {
1371         case PLUS_EXPR:
1372           t = build_complex (const_binop (PLUS_EXPR, r1, r2, notrunc),
1373                              const_binop (PLUS_EXPR, i1, i2, notrunc));
1374           break;
1375
1376         case MINUS_EXPR:
1377           t = build_complex (const_binop (MINUS_EXPR, r1, r2, notrunc),
1378                              const_binop (MINUS_EXPR, i1, i2, notrunc));
1379           break;
1380
1381         case MULT_EXPR:
1382           t = build_complex (const_binop (MINUS_EXPR,
1383                                           const_binop (MULT_EXPR,
1384                                                        r1, r2, notrunc),
1385                                           const_binop (MULT_EXPR,
1386                                                        i1, i2, notrunc),
1387                                           notrunc),
1388                              const_binop (PLUS_EXPR,
1389                                           const_binop (MULT_EXPR,
1390                                                        r1, i2, notrunc),
1391                                           const_binop (MULT_EXPR,
1392                                                        i1, r2, notrunc),
1393                                           notrunc));
1394           break;
1395
1396         case RDIV_EXPR:
1397           {
1398             register tree magsquared
1399               = const_binop (PLUS_EXPR,
1400                              const_binop (MULT_EXPR, r2, r2, notrunc),
1401                              const_binop (MULT_EXPR, i2, i2, notrunc),
1402                              notrunc);
1403             t = build_complex (const_binop (RDIV_EXPR,
1404                                             const_binop (PLUS_EXPR,
1405                                                          const_binop (MULT_EXPR, r1, r2, notrunc),
1406                                                          const_binop (MULT_EXPR, i1, i2, notrunc),
1407                                                          notrunc),
1408                                             magsquared, notrunc),
1409                                const_binop (RDIV_EXPR,
1410                                             const_binop (MINUS_EXPR,
1411                                                          const_binop (MULT_EXPR, i1, r2, notrunc),
1412                                                          const_binop (MULT_EXPR, r1, i2, notrunc),
1413                                                          notrunc),
1414                                             magsquared, notrunc));
1415           }
1416           break;
1417
1418         default:
1419           abort ();
1420         }
1421       TREE_TYPE (t) = TREE_TYPE (arg1);
1422       return t;
1423     }
1424   return 0;
1425 }
1426 \f
1427 /* Return an INTEGER_CST with value V and type from `sizetype'.  */
1428
1429 tree
1430 size_int (number)
1431      unsigned int number;
1432 {
1433   register tree t;
1434   /* Type-size nodes already made for small sizes.  */
1435   static tree size_table[2*HOST_BITS_PER_WIDE_INT + 1];
1436
1437   if (number >= 0 && number < 2*HOST_BITS_PER_WIDE_INT + 1
1438       && size_table[number] != 0)
1439     return size_table[number];
1440   if (number >= 0 && number < 2*HOST_BITS_PER_WIDE_INT + 1)
1441     {
1442       push_obstacks_nochange ();
1443       /* Make this a permanent node.  */
1444       end_temporary_allocation ();
1445       t = build_int_2 (number, 0);
1446       TREE_TYPE (t) = sizetype;
1447       size_table[number] = t;
1448       pop_obstacks ();
1449     }
1450   else
1451     {
1452       t = build_int_2 (number, 0);
1453       TREE_TYPE (t) = sizetype;
1454     }
1455   return t;
1456 }
1457
1458 /* Combine operands OP1 and OP2 with arithmetic operation CODE.
1459    CODE is a tree code.  Data type is taken from `sizetype',
1460    If the operands are constant, so is the result.  */
1461
1462 tree
1463 size_binop (code, arg0, arg1)
1464      enum tree_code code;
1465      tree arg0, arg1;
1466 {
1467   /* Handle the special case of two integer constants faster.  */
1468   if (TREE_CODE (arg0) == INTEGER_CST && TREE_CODE (arg1) == INTEGER_CST)
1469     {
1470       /* And some specific cases even faster than that.  */
1471       if (code == PLUS_EXPR
1472           && TREE_INT_CST_LOW (arg0) == 0
1473           && TREE_INT_CST_HIGH (arg0) == 0)
1474         return arg1;
1475       if (code == MINUS_EXPR
1476           && TREE_INT_CST_LOW (arg1) == 0
1477           && TREE_INT_CST_HIGH (arg1) == 0)
1478         return arg0;
1479       if (code == MULT_EXPR
1480           && TREE_INT_CST_LOW (arg0) == 1
1481           && TREE_INT_CST_HIGH (arg0) == 0)
1482         return arg1;
1483       /* Handle general case of two integer constants.  */
1484       return const_binop (code, arg0, arg1, 1);
1485     }
1486
1487   if (arg0 == error_mark_node || arg1 == error_mark_node)
1488     return error_mark_node;
1489
1490   return fold (build (code, sizetype, arg0, arg1));
1491 }
1492 \f
1493 /* Given T, a tree representing type conversion of ARG1, a constant,
1494    return a constant tree representing the result of conversion.  */
1495
1496 static tree
1497 fold_convert (t, arg1)
1498      register tree t;
1499      register tree arg1;
1500 {
1501   register tree type = TREE_TYPE (t);
1502
1503   if (TREE_CODE (type) == POINTER_TYPE
1504       || TREE_CODE (type) == INTEGER_TYPE
1505       || TREE_CODE (type) == ENUMERAL_TYPE)
1506     {
1507       if (TREE_CODE (arg1) == INTEGER_CST)
1508         {
1509           /* Given an integer constant, make new constant with new type,
1510              appropriately sign-extended or truncated.  */
1511           t = build_int_2 (TREE_INT_CST_LOW (arg1),
1512                            TREE_INT_CST_HIGH (arg1));
1513           TREE_TYPE (t) = type;
1514           /* Indicate an overflow if (1) ARG1 already overflowed,
1515              or (2) ARG1 is a too-large unsigned value and T is signed,
1516              or (3) force_fit_type indicates an overflow.
1517              force_fit_type can't detect (2), since it sees only T's type.  */
1518           TREE_CONSTANT_OVERFLOW (t) =
1519             (TREE_CONSTANT_OVERFLOW (arg1)
1520              | (TREE_INT_CST_HIGH (arg1) < 0
1521                 & TREE_UNSIGNED (type) < TREE_UNSIGNED (TREE_TYPE (arg1)))
1522              | force_fit_type (t, 0));
1523         }
1524 #if !defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
1525       else if (TREE_CODE (arg1) == REAL_CST)
1526         {
1527           REAL_VALUE_TYPE
1528             l = real_value_from_int_cst (TYPE_MIN_VALUE (type)),
1529             x = TREE_REAL_CST (arg1),
1530             u = real_value_from_int_cst (TYPE_MAX_VALUE (type));
1531           /* See if X will be in range after truncation towards 0.
1532              To compensate for truncation, move the bounds away from 0,
1533              but reject if X exactly equals the adjusted bounds.  */
1534 #ifdef REAL_ARITHMETIC
1535           REAL_ARITHMETIC (l, MINUS_EXPR, l, dconst1);
1536           REAL_ARITHMETIC (u, PLUS_EXPR, u, dconst1);
1537 #else
1538           l--;
1539           u++;
1540 #endif
1541           if (! (REAL_VALUES_LESS (l, x) && REAL_VALUES_LESS (x, u)))
1542             {
1543               pedwarn ("real constant out of range for integer conversion");
1544               return t;
1545             }
1546 #ifndef REAL_ARITHMETIC
1547           {
1548             REAL_VALUE_TYPE d;
1549             HOST_WIDE_INT low, high;
1550             HOST_WIDE_INT half_word
1551               = (HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT / 2);
1552
1553             d = TREE_REAL_CST (arg1);
1554             if (d < 0)
1555               d = -d;
1556
1557             high = (HOST_WIDE_INT) (d / half_word / half_word);
1558             d -= (REAL_VALUE_TYPE) high * half_word * half_word;
1559             if (d >= (REAL_VALUE_TYPE) half_word * half_word / 2)
1560               {
1561                 low = d - (REAL_VALUE_TYPE) half_word * half_word / 2;
1562                 low |= (HOST_WIDE_INT) -1 << (HOST_BITS_PER_WIDE_INT - 1);
1563               }
1564             else
1565               low = (HOST_WIDE_INT) d;
1566             if (TREE_REAL_CST (arg1) < 0)
1567               neg_double (low, high, &low, &high);
1568             t = build_int_2 (low, high);
1569           }
1570 #else
1571           {
1572             HOST_WIDE_INT low, high;
1573             REAL_VALUE_TO_INT (low, high, TREE_REAL_CST (arg1));
1574             t = build_int_2 (low, high);
1575           }
1576 #endif
1577           TREE_TYPE (t) = type;
1578           force_fit_type (t, 0);
1579         }
1580 #endif /* not REAL_IS_NOT_DOUBLE, or REAL_ARITHMETIC */
1581       TREE_TYPE (t) = type;
1582     }
1583   else if (TREE_CODE (type) == REAL_TYPE)
1584     {
1585 #if !defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
1586       if (TREE_CODE (arg1) == INTEGER_CST)
1587         return build_real_from_int_cst (type, arg1);
1588 #endif /* not REAL_IS_NOT_DOUBLE, or REAL_ARITHMETIC */
1589       if (TREE_CODE (arg1) == REAL_CST)
1590         {
1591           if (setjmp (float_error))
1592             {
1593               pedwarn ("floating overflow in constant expression");
1594               return t;
1595             }
1596           set_float_handler (float_error);
1597
1598           t = build_real (type, real_value_truncate (TYPE_MODE (type),
1599                                                      TREE_REAL_CST (arg1)));
1600           set_float_handler (NULL_PTR);
1601           return t;
1602         }
1603     }
1604   TREE_CONSTANT (t) = 1;
1605   return t;
1606 }
1607 \f
1608 /* Return an expr equal to X but certainly not valid as an lvalue.
1609    Also make sure it is not valid as an null pointer constant.  */
1610
1611 tree
1612 non_lvalue (x)
1613      tree x;
1614 {
1615   tree result;
1616
1617   /* These things are certainly not lvalues.  */
1618   if (TREE_CODE (x) == NON_LVALUE_EXPR
1619       || TREE_CODE (x) == INTEGER_CST
1620       || TREE_CODE (x) == REAL_CST
1621       || TREE_CODE (x) == STRING_CST
1622       || TREE_CODE (x) == ADDR_EXPR)
1623     {
1624       if (TREE_CODE (x) == INTEGER_CST && integer_zerop (x))
1625         {
1626           result = build1 (NOP_EXPR, TREE_TYPE (x), x);
1627           TREE_CONSTANT (result) = TREE_CONSTANT (x);
1628           return result;
1629         }
1630       return x;
1631     }
1632
1633   result = build1 (NON_LVALUE_EXPR, TREE_TYPE (x), x);
1634   TREE_CONSTANT (result) = TREE_CONSTANT (x);
1635   return result;
1636 }
1637 \f
1638 /* Given a tree comparison code, return the code that is the logical inverse
1639    of the given code.  It is not safe to do this for floating-point
1640    comparisons, except for NE_EXPR and EQ_EXPR.  */
1641
1642 static enum tree_code
1643 invert_tree_comparison (code)
1644      enum tree_code code;
1645 {
1646   switch (code)
1647     {
1648     case EQ_EXPR:
1649       return NE_EXPR;
1650     case NE_EXPR:
1651       return EQ_EXPR;
1652     case GT_EXPR:
1653       return LE_EXPR;
1654     case GE_EXPR:
1655       return LT_EXPR;
1656     case LT_EXPR:
1657       return GE_EXPR;
1658     case LE_EXPR:
1659       return GT_EXPR;
1660     default:
1661       abort ();
1662     }
1663 }
1664
1665 /* Similar, but return the comparison that results if the operands are
1666    swapped.  This is safe for floating-point.  */
1667
1668 static enum tree_code
1669 swap_tree_comparison (code)
1670      enum tree_code code;
1671 {
1672   switch (code)
1673     {
1674     case EQ_EXPR:
1675     case NE_EXPR:
1676       return code;
1677     case GT_EXPR:
1678       return LT_EXPR;
1679     case GE_EXPR:
1680       return LE_EXPR;
1681     case LT_EXPR:
1682       return GT_EXPR;
1683     case LE_EXPR:
1684       return GE_EXPR;
1685     default:
1686       abort ();
1687     }
1688 }
1689 \f
1690 /* Return nonzero if two operands are necessarily equal.
1691    If ONLY_CONST is non-zero, only return non-zero for constants.
1692    This function tests whether the operands are indistinguishable;
1693    it does not test whether they are equal using C's == operation.
1694    The distinction is important for IEEE floating point, because
1695    (1) -0.0 and 0.0 are distinguishable, but -0.0==0.0, and
1696    (2) two NaNs may be indistinguishable, but NaN!=NaN.  */
1697
1698 int
1699 operand_equal_p (arg0, arg1, only_const)
1700      tree arg0, arg1;
1701      int only_const;
1702 {
1703   /* If both types don't have the same signedness, then we can't consider
1704      them equal.  We must check this before the STRIP_NOPS calls
1705      because they may change the signedness of the arguments.  */
1706   if (TREE_UNSIGNED (TREE_TYPE (arg0)) != TREE_UNSIGNED (TREE_TYPE (arg1)))
1707     return 0;
1708
1709   STRIP_NOPS (arg0);
1710   STRIP_NOPS (arg1);
1711
1712   /* If ARG0 and ARG1 are the same SAVE_EXPR, they are necessarily equal.
1713      We don't care about side effects in that case because the SAVE_EXPR
1714      takes care of that for us.  */
1715   if (TREE_CODE (arg0) == SAVE_EXPR && arg0 == arg1)
1716     return ! only_const;
1717
1718   if (TREE_SIDE_EFFECTS (arg0) || TREE_SIDE_EFFECTS (arg1))
1719     return 0;
1720
1721   if (TREE_CODE (arg0) == TREE_CODE (arg1)
1722       && TREE_CODE (arg0) == ADDR_EXPR
1723       && TREE_OPERAND (arg0, 0) == TREE_OPERAND (arg1, 0))
1724     return 1;
1725
1726   if (TREE_CODE (arg0) == TREE_CODE (arg1)
1727       && TREE_CODE (arg0) == INTEGER_CST
1728       && TREE_INT_CST_LOW (arg0) == TREE_INT_CST_LOW (arg1)
1729       && TREE_INT_CST_HIGH (arg0) == TREE_INT_CST_HIGH (arg1))
1730     return 1;
1731
1732   /* Detect when real constants are equal.  */
1733   if (TREE_CODE (arg0) == TREE_CODE (arg1)
1734       && TREE_CODE (arg0) == REAL_CST)
1735     return !bcmp (&TREE_REAL_CST (arg0), &TREE_REAL_CST (arg1),
1736                   sizeof (REAL_VALUE_TYPE));
1737
1738   if (only_const)
1739     return 0;
1740
1741   if (arg0 == arg1)
1742     return 1;
1743
1744   if (TREE_CODE (arg0) != TREE_CODE (arg1))
1745     return 0;
1746   /* This is needed for conversions and for COMPONENT_REF.
1747      Might as well play it safe and always test this.  */
1748   if (TYPE_MODE (TREE_TYPE (arg0)) != TYPE_MODE (TREE_TYPE (arg1)))
1749     return 0;
1750
1751   switch (TREE_CODE_CLASS (TREE_CODE (arg0)))
1752     {
1753     case '1':
1754       /* Two conversions are equal only if signedness and modes match.  */
1755       if ((TREE_CODE (arg0) == NOP_EXPR || TREE_CODE (arg0) == CONVERT_EXPR)
1756           && (TREE_UNSIGNED (TREE_TYPE (arg0))
1757               != TREE_UNSIGNED (TREE_TYPE (arg1))))
1758         return 0;
1759
1760       return operand_equal_p (TREE_OPERAND (arg0, 0),
1761                               TREE_OPERAND (arg1, 0), 0);
1762
1763     case '<':
1764     case '2':
1765       return (operand_equal_p (TREE_OPERAND (arg0, 0),
1766                                TREE_OPERAND (arg1, 0), 0)
1767               && operand_equal_p (TREE_OPERAND (arg0, 1),
1768                                   TREE_OPERAND (arg1, 1), 0));
1769
1770     case 'r':
1771       switch (TREE_CODE (arg0))
1772         {
1773         case INDIRECT_REF:
1774           return operand_equal_p (TREE_OPERAND (arg0, 0),
1775                                   TREE_OPERAND (arg1, 0), 0);
1776
1777         case COMPONENT_REF:
1778         case ARRAY_REF:
1779           return (operand_equal_p (TREE_OPERAND (arg0, 0),
1780                                    TREE_OPERAND (arg1, 0), 0)
1781                   && operand_equal_p (TREE_OPERAND (arg0, 1),
1782                                       TREE_OPERAND (arg1, 1), 0));
1783
1784         case BIT_FIELD_REF:
1785           return (operand_equal_p (TREE_OPERAND (arg0, 0),
1786                                    TREE_OPERAND (arg1, 0), 0)
1787                   && operand_equal_p (TREE_OPERAND (arg0, 1),
1788                                       TREE_OPERAND (arg1, 1), 0)
1789                   && operand_equal_p (TREE_OPERAND (arg0, 2),
1790                                       TREE_OPERAND (arg1, 2), 0));
1791         }
1792       break;
1793     }
1794
1795   return 0;
1796 }
1797 \f
1798 /* Similar to operand_equal_p, but see if ARG0 might have been made by
1799    shorten_compare from ARG1 when ARG1 was being compared with OTHER.
1800
1801    When in doubt, return 0.  */
1802
1803 static int
1804 operand_equal_for_comparison_p (arg0, arg1, other)
1805      tree arg0, arg1;
1806      tree other;
1807 {
1808   int unsignedp1, unsignedpo;
1809   tree primarg1, primother;
1810   int correct_width;
1811
1812   if (operand_equal_p (arg0, arg1, 0))
1813     return 1;
1814
1815   if (TREE_CODE (TREE_TYPE (arg0)) != INTEGER_TYPE)
1816     return 0;
1817
1818   /* Duplicate what shorten_compare does to ARG1 and see if that gives the
1819      actual comparison operand, ARG0.
1820
1821      First throw away any conversions to wider types
1822      already present in the operands.  */
1823
1824   primarg1 = get_narrower (arg1, &unsignedp1);
1825   primother = get_narrower (other, &unsignedpo);
1826
1827   correct_width = TYPE_PRECISION (TREE_TYPE (arg1));
1828   if (unsignedp1 == unsignedpo
1829       && TYPE_PRECISION (TREE_TYPE (primarg1)) < correct_width
1830       && TYPE_PRECISION (TREE_TYPE (primother)) < correct_width)
1831     {
1832       tree type = TREE_TYPE (arg0);
1833
1834       /* Make sure shorter operand is extended the right way
1835          to match the longer operand.  */
1836       primarg1 = convert (signed_or_unsigned_type (unsignedp1,
1837                                                   TREE_TYPE (primarg1)),
1838                          primarg1);
1839
1840       if (operand_equal_p (arg0, convert (type, primarg1), 0))
1841         return 1;
1842     }
1843
1844   return 0;
1845 }
1846 \f
1847 /* See if ARG is an expression that is either a comparison or is performing
1848    arithmetic on comparisons.  The comparisons must only be comparing
1849    two different values, which will be stored in *CVAL1 and *CVAL2; if
1850    they are non-zero it means that some operands have already been found.
1851    No variables may be used anywhere else in the expression except in the
1852    comparisons.
1853
1854    If this is true, return 1.  Otherwise, return zero.  */
1855
1856 static int
1857 twoval_comparison_p (arg, cval1, cval2)
1858      tree arg;
1859      tree *cval1, *cval2;
1860 {
1861   enum tree_code code = TREE_CODE (arg);
1862   char class = TREE_CODE_CLASS (code);
1863
1864   /* We can handle some of the 'e' cases here.  */
1865   if (class == 'e'
1866       && (code == TRUTH_NOT_EXPR
1867           || (code == SAVE_EXPR && SAVE_EXPR_RTL (arg) == 0)))
1868     class = '1';
1869   else if (class == 'e'
1870            && (code == TRUTH_ANDIF_EXPR || code == TRUTH_ORIF_EXPR
1871                || code == COMPOUND_EXPR))
1872     class = '2';
1873
1874   switch (class)
1875     {
1876     case '1':
1877       return twoval_comparison_p (TREE_OPERAND (arg, 0), cval1, cval2);
1878
1879     case '2':
1880       return (twoval_comparison_p (TREE_OPERAND (arg, 0), cval1, cval2)
1881               && twoval_comparison_p (TREE_OPERAND (arg, 1), cval1, cval2));
1882
1883     case 'c':
1884       return 1;
1885
1886     case 'e':
1887       if (code == COND_EXPR)
1888         return (twoval_comparison_p (TREE_OPERAND (arg, 0), cval1, cval2)
1889                 && twoval_comparison_p (TREE_OPERAND (arg, 1), cval1, cval2)
1890                 && twoval_comparison_p (TREE_OPERAND (arg, 2),
1891                                         cval1, cval2));
1892       return 0;
1893
1894     case '<':
1895       /* First see if we can handle the first operand, then the second.  For
1896          the second operand, we know *CVAL1 can't be zero.  It must be that
1897          one side of the comparison is each of the values; test for the
1898          case where this isn't true by failing if the two operands
1899          are the same.  */
1900
1901       if (operand_equal_p (TREE_OPERAND (arg, 0),
1902                            TREE_OPERAND (arg, 1), 0))
1903         return 0;
1904
1905       if (*cval1 == 0)
1906         *cval1 = TREE_OPERAND (arg, 0);
1907       else if (operand_equal_p (*cval1, TREE_OPERAND (arg, 0), 0))
1908         ;
1909       else if (*cval2 == 0)
1910         *cval2 = TREE_OPERAND (arg, 0);
1911       else if (operand_equal_p (*cval2, TREE_OPERAND (arg, 0), 0))
1912         ;
1913       else
1914         return 0;
1915
1916       if (operand_equal_p (*cval1, TREE_OPERAND (arg, 1), 0))
1917         ;
1918       else if (*cval2 == 0)
1919         *cval2 = TREE_OPERAND (arg, 1);
1920       else if (operand_equal_p (*cval2, TREE_OPERAND (arg, 1), 0))
1921         ;
1922       else
1923         return 0;
1924
1925       return 1;
1926     }
1927
1928   return 0;
1929 }
1930 \f
1931 /* ARG is a tree that is known to contain just arithmetic operations and
1932    comparisons.  Evaluate the operations in the tree substituting NEW0 for
1933    any occurrence of OLD0 as an operand of a comparison and likewise for
1934    NEW1 and OLD1.  */
1935
1936 static tree
1937 eval_subst (arg, old0, new0, old1, new1)
1938      tree arg;
1939      tree old0, new0, old1, new1;
1940 {
1941   tree type = TREE_TYPE (arg);
1942   enum tree_code code = TREE_CODE (arg);
1943   char class = TREE_CODE_CLASS (code);
1944
1945   /* We can handle some of the 'e' cases here.  */
1946   if (class == 'e' && code == TRUTH_NOT_EXPR)
1947     class = '1';
1948   else if (class == 'e'
1949            && (code == TRUTH_ANDIF_EXPR || code == TRUTH_ORIF_EXPR))
1950     class = '2';
1951
1952   switch (class)
1953     {
1954     case '1':
1955       return fold (build1 (code, type,
1956                            eval_subst (TREE_OPERAND (arg, 0),
1957                                        old0, new0, old1, new1)));
1958
1959     case '2':
1960       return fold (build (code, type,
1961                           eval_subst (TREE_OPERAND (arg, 0),
1962                                       old0, new0, old1, new1),
1963                           eval_subst (TREE_OPERAND (arg, 1),
1964                                       old0, new0, old1, new1)));
1965
1966     case 'e':
1967       switch (code)
1968         {
1969         case SAVE_EXPR:
1970           return eval_subst (TREE_OPERAND (arg, 0), old0, new0, old1, new1);
1971
1972         case COMPOUND_EXPR:
1973           return eval_subst (TREE_OPERAND (arg, 1), old0, new0, old1, new1);
1974
1975         case COND_EXPR:
1976           return fold (build (code, type,
1977                               eval_subst (TREE_OPERAND (arg, 0),
1978                                           old0, new0, old1, new1),
1979                               eval_subst (TREE_OPERAND (arg, 1),
1980                                           old0, new0, old1, new1),
1981                               eval_subst (TREE_OPERAND (arg, 2),
1982                                           old0, new0, old1, new1)));
1983         }
1984
1985     case '<':
1986       {
1987         tree arg0 = TREE_OPERAND (arg, 0);
1988         tree arg1 = TREE_OPERAND (arg, 1);
1989
1990         /* We need to check both for exact equality and tree equality.  The
1991            former will be true if the operand has a side-effect.  In that
1992            case, we know the operand occurred exactly once.  */
1993
1994         if (arg0 == old0 || operand_equal_p (arg0, old0, 0))
1995           arg0 = new0;
1996         else if (arg0 == old1 || operand_equal_p (arg0, old1, 0))
1997           arg0 = new1;
1998
1999         if (arg1 == old0 || operand_equal_p (arg1, old0, 0))
2000           arg1 = new0;
2001         else if (arg1 == old1 || operand_equal_p (arg1, old1, 0))
2002           arg1 = new1;
2003
2004         return fold (build (code, type, arg0, arg1));
2005       }
2006     }
2007
2008   return arg;
2009 }
2010 \f
2011 /* Return a tree for the case when the result of an expression is RESULT
2012    converted to TYPE and OMITTED was previously an operand of the expression
2013    but is now not needed (e.g., we folded OMITTED * 0).
2014
2015    If OMITTED has side effects, we must evaluate it.  Otherwise, just do
2016    the conversion of RESULT to TYPE.  */
2017
2018 static tree
2019 omit_one_operand (type, result, omitted)
2020      tree type, result, omitted;
2021 {
2022   tree t = convert (type, result);
2023
2024   if (TREE_SIDE_EFFECTS (omitted))
2025     return build (COMPOUND_EXPR, type, omitted, t);
2026
2027   return non_lvalue (t);
2028 }
2029 \f
2030 /* Return a simplified tree node for the truth-negation of ARG.  This
2031    never alters ARG itself.  We assume that ARG is an operation that
2032    returns a truth value (0 or 1).  */
2033
2034 tree
2035 invert_truthvalue (arg)
2036      tree arg;
2037 {
2038   tree type = TREE_TYPE (arg);
2039   enum tree_code code = TREE_CODE (arg);
2040
2041   /* If this is a comparison, we can simply invert it, except for
2042      floating-point non-equality comparisons, in which case we just
2043      enclose a TRUTH_NOT_EXPR around what we have.  */
2044
2045   if (TREE_CODE_CLASS (code) == '<')
2046     {
2047       if (TREE_CODE (TREE_TYPE (TREE_OPERAND (arg, 0))) == REAL_TYPE
2048           && code != NE_EXPR && code != EQ_EXPR)
2049         return build1 (TRUTH_NOT_EXPR, type, arg);
2050       else
2051         return build (invert_tree_comparison (code), type,
2052                       TREE_OPERAND (arg, 0), TREE_OPERAND (arg, 1));
2053     }
2054
2055   switch (code)
2056     {
2057     case INTEGER_CST:
2058       return convert (type, build_int_2 (TREE_INT_CST_LOW (arg) == 0
2059                                          && TREE_INT_CST_HIGH (arg) == 0, 0));
2060
2061     case TRUTH_AND_EXPR:
2062       return build (TRUTH_OR_EXPR, type,
2063                     invert_truthvalue (TREE_OPERAND (arg, 0)),
2064                     invert_truthvalue (TREE_OPERAND (arg, 1)));
2065
2066     case TRUTH_OR_EXPR:
2067       return build (TRUTH_AND_EXPR, type,
2068                     invert_truthvalue (TREE_OPERAND (arg, 0)),
2069                     invert_truthvalue (TREE_OPERAND (arg, 1)));
2070
2071     case TRUTH_XOR_EXPR:
2072       /* Here we can invert either operand.  We invert the first operand
2073          unless the second operand is a TRUTH_NOT_EXPR in which case our
2074          result is the XOR of the first operand with the inside of the
2075          negation of the second operand.  */
2076
2077       if (TREE_CODE (TREE_OPERAND (arg, 1)) == TRUTH_NOT_EXPR)
2078         return build (TRUTH_XOR_EXPR, type, TREE_OPERAND (arg, 0),
2079                       TREE_OPERAND (TREE_OPERAND (arg, 1), 0));
2080       else
2081         return build (TRUTH_XOR_EXPR, type,
2082                       invert_truthvalue (TREE_OPERAND (arg, 0)),
2083                       TREE_OPERAND (arg, 1));
2084
2085     case TRUTH_ANDIF_EXPR:
2086       return build (TRUTH_ORIF_EXPR, type,
2087                     invert_truthvalue (TREE_OPERAND (arg, 0)),
2088                     invert_truthvalue (TREE_OPERAND (arg, 1)));
2089
2090     case TRUTH_ORIF_EXPR:
2091       return build (TRUTH_ANDIF_EXPR, type,
2092                     invert_truthvalue (TREE_OPERAND (arg, 0)),
2093                     invert_truthvalue (TREE_OPERAND (arg, 1)));
2094
2095     case TRUTH_NOT_EXPR:
2096       return TREE_OPERAND (arg, 0);
2097
2098     case COND_EXPR:
2099       return build (COND_EXPR, type, TREE_OPERAND (arg, 0),
2100                     invert_truthvalue (TREE_OPERAND (arg, 1)),
2101                     invert_truthvalue (TREE_OPERAND (arg, 2)));
2102
2103     case COMPOUND_EXPR:
2104       return build (COMPOUND_EXPR, type, TREE_OPERAND (arg, 0),
2105                     invert_truthvalue (TREE_OPERAND (arg, 1)));
2106
2107     case NON_LVALUE_EXPR:
2108       return invert_truthvalue (TREE_OPERAND (arg, 0));
2109
2110     case NOP_EXPR:
2111     case CONVERT_EXPR:
2112     case FLOAT_EXPR:
2113       return build1 (TREE_CODE (arg), type,
2114                      invert_truthvalue (TREE_OPERAND (arg, 0)));
2115
2116     case BIT_AND_EXPR:
2117       if (! integer_onep (TREE_OPERAND (arg, 1)))
2118         abort ();
2119       return build (EQ_EXPR, type, arg, convert (type, integer_zero_node));
2120     }
2121
2122   abort ();
2123 }
2124
2125 /* Given a bit-wise operation CODE applied to ARG0 and ARG1, see if both
2126    operands are another bit-wise operation with a common input.  If so,
2127    distribute the bit operations to save an operation and possibly two if
2128    constants are involved.  For example, convert
2129         (A | B) & (A | C) into A | (B & C)
2130    Further simplification will occur if B and C are constants.
2131
2132    If this optimization cannot be done, 0 will be returned.  */
2133
2134 static tree
2135 distribute_bit_expr (code, type, arg0, arg1)
2136      enum tree_code code;
2137      tree type;
2138      tree arg0, arg1;
2139 {
2140   tree common;
2141   tree left, right;
2142
2143   if (TREE_CODE (arg0) != TREE_CODE (arg1)
2144       || TREE_CODE (arg0) == code
2145       || (TREE_CODE (arg0) != BIT_AND_EXPR
2146           && TREE_CODE (arg0) != BIT_IOR_EXPR))
2147     return 0;
2148
2149   if (operand_equal_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg1, 0), 0))
2150     {
2151       common = TREE_OPERAND (arg0, 0);
2152       left = TREE_OPERAND (arg0, 1);
2153       right = TREE_OPERAND (arg1, 1);
2154     }
2155   else if (operand_equal_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg1, 1), 0))
2156     {
2157       common = TREE_OPERAND (arg0, 0);
2158       left = TREE_OPERAND (arg0, 1);
2159       right = TREE_OPERAND (arg1, 0);
2160     }
2161   else if (operand_equal_p (TREE_OPERAND (arg0, 1), TREE_OPERAND (arg1, 0), 0))
2162     {
2163       common = TREE_OPERAND (arg0, 1);
2164       left = TREE_OPERAND (arg0, 0);
2165       right = TREE_OPERAND (arg1, 1);
2166     }
2167   else if (operand_equal_p (TREE_OPERAND (arg0, 1), TREE_OPERAND (arg1, 1), 0))
2168     {
2169       common = TREE_OPERAND (arg0, 1);
2170       left = TREE_OPERAND (arg0, 0);
2171       right = TREE_OPERAND (arg1, 0);
2172     }
2173   else
2174     return 0;
2175
2176   return fold (build (TREE_CODE (arg0), type, common,
2177                       fold (build (code, type, left, right))));
2178 }
2179 \f
2180 /* Return a BIT_FIELD_REF of type TYPE to refer to BITSIZE bits of INNER
2181    starting at BITPOS.  The field is unsigned if UNSIGNEDP is non-zero.  */
2182
2183 static tree
2184 make_bit_field_ref (inner, type, bitsize, bitpos, unsignedp)
2185      tree inner;
2186      tree type;
2187      int bitsize, bitpos;
2188      int unsignedp;
2189 {
2190   tree result = build (BIT_FIELD_REF, type, inner,
2191                        size_int (bitsize), size_int (bitpos));
2192
2193   TREE_UNSIGNED (result) = unsignedp;
2194
2195   return result;
2196 }
2197
2198 /* Optimize a bit-field compare.
2199
2200    There are two cases:  First is a compare against a constant and the
2201    second is a comparison of two items where the fields are at the same
2202    bit position relative to the start of a chunk (byte, halfword, word)
2203    large enough to contain it.  In these cases we can avoid the shift
2204    implicit in bitfield extractions.
2205
2206    For constants, we emit a compare of the shifted constant with the
2207    BIT_AND_EXPR of a mask and a byte, halfword, or word of the operand being
2208    compared.  For two fields at the same position, we do the ANDs with the
2209    similar mask and compare the result of the ANDs.
2210
2211    CODE is the comparison code, known to be either NE_EXPR or EQ_EXPR.
2212    COMPARE_TYPE is the type of the comparison, and LHS and RHS
2213    are the left and right operands of the comparison, respectively.
2214
2215    If the optimization described above can be done, we return the resulting
2216    tree.  Otherwise we return zero.  */
2217
2218 static tree
2219 optimize_bit_field_compare (code, compare_type, lhs, rhs)
2220      enum tree_code code;
2221      tree compare_type;
2222      tree lhs, rhs;
2223 {
2224   int lbitpos, lbitsize, rbitpos, rbitsize;
2225   int lnbitpos, lnbitsize, rnbitpos, rnbitsize;
2226   tree type = TREE_TYPE (lhs);
2227   tree signed_type, unsigned_type;
2228   int const_p = TREE_CODE (rhs) == INTEGER_CST;
2229   enum machine_mode lmode, rmode, lnmode, rnmode;
2230   int lunsignedp, runsignedp;
2231   int lvolatilep = 0, rvolatilep = 0;
2232   tree linner, rinner;
2233   tree mask;
2234   tree offset;
2235
2236   /* Get all the information about the extractions being done.  If the bit size
2237      if the same as the size of the underlying object, we aren't doing an
2238      extraction at all and so can do nothing.  */
2239   linner = get_inner_reference (lhs, &lbitsize, &lbitpos, &offset, &lmode,
2240                                 &lunsignedp, &lvolatilep);
2241   if (lbitsize == GET_MODE_BITSIZE (lmode) || lbitsize < 0
2242       || offset != 0)
2243     return 0;
2244
2245  if (!const_p)
2246    {
2247      /* If this is not a constant, we can only do something if bit positions,
2248         sizes, and signedness are the same.   */
2249      rinner = get_inner_reference (rhs, &rbitsize, &rbitpos, &offset,
2250                                    &rmode, &runsignedp, &rvolatilep);
2251
2252      if (lbitpos != rbitpos || lbitsize != rbitsize
2253          || lunsignedp != runsignedp || offset != 0)
2254        return 0;
2255    }
2256
2257   /* See if we can find a mode to refer to this field.  We should be able to,
2258      but fail if we can't.  */
2259   lnmode = get_best_mode (lbitsize, lbitpos,
2260                           TYPE_ALIGN (TREE_TYPE (linner)), word_mode,
2261                           lvolatilep);
2262   if (lnmode == VOIDmode)
2263     return 0;
2264
2265   /* Set signed and unsigned types of the precision of this mode for the
2266      shifts below.  */
2267   signed_type = type_for_mode (lnmode, 0);
2268   unsigned_type = type_for_mode (lnmode, 1);
2269
2270   if (! const_p)
2271     {
2272       rnmode = get_best_mode (rbitsize, rbitpos,
2273                               TYPE_ALIGN (TREE_TYPE (rinner)), word_mode,
2274                               rvolatilep);
2275       if (rnmode == VOIDmode)
2276         return 0;
2277     }
2278
2279   /* Compute the bit position and size for the new reference and our offset
2280      within it. If the new reference is the same size as the original, we
2281      won't optimize anything, so return zero.  */
2282   lnbitsize = GET_MODE_BITSIZE (lnmode);
2283   lnbitpos = lbitpos & ~ (lnbitsize - 1);
2284   lbitpos -= lnbitpos;
2285   if (lnbitsize == lbitsize)
2286     return 0;
2287
2288   if (! const_p)
2289     {
2290       rnbitsize = GET_MODE_BITSIZE (rnmode);
2291       rnbitpos = rbitpos & ~ (rnbitsize - 1);
2292       rbitpos -= rnbitpos;
2293       if (rnbitsize == rbitsize)
2294         return 0;
2295     }
2296
2297 #if BYTES_BIG_ENDIAN
2298   lbitpos = lnbitsize - lbitsize - lbitpos;
2299 #endif
2300
2301   /* Make the mask to be used against the extracted field.  */
2302   mask = build_int_2 (~0, ~0);
2303   TREE_TYPE (mask) = unsigned_type;
2304   force_fit_type (mask);
2305   mask = convert (unsigned_type, mask);
2306   mask = const_binop (LSHIFT_EXPR, mask, size_int (lnbitsize - lbitsize), 0);
2307   mask = const_binop (RSHIFT_EXPR, mask,
2308                       size_int (lnbitsize - lbitsize - lbitpos), 0);
2309
2310   if (! const_p)
2311     /* If not comparing with constant, just rework the comparison
2312        and return.  */
2313     return build (code, compare_type,
2314                   build (BIT_AND_EXPR, unsigned_type,
2315                          make_bit_field_ref (linner, unsigned_type,
2316                                              lnbitsize, lnbitpos, 1),
2317                          mask),
2318                   build (BIT_AND_EXPR, unsigned_type,
2319                          make_bit_field_ref (rinner, unsigned_type,
2320                                              rnbitsize, rnbitpos, 1),
2321                          mask));
2322
2323   /* Otherwise, we are handling the constant case. See if the constant is too
2324      big for the field.  Warn and return a tree of for 0 (false) if so.  We do
2325      this not only for its own sake, but to avoid having to test for this
2326      error case below.  If we didn't, we might generate wrong code.
2327
2328      For unsigned fields, the constant shifted right by the field length should
2329      be all zero.  For signed fields, the high-order bits should agree with
2330      the sign bit.  */
2331
2332   if (lunsignedp)
2333     {
2334       if (! integer_zerop (const_binop (RSHIFT_EXPR,
2335                                         convert (unsigned_type, rhs),
2336                                         size_int (lbitsize), 0)))
2337         {
2338           warning ("comparison is always %s due to width of bitfield",
2339                    code == NE_EXPR ? "one" : "zero");
2340           return convert (compare_type,
2341                           (code == NE_EXPR
2342                            ? integer_one_node : integer_zero_node));
2343         }
2344     }
2345   else
2346     {
2347       tree tem = const_binop (RSHIFT_EXPR, convert (signed_type, rhs),
2348                               size_int (lbitsize - 1), 0);
2349       if (! integer_zerop (tem) && ! integer_all_onesp (tem))
2350         {
2351           warning ("comparison is always %s due to width of bitfield",
2352                    code == NE_EXPR ? "one" : "zero");
2353           return convert (compare_type,
2354                           (code == NE_EXPR
2355                            ? integer_one_node : integer_zero_node));
2356         }
2357     }
2358
2359   /* Single-bit compares should always be against zero.  */
2360   if (lbitsize == 1 && ! integer_zerop (rhs))
2361     {
2362       code = code == EQ_EXPR ? NE_EXPR : EQ_EXPR;
2363       rhs = convert (type, integer_zero_node);
2364     }
2365
2366   /* Make a new bitfield reference, shift the constant over the
2367      appropriate number of bits and mask it with the computed mask
2368      (in case this was a signed field).  If we changed it, make a new one.  */
2369   lhs = make_bit_field_ref (linner, unsigned_type, lnbitsize, lnbitpos, 1);
2370
2371   rhs = fold (const_binop (BIT_AND_EXPR,
2372                            const_binop (LSHIFT_EXPR,
2373                                         convert (unsigned_type, rhs),
2374                                         size_int (lbitpos)),
2375                            mask, 0));
2376
2377   return build (code, compare_type,
2378                 build (BIT_AND_EXPR, unsigned_type, lhs, mask),
2379                 rhs);
2380 }
2381 \f
2382 /* Subroutine for fold_truthop: decode a field reference.
2383
2384    If EXP is a comparison reference, we return the innermost reference.
2385
2386    *PBITSIZE is set to the number of bits in the reference, *PBITPOS is
2387    set to the starting bit number.
2388
2389    If the innermost field can be completely contained in a mode-sized
2390    unit, *PMODE is set to that mode.  Otherwise, it is set to VOIDmode.
2391
2392    *PVOLATILEP is set to 1 if the any expression encountered is volatile;
2393    otherwise it is not changed.
2394
2395    *PUNSIGNEDP is set to the signedness of the field.
2396
2397    *PMASK is set to the mask used.  This is either contained in a
2398    BIT_AND_EXPR or derived from the width of the field.
2399
2400    Return 0 if this is not a component reference or is one that we can't
2401    do anything with.  */
2402
2403 static tree
2404 decode_field_reference (exp, pbitsize, pbitpos, pmode, punsignedp,
2405                         pvolatilep, pmask)
2406      tree exp;
2407      int *pbitsize, *pbitpos;
2408      enum machine_mode *pmode;
2409      int *punsignedp, *pvolatilep;
2410      tree *pmask;
2411 {
2412   tree mask = 0;
2413   tree inner;
2414   tree offset;
2415
2416   STRIP_NOPS (exp);
2417
2418   if (TREE_CODE (exp) == BIT_AND_EXPR)
2419     {
2420       mask = TREE_OPERAND (exp, 1);
2421       exp = TREE_OPERAND (exp, 0);
2422       STRIP_NOPS (exp); STRIP_NOPS (mask);
2423       if (TREE_CODE (mask) != INTEGER_CST)
2424         return 0;
2425     }
2426
2427   if (TREE_CODE (exp) != COMPONENT_REF && TREE_CODE (exp) != ARRAY_REF
2428       && TREE_CODE (exp) != BIT_FIELD_REF)
2429     return 0;
2430
2431   inner = get_inner_reference (exp, pbitsize, pbitpos, &offset, pmode,
2432                                punsignedp, pvolatilep);
2433   if (*pbitsize < 0 || offset != 0)
2434     return 0;
2435
2436   if (mask == 0)
2437     {
2438       tree unsigned_type = type_for_size (*pbitsize, 1);
2439       int precision = TYPE_PRECISION (unsigned_type);
2440
2441       mask = build_int_2 (~0, ~0);
2442       TREE_TYPE (mask) = unsigned_type;
2443       force_fit_type (mask, 0);
2444       mask = const_binop (LSHIFT_EXPR, mask, size_int (precision - *pbitsize), 0);
2445       mask = const_binop (RSHIFT_EXPR, mask, size_int (precision - *pbitsize), 0);
2446     }
2447
2448   *pmask = mask;
2449   return inner;
2450 }
2451
2452 /* Return non-zero if MASK represents a mask of SIZE ones in the low-order
2453    bit positions.  */
2454
2455 static int
2456 all_ones_mask_p (mask, size)
2457      tree mask;
2458      int size;
2459 {
2460   tree type = TREE_TYPE (mask);
2461   int precision = TYPE_PRECISION (type);
2462   tree tmask;
2463
2464   tmask = build_int_2 (~0, ~0);
2465   TREE_TYPE (tmask) = signed_type (type);
2466   force_fit_type (tmask);
2467   return
2468     operand_equal_p (mask,
2469                      const_binop (RSHIFT_EXPR,
2470                                   const_binop (LSHIFT_EXPR, tmask,
2471                                                size_int (precision - size), 0),
2472                                   size_int (precision - size), 0),
2473                      0);
2474 }
2475
2476 /* Subroutine for fold_truthop: determine if an operand is simple enough
2477    to be evaluated unconditionally.  */
2478
2479 #ifdef __GNUC__
2480 __inline
2481 #endif
2482 static int
2483 simple_operand_p (exp)
2484      tree exp;
2485 {
2486   /* Strip any conversions that don't change the machine mode.  */
2487   while ((TREE_CODE (exp) == NOP_EXPR
2488           || TREE_CODE (exp) == CONVERT_EXPR)
2489          && (TYPE_MODE (TREE_TYPE (exp))
2490              == TYPE_MODE (TREE_TYPE (TREE_OPERAND (exp, 0)))))
2491     exp = TREE_OPERAND (exp, 0);
2492
2493   return (TREE_CODE_CLASS (TREE_CODE (exp)) == 'c'
2494           || (TREE_CODE_CLASS (TREE_CODE (exp)) == 'd'
2495               && ! TREE_ADDRESSABLE (exp)
2496               && ! TREE_THIS_VOLATILE (exp)
2497               && ! DECL_NONLOCAL (exp)
2498               /* Don't regard global variables as simple.  They may be
2499                  allocated in ways unknown to the compiler (shared memory,
2500                  #pragma weak, etc).  */
2501               && ! TREE_PUBLIC (exp)
2502               && ! DECL_EXTERNAL (exp)
2503               /* Loading a static variable is unduly expensive, but global
2504                  registers aren't expensive.  */
2505               && (! TREE_STATIC (exp) || DECL_REGISTER (exp))));
2506 }
2507 \f
2508 /* Subroutine for fold_truthop: try to optimize a range test.
2509
2510    For example, "i >= 2 && i =< 9" can be done as "(unsigned) (i - 2) <= 7".
2511
2512    JCODE is the logical combination of the two terms.  It is TRUTH_AND_EXPR
2513    (representing TRUTH_ANDIF_EXPR and TRUTH_AND_EXPR) or TRUTH_OR_EXPR
2514    (representing TRUTH_ORIF_EXPR and TRUTH_OR_EXPR).  TYPE is the type of
2515    the result.
2516
2517    VAR is the value being tested.  LO_CODE and HI_CODE are the comparison
2518    operators comparing VAR to LO_CST and HI_CST.  LO_CST is known to be no
2519    larger than HI_CST (they may be equal).
2520
2521    We return the simplified tree or 0 if no optimization is possible.  */
2522
2523 tree
2524 range_test (jcode, type, lo_code, hi_code, var, lo_cst, hi_cst)
2525      enum tree_code jcode, lo_code, hi_code;
2526      tree type, var, lo_cst, hi_cst;
2527 {
2528   tree utype;
2529   enum tree_code rcode;
2530
2531   /* See if this is a range test and normalize the constant terms.  */
2532
2533   if (jcode == TRUTH_AND_EXPR)
2534     {
2535       switch (lo_code)
2536         {
2537         case NE_EXPR:
2538           /* See if we have VAR != CST && VAR != CST+1.  */
2539           if (! (hi_code == NE_EXPR
2540                  && TREE_INT_CST_LOW (hi_cst) - TREE_INT_CST_LOW (lo_cst) == 1
2541                  && tree_int_cst_equal (integer_one_node,
2542                                         const_binop (MINUS_EXPR,
2543                                                      hi_cst, lo_cst, 0))))
2544             return 0;
2545
2546           rcode = GT_EXPR;
2547           break;
2548
2549         case GT_EXPR:
2550         case GE_EXPR:
2551           if (hi_code == LT_EXPR)
2552             hi_cst = const_binop (MINUS_EXPR, hi_cst, integer_one_node, 0);
2553           else if (hi_code != LE_EXPR)
2554             return 0;
2555
2556           if (lo_code == GT_EXPR)
2557             lo_cst = const_binop (PLUS_EXPR, lo_cst, integer_one_node, 0);
2558
2559           /* We now have VAR >= LO_CST && VAR <= HI_CST.  */
2560           rcode = LE_EXPR;
2561           break;
2562
2563         default:
2564           return 0;
2565         }
2566     }
2567   else
2568     {
2569       switch (lo_code)
2570         {
2571         case EQ_EXPR:
2572           /* See if we have VAR == CST || VAR == CST+1.  */
2573           if (! (hi_code == EQ_EXPR
2574                  && TREE_INT_CST_LOW (hi_cst) - TREE_INT_CST_LOW (lo_cst) == 1
2575                  && tree_int_cst_equal (integer_one_node,
2576                                         const_binop (MINUS_EXPR,
2577                                                      hi_cst, lo_cst, 0))))
2578             return 0;
2579
2580           rcode = LE_EXPR;
2581           break;
2582
2583         case LE_EXPR:
2584         case LT_EXPR:
2585           if (hi_code == GE_EXPR)
2586             hi_cst = const_binop (MINUS_EXPR, hi_cst, integer_one_node, 0);
2587           else if (hi_code != GT_EXPR)
2588             return 0;
2589
2590           if (lo_code == LE_EXPR)
2591             lo_cst = const_binop (PLUS_EXPR, lo_cst, integer_one_node, 0);
2592
2593           /* We now have VAR < LO_CST || VAR > HI_CST.  */
2594           rcode = GT_EXPR;
2595           break;
2596
2597         default:
2598           return 0;
2599         }
2600     }
2601
2602   /* When normalizing, it is possible to both increment the smaller constant
2603      and decrement the larger constant.  See if they are still ordered.  */
2604   if (tree_int_cst_lt (hi_cst, lo_cst))
2605     return 0;
2606
2607   /* Fail if VAR isn't an integer.  */
2608   utype = TREE_TYPE (var);
2609   if (TREE_CODE (utype) != INTEGER_TYPE
2610       && TREE_CODE (utype) != ENUMERAL_TYPE)
2611     return 0;
2612
2613   /* The range test is invalid if subtracting the two constants results
2614      in overflow.  This can happen in traditional mode.  */
2615   if (! int_fits_type_p (hi_cst, TREE_TYPE (var))
2616       || ! int_fits_type_p (lo_cst, TREE_TYPE (var)))
2617     return 0;
2618
2619   if (! TREE_UNSIGNED (utype))
2620     {
2621       utype = unsigned_type (utype);
2622       var = convert (utype, var);
2623       lo_cst = convert (utype, lo_cst);
2624       hi_cst = convert (utype, hi_cst);
2625     }
2626
2627   return fold (convert (type,
2628                         build (rcode, utype,
2629                                build (MINUS_EXPR, utype, var, lo_cst),
2630                                const_binop (MINUS_EXPR, hi_cst, lo_cst, 0))));
2631 }
2632 \f
2633 /* Find ways of folding logical expressions of LHS and RHS:
2634    Try to merge two comparisons to the same innermost item.
2635    Look for range tests like "ch >= '0' && ch <= '9'".
2636    Look for combinations of simple terms on machines with expensive branches
2637    and evaluate the RHS unconditionally.
2638
2639    For example, if we have p->a == 2 && p->b == 4 and we can make an
2640    object large enough to span both A and B, we can do this with a comparison
2641    against the object ANDed with the a mask.
2642
2643    If we have p->a == q->a && p->b == q->b, we may be able to use bit masking
2644    operations to do this with one comparison.
2645
2646    We check for both normal comparisons and the BIT_AND_EXPRs made this by
2647    function and the one above.
2648
2649    CODE is the logical operation being done.  It can be TRUTH_ANDIF_EXPR,
2650    TRUTH_AND_EXPR, TRUTH_ORIF_EXPR, or TRUTH_OR_EXPR.
2651
2652    TRUTH_TYPE is the type of the logical operand and LHS and RHS are its
2653    two operands.
2654
2655    We return the simplified tree or 0 if no optimization is possible.  */
2656
2657 static tree
2658 fold_truthop (code, truth_type, lhs, rhs)
2659      enum tree_code code;
2660      tree truth_type, lhs, rhs;
2661 {
2662   /* If this is the "or" of two comparisons, we can do something if we
2663      the comparisons are NE_EXPR.  If this is the "and", we can do something
2664      if the comparisons are EQ_EXPR.  I.e.,
2665         (a->b == 2 && a->c == 4) can become (a->new == NEW).
2666
2667      WANTED_CODE is this operation code.  For single bit fields, we can
2668      convert EQ_EXPR to NE_EXPR so we need not reject the "wrong"
2669      comparison for one-bit fields.  */
2670
2671   enum tree_code wanted_code;
2672   enum tree_code lcode, rcode;
2673   tree ll_arg, lr_arg, rl_arg, rr_arg;
2674   tree ll_inner, lr_inner, rl_inner, rr_inner;
2675   int ll_bitsize, ll_bitpos, lr_bitsize, lr_bitpos;
2676   int rl_bitsize, rl_bitpos, rr_bitsize, rr_bitpos;
2677   int xll_bitpos, xlr_bitpos, xrl_bitpos, xrr_bitpos;
2678   int lnbitsize, lnbitpos, rnbitsize, rnbitpos;
2679   int ll_unsignedp, lr_unsignedp, rl_unsignedp, rr_unsignedp;
2680   enum machine_mode ll_mode, lr_mode, rl_mode, rr_mode;
2681   enum machine_mode lnmode, rnmode;
2682   tree ll_mask, lr_mask, rl_mask, rr_mask;
2683   tree l_const, r_const;
2684   tree type, result;
2685   int first_bit, end_bit;
2686   int volatilep;
2687
2688   /* Start by getting the comparison codes and seeing if this looks like
2689      a range test.  Fail if anything is volatile.  */
2690
2691   if (TREE_SIDE_EFFECTS (lhs)
2692       || TREE_SIDE_EFFECTS (rhs))
2693     return 0;
2694
2695   lcode = TREE_CODE (lhs);
2696   rcode = TREE_CODE (rhs);
2697
2698   if (TREE_CODE_CLASS (lcode) != '<'
2699       || TREE_CODE_CLASS (rcode) != '<')
2700     return 0;
2701
2702   code = ((code == TRUTH_AND_EXPR || code == TRUTH_ANDIF_EXPR)
2703           ? TRUTH_AND_EXPR : TRUTH_OR_EXPR);
2704
2705   ll_arg = TREE_OPERAND (lhs, 0);
2706   lr_arg = TREE_OPERAND (lhs, 1);
2707   rl_arg = TREE_OPERAND (rhs, 0);
2708   rr_arg = TREE_OPERAND (rhs, 1);
2709
2710   if (TREE_CODE (lr_arg) == INTEGER_CST
2711       && TREE_CODE (rr_arg) == INTEGER_CST
2712       && operand_equal_p (ll_arg, rl_arg, 0))
2713     {
2714       if (tree_int_cst_lt (lr_arg, rr_arg))
2715         result = range_test (code, truth_type, lcode, rcode,
2716                              ll_arg, lr_arg, rr_arg);
2717       else
2718         result = range_test (code, truth_type, rcode, lcode,
2719                              ll_arg, rr_arg, lr_arg);
2720
2721       /* If this isn't a range test, it also isn't a comparison that
2722          can be merged.  However, it wins to evaluate the RHS unconditionally
2723          on machines with expensive branches.   */
2724
2725       if (result == 0 && BRANCH_COST >= 2)
2726         {
2727           if (TREE_CODE (ll_arg) != VAR_DECL
2728               && TREE_CODE (ll_arg) != PARM_DECL)
2729             {
2730               /* Avoid evaluating the variable part twice.  */
2731               ll_arg = save_expr (ll_arg);
2732               lhs = build (lcode, TREE_TYPE (lhs), ll_arg, lr_arg);
2733               rhs = build (rcode, TREE_TYPE (rhs), ll_arg, rr_arg);
2734             }
2735           return build (code, truth_type, lhs, rhs);
2736         }
2737       return result;
2738     }
2739
2740   /* If the RHS can be evaluated unconditionally and its operands are
2741      simple, it wins to evaluate the RHS unconditionally on machines
2742      with expensive branches.  In this case, this isn't a comparison
2743      that can be merged.  */
2744
2745   /* @@ I'm not sure it wins on the m88110 to do this if the comparisons
2746      are with zero (tmw).  */
2747
2748   if (BRANCH_COST >= 2
2749       && TREE_CODE (TREE_TYPE (rhs)) == INTEGER_TYPE
2750       && simple_operand_p (rl_arg)
2751       && simple_operand_p (rr_arg))
2752     return build (code, truth_type, lhs, rhs);
2753
2754   /* See if the comparisons can be merged.  Then get all the parameters for
2755      each side.  */
2756
2757   if ((lcode != EQ_EXPR && lcode != NE_EXPR)
2758       || (rcode != EQ_EXPR && rcode != NE_EXPR))
2759     return 0;
2760
2761   volatilep = 0;
2762   ll_inner = decode_field_reference (ll_arg,
2763                                      &ll_bitsize, &ll_bitpos, &ll_mode,
2764                                      &ll_unsignedp, &volatilep, &ll_mask);
2765   lr_inner = decode_field_reference (lr_arg,
2766                                      &lr_bitsize, &lr_bitpos, &lr_mode,
2767                                      &lr_unsignedp, &volatilep, &lr_mask);
2768   rl_inner = decode_field_reference (rl_arg,
2769                                      &rl_bitsize, &rl_bitpos, &rl_mode,
2770                                      &rl_unsignedp, &volatilep, &rl_mask);
2771   rr_inner = decode_field_reference (rr_arg,
2772                                      &rr_bitsize, &rr_bitpos, &rr_mode,
2773                                      &rr_unsignedp, &volatilep, &rr_mask);
2774
2775   /* It must be true that the inner operation on the lhs of each
2776      comparison must be the same if we are to be able to do anything.
2777      Then see if we have constants.  If not, the same must be true for
2778      the rhs's.  */
2779   if (volatilep || ll_inner == 0 || rl_inner == 0
2780       || ! operand_equal_p (ll_inner, rl_inner, 0))
2781     return 0;
2782
2783   if (TREE_CODE (lr_arg) == INTEGER_CST
2784       && TREE_CODE (rr_arg) == INTEGER_CST)
2785     l_const = lr_arg, r_const = rr_arg;
2786   else if (lr_inner == 0 || rr_inner == 0
2787            || ! operand_equal_p (lr_inner, rr_inner, 0))
2788     return 0;
2789   else
2790     l_const = r_const = 0;
2791
2792   /* If either comparison code is not correct for our logical operation,
2793      fail.  However, we can convert a one-bit comparison against zero into
2794      the opposite comparison against that bit being set in the field.  */
2795
2796   wanted_code = (code == TRUTH_AND_EXPR ? EQ_EXPR : NE_EXPR);
2797   if (lcode != wanted_code)
2798     {
2799       if (l_const && integer_zerop (l_const) && integer_pow2p (ll_mask))
2800         l_const = ll_mask;
2801       else
2802         return 0;
2803     }
2804
2805   if (rcode != wanted_code)
2806     {
2807       if (r_const && integer_zerop (r_const) && integer_pow2p (rl_mask))
2808         r_const = rl_mask;
2809       else
2810         return 0;
2811     }
2812
2813   /* See if we can find a mode that contains both fields being compared on
2814      the left.  If we can't, fail.  Otherwise, update all constants and masks
2815      to be relative to a field of that size.  */
2816   first_bit = MIN (ll_bitpos, rl_bitpos);
2817   end_bit = MAX (ll_bitpos + ll_bitsize, rl_bitpos + rl_bitsize);
2818   lnmode = get_best_mode (end_bit - first_bit, first_bit,
2819                           TYPE_ALIGN (TREE_TYPE (ll_inner)), word_mode,
2820                           volatilep);
2821   if (lnmode == VOIDmode)
2822     return 0;
2823
2824   lnbitsize = GET_MODE_BITSIZE (lnmode);
2825   lnbitpos = first_bit & ~ (lnbitsize - 1);
2826   type = type_for_size (lnbitsize, 1);
2827   xll_bitpos = ll_bitpos - lnbitpos, xrl_bitpos = rl_bitpos - lnbitpos;
2828
2829 #if BYTES_BIG_ENDIAN
2830   xll_bitpos = lnbitsize - xll_bitpos - ll_bitsize;
2831   xrl_bitpos = lnbitsize - xrl_bitpos - rl_bitsize;
2832 #endif
2833
2834   ll_mask = const_binop (LSHIFT_EXPR, convert (type, ll_mask),
2835                          size_int (xll_bitpos), 0);
2836   rl_mask = const_binop (LSHIFT_EXPR, convert (type, rl_mask),
2837                          size_int (xrl_bitpos), 0);
2838
2839   /* Make sure the constants are interpreted as unsigned, so we
2840      don't have sign bits outside the range of their type.  */
2841
2842   if (l_const)
2843     {
2844       l_const = convert (unsigned_type (TREE_TYPE (l_const)), l_const);
2845       l_const = const_binop (LSHIFT_EXPR, convert (type, l_const),
2846                              size_int (xll_bitpos), 0);
2847     }
2848   if (r_const)
2849     {
2850       r_const = convert (unsigned_type (TREE_TYPE (r_const)), r_const);
2851       r_const = const_binop (LSHIFT_EXPR, convert (type, r_const),
2852                              size_int (xrl_bitpos), 0);
2853     }
2854
2855   /* If the right sides are not constant, do the same for it.  Also,
2856      disallow this optimization if a size or signedness mismatch occurs
2857      between the left and right sides.  */
2858   if (l_const == 0)
2859     {
2860       if (ll_bitsize != lr_bitsize || rl_bitsize != rr_bitsize
2861           || ll_unsignedp != lr_unsignedp || rl_unsignedp != rr_unsignedp
2862           /* Make sure the two fields on the right
2863              correspond to the left without being swapped.  */
2864           || ll_bitpos - rl_bitpos != lr_bitpos - rr_bitpos)
2865         return 0;
2866
2867       first_bit = MIN (lr_bitpos, rr_bitpos);
2868       end_bit = MAX (lr_bitpos + lr_bitsize, rr_bitpos + rr_bitsize);
2869       rnmode = get_best_mode (end_bit - first_bit, first_bit,
2870                               TYPE_ALIGN (TREE_TYPE (lr_inner)), word_mode,
2871                               volatilep);
2872       if (rnmode == VOIDmode)
2873         return 0;
2874
2875       rnbitsize = GET_MODE_BITSIZE (rnmode);
2876       rnbitpos = first_bit & ~ (rnbitsize - 1);
2877       xlr_bitpos = lr_bitpos - rnbitpos, xrr_bitpos = rr_bitpos - rnbitpos;
2878
2879 #if BYTES_BIG_ENDIAN
2880       xlr_bitpos = rnbitsize - xlr_bitpos - lr_bitsize;
2881       xrr_bitpos = rnbitsize - xrr_bitpos - rr_bitsize;
2882 #endif
2883
2884       lr_mask = const_binop (LSHIFT_EXPR, convert (type, lr_mask),
2885                              size_int (xlr_bitpos), 0);
2886       rr_mask = const_binop (LSHIFT_EXPR, convert (type, rr_mask),
2887                              size_int (xrr_bitpos), 0);
2888
2889       /* Make a mask that corresponds to both fields being compared.
2890          Do this for both items being compared.  If the masks agree,
2891          we can do this by masking both and comparing the masked
2892          results.  */
2893       ll_mask = const_binop (BIT_IOR_EXPR, ll_mask, rl_mask, 0);
2894       lr_mask = const_binop (BIT_IOR_EXPR, lr_mask, rr_mask, 0);
2895       if (operand_equal_p (ll_mask, lr_mask, 0) && lnbitsize == rnbitsize)
2896         {
2897           lhs = make_bit_field_ref (ll_inner, type, lnbitsize, lnbitpos,
2898                                     ll_unsignedp || rl_unsignedp);
2899           rhs = make_bit_field_ref (lr_inner, type, rnbitsize, rnbitpos,
2900                                     lr_unsignedp || rr_unsignedp);
2901           if (! all_ones_mask_p (ll_mask, lnbitsize))
2902             {
2903               lhs = build (BIT_AND_EXPR, type, lhs, ll_mask);
2904               rhs = build (BIT_AND_EXPR, type, rhs, ll_mask);
2905             }
2906           return build (wanted_code, truth_type, lhs, rhs);
2907         }
2908
2909       /* There is still another way we can do something:  If both pairs of
2910          fields being compared are adjacent, we may be able to make a wider
2911          field containing them both.  */
2912       if ((ll_bitsize + ll_bitpos == rl_bitpos
2913            && lr_bitsize + lr_bitpos == rr_bitpos)
2914           || (ll_bitpos == rl_bitpos + rl_bitsize
2915               && lr_bitpos == rr_bitpos + rr_bitsize))
2916         return build (wanted_code, truth_type,
2917                       make_bit_field_ref (ll_inner, type,
2918                                           ll_bitsize + rl_bitsize,
2919                                           MIN (ll_bitpos, rl_bitpos),
2920                                           ll_unsignedp),
2921                       make_bit_field_ref (lr_inner, type,
2922                                           lr_bitsize + rr_bitsize,
2923                                           MIN (lr_bitpos, rr_bitpos),
2924                                           lr_unsignedp));
2925
2926       return 0;
2927     }
2928
2929   /* Handle the case of comparisons with constants.  If there is something in
2930      common between the masks, those bits of the constants must be the same.
2931      If not, the condition is always false.  Test for this to avoid generating
2932      incorrect code below.  */
2933   result = const_binop (BIT_AND_EXPR, ll_mask, rl_mask, 0);
2934   if (! integer_zerop (result)
2935       && simple_cst_equal (const_binop (BIT_AND_EXPR, result, l_const, 0),
2936                            const_binop (BIT_AND_EXPR, result, r_const, 0)) != 1)
2937     {
2938       if (wanted_code == NE_EXPR)
2939         {
2940           warning ("`or' of unmatched not-equal tests is always 1");
2941           return convert (truth_type, integer_one_node);
2942         }
2943       else
2944         {
2945           warning ("`and' of mutually exclusive equal-tests is always zero");
2946           return convert (truth_type, integer_zero_node);
2947         }
2948     }
2949
2950   /* Construct the expression we will return.  First get the component
2951      reference we will make.  Unless the mask is all ones the width of
2952      that field, perform the mask operation.  Then compare with the
2953      merged constant.  */
2954   result = make_bit_field_ref (ll_inner, type, lnbitsize, lnbitpos,
2955                                ll_unsignedp || rl_unsignedp);
2956
2957   ll_mask = const_binop (BIT_IOR_EXPR, ll_mask, rl_mask, 0);
2958   if (! all_ones_mask_p (ll_mask, lnbitsize))
2959     result = build (BIT_AND_EXPR, type, result, ll_mask);
2960
2961   return build (wanted_code, truth_type, result,
2962                 const_binop (BIT_IOR_EXPR, l_const, r_const, 0));
2963 }
2964 \f
2965 /* Perform constant folding and related simplification of EXPR.
2966    The related simplifications include x*1 => x, x*0 => 0, etc.,
2967    and application of the associative law.
2968    NOP_EXPR conversions may be removed freely (as long as we
2969    are careful not to change the C type of the overall expression)
2970    We cannot simplify through a CONVERT_EXPR, FIX_EXPR or FLOAT_EXPR,
2971    but we can constant-fold them if they have constant operands.  */
2972
2973 tree
2974 fold (expr)
2975      tree expr;
2976 {
2977   register tree t = expr;
2978   tree t1 = NULL_TREE;
2979   tree tem;
2980   tree type = TREE_TYPE (expr);
2981   register tree arg0, arg1;
2982   register enum tree_code code = TREE_CODE (t);
2983   register int kind;
2984   int invert;
2985
2986   /* WINS will be nonzero when the switch is done
2987      if all operands are constant.  */
2988
2989   int wins = 1;
2990
2991   /* Return right away if already constant.  */
2992   if (TREE_CONSTANT (t))
2993     {
2994       if (code == CONST_DECL)
2995         return DECL_INITIAL (t);
2996       return t;
2997     }
2998
2999   kind = TREE_CODE_CLASS (code);
3000   if (code == NOP_EXPR || code == FLOAT_EXPR || code == CONVERT_EXPR)
3001     {
3002       tree subop;
3003
3004       /* Special case for conversion ops that can have fixed point args.  */
3005       arg0 = TREE_OPERAND (t, 0);
3006
3007       /* Don't use STRIP_NOPS, because signedness of argument type matters.  */
3008       if (arg0 != 0)
3009         STRIP_TYPE_NOPS (arg0);
3010
3011       if (arg0 != 0 && TREE_CODE (arg0) == COMPLEX_CST)
3012         subop = TREE_REALPART (arg0);
3013       else
3014         subop = arg0;
3015
3016       if (subop != 0 && TREE_CODE (subop) != INTEGER_CST
3017 #if ! defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
3018           && TREE_CODE (subop) != REAL_CST
3019 #endif /* not REAL_IS_NOT_DOUBLE, or REAL_ARITHMETIC */
3020           )
3021         /* Note that TREE_CONSTANT isn't enough:
3022            static var addresses are constant but we can't
3023            do arithmetic on them.  */
3024         wins = 0;
3025     }
3026   else if (kind == 'e' || kind == '<'
3027            || kind == '1' || kind == '2' || kind == 'r')
3028     {
3029       register int len = tree_code_length[(int) code];
3030       register int i;
3031       for (i = 0; i < len; i++)
3032         {
3033           tree op = TREE_OPERAND (t, i);
3034           tree subop;
3035
3036           if (op == 0)
3037             continue;           /* Valid for CALL_EXPR, at least.  */
3038
3039           /* Strip any conversions that don't change the mode.  */
3040           STRIP_NOPS (op);
3041
3042           if (TREE_CODE (op) == COMPLEX_CST)
3043             subop = TREE_REALPART (op);
3044           else
3045             subop = op;
3046
3047           if (TREE_CODE (subop) != INTEGER_CST
3048 #if ! defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
3049               && TREE_CODE (subop) != REAL_CST
3050 #endif /* not REAL_IS_NOT_DOUBLE, or REAL_ARITHMETIC */
3051               )
3052             /* Note that TREE_CONSTANT isn't enough:
3053                static var addresses are constant but we can't
3054                do arithmetic on them.  */
3055             wins = 0;
3056
3057           if (i == 0)
3058             arg0 = op;
3059           else if (i == 1)
3060             arg1 = op;
3061         }
3062     }
3063
3064   /* If this is a commutative operation, and ARG0 is a constant, move it
3065      to ARG1 to reduce the number of tests below.  */
3066   if ((code == PLUS_EXPR || code == MULT_EXPR || code == MIN_EXPR
3067        || code == MAX_EXPR || code == BIT_IOR_EXPR || code == BIT_XOR_EXPR
3068        || code == BIT_AND_EXPR)
3069       && (TREE_CODE (arg0) == INTEGER_CST || TREE_CODE (arg0) == REAL_CST))
3070     {
3071       tem = arg0; arg0 = arg1; arg1 = tem;
3072
3073       tem = TREE_OPERAND (t, 0); TREE_OPERAND (t, 0) = TREE_OPERAND (t, 1);
3074       TREE_OPERAND (t, 1) = tem;
3075     }
3076
3077   /* Now WINS is set as described above,
3078      ARG0 is the first operand of EXPR,
3079      and ARG1 is the second operand (if it has more than one operand).
3080
3081      First check for cases where an arithmetic operation is applied to a
3082      compound, conditional, or comparison operation.  Push the arithmetic
3083      operation inside the compound or conditional to see if any folding
3084      can then be done.  Convert comparison to conditional for this purpose.
3085      The also optimizes non-constant cases that used to be done in
3086      expand_expr.  */
3087   if (TREE_CODE_CLASS (code) == '1')
3088     {
3089       if (TREE_CODE (arg0) == COMPOUND_EXPR)
3090         return build (COMPOUND_EXPR, type, TREE_OPERAND (arg0, 0),
3091                       fold (build1 (code, type, TREE_OPERAND (arg0, 1))));
3092       else if (TREE_CODE (arg0) == COND_EXPR)
3093         {
3094           t = fold (build (COND_EXPR, type, TREE_OPERAND (arg0, 0),
3095                            fold (build1 (code, type, TREE_OPERAND (arg0, 1))),
3096                            fold (build1 (code, type, TREE_OPERAND (arg0, 2)))));
3097
3098           /* If this was a conversion, and all we did was to move into
3099              inside the COND_EXPR, bring it back out.  Then return so we
3100              don't get into an infinite recursion loop taking the conversion
3101              out and then back in.  */
3102
3103           if ((code == NOP_EXPR || code == CONVERT_EXPR
3104                || code == NON_LVALUE_EXPR)
3105               && TREE_CODE (t) == COND_EXPR
3106               && TREE_CODE (TREE_OPERAND (t, 1)) == code
3107               && TREE_CODE (TREE_OPERAND (t, 2)) == code
3108               && (TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 1), 0))
3109                   == TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 2), 0))))
3110             t = build1 (code, type,
3111                         build (COND_EXPR,
3112                                TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 1), 0)),
3113                                TREE_OPERAND (t, 0),
3114                                TREE_OPERAND (TREE_OPERAND (t, 1), 0),
3115                                TREE_OPERAND (TREE_OPERAND (t, 2), 0)));
3116           return t;
3117         }
3118       else if (TREE_CODE_CLASS (TREE_CODE (arg0)) == '<')
3119         return fold (build (COND_EXPR, type, arg0,
3120                             fold (build1 (code, type, integer_one_node)),
3121                             fold (build1 (code, type, integer_zero_node))));
3122    }
3123   else if (TREE_CODE_CLASS (code) == '2')
3124     {
3125       if (TREE_CODE (arg1) == COMPOUND_EXPR)
3126         return build (COMPOUND_EXPR, type, TREE_OPERAND (arg1, 0),
3127                       fold (build (code, type, arg0, TREE_OPERAND (arg1, 1))));
3128       else if (TREE_CODE (arg1) == COND_EXPR
3129                || TREE_CODE_CLASS (TREE_CODE (arg1)) == '<')
3130         {
3131           tree test, true_value, false_value;
3132
3133           if (TREE_CODE (arg1) == COND_EXPR)
3134             {
3135               test = TREE_OPERAND (arg1, 0);
3136               true_value = TREE_OPERAND (arg1, 1);
3137               false_value = TREE_OPERAND (arg1, 2);
3138             }
3139           else
3140             {
3141               test = arg1;
3142               true_value = integer_one_node;
3143               false_value = integer_zero_node;
3144             }
3145
3146           if (TREE_CODE (arg0) != VAR_DECL && TREE_CODE (arg0) != PARM_DECL)
3147             arg0 = save_expr (arg0);
3148           test = fold (build (COND_EXPR, type, test,
3149                               fold (build (code, type, arg0, true_value)),
3150                               fold (build (code, type, arg0, false_value))));
3151           if (TREE_CODE (arg0) == SAVE_EXPR)
3152             return build (COMPOUND_EXPR, type,
3153                           convert (void_type_node, arg0), test);
3154           else
3155             return convert (type, test);
3156         }
3157
3158       else if (TREE_CODE (arg0) == COMPOUND_EXPR)
3159         return build (COMPOUND_EXPR, type, TREE_OPERAND (arg0, 0),
3160                       fold (build (code, type, TREE_OPERAND (arg0, 1), arg1)));
3161       else if (TREE_CODE (arg0) == COND_EXPR
3162                || TREE_CODE_CLASS (TREE_CODE (arg0)) == '<')
3163         {
3164           tree test, true_value, false_value;
3165
3166           if (TREE_CODE (arg0) == COND_EXPR)
3167             {
3168               test = TREE_OPERAND (arg0, 0);
3169               true_value = TREE_OPERAND (arg0, 1);
3170               false_value = TREE_OPERAND (arg0, 2);
3171             }
3172           else
3173             {
3174               test = arg0;
3175               true_value = integer_one_node;
3176               false_value = integer_zero_node;
3177             }
3178
3179           if (TREE_CODE (arg1) != VAR_DECL && TREE_CODE (arg1) != PARM_DECL)
3180             arg1 = save_expr (arg1);
3181           test = fold (build (COND_EXPR, type, test,
3182                               fold (build (code, type, true_value, arg1)),
3183                               fold (build (code, type, false_value, arg1))));
3184           if (TREE_CODE (arg1) == SAVE_EXPR)
3185             return build (COMPOUND_EXPR, type,
3186                           convert (void_type_node, arg1), test);
3187           else
3188             return convert (type, test);
3189         }
3190     }
3191   else if (TREE_CODE_CLASS (code) == '<'
3192            && TREE_CODE (arg0) == COMPOUND_EXPR)
3193     return build (COMPOUND_EXPR, type, TREE_OPERAND (arg0, 0),
3194                   fold (build (code, type, TREE_OPERAND (arg0, 1), arg1)));
3195   else if (TREE_CODE_CLASS (code) == '<'
3196            && TREE_CODE (arg1) == COMPOUND_EXPR)
3197     return build (COMPOUND_EXPR, type, TREE_OPERAND (arg1, 0),
3198                   fold (build (code, type, arg0, TREE_OPERAND (arg1, 1))));
3199
3200   switch (code)
3201     {
3202     case INTEGER_CST:
3203     case REAL_CST:
3204     case STRING_CST:
3205     case COMPLEX_CST:
3206     case CONSTRUCTOR:
3207       return t;
3208
3209     case CONST_DECL:
3210       return fold (DECL_INITIAL (t));
3211
3212     case NOP_EXPR:
3213     case FLOAT_EXPR:
3214     case CONVERT_EXPR:
3215     case FIX_TRUNC_EXPR:
3216       /* Other kinds of FIX are not handled properly by fold_convert.  */
3217       /* Two conversions in a row are not needed unless:
3218          - the intermediate type is narrower than both initial and final, or
3219          - the intermediate type and innermost type differ in signedness,
3220            and the outermost type is wider than the intermediate, or
3221          - the initial type is a pointer type and the precisions of the
3222            intermediate and final types differ, or
3223          - the final type is a pointer type and the precisions of the
3224           initial and intermediate types differ.  */
3225       if ((TREE_CODE (TREE_OPERAND (t, 0)) == NOP_EXPR
3226            || TREE_CODE (TREE_OPERAND (t, 0)) == CONVERT_EXPR)
3227           && (TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (t, 0)))
3228               > TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 0), 0)))
3229               ||
3230               TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (t, 0)))
3231               > TYPE_PRECISION (TREE_TYPE (t)))
3232           && ! ((TREE_CODE (TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 0), 0)))
3233                  == INTEGER_TYPE)
3234                 && (TREE_CODE (TREE_TYPE (TREE_OPERAND (t, 0)))
3235                     == INTEGER_TYPE)
3236                 && (TREE_UNSIGNED (TREE_TYPE (TREE_OPERAND (t, 0)))
3237                     != TREE_UNSIGNED (TREE_OPERAND (TREE_OPERAND (t, 0), 0)))
3238                 && (TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (t, 0)))
3239                     < TYPE_PRECISION (TREE_TYPE (t))))
3240           && ((TREE_UNSIGNED (TREE_TYPE (TREE_OPERAND (t, 0)))
3241                && (TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (t, 0)))
3242                    > TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 0), 0)))))
3243               ==
3244               (TREE_UNSIGNED (TREE_TYPE (t))
3245                && (TYPE_PRECISION (TREE_TYPE (t))
3246                    > TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (t, 0))))))
3247           && ! ((TREE_CODE (TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 0), 0)))
3248                  == POINTER_TYPE)
3249                 && (TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (t, 0)))
3250                     != TYPE_PRECISION (TREE_TYPE (t))))
3251           && ! (TREE_CODE (TREE_TYPE (t)) == POINTER_TYPE
3252                 && (TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 0), 0)))
3253                     != TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (t, 0))))))
3254         return convert (TREE_TYPE (t), TREE_OPERAND (TREE_OPERAND (t, 0), 0));
3255
3256       if (TREE_CODE (TREE_OPERAND (t, 0)) == MODIFY_EXPR
3257           && TREE_CONSTANT (TREE_OPERAND (TREE_OPERAND (t, 0), 1))
3258           /* Detect assigning a bitfield.  */
3259           && !(TREE_CODE (TREE_OPERAND (TREE_OPERAND (t, 0), 0)) == COMPONENT_REF
3260                && DECL_BIT_FIELD (TREE_OPERAND (TREE_OPERAND (TREE_OPERAND (t, 0), 0), 1))))
3261         {
3262           /* Don't leave an assignment inside a conversion
3263              unless assigning a bitfield.  */
3264           tree prev = TREE_OPERAND (t, 0);
3265           TREE_OPERAND (t, 0) = TREE_OPERAND (prev, 1);
3266           /* First do the assignment, then return converted constant.  */
3267           t = build (COMPOUND_EXPR, TREE_TYPE (t), prev, fold (t));
3268           TREE_USED (t) = 1;
3269           return t;
3270         }
3271       if (!wins)
3272         {
3273           TREE_CONSTANT (t) = TREE_CONSTANT (arg0);
3274           return t;
3275         }
3276       return fold_convert (t, arg0);
3277
3278 #if 0  /* This loses on &"foo"[0].  */
3279     case ARRAY_REF:
3280         {
3281           int i;
3282
3283           /* Fold an expression like: "foo"[2] */
3284           if (TREE_CODE (arg0) == STRING_CST
3285               && TREE_CODE (arg1) == INTEGER_CST
3286               && !TREE_INT_CST_HIGH (arg1)
3287               && (i = TREE_INT_CST_LOW (arg1)) < TREE_STRING_LENGTH (arg0))
3288             {
3289               t = build_int_2 (TREE_STRING_POINTER (arg0)[i], 0);
3290               TREE_TYPE (t) = TREE_TYPE (TREE_TYPE (arg0));
3291               force_fit_type (t, 0);
3292             }
3293         }
3294       return t;
3295 #endif /* 0 */
3296
3297     case RANGE_EXPR:
3298       TREE_CONSTANT (t) = wins;
3299       return t;
3300
3301     case NEGATE_EXPR:
3302       if (wins)
3303         {
3304           if (TREE_CODE (arg0) == INTEGER_CST)
3305             {
3306               HOST_WIDE_INT low, high;
3307               int overflow = neg_double (TREE_INT_CST_LOW (arg0),
3308                                          TREE_INT_CST_HIGH (arg0),
3309                                          &low, &high);
3310               t = build_int_2 (low, high);
3311               TREE_TYPE (t) = type;
3312               TREE_CONSTANT_OVERFLOW (t)
3313                 = (TREE_CONSTANT_OVERFLOW (arg0)
3314                    | force_fit_type (t, overflow));
3315             }
3316           else if (TREE_CODE (arg0) == REAL_CST)
3317             t = build_real (type, REAL_VALUE_NEGATE (TREE_REAL_CST (arg0)));
3318           TREE_TYPE (t) = type;
3319         }
3320       else if (TREE_CODE (arg0) == NEGATE_EXPR)
3321         return TREE_OPERAND (arg0, 0);
3322
3323       /* Convert - (a - b) to (b - a) for non-floating-point.  */
3324       else if (TREE_CODE (arg0) == MINUS_EXPR && TREE_CODE (type) != REAL_TYPE)
3325         return build (MINUS_EXPR, type, TREE_OPERAND (arg0, 1),
3326                       TREE_OPERAND (arg0, 0));
3327
3328       return t;
3329
3330     case ABS_EXPR:
3331       if (wins)
3332         {
3333           if (TREE_CODE (arg0) == INTEGER_CST)
3334             {
3335               if (! TREE_UNSIGNED (type)
3336                   && TREE_INT_CST_HIGH (arg0) < 0)
3337                 {
3338                   HOST_WIDE_INT low, high;
3339                   int overflow = neg_double (TREE_INT_CST_LOW (arg0),
3340                                              TREE_INT_CST_HIGH (arg0),
3341                                              &low, &high);
3342                   t = build_int_2 (low, high);
3343                   TREE_TYPE (t) = type;
3344                   TREE_CONSTANT_OVERFLOW (t)
3345                     = (TREE_CONSTANT_OVERFLOW (arg0)
3346                        | force_fit_type (t, overflow));
3347                 }
3348             }
3349           else if (TREE_CODE (arg0) == REAL_CST)
3350             {
3351               if (REAL_VALUE_NEGATIVE (TREE_REAL_CST (arg0)))
3352                 t = build_real (type,
3353                                 REAL_VALUE_NEGATE (TREE_REAL_CST (arg0)));
3354             }
3355           TREE_TYPE (t) = type;
3356         }
3357       else if (TREE_CODE (arg0) == ABS_EXPR || TREE_CODE (arg0) == NEGATE_EXPR)
3358         return build1 (ABS_EXPR, type, TREE_OPERAND (arg0, 0));
3359       return t;
3360
3361     case BIT_NOT_EXPR:
3362       if (wins)
3363         {
3364           if (TREE_CODE (arg0) == INTEGER_CST)
3365             t = build_int_2 (~ TREE_INT_CST_LOW (arg0),
3366                              ~ TREE_INT_CST_HIGH (arg0));
3367           TREE_TYPE (t) = type;
3368           force_fit_type (t, 0);
3369           TREE_CONSTANT_OVERFLOW (t) = TREE_CONSTANT_OVERFLOW (arg0);
3370         }
3371       else if (TREE_CODE (arg0) == BIT_NOT_EXPR)
3372         return TREE_OPERAND (arg0, 0);
3373       return t;
3374
3375     case PLUS_EXPR:
3376       /* A + (-B) -> A - B */
3377       if (TREE_CODE (arg1) == NEGATE_EXPR)
3378         return fold (build (MINUS_EXPR, type, arg0, TREE_OPERAND (arg1, 0)));
3379       else if (TREE_CODE (type) != REAL_TYPE)
3380         {
3381           if (integer_zerop (arg1))
3382             return non_lvalue (convert (type, arg0));
3383
3384           /* If we are adding two BIT_AND_EXPR's, both of which are and'ing
3385              with a constant, and the two constants have no bits in common,
3386              we should treat this as a BIT_IOR_EXPR since this may produce more
3387              simplifications.  */
3388           if (TREE_CODE (arg0) == BIT_AND_EXPR
3389               && TREE_CODE (arg1) == BIT_AND_EXPR
3390               && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
3391               && TREE_CODE (TREE_OPERAND (arg1, 1)) == INTEGER_CST
3392               && integer_zerop (const_binop (BIT_AND_EXPR,
3393                                              TREE_OPERAND (arg0, 1),
3394                                              TREE_OPERAND (arg1, 1), 0)))
3395             {
3396               code = BIT_IOR_EXPR;
3397               goto bit_ior;
3398             }
3399         }
3400       /* In IEEE floating point, x+0 may not equal x.  */
3401       else if (TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
3402                && real_zerop (arg1))
3403         return non_lvalue (convert (type, arg0));
3404     associate:
3405       /* In most languages, can't associate operations on floats
3406          through parentheses.  Rather than remember where the parentheses
3407          were, we don't associate floats at all.  It shouldn't matter much.  */
3408       if (TREE_CODE (type) == REAL_TYPE)
3409         goto binary;
3410       /* The varsign == -1 cases happen only for addition and subtraction.
3411          It says that the arg that was split was really CON minus VAR.
3412          The rest of the code applies to all associative operations.  */
3413       if (!wins)
3414         {
3415           tree var, con;
3416           int varsign;
3417
3418           if (split_tree (arg0, code, &var, &con, &varsign))
3419             {
3420               if (varsign == -1)
3421                 {
3422                   /* EXPR is (CON-VAR) +- ARG1.  */
3423                   /* If it is + and VAR==ARG1, return just CONST.  */
3424                   if (code == PLUS_EXPR && operand_equal_p (var, arg1, 0))
3425                     return convert (TREE_TYPE (t), con);
3426
3427                   /* If ARG0 is a constant, don't change things around;
3428                      instead keep all the constant computations together.  */
3429
3430                   if (TREE_CONSTANT (arg0))
3431                     return t;
3432
3433                   /* Otherwise return (CON +- ARG1) - VAR.  */
3434                   TREE_SET_CODE (t, MINUS_EXPR);
3435                   TREE_OPERAND (t, 1) = var;
3436                   TREE_OPERAND (t, 0)
3437                     = fold (build (code, TREE_TYPE (t), con, arg1));
3438                 }
3439               else
3440                 {
3441                   /* EXPR is (VAR+CON) +- ARG1.  */
3442                   /* If it is - and VAR==ARG1, return just CONST.  */
3443                   if (code == MINUS_EXPR && operand_equal_p (var, arg1, 0))
3444                     return convert (TREE_TYPE (t), con);
3445
3446                   /* If ARG0 is a constant, don't change things around;
3447                      instead keep all the constant computations together.  */
3448
3449                   if (TREE_CONSTANT (arg0))
3450                     return t;
3451
3452                   /* Otherwise return VAR +- (ARG1 +- CON).  */
3453                   TREE_OPERAND (t, 1) = tem
3454                     = fold (build (code, TREE_TYPE (t), arg1, con));
3455                   TREE_OPERAND (t, 0) = var;
3456                   if (integer_zerop (tem)
3457                       && (code == PLUS_EXPR || code == MINUS_EXPR))
3458                     return convert (type, var);
3459                   /* If we have x +/- (c - d) [c an explicit integer]
3460                      change it to x -/+ (d - c) since if d is relocatable
3461                      then the latter can be a single immediate insn
3462                      and the former cannot.  */
3463                   if (TREE_CODE (tem) == MINUS_EXPR
3464                       && TREE_CODE (TREE_OPERAND (tem, 0)) == INTEGER_CST)
3465                     {
3466                       tree tem1 = TREE_OPERAND (tem, 1);
3467                       TREE_OPERAND (tem, 1) = TREE_OPERAND (tem, 0);
3468                       TREE_OPERAND (tem, 0) = tem1;
3469                       TREE_SET_CODE (t,
3470                                      (code == PLUS_EXPR ? MINUS_EXPR : PLUS_EXPR));
3471                     }
3472                 }
3473               return t;
3474             }
3475
3476           if (split_tree (arg1, code, &var, &con, &varsign))
3477             {
3478               /* EXPR is ARG0 +- (CON +- VAR).  */
3479               if (TREE_CODE (t) == MINUS_EXPR
3480                   && operand_equal_p (var, arg0, 0))
3481                 {
3482                   /* If VAR and ARG0 cancel, return just CON or -CON.  */
3483                   if (code == PLUS_EXPR)
3484                     return convert (TREE_TYPE (t), con);
3485                   return fold (build1 (NEGATE_EXPR, TREE_TYPE (t),
3486                                        convert (TREE_TYPE (t), con)));
3487                 }
3488               if (TREE_CONSTANT (arg1))
3489                 return t;
3490               if (varsign == -1)
3491                 TREE_SET_CODE (t,
3492                                (code == PLUS_EXPR ? MINUS_EXPR : PLUS_EXPR));
3493               TREE_OPERAND (t, 0)
3494                 = fold (build (code, TREE_TYPE (t), arg0, con));
3495               TREE_OPERAND (t, 1) = var;
3496               if (integer_zerop (TREE_OPERAND (t, 0))
3497                   && TREE_CODE (t) == PLUS_EXPR)
3498                 return convert (TREE_TYPE (t), var);
3499               return t;
3500             }
3501         }
3502     binary:
3503 #if defined (REAL_IS_NOT_DOUBLE) && ! defined (REAL_ARITHMETIC)
3504       if (TREE_CODE (arg1) == REAL_CST)
3505         return t;
3506 #endif /* REAL_IS_NOT_DOUBLE, and no REAL_ARITHMETIC */
3507       if (wins)
3508         t1 = const_binop (code, arg0, arg1, 0);
3509       if (t1 != NULL_TREE)
3510         {
3511           /* The return value should always have
3512              the same type as the original expression.  */
3513           TREE_TYPE (t1) = TREE_TYPE (t);
3514           return t1;
3515         }
3516       return t;
3517
3518     case MINUS_EXPR:
3519       if (TREE_CODE (type) != REAL_TYPE)
3520         {
3521           if (! wins && integer_zerop (arg0))
3522             return build1 (NEGATE_EXPR, type, arg1);
3523           if (integer_zerop (arg1))
3524             return non_lvalue (convert (type, arg0));
3525         }
3526       /* Convert A - (-B) to A + B.  */
3527       else if (TREE_CODE (arg1) == NEGATE_EXPR)
3528         return fold (build (PLUS_EXPR, type, arg0, TREE_OPERAND (arg1, 0)));
3529       else if (TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT)
3530         {
3531           /* Except with IEEE floating point, 0-x equals -x.  */
3532           if (! wins && real_zerop (arg0))
3533             return build1 (NEGATE_EXPR, type, arg1);
3534           /* Except with IEEE floating point, x-0 equals x.  */
3535           if (real_zerop (arg1))
3536             return non_lvalue (convert (type, arg0));
3537
3538           /* Fold &x - &x.  This can happen from &x.foo - &x.
3539              This is unsafe for certain floats even in non-IEEE formats.
3540              In IEEE, it is unsafe because it does wrong for NaNs.
3541              Also note that operand_equal_p is always false if an operand
3542              is volatile.  */
3543
3544           if (operand_equal_p (arg0, arg1,
3545                                TREE_CODE (type) == REAL_TYPE))
3546             return convert (type, integer_zero_node);
3547         }
3548       goto associate;
3549
3550     case MULT_EXPR:
3551       if (TREE_CODE (type) != REAL_TYPE)
3552         {
3553           if (integer_zerop (arg1))
3554             return omit_one_operand (type, arg1, arg0);
3555           if (integer_onep (arg1))
3556             return non_lvalue (convert (type, arg0));
3557
3558           /* (a * (1 << b)) is (a << b)  */
3559           if (TREE_CODE (arg1) == LSHIFT_EXPR
3560               && integer_onep (TREE_OPERAND (arg1, 0)))
3561             return fold (build (LSHIFT_EXPR, type, arg0,
3562                                 TREE_OPERAND (arg1, 1)));
3563           if (TREE_CODE (arg0) == LSHIFT_EXPR
3564               && integer_onep (TREE_OPERAND (arg0, 0)))
3565             return fold (build (LSHIFT_EXPR, type, arg1,
3566                                 TREE_OPERAND (arg0, 1)));
3567         }
3568       else
3569         {
3570           /* x*0 is 0, except for IEEE floating point.  */
3571           if (TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
3572               && real_zerop (arg1))
3573             return omit_one_operand (type, arg1, arg0);
3574           /* In IEEE floating point, x*1 is not equivalent to x for snans.
3575              However, ANSI says we can drop signals,
3576              so we can do this anyway.  */
3577           if (real_onep (arg1))
3578             return non_lvalue (convert (type, arg0));
3579           /* x*2 is x+x */
3580           if (! wins && real_twop (arg1))
3581             {
3582               tree arg = save_expr (arg0);
3583               return build (PLUS_EXPR, type, arg, arg);
3584             }
3585         }
3586       goto associate;
3587
3588     case BIT_IOR_EXPR:
3589     bit_ior:
3590       if (integer_all_onesp (arg1))
3591         return omit_one_operand (type, arg1, arg0);
3592       if (integer_zerop (arg1))
3593         return non_lvalue (convert (type, arg0));
3594       t1 = distribute_bit_expr (code, type, arg0, arg1);
3595       if (t1 != NULL_TREE)
3596         return t1;
3597
3598       /* (a << C1) | (a >> C2) if A is unsigned and C1+C2 is the size of A
3599          is a rotate of A by C1 bits.  */
3600
3601       if ((TREE_CODE (arg0) == RSHIFT_EXPR
3602            || TREE_CODE (arg0) == LSHIFT_EXPR)
3603           && (TREE_CODE (arg1) == RSHIFT_EXPR
3604               || TREE_CODE (arg1) == LSHIFT_EXPR)
3605           && TREE_CODE (arg0) != TREE_CODE (arg1)
3606           && operand_equal_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg1,0), 0)
3607           && TREE_UNSIGNED (TREE_TYPE (TREE_OPERAND (arg0, 0)))
3608           && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
3609           && TREE_CODE (TREE_OPERAND (arg1, 1)) == INTEGER_CST
3610           && TREE_INT_CST_HIGH (TREE_OPERAND (arg0, 1)) == 0
3611           && TREE_INT_CST_HIGH (TREE_OPERAND (arg1, 1)) == 0
3612           && ((TREE_INT_CST_LOW (TREE_OPERAND (arg0, 1))
3613                + TREE_INT_CST_LOW (TREE_OPERAND (arg1, 1)))
3614               == TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (arg0, 0)))))
3615         return build (LROTATE_EXPR, type, TREE_OPERAND (arg0, 0),
3616                       TREE_CODE (arg0) == LSHIFT_EXPR
3617                       ? TREE_OPERAND (arg0, 1) : TREE_OPERAND (arg1, 1));
3618
3619       goto associate;
3620
3621     case BIT_XOR_EXPR:
3622       if (integer_zerop (arg1))
3623         return non_lvalue (convert (type, arg0));
3624       if (integer_all_onesp (arg1))
3625         return fold (build1 (BIT_NOT_EXPR, type, arg0));
3626       goto associate;
3627
3628     case BIT_AND_EXPR:
3629     bit_and:
3630       if (integer_all_onesp (arg1))
3631         return non_lvalue (convert (type, arg0));
3632       if (integer_zerop (arg1))
3633         return omit_one_operand (type, arg1, arg0);
3634       t1 = distribute_bit_expr (code, type, arg0, arg1);
3635       if (t1 != NULL_TREE)
3636         return t1;
3637       /* Simplify ((int)c & 0x377) into (int)c, if c is unsigned char.  */
3638       if (TREE_CODE (arg0) == INTEGER_CST && TREE_CODE (arg1) == NOP_EXPR
3639           && TREE_UNSIGNED (TREE_TYPE (TREE_OPERAND (arg1, 0))))
3640         {
3641           int prec = TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (arg1, 0)));
3642           if (prec < BITS_PER_WORD && prec < HOST_BITS_PER_WIDE_INT
3643               && (~TREE_INT_CST_LOW (arg0)
3644                   & (((HOST_WIDE_INT) 1 << prec) - 1)) == 0)
3645             return build1 (NOP_EXPR, type, TREE_OPERAND (arg1, 0));
3646         }
3647       if (TREE_CODE (arg1) == INTEGER_CST && TREE_CODE (arg0) == NOP_EXPR
3648           && TREE_UNSIGNED (TREE_TYPE (TREE_OPERAND (arg0, 0))))
3649         {
3650           int prec = TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (arg0, 0)));
3651           if (prec < BITS_PER_WORD && prec < HOST_BITS_PER_WIDE_INT
3652               && (~TREE_INT_CST_LOW (arg1)
3653                   & (((HOST_WIDE_INT) 1 << prec) - 1)) == 0)
3654             return build1 (NOP_EXPR, type, TREE_OPERAND (arg0, 0));
3655         }
3656       goto associate;
3657
3658     case BIT_ANDTC_EXPR:
3659       if (integer_all_onesp (arg0))
3660         return non_lvalue (convert (type, arg1));
3661       if (integer_zerop (arg0))
3662         return omit_one_operand (type, arg0, arg1);
3663       if (TREE_CODE (arg1) == INTEGER_CST)
3664         {
3665           arg1 = fold (build1 (BIT_NOT_EXPR, type, arg1));
3666           code = BIT_AND_EXPR;
3667           goto bit_and;
3668         }
3669       goto binary;
3670
3671     case TRUNC_DIV_EXPR:
3672     case ROUND_DIV_EXPR:
3673     case FLOOR_DIV_EXPR:
3674     case CEIL_DIV_EXPR:
3675     case EXACT_DIV_EXPR:
3676     case RDIV_EXPR:
3677       if (integer_onep (arg1))
3678         return non_lvalue (convert (type, arg0));
3679       if (integer_zerop (arg1))
3680         return t;
3681
3682       /* If we have ((a * C1) / C2) and C1 % C2 == 0, we can replace this with
3683          (a * (C1/C2).  Also look for when we have a SAVE_EXPR in
3684          between.  */
3685       if (TREE_CODE (arg1) == INTEGER_CST
3686           && TREE_INT_CST_LOW (arg1) > 0 && TREE_INT_CST_HIGH (arg1) == 0
3687           && TREE_CODE (arg0) == MULT_EXPR
3688           && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
3689           && TREE_INT_CST_LOW (TREE_OPERAND (arg0, 1)) > 0
3690           && TREE_INT_CST_HIGH (TREE_OPERAND (arg0, 1)) == 0
3691           && 0 == (TREE_INT_CST_LOW (TREE_OPERAND (arg0, 1))
3692                    % TREE_INT_CST_LOW (arg1)))
3693         {
3694           tree new_op
3695             = build_int_2 (TREE_INT_CST_LOW (TREE_OPERAND (arg0, 1))
3696                            / TREE_INT_CST_LOW (arg1), 0);
3697
3698           TREE_TYPE (new_op) = type;
3699           return build (MULT_EXPR, type, TREE_OPERAND (arg0, 0), new_op);
3700         }
3701
3702       else if (TREE_CODE (arg1) == INTEGER_CST
3703                && TREE_INT_CST_LOW (arg1) > 0 && TREE_INT_CST_HIGH (arg1) == 0
3704                && TREE_CODE (arg0) == SAVE_EXPR
3705                && TREE_CODE (TREE_OPERAND (arg0, 0)) == MULT_EXPR
3706                && (TREE_CODE (TREE_OPERAND (TREE_OPERAND (arg0, 0), 1))
3707                    == INTEGER_CST)
3708                && (TREE_INT_CST_LOW (TREE_OPERAND (TREE_OPERAND (arg0, 0), 1))
3709                    > 0)
3710                && (TREE_INT_CST_HIGH (TREE_OPERAND (TREE_OPERAND (arg0, 0), 1))
3711                    == 0)
3712                && (TREE_INT_CST_LOW (TREE_OPERAND (TREE_OPERAND (arg0, 0), 1))
3713                    % TREE_INT_CST_LOW (arg1)) == 0)
3714         {
3715           tree new_op
3716             = build_int_2 (TREE_INT_CST_LOW (TREE_OPERAND (TREE_OPERAND (arg0, 0), 1))
3717                            / TREE_INT_CST_LOW (arg1), 0);
3718
3719           TREE_TYPE (new_op) = type;
3720           return build (MULT_EXPR, type,
3721                         TREE_OPERAND (TREE_OPERAND (arg0, 0), 0), new_op);
3722         }
3723
3724 #if !defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
3725 #ifndef REAL_INFINITY
3726       if (TREE_CODE (arg1) == REAL_CST
3727           && real_zerop (arg1))
3728         return t;
3729 #endif
3730 #endif /* not REAL_IS_NOT_DOUBLE, or REAL_ARITHMETIC */
3731
3732       goto binary;
3733
3734     case CEIL_MOD_EXPR:
3735     case FLOOR_MOD_EXPR:
3736     case ROUND_MOD_EXPR:
3737     case TRUNC_MOD_EXPR:
3738       if (integer_onep (arg1))
3739         return omit_one_operand (type, integer_zero_node, arg0);
3740       if (integer_zerop (arg1))
3741         return t;
3742       goto binary;
3743
3744     case LSHIFT_EXPR:
3745     case RSHIFT_EXPR:
3746     case LROTATE_EXPR:
3747     case RROTATE_EXPR:
3748       if (integer_zerop (arg1))
3749         return non_lvalue (convert (type, arg0));
3750       /* Since negative shift count is not well-defined,
3751          don't try to compute it in the compiler.  */
3752       if (tree_int_cst_lt (arg1, integer_zero_node))
3753         return t;
3754       goto binary;
3755
3756     case MIN_EXPR:
3757       if (operand_equal_p (arg0, arg1, 0))
3758         return arg0;
3759       if (TREE_CODE (type) == INTEGER_TYPE
3760           && operand_equal_p (arg1, TYPE_MIN_VALUE (type), 1))
3761         return omit_one_operand (type, arg1, arg0);
3762       goto associate;
3763
3764     case MAX_EXPR:
3765       if (operand_equal_p (arg0, arg1, 0))
3766         return arg0;
3767       if (TREE_CODE (type) == INTEGER_TYPE
3768           && operand_equal_p (arg1, TYPE_MAX_VALUE (type), 1))
3769         return omit_one_operand (type, arg1, arg0);
3770       goto associate;
3771
3772     case TRUTH_NOT_EXPR:
3773       /* Note that the operand of this must be an int
3774          and its values must be 0 or 1.
3775          ("true" is a fixed value perhaps depending on the language,
3776          but we don't handle values other than 1 correctly yet.)  */
3777       return invert_truthvalue (arg0);
3778
3779     case TRUTH_ANDIF_EXPR:
3780       /* Note that the operands of this must be ints
3781          and their values must be 0 or 1.
3782          ("true" is a fixed value perhaps depending on the language.)  */
3783       /* If first arg is constant zero, return it.  */
3784       if (integer_zerop (arg0))
3785         return arg0;
3786     case TRUTH_AND_EXPR:
3787       /* If either arg is constant true, drop it.  */
3788       if (TREE_CODE (arg0) == INTEGER_CST && ! integer_zerop (arg0))
3789         return non_lvalue (arg1);
3790       if (TREE_CODE (arg1) == INTEGER_CST && ! integer_zerop (arg1))
3791         return non_lvalue (arg0);
3792       /* If second arg is constant zero, result is zero, but first arg
3793          must be evaluated.  */
3794       if (integer_zerop (arg1))
3795         return omit_one_operand (type, arg1, arg0);
3796
3797     truth_andor:
3798       /* Check for the possibility of merging component references.  If our
3799          lhs is another similar operation, try to merge its rhs with our
3800          rhs.  Then try to merge our lhs and rhs.  */
3801       if (optimize)
3802         {
3803           if (TREE_CODE (arg0) == code)
3804             {
3805               tem = fold_truthop (code, type,
3806                                   TREE_OPERAND (arg0, 1), arg1);
3807               if (tem)
3808                 return fold (build (code, type, TREE_OPERAND (arg0, 0), tem));
3809             }
3810
3811           tem = fold_truthop (code, type, arg0, arg1);
3812           if (tem)
3813             return tem;
3814         }
3815       return t;
3816
3817     case TRUTH_ORIF_EXPR:
3818       /* Note that the operands of this must be ints
3819          and their values must be 0 or true.
3820          ("true" is a fixed value perhaps depending on the language.)  */
3821       /* If first arg is constant true, return it.  */
3822       if (TREE_CODE (arg0) == INTEGER_CST && ! integer_zerop (arg0))
3823         return arg0;
3824     case TRUTH_OR_EXPR:
3825       /* If either arg is constant zero, drop it.  */
3826       if (TREE_CODE (arg0) == INTEGER_CST && integer_zerop (arg0))
3827         return non_lvalue (arg1);
3828       if (TREE_CODE (arg1) == INTEGER_CST && integer_zerop (arg1))
3829         return non_lvalue (arg0);
3830       /* If second arg is constant true, result is true, but we must
3831          evaluate first arg.  */
3832       if (TREE_CODE (arg1) == INTEGER_CST && ! integer_zerop (arg1))
3833         return omit_one_operand (type, arg1, arg0);
3834       goto truth_andor;
3835
3836     case TRUTH_XOR_EXPR:
3837       /* If either arg is constant zero, drop it.  */
3838       if (integer_zerop (arg0))
3839         return non_lvalue (arg1);
3840       if (integer_zerop (arg1))
3841         return non_lvalue (arg0);
3842       /* If either arg is constant true, this is a logical inversion.  */
3843       if (integer_onep (arg0))
3844         return non_lvalue (invert_truthvalue (arg1));
3845       if (integer_onep (arg1))
3846         return non_lvalue (invert_truthvalue (arg0));
3847       break;
3848
3849     case EQ_EXPR:
3850     case NE_EXPR:
3851     case LT_EXPR:
3852     case GT_EXPR:
3853     case LE_EXPR:
3854     case GE_EXPR:
3855       /* If one arg is a constant integer, put it last.  */
3856       if (TREE_CODE (arg0) == INTEGER_CST
3857           && TREE_CODE (arg1) != INTEGER_CST)
3858         {
3859           TREE_OPERAND (t, 0) = arg1;
3860           TREE_OPERAND (t, 1) = arg0;
3861           arg0 = TREE_OPERAND (t, 0);
3862           arg1 = TREE_OPERAND (t, 1);
3863           code = swap_tree_comparison (code);
3864           TREE_SET_CODE (t, code);
3865         }
3866
3867       /* Convert foo++ == CONST into ++foo == CONST + INCR.
3868          First, see if one arg is constant; find the constant arg
3869          and the other one.  */
3870       {
3871         tree constop = 0, varop;
3872         tree *constoploc;
3873
3874         if (TREE_CONSTANT (arg1))
3875           constoploc = &TREE_OPERAND (t, 1), constop = arg1, varop = arg0;
3876         if (TREE_CONSTANT (arg0))
3877           constoploc = &TREE_OPERAND (t, 0), constop = arg0, varop = arg1;
3878
3879         if (constop && TREE_CODE (varop) == POSTINCREMENT_EXPR)
3880           {
3881             /* This optimization is invalid for ordered comparisons
3882                if CONST+INCR overflows or if foo+incr might overflow.
3883                This optimization is invalid for floating point due to rounding.
3884                For pointer types we assume overflow doesn't happen.  */
3885             if (TREE_CODE (TREE_TYPE (varop)) == POINTER_TYPE
3886                 || (TREE_CODE (TREE_TYPE (varop)) != REAL_TYPE
3887                     && (code == EQ_EXPR || code == NE_EXPR)))
3888               {
3889                 tree newconst
3890                   = fold (build (PLUS_EXPR, TREE_TYPE (varop),
3891                                  constop, TREE_OPERAND (varop, 1)));
3892                 TREE_SET_CODE (varop, PREINCREMENT_EXPR);
3893                 *constoploc = newconst;
3894                 return t;
3895               }
3896           }
3897         else if (constop && TREE_CODE (varop) == POSTDECREMENT_EXPR)
3898           {
3899             if (TREE_CODE (TREE_TYPE (varop)) == POINTER_TYPE
3900                 || (TREE_CODE (TREE_TYPE (varop)) != REAL_TYPE
3901                     && (code == EQ_EXPR || code == NE_EXPR)))
3902               {
3903                 tree newconst
3904                   = fold (build (MINUS_EXPR, TREE_TYPE (varop),
3905                                  constop, TREE_OPERAND (varop, 1)));
3906                 TREE_SET_CODE (varop, PREDECREMENT_EXPR);
3907                 *constoploc = newconst;
3908                 return t;
3909               }
3910           }
3911       }
3912
3913       /* Change X >= CST to X > (CST - 1) if CST is positive.  */
3914       if (TREE_CODE (arg1) == INTEGER_CST
3915           && TREE_CODE (arg0) != INTEGER_CST
3916           && ! tree_int_cst_lt (arg1, integer_one_node))
3917         {
3918           switch (TREE_CODE (t))
3919             {
3920             case GE_EXPR:
3921               code = GT_EXPR;
3922               TREE_SET_CODE (t, code);
3923               arg1 = const_binop (MINUS_EXPR, arg1, integer_one_node, 0);
3924               TREE_OPERAND (t, 1) = arg1;
3925               break;
3926
3927             case LT_EXPR:
3928               code = LE_EXPR;
3929               TREE_SET_CODE (t, code);
3930               arg1 = const_binop (MINUS_EXPR, arg1, integer_one_node, 0);
3931               TREE_OPERAND (t, 1) = arg1;
3932             }
3933         }
3934
3935       /* If this is an EQ or NE comparison with zero and ARG0 is
3936          (1 << foo) & bar, convert it to (bar >> foo) & 1.  Both require
3937          two operations, but the latter can be done in one less insn
3938          one machine that have only two-operand insns or on which a
3939          constant cannot be the first operand.  */
3940       if (integer_zerop (arg1) && (code == EQ_EXPR || code == NE_EXPR)
3941           && TREE_CODE (arg0) == BIT_AND_EXPR)
3942         {
3943           if (TREE_CODE (TREE_OPERAND (arg0, 0)) == LSHIFT_EXPR
3944               && integer_onep (TREE_OPERAND (TREE_OPERAND (arg0, 0), 0)))
3945             return
3946               fold (build (code, type,
3947                            build (BIT_AND_EXPR, TREE_TYPE (arg0),
3948                                   build (RSHIFT_EXPR,
3949                                          TREE_TYPE (TREE_OPERAND (arg0, 0)),
3950                                          TREE_OPERAND (arg0, 1),
3951                                          TREE_OPERAND (TREE_OPERAND (arg0, 0), 1)),
3952                                   convert (TREE_TYPE (arg0),
3953                                            integer_one_node)),
3954                            arg1));
3955           else if (TREE_CODE (TREE_OPERAND (arg0, 1)) == LSHIFT_EXPR
3956                    && integer_onep (TREE_OPERAND (TREE_OPERAND (arg0, 1), 0)))
3957             return
3958               fold (build (code, type,
3959                            build (BIT_AND_EXPR, TREE_TYPE (arg0),
3960                                   build (RSHIFT_EXPR,
3961                                          TREE_TYPE (TREE_OPERAND (arg0, 1)),
3962                                          TREE_OPERAND (arg0, 0),
3963                                          TREE_OPERAND (TREE_OPERAND (arg0, 1), 1)),
3964                                   convert (TREE_TYPE (arg0),
3965                                            integer_one_node)),
3966                            arg1));
3967         }
3968
3969       /* If this is an NE comparison of zero with an AND of one, remove the
3970          comparison since the AND will give the correct value.  */
3971       if (code == NE_EXPR && integer_zerop (arg1)
3972           && TREE_CODE (arg0) == BIT_AND_EXPR
3973           && integer_onep (TREE_OPERAND (arg0, 1)))
3974         return convert (type, arg0);
3975
3976       /* If we have (A & C) == C where C is a power of 2, convert this into
3977          (A & C) != 0.  Similarly for NE_EXPR.  */
3978       if ((code == EQ_EXPR || code == NE_EXPR)
3979           && TREE_CODE (arg0) == BIT_AND_EXPR
3980           && integer_pow2p (TREE_OPERAND (arg0, 1))
3981           && operand_equal_p (TREE_OPERAND (arg0, 1), arg1, 0))
3982         return build (code == EQ_EXPR ? NE_EXPR : EQ_EXPR, type,
3983                       arg0, integer_zero_node);
3984
3985       /* Simplify comparison of something with itself.  (For IEEE
3986          floating-point, we can only do some of these simplifications.)  */
3987       if (operand_equal_p (arg0, arg1, 0))
3988         {
3989           switch (code)
3990             {
3991             case EQ_EXPR:
3992             case GE_EXPR:
3993             case LE_EXPR:
3994               if (TREE_CODE (TREE_TYPE (arg0)) == INTEGER_TYPE)
3995                 {
3996                   t = build_int_2 (1, 0);
3997                   TREE_TYPE (t) = type;
3998                   return t;
3999                 }
4000               code = EQ_EXPR;
4001               TREE_SET_CODE (t, code);
4002               break;
4003
4004             case NE_EXPR:
4005               /* For NE, we can only do this simplification if integer.  */
4006               if (TREE_CODE (TREE_TYPE (arg0)) != INTEGER_TYPE)
4007                 break;
4008               /* ... fall through ... */
4009             case GT_EXPR:
4010             case LT_EXPR:
4011               t = build_int_2 (0, 0);
4012               TREE_TYPE (t) = type;
4013               return t;
4014             }
4015         }
4016
4017       /* An unsigned comparison against 0 can be simplified.  */
4018       if (integer_zerop (arg1)
4019           && (TREE_CODE (TREE_TYPE (arg1)) == INTEGER_TYPE
4020               || TREE_CODE (TREE_TYPE (arg1)) == POINTER_TYPE)
4021           && TREE_UNSIGNED (TREE_TYPE (arg1)))
4022         {
4023           switch (TREE_CODE (t))
4024             {
4025             case GT_EXPR:
4026               code = NE_EXPR;
4027               TREE_SET_CODE (t, NE_EXPR);
4028               break;
4029             case LE_EXPR:
4030               code = EQ_EXPR;
4031               TREE_SET_CODE (t, EQ_EXPR);
4032               break;
4033             case GE_EXPR:
4034               return omit_one_operand (integer_type_node,
4035                                        integer_one_node, arg0);
4036             case LT_EXPR:
4037               return omit_one_operand (integer_type_node,
4038                                        integer_zero_node, arg0);
4039             }
4040         }
4041
4042       /* If we are comparing an expression that just has comparisons
4043          of two integer values, arithmetic expressions of those comparisons,
4044          and constants, we can simplify it.  There are only three cases
4045          to check: the two values can either be equal, the first can be
4046          greater, or the second can be greater.  Fold the expression for
4047          those three values.  Since each value must be 0 or 1, we have
4048          eight possibilities, each of which corresponds to the constant 0
4049          or 1 or one of the six possible comparisons.
4050
4051          This handles common cases like (a > b) == 0 but also handles
4052          expressions like  ((x > y) - (y > x)) > 0, which supposedly
4053          occur in macroized code.  */
4054
4055       if (TREE_CODE (arg1) == INTEGER_CST && TREE_CODE (arg0) != INTEGER_CST)
4056         {
4057           tree cval1 = 0, cval2 = 0;
4058
4059           if (twoval_comparison_p (arg0, &cval1, &cval2)
4060               /* Don't handle degenerate cases here; they should already
4061                  have been handled anyway.  */
4062               && cval1 != 0 && cval2 != 0
4063               && ! (TREE_CONSTANT (cval1) && TREE_CONSTANT (cval2))
4064               && TREE_TYPE (cval1) == TREE_TYPE (cval2)
4065               && TREE_CODE (TREE_TYPE (cval1)) == INTEGER_TYPE
4066               && ! operand_equal_p (TYPE_MIN_VALUE (TREE_TYPE (cval1)),
4067                                     TYPE_MAX_VALUE (TREE_TYPE (cval2)), 0))
4068             {
4069               tree maxval = TYPE_MAX_VALUE (TREE_TYPE (cval1));
4070               tree minval = TYPE_MIN_VALUE (TREE_TYPE (cval1));
4071
4072               /* We can't just pass T to eval_subst in case cval1 or cval2
4073                  was the same as ARG1.  */
4074
4075               tree high_result
4076                 = fold (build (code, type,
4077                                eval_subst (arg0, cval1, maxval, cval2, minval),
4078                                arg1));
4079               tree equal_result
4080                 = fold (build (code, type,
4081                                eval_subst (arg0, cval1, maxval, cval2, maxval),
4082                                arg1));
4083               tree low_result
4084                 = fold (build (code, type,
4085                                eval_subst (arg0, cval1, minval, cval2, maxval),
4086                                arg1));
4087
4088               /* All three of these results should be 0 or 1.  Confirm they
4089                  are.  Then use those values to select the proper code
4090                  to use.  */
4091
4092               if ((integer_zerop (high_result)
4093                    || integer_onep (high_result))
4094                   && (integer_zerop (equal_result)
4095                       || integer_onep (equal_result))
4096                   && (integer_zerop (low_result)
4097                       || integer_onep (low_result)))
4098                 {
4099                   /* Make a 3-bit mask with the high-order bit being the
4100                      value for `>', the next for '=', and the low for '<'.  */
4101                   switch ((integer_onep (high_result) * 4)
4102                           + (integer_onep (equal_result) * 2)
4103                           + integer_onep (low_result))
4104                     {
4105                     case 0:
4106                       /* Always false.  */
4107                       return omit_one_operand (type, integer_zero_node, arg0);
4108                     case 1:
4109                       code = LT_EXPR;
4110                       break;
4111                     case 2:
4112                       code = EQ_EXPR;
4113                       break;
4114                     case 3:
4115                       code = LE_EXPR;
4116                       break;
4117                     case 4:
4118                       code = GT_EXPR;
4119                       break;
4120                     case 5:
4121                       code = NE_EXPR;
4122                       break;
4123                     case 6:
4124                       code = GE_EXPR;
4125                       break;
4126                     case 7:
4127                       /* Always true.  */
4128                       return omit_one_operand (type, integer_one_node, arg0);
4129                     }
4130
4131                   return fold (build (code, type, cval1, cval2));
4132                 }
4133             }
4134         }
4135
4136       /* If this is a comparison of a field, we may be able to simplify it.  */
4137       if ((TREE_CODE (arg0) == COMPONENT_REF
4138                 || TREE_CODE (arg0) == BIT_FIELD_REF)
4139                && (code == EQ_EXPR || code == NE_EXPR)
4140                /* Handle the constant case even without -O
4141                   to make sure the warnings are given.  */
4142                && (optimize || TREE_CODE (arg1) == INTEGER_CST))
4143         {
4144           t1 = optimize_bit_field_compare (code, type, arg0, arg1);
4145           return t1 ? t1 : t;
4146         }
4147
4148       /* From here on, the only cases we handle are when the result is
4149          known to be a constant.
4150
4151          To compute GT, swap the arguments and do LT.
4152          To compute GE, do LT and invert the result.
4153          To compute LE, swap the arguments, do LT and invert the result.
4154          To compute NE, do EQ and invert the result.
4155
4156          Therefore, the code below must handle only EQ and LT.  */
4157
4158       if (code == LE_EXPR || code == GT_EXPR)
4159         {
4160           tem = arg0, arg0 = arg1, arg1 = tem;
4161           code = swap_tree_comparison (code);
4162         }
4163
4164       /* Note that it is safe to invert for real values here because we
4165          will check below in the one case that it matters.  */
4166
4167       invert = 0;
4168       if (code == NE_EXPR || code == GE_EXPR)
4169         {
4170           invert = 1;
4171           code = invert_tree_comparison (code);
4172         }
4173
4174       /* Compute a result for LT or EQ if args permit;
4175          otherwise return T.  */
4176       if (TREE_CODE (arg0) == INTEGER_CST && TREE_CODE (arg1) == INTEGER_CST)
4177         {
4178           if (code == EQ_EXPR)
4179             t1 = build_int_2 ((TREE_INT_CST_LOW (arg0)
4180                                == TREE_INT_CST_LOW (arg1))
4181                               && (TREE_INT_CST_HIGH (arg0)
4182                                   == TREE_INT_CST_HIGH (arg1)),
4183                               0);
4184           else
4185             t1 = build_int_2 ((TREE_UNSIGNED (TREE_TYPE (arg0))
4186                                ? INT_CST_LT_UNSIGNED (arg0, arg1)
4187                                : INT_CST_LT (arg0, arg1)),
4188                               0);
4189         }
4190
4191       /* Assume a nonexplicit constant cannot equal an explicit one,
4192          since such code would be undefined anyway.
4193          Exception: on sysvr4, using #pragma weak,
4194          a label can come out as 0.  */
4195       else if (TREE_CODE (arg1) == INTEGER_CST
4196                && !integer_zerop (arg1)
4197                && TREE_CONSTANT (arg0)
4198                && TREE_CODE (arg0) == ADDR_EXPR
4199                && code == EQ_EXPR)
4200         t1 = build_int_2 (0, 0);
4201
4202       /* Two real constants can be compared explicitly.  */
4203       else if (TREE_CODE (arg0) == REAL_CST && TREE_CODE (arg1) == REAL_CST)
4204         {
4205           /* If either operand is a NaN, the result is false with two
4206              exceptions: First, an NE_EXPR is true on NaNs, but that case
4207              is already handled correctly since we will be inverting the
4208              result for NE_EXPR.  Second, if we had inverted a LE_EXPR
4209              or a GE_EXPR into a LT_EXPR, we must return true so that it
4210              will be inverted into false.  */
4211
4212           if (REAL_VALUE_ISNAN (TREE_REAL_CST (arg0))
4213               || REAL_VALUE_ISNAN (TREE_REAL_CST (arg1)))
4214             t1 = build_int_2 (invert && code == LT_EXPR, 0);
4215
4216           else if (code == EQ_EXPR)
4217             t1 = build_int_2 (REAL_VALUES_EQUAL (TREE_REAL_CST (arg0),
4218                                                  TREE_REAL_CST (arg1)),
4219                               0);
4220           else
4221             t1 = build_int_2 (REAL_VALUES_LESS (TREE_REAL_CST (arg0),
4222                                                 TREE_REAL_CST (arg1)),
4223                               0);
4224         }
4225
4226       if (t1 == NULL_TREE)
4227         return t;
4228
4229       if (invert)
4230         TREE_INT_CST_LOW (t1) ^= 1;
4231
4232       TREE_TYPE (t1) = type;
4233       return t1;
4234
4235     case COND_EXPR:
4236       if (TREE_CODE (arg0) == INTEGER_CST)
4237         return TREE_OPERAND (t, (integer_zerop (arg0) ? 2 : 1));
4238       else if (operand_equal_p (arg1, TREE_OPERAND (expr, 2), 0))
4239         return omit_one_operand (type, arg1, arg0);
4240
4241       /* If the second operand is zero, invert the comparison and swap
4242          the second and third operands.  Likewise if the second operand
4243          is constant and the third is not or if the third operand is
4244          equivalent to the first operand of the comparison.  */
4245
4246       if (integer_zerop (arg1)
4247           || (TREE_CONSTANT (arg1) && ! TREE_CONSTANT (TREE_OPERAND (t, 2)))
4248           || (TREE_CODE_CLASS (TREE_CODE (arg0)) == '<'
4249               && operand_equal_for_comparison_p (TREE_OPERAND (arg0, 0),
4250                                                  TREE_OPERAND (t, 2),
4251                                                  TREE_OPERAND (arg0, 1))))
4252         {
4253           /* See if this can be inverted.  If it can't, possibly because
4254              it was a floating-point inequality comparison, don't do
4255              anything.  */
4256           tem = invert_truthvalue (arg0);
4257
4258           if (TREE_CODE (tem) != TRUTH_NOT_EXPR)
4259             {
4260               arg0 = TREE_OPERAND (t, 0) = tem;
4261               TREE_OPERAND (t, 1) = TREE_OPERAND (t, 2);
4262               TREE_OPERAND (t, 2) = arg1;
4263               arg1 = TREE_OPERAND (t, 1);
4264             }
4265         }
4266
4267       /* If we have A op B ? A : C, we may be able to convert this to a
4268          simpler expression, depending on the operation and the values
4269          of B and C.  IEEE floating point prevents this though,
4270          because A or B might be -0.0 or a NaN.  */
4271
4272       if (TREE_CODE_CLASS (TREE_CODE (arg0)) == '<'
4273           && (TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
4274               || TREE_CODE (TREE_TYPE (TREE_OPERAND (arg0, 0))) != REAL_TYPE)
4275           && operand_equal_for_comparison_p (TREE_OPERAND (arg0, 0),
4276                                              arg1, TREE_OPERAND (arg0, 1)))
4277         {
4278           tree arg2 = TREE_OPERAND (t, 2);
4279           enum tree_code comp_code = TREE_CODE (arg0);
4280
4281           /* If we have A op 0 ? A : -A, this is A, -A, abs (A), or abs (-A),
4282              depending on the comparison operation.  */
4283           if (integer_zerop (TREE_OPERAND (arg0, 1))
4284               && TREE_CODE (arg2) == NEGATE_EXPR
4285               && operand_equal_p (TREE_OPERAND (arg2, 0), arg1, 0))
4286             switch (comp_code)
4287               {
4288               case EQ_EXPR:
4289                 return fold (build1 (NEGATE_EXPR, type, arg1));
4290               case NE_EXPR:
4291                 return convert (type, arg1);
4292               case GE_EXPR:
4293               case GT_EXPR:
4294                 return fold (build1 (ABS_EXPR, type, arg1));
4295               case LE_EXPR:
4296               case LT_EXPR:
4297                 return fold (build1 (NEGATE_EXPR, type,
4298                                      fold (build1 (ABS_EXPR, type, arg1))));
4299               }
4300
4301           /* If this is A != 0 ? A : 0, this is simply A.  For ==, it is
4302              always zero.  */
4303
4304           if (integer_zerop (TREE_OPERAND (arg0, 1)) && integer_zerop (arg2))
4305             {
4306               if (comp_code == NE_EXPR)
4307                 return convert (type, arg1);
4308               else if (comp_code == EQ_EXPR)
4309                 return convert (type, integer_zero_node);
4310             }
4311
4312           /* If this is A op B ? A : B, this is either A, B, min (A, B),
4313              or max (A, B), depending on the operation.  */
4314
4315           if (operand_equal_for_comparison_p (TREE_OPERAND (arg0, 1),
4316                                               arg2, TREE_OPERAND (arg0, 0)))
4317             switch (comp_code)
4318               {
4319               case EQ_EXPR:
4320                 return convert (type, arg2);
4321               case NE_EXPR:
4322                 return convert (type, arg1);
4323               case LE_EXPR:
4324               case LT_EXPR:
4325                 return fold (build (MIN_EXPR, type, arg1, arg2));
4326               case GE_EXPR:
4327               case GT_EXPR:
4328                 return fold (build (MAX_EXPR, type, arg1, arg2));
4329               }
4330
4331           /* If this is A op C1 ? A : C2 with C1 and C2 constant integers,
4332              we might still be able to simplify this.  For example,
4333              if C1 is one less or one more than C2, this might have started
4334              out as a MIN or MAX and been transformed by this function.
4335              Only good for INTEGER_TYPE, because we need TYPE_MAX_VALUE.  */
4336
4337           if (TREE_CODE (type) == INTEGER_TYPE
4338               && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
4339               && TREE_CODE (arg2) == INTEGER_CST)
4340             switch (comp_code)
4341               {
4342               case EQ_EXPR:
4343                 /* We can replace A with C1 in this case.  */
4344                 arg1 = TREE_OPERAND (t, 1)
4345                   = convert (type, TREE_OPERAND (arg0, 1));
4346                 break;
4347
4348               case LT_EXPR:
4349                 /* If C1 is C2 + 1, this is min(A, C2).  */
4350                 if (! operand_equal_p (arg2, TYPE_MAX_VALUE (type), 1)
4351                     && operand_equal_p (TREE_OPERAND (arg0, 1),
4352                                         const_binop (PLUS_EXPR, arg2,
4353                                                      integer_one_node, 0), 1))
4354                   return fold (build (MIN_EXPR, type, arg1, arg2));
4355                 break;
4356
4357               case LE_EXPR:
4358                 /* If C1 is C2 - 1, this is min(A, C2).  */
4359                 if (! operand_equal_p (arg2, TYPE_MIN_VALUE (type), 1)
4360                     && operand_equal_p (TREE_OPERAND (arg0, 1),
4361                                         const_binop (MINUS_EXPR, arg2,
4362                                                      integer_one_node, 0), 1))
4363                   return fold (build (MIN_EXPR, type, arg1, arg2));
4364                 break;
4365
4366               case GT_EXPR:
4367                 /* If C1 is C2 - 1, this is max(A, C2).  */
4368                 if (! operand_equal_p (arg2, TYPE_MIN_VALUE (type), 1)
4369                     && operand_equal_p (TREE_OPERAND (arg0, 1),
4370                                         const_binop (MINUS_EXPR, arg2,
4371                                                      integer_one_node, 0), 1))
4372                   return fold (build (MAX_EXPR, type, arg1, arg2));
4373                 break;
4374
4375               case GE_EXPR:
4376                 /* If C1 is C2 + 1, this is max(A, C2).  */
4377                 if (! operand_equal_p (arg2, TYPE_MAX_VALUE (type), 1)
4378                     && operand_equal_p (TREE_OPERAND (arg0, 1),
4379                                         const_binop (PLUS_EXPR, arg2,
4380                                                      integer_one_node, 0), 1))
4381                   return fold (build (MAX_EXPR, type, arg1, arg2));
4382                 break;
4383               }
4384         }
4385
4386       /* Convert A ? 1 : 0 to simply A.  */
4387       if (integer_onep (TREE_OPERAND (t, 1))
4388           && integer_zerop (TREE_OPERAND (t, 2))
4389           /* If we try to convert TREE_OPERAND (t, 0) to our type, the
4390              call to fold will try to move the conversion inside
4391              a COND, which will recurse.  In that case, the COND_EXPR
4392              is probably the best choice, so leave it alone.  */
4393           && type == TREE_TYPE (arg0))
4394         return arg0;
4395
4396
4397       /* Look for expressions of the form A & 2 ? 2 : 0.  The result of this
4398          operation is simply A & 2.  */
4399
4400       if (integer_zerop (TREE_OPERAND (t, 2))
4401           && TREE_CODE (arg0) == NE_EXPR
4402           && integer_zerop (TREE_OPERAND (arg0, 1))
4403           && integer_pow2p (arg1)
4404           && TREE_CODE (TREE_OPERAND (arg0, 0)) == BIT_AND_EXPR
4405           && operand_equal_p (TREE_OPERAND (TREE_OPERAND (arg0, 0), 1),
4406                               arg1, 1))
4407         return convert (type, TREE_OPERAND (arg0, 0));
4408
4409       return t;
4410
4411     case COMPOUND_EXPR:
4412       if (TREE_SIDE_EFFECTS (arg0))
4413         return t;
4414       /* Don't let (0, 0) be null pointer constant.  */
4415       if (integer_zerop (arg1))
4416         return non_lvalue (arg1);
4417       return arg1;
4418
4419     case COMPLEX_EXPR:
4420       if (wins)
4421         return build_complex (arg0, arg1);
4422       return t;
4423
4424     case REALPART_EXPR:
4425       if (TREE_CODE (TREE_TYPE (arg0)) != COMPLEX_TYPE)
4426         return t;
4427       else if (TREE_CODE (arg0) == COMPLEX_EXPR)
4428         return omit_one_operand (type, TREE_OPERAND (arg0, 0),
4429                                  TREE_OPERAND (arg0, 1));
4430       else if (TREE_CODE (arg0) == COMPLEX_CST)
4431         return TREE_REALPART (arg0);
4432       else if (TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MINUS_EXPR)
4433         return build_binary_op (TREE_CODE (arg0), type,
4434                                 build_unary_op (REALPART_EXPR,
4435                                                 TREE_OPERAND (arg0, 0),
4436                                                 1),
4437                                 build_unary_op (REALPART_EXPR,
4438                                                 TREE_OPERAND (arg0, 1),
4439                                                 1),
4440                                 0);
4441       return t;
4442
4443     case IMAGPART_EXPR:
4444       if (TREE_CODE (TREE_TYPE (arg0)) != COMPLEX_TYPE)
4445         return convert (type, integer_zero_node);
4446       else if (TREE_CODE (arg0) == COMPLEX_EXPR)
4447         return omit_one_operand (type, TREE_OPERAND (arg0, 1),
4448                                  TREE_OPERAND (arg0, 0));
4449       else if (TREE_CODE (arg0) == COMPLEX_CST)
4450         return TREE_IMAGPART (arg0);
4451       else if (TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MINUS_EXPR)
4452         return build_binary_op (TREE_CODE (arg0), type,
4453                                 build_unary_op (IMAGPART_EXPR,
4454                                                 TREE_OPERAND (arg0, 0),
4455                                                 1),
4456                                 build_unary_op (IMAGPART_EXPR,
4457                                                 TREE_OPERAND (arg0, 1),
4458                                                 1),
4459                                 0);
4460       return t;
4461
4462     default:
4463       return t;
4464     } /* switch (code) */
4465 }