gcc/fold-const.c

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