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