gcc/fold-const.c

   1 /* Fold a constant sub-tree into a single node for C-compiler
   2    Copyright (C) 1987, 88, 92-98, 1999 Free Software Foundation, Inc.
   3
   4 This file is part of GNU CC.
   5
   6 GNU CC is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 2, or (at your option)
   9 any later version.
  10
  11 GNU CC is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 GNU General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GNU CC; see the file COPYING.  If not, write to
  18 the Free Software Foundation, 59 Temple Place - Suite 330,
  19 Boston, MA 02111-1307, USA.  */
  20
  21 /*@@ This file should be rewritten to use an arbitrary precision
  22   @@ representation for "struct tree_int_cst" and "struct tree_real_cst".
  23   @@ Perhaps the routines could also be used for bc/dc, and made a lib.
  24   @@ The routines that translate from the ap rep should
  25   @@ warn if precision et. al. is lost.
  26   @@ This would also make life easier when this technology is used
  27   @@ for cross-compilers.  */
  28
  29
  30 /* The entry points in this file are fold, size_int_wide, size_binop
  31    and force_fit_type.
  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    force_fit_type takes a constant and prior overflow indicator, and
  43    forces the value to fit the type.  It returns an overflow indicator.  */
  44
  45 #include "config.h"
  46 #include "system.h"
  47 #include <setjmp.h>
  48 #include "flags.h"
  49 #include "tree.h"
  50 #include "rtl.h"
  51 #include "toplev.h"
  52 #include "ggc.h"
  53
  54 static void encode              PROTO((HOST_WIDE_INT *,
  55                                        HOST_WIDE_INT, HOST_WIDE_INT));
  56 static void decode              PROTO((HOST_WIDE_INT *,
  57                                        HOST_WIDE_INT *, HOST_WIDE_INT *));
  58 int div_and_round_double        PROTO((enum tree_code, int, HOST_WIDE_INT,
  59                                        HOST_WIDE_INT, HOST_WIDE_INT,
  60                                        HOST_WIDE_INT, HOST_WIDE_INT *,
  61                                        HOST_WIDE_INT *, HOST_WIDE_INT *,
  62                                        HOST_WIDE_INT *));
  63 static int split_tree           PROTO((tree, enum tree_code, tree *,
  64                                        tree *, int *));
  65 static tree int_const_binop     PROTO((enum tree_code, tree, tree, int, int));
  66 static tree const_binop         PROTO((enum tree_code, tree, tree, int));
  67 static tree fold_convert        PROTO((tree, tree));
  68 static enum tree_code invert_tree_comparison PROTO((enum tree_code));
  69 static enum tree_code swap_tree_comparison PROTO((enum tree_code));
  70 static int truth_value_p        PROTO((enum tree_code));
  71 static int operand_equal_for_comparison_p PROTO((tree, tree, tree));
  72 static int twoval_comparison_p  PROTO((tree, tree *, tree *, int *));
  73 static tree eval_subst          PROTO((tree, tree, tree, tree, tree));
  74 static tree omit_one_operand    PROTO((tree, tree, tree));
  75 static tree pedantic_omit_one_operand PROTO((tree, tree, tree));
  76 static tree distribute_bit_expr PROTO((enum tree_code, tree, tree, tree));
  77 static tree make_bit_field_ref  PROTO((tree, tree, int, int, int));
  78 static tree optimize_bit_field_compare PROTO((enum tree_code, tree,
  79                                               tree, tree));
  80 static tree decode_field_reference PROTO((tree, int *, int *,
  81                                           enum machine_mode *, int *,
  82                                           int *, tree *, tree *));
  83 static int all_ones_mask_p      PROTO((tree, int));
  84 static int simple_operand_p     PROTO((tree));
  85 static tree range_binop         PROTO((enum tree_code, tree, tree, int,
  86                                        tree, int));
  87 static tree make_range          PROTO((tree, int *, tree *, tree *));
  88 static tree build_range_check   PROTO((tree, tree, int, tree, tree));
  89 static int merge_ranges         PROTO((int *, tree *, tree *, int, tree, tree,
  90                                        int, tree, tree));
  91 static tree fold_range_test     PROTO((tree));
  92 static tree unextend            PROTO((tree, int, int, tree));
  93 static tree fold_truthop        PROTO((enum tree_code, tree, tree, tree));
  94 static tree strip_compound_expr PROTO((tree, tree));
  95 static int multiple_of_p        PROTO((tree, tree, tree));
  96 static tree constant_boolean_node PROTO((int, tree));
  97 static int count_cond           PROTO((tree, int));
  98 static void const_binop_1       PROTO((PTR));
  99 static void fold_convert_1      PROTO((PTR));
 100
 101 #ifndef BRANCH_COST
 102 #define BRANCH_COST 1
 103 #endif
 104
 105 /* Suppose A1 + B1 = SUM1, using 2's complement arithmetic ignoring overflow.
 106    Suppose A, B and SUM have the same respective signs as A1, B1, and SUM1.
 107    Then this yields nonzero if overflow occurred during the addition.
 108    Overflow occurs if A and B have the same sign, but A and SUM differ in sign.
 109    Use `^' to test whether signs differ, and `< 0' to isolate the sign.  */
 110 #define overflow_sum_sign(a, b, sum) ((~((a) ^ (b)) & ((a) ^ (sum))) < 0)
 111 \f
 112 /* To do constant folding on INTEGER_CST nodes requires two-word arithmetic.
 113    We do that by representing the two-word integer in 4 words, with only
 114    HOST_BITS_PER_WIDE_INT/2 bits stored in each word, as a positive number.  */
 115
 116 #define LOWPART(x) \
 117   ((x) & (((unsigned HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT/2)) - 1))
 118 #define HIGHPART(x) \
 119   ((unsigned HOST_WIDE_INT) (x) >> HOST_BITS_PER_WIDE_INT/2)
 120 #define BASE ((unsigned HOST_WIDE_INT) 1 << HOST_BITS_PER_WIDE_INT/2)
 121
 122 /* Unpack a two-word integer into 4 words.
 123    LOW and HI are the integer, as two `HOST_WIDE_INT' pieces.
 124    WORDS points to the array of HOST_WIDE_INTs.  */
 125
 126 static void
 127 encode (words, low, hi)
 128      HOST_WIDE_INT *words;
 129      HOST_WIDE_INT low, hi;
 130 {
 131   words[0] = LOWPART (low);
 132   words[1] = HIGHPART (low);
 133   words[2] = LOWPART (hi);
 134   words[3] = HIGHPART (hi);
 135 }
 136
 137 /* Pack an array of 4 words into a two-word integer.
 138    WORDS points to the array of words.
 139    The integer is stored into *LOW and *HI as two `HOST_WIDE_INT' pieces.  */
 140
 141 static void
 142 decode (words, low, hi)
 143      HOST_WIDE_INT *words;
 144      HOST_WIDE_INT *low, *hi;
 145 {
 146   *low = words[0] | words[1] * BASE;
 147   *hi = words[2] | words[3] * BASE;
 148 }
 149 \f
 150 /* Make the integer constant T valid for its type
 151    by setting to 0 or 1 all the bits in the constant
 152    that don't belong in the type.
 153    Yield 1 if a signed overflow occurs, 0 otherwise.
 154    If OVERFLOW is nonzero, a signed overflow has already occurred
 155    in calculating T, so propagate it.
 156
 157    Make the real constant T valid for its type by calling CHECK_FLOAT_VALUE,
 158    if it exists.  */
 159
 160 int
 161 force_fit_type (t, overflow)
 162      tree t;
 163      int overflow;
 164 {
 165   HOST_WIDE_INT low, high;
 166   register int prec;
 167
 168   if (TREE_CODE (t) == REAL_CST)
 169     {
 170 #ifdef CHECK_FLOAT_VALUE
 171       CHECK_FLOAT_VALUE (TYPE_MODE (TREE_TYPE (t)), TREE_REAL_CST (t),
 172                          overflow);
 173 #endif
 174       return overflow;
 175     }
 176
 177   else if (TREE_CODE (t) != INTEGER_CST)
 178     return overflow;
 179
 180   low = TREE_INT_CST_LOW (t);
 181   high = TREE_INT_CST_HIGH (t);
 182
 183   if (POINTER_TYPE_P (TREE_TYPE (t)))
 184     prec = POINTER_SIZE;
 185   else
 186     prec = TYPE_PRECISION (TREE_TYPE (t));
 187
 188   /* First clear all bits that are beyond the type's precision.  */
 189
 190   if (prec == 2 * HOST_BITS_PER_WIDE_INT)
 191     ;
 192   else 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) = 0;
 200       if (prec < HOST_BITS_PER_WIDE_INT)
 201         TREE_INT_CST_LOW (t) &= ~((HOST_WIDE_INT) (-1) << prec);
 202     }
 203
 204   /* Unsigned types do not suffer sign extension or overflow.  */
 205   if (TREE_UNSIGNED (TREE_TYPE (t)))
 206     return overflow;
 207
 208   /* If the value's sign bit is set, extend the sign.  */
 209   if (prec != 2 * HOST_BITS_PER_WIDE_INT
 210       && (prec > HOST_BITS_PER_WIDE_INT
 211           ? (TREE_INT_CST_HIGH (t)
 212              & ((HOST_WIDE_INT) 1 << (prec - HOST_BITS_PER_WIDE_INT - 1)))
 213           : TREE_INT_CST_LOW (t) & ((HOST_WIDE_INT) 1 << (prec - 1))))
 214     {
 215       /* Value is negative:
 216          set to 1 all the bits that are outside this type's precision.  */
 217       if (prec > HOST_BITS_PER_WIDE_INT)
 218         {
 219           TREE_INT_CST_HIGH (t)
 220             |= ((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
 221         }
 222       else
 223         {
 224           TREE_INT_CST_HIGH (t) = -1;
 225           if (prec < HOST_BITS_PER_WIDE_INT)
 226             TREE_INT_CST_LOW (t) |= ((HOST_WIDE_INT) (-1) << prec);
 227         }
 228     }
 229
 230   /* Yield nonzero if signed overflow occurred.  */
 231   return
 232     ((overflow | (low ^ TREE_INT_CST_LOW (t)) | (high ^ TREE_INT_CST_HIGH (t)))
 233      != 0);
 234 }
 235 \f
 236 /* Add two doubleword integers with doubleword result.
 237    Each argument is given as two `HOST_WIDE_INT' pieces.
 238    One argument is L1 and H1; the other, L2 and H2.
 239    The value is stored as two `HOST_WIDE_INT' pieces in *LV and *HV.  */
 240
 241 int
 242 add_double (l1, h1, l2, h2, lv, hv)
 243      HOST_WIDE_INT l1, h1, l2, h2;
 244      HOST_WIDE_INT *lv, *hv;
 245 {
 246   HOST_WIDE_INT l, h;
 247
 248   l = l1 + l2;
 249   h = h1 + h2 + ((unsigned HOST_WIDE_INT) l < l1);
 250
 251   *lv = l;
 252   *hv = h;
 253   return overflow_sum_sign (h1, h2, h);
 254 }
 255
 256 /* Negate a doubleword integer with doubleword result.
 257    Return nonzero if the operation overflows, assuming it's signed.
 258    The argument is given as two `HOST_WIDE_INT' pieces in L1 and H1.
 259    The value is stored as two `HOST_WIDE_INT' pieces in *LV and *HV.  */
 260
 261 int
 262 neg_double (l1, h1, lv, hv)
 263      HOST_WIDE_INT l1, h1;
 264      HOST_WIDE_INT *lv, *hv;
 265 {
 266   if (l1 == 0)
 267     {
 268       *lv = 0;
 269       *hv = - h1;
 270       return (*hv & h1) < 0;
 271     }
 272   else
 273     {
 274       *lv = - l1;
 275       *hv = ~ h1;
 276       return 0;
 277     }
 278 }
 279 \f
 280 /* Multiply two doubleword integers with doubleword result.
 281    Return nonzero if the operation overflows, assuming it's signed.
 282    Each argument is given as two `HOST_WIDE_INT' pieces.
 283    One argument is L1 and H1; the other, L2 and H2.
 284    The value is stored as two `HOST_WIDE_INT' pieces in *LV and *HV.  */
 285
 286 int
 287 mul_double (l1, h1, l2, h2, lv, hv)
 288      HOST_WIDE_INT l1, h1, l2, h2;
 289      HOST_WIDE_INT *lv, *hv;
 290 {
 291   HOST_WIDE_INT arg1[4];
 292   HOST_WIDE_INT arg2[4];
 293   HOST_WIDE_INT prod[4 * 2];
 294   register unsigned HOST_WIDE_INT carry;
 295   register int i, j, k;
 296   HOST_WIDE_INT toplow, tophigh, neglow, neghigh;
 297
 298   encode (arg1, l1, h1);
 299   encode (arg2, l2, h2);
 300
 301   bzero ((char *) prod, sizeof prod);
 302
 303   for (i = 0; i < 4; i++)
 304     {
 305       carry = 0;
 306       for (j = 0; j < 4; j++)
 307         {
 308           k = i + j;
 309           /* This product is <= 0xFFFE0001, the sum <= 0xFFFF0000.  */
 310           carry += arg1[i] * arg2[j];
 311           /* Since prod[p] < 0xFFFF, this sum <= 0xFFFFFFFF.  */
 312           carry += prod[k];
 313           prod[k] = LOWPART (carry);
 314           carry = HIGHPART (carry);
 315         }
 316       prod[i + 4] = carry;
 317     }
 318
 319   decode (prod, lv, hv);        /* This ignores prod[4] through prod[4*2-1] */
 320
 321   /* Check for overflow by calculating the top half of the answer in full;
 322      it should agree with the low half's sign bit.  */
 323   decode (prod+4, &toplow, &tophigh);
 324   if (h1 < 0)
 325     {
 326       neg_double (l2, h2, &neglow, &neghigh);
 327       add_double (neglow, neghigh, toplow, tophigh, &toplow, &tophigh);
 328     }
 329   if (h2 < 0)
 330     {
 331       neg_double (l1, h1, &neglow, &neghigh);
 332       add_double (neglow, neghigh, toplow, tophigh, &toplow, &tophigh);
 333     }
 334   return (*hv < 0 ? ~(toplow & tophigh) : toplow | tophigh) != 0;
 335 }
 336 \f
 337 /* Shift the doubleword integer in L1, H1 left by COUNT places
 338    keeping only PREC bits of result.
 339    Shift right if COUNT is negative.
 340    ARITH nonzero specifies arithmetic shifting; otherwise use logical shift.
 341    Store the value as two `HOST_WIDE_INT' pieces in *LV and *HV.  */
 342
 343 void
 344 lshift_double (l1, h1, count, prec, lv, hv, arith)
 345      HOST_WIDE_INT l1, h1, count;
 346      int prec;
 347      HOST_WIDE_INT *lv, *hv;
 348      int arith;
 349 {
 350   if (count < 0)
 351     {
 352       rshift_double (l1, h1, - count, prec, lv, hv, arith);
 353       return;
 354     }
 355
 356 #ifdef SHIFT_COUNT_TRUNCATED
 357   if (SHIFT_COUNT_TRUNCATED)
 358     count %= prec;
 359 #endif
 360
 361   if (count >= HOST_BITS_PER_WIDE_INT)
 362     {
 363       *hv = (unsigned HOST_WIDE_INT) l1 << (count - HOST_BITS_PER_WIDE_INT);
 364       *lv = 0;
 365     }
 366   else
 367     {
 368       *hv = (((unsigned HOST_WIDE_INT) h1 << count)
 369              | ((unsigned HOST_WIDE_INT) l1 >> (HOST_BITS_PER_WIDE_INT - count - 1) >> 1));
 370       *lv = (unsigned HOST_WIDE_INT) l1 << count;
 371     }
 372 }
 373
 374 /* Shift the doubleword integer in L1, H1 right by COUNT places
 375    keeping only PREC bits of result.  COUNT must be positive.
 376    ARITH nonzero specifies arithmetic shifting; otherwise use logical shift.
 377    Store the value as two `HOST_WIDE_INT' pieces in *LV and *HV.  */
 378
 379 void
 380 rshift_double (l1, h1, count, prec, lv, hv, arith)
 381      HOST_WIDE_INT l1, h1, count;
 382      int prec ATTRIBUTE_UNUSED;
 383      HOST_WIDE_INT *lv, *hv;
 384      int arith;
 385 {
 386   unsigned HOST_WIDE_INT signmask;
 387   signmask = (arith
 388               ? -((unsigned HOST_WIDE_INT) h1 >> (HOST_BITS_PER_WIDE_INT - 1))
 389               : 0);
 390
 391 #ifdef SHIFT_COUNT_TRUNCATED
 392   if (SHIFT_COUNT_TRUNCATED)
 393     count %= prec;
 394 #endif
 395
 396   if (count >= HOST_BITS_PER_WIDE_INT)
 397     {
 398       *hv = signmask;
 399       *lv = ((signmask << (2 * HOST_BITS_PER_WIDE_INT - count - 1) << 1)
 400              | ((unsigned HOST_WIDE_INT) h1 >> (count - HOST_BITS_PER_WIDE_INT)));
 401     }
 402   else
 403     {
 404       *lv = (((unsigned HOST_WIDE_INT) l1 >> count)
 405              | ((unsigned HOST_WIDE_INT) h1 << (HOST_BITS_PER_WIDE_INT - count - 1) << 1));
 406       *hv = ((signmask << (HOST_BITS_PER_WIDE_INT - count))
 407              | ((unsigned HOST_WIDE_INT) h1 >> count));
 408     }
 409 }
 410 \f
 411 /* Rotate the doubleword integer in L1, H1 left by COUNT places
 412    keeping only PREC bits of result.
 413    Rotate right if COUNT is negative.
 414    Store the value as two `HOST_WIDE_INT' pieces in *LV and *HV.  */
 415
 416 void
 417 lrotate_double (l1, h1, count, prec, lv, hv)
 418      HOST_WIDE_INT l1, h1, count;
 419      int prec;
 420      HOST_WIDE_INT *lv, *hv;
 421 {
 422   HOST_WIDE_INT s1l, s1h, s2l, s2h;
 423
 424   count %= prec;
 425   if (count < 0)
 426     count += prec;
 427
 428   lshift_double (l1, h1, count, prec, &s1l, &s1h, 0);
 429   rshift_double (l1, h1, prec - count, prec, &s2l, &s2h, 0);
 430   *lv = s1l | s2l;
 431   *hv = s1h | s2h;
 432 }
 433
 434 /* Rotate the doubleword integer in L1, H1 left by COUNT places
 435    keeping only PREC bits of result.  COUNT must be positive.
 436    Store the value as two `HOST_WIDE_INT' pieces in *LV and *HV.  */
 437
 438 void
 439 rrotate_double (l1, h1, count, prec, lv, hv)
 440      HOST_WIDE_INT l1, h1, count;
 441      int prec;
 442      HOST_WIDE_INT *lv, *hv;
 443 {
 444   HOST_WIDE_INT s1l, s1h, s2l, s2h;
 445
 446   count %= prec;
 447   if (count < 0)
 448     count += prec;
 449
 450   rshift_double (l1, h1, count, prec, &s1l, &s1h, 0);
 451   lshift_double (l1, h1, prec - count, prec, &s2l, &s2h, 0);
 452   *lv = s1l | s2l;
 453   *hv = s1h | s2h;
 454 }
 455 \f
 456 /* Divide doubleword integer LNUM, HNUM by doubleword integer LDEN, HDEN
 457    for a quotient (stored in *LQUO, *HQUO) and remainder (in *LREM, *HREM).
 458    CODE is a tree code for a kind of division, one of
 459    TRUNC_DIV_EXPR, FLOOR_DIV_EXPR, CEIL_DIV_EXPR, ROUND_DIV_EXPR
 460    or EXACT_DIV_EXPR
 461    It controls how the quotient is rounded to a integer.
 462    Return nonzero if the operation overflows.
 463    UNS nonzero says do unsigned division.  */
 464
 465 int
 466 div_and_round_double (code, uns,
 467                       lnum_orig, hnum_orig, lden_orig, hden_orig,
 468                       lquo, hquo, lrem, hrem)
 469      enum tree_code code;
 470      int uns;
 471      HOST_WIDE_INT lnum_orig, hnum_orig; /* num == numerator == dividend */
 472      HOST_WIDE_INT lden_orig, hden_orig; /* den == denominator == divisor */
 473      HOST_WIDE_INT *lquo, *hquo, *lrem, *hrem;
 474 {
 475   int quo_neg = 0;
 476   HOST_WIDE_INT num[4 + 1];     /* extra element for scaling.  */
 477   HOST_WIDE_INT den[4], quo[4];
 478   register int i, j;
 479   unsigned HOST_WIDE_INT work;
 480   register unsigned HOST_WIDE_INT carry = 0;
 481   HOST_WIDE_INT lnum = lnum_orig;
 482   HOST_WIDE_INT hnum = hnum_orig;
 483   HOST_WIDE_INT lden = lden_orig;
 484   HOST_WIDE_INT hden = hden_orig;
 485   int overflow = 0;
 486
 487   if ((hden == 0) && (lden == 0))
 488     overflow = 1, lden = 1;
 489
 490   /* calculate quotient sign and convert operands to unsigned.  */
 491   if (!uns)
 492     {
 493       if (hnum < 0)
 494         {
 495           quo_neg = ~ quo_neg;
 496           /* (minimum integer) / (-1) is the only overflow case.  */
 497           if (neg_double (lnum, hnum, &lnum, &hnum) && (lden & hden) == -1)
 498             overflow = 1;
 499         }
 500       if (hden < 0)
 501         {
 502           quo_neg = ~ quo_neg;
 503           neg_double (lden, hden, &lden, &hden);
 504         }
 505     }
 506
 507   if (hnum == 0 && hden == 0)
 508     {                           /* single precision */
 509       *hquo = *hrem = 0;
 510       /* This unsigned division rounds toward zero.  */
 511       *lquo = lnum / (unsigned HOST_WIDE_INT) lden;
 512       goto finish_up;
 513     }
 514
 515   if (hnum == 0)
 516     {                           /* trivial case: dividend < divisor */
 517       /* hden != 0 already checked.  */
 518       *hquo = *lquo = 0;
 519       *hrem = hnum;
 520       *lrem = lnum;
 521       goto finish_up;
 522     }
 523
 524   bzero ((char *) quo, sizeof quo);
 525
 526   bzero ((char *) num, sizeof num);     /* to zero 9th element */
 527   bzero ((char *) den, sizeof den);
 528
 529   encode (num, lnum, hnum);
 530   encode (den, lden, hden);
 531
 532   /* Special code for when the divisor < BASE.  */
 533   if (hden == 0 && lden < (HOST_WIDE_INT) BASE)
 534     {
 535       /* hnum != 0 already checked.  */
 536       for (i = 4 - 1; i >= 0; i--)
 537         {
 538           work = num[i] + carry * BASE;
 539           quo[i] = work / (unsigned HOST_WIDE_INT) lden;
 540           carry = work % (unsigned HOST_WIDE_INT) lden;
 541         }
 542     }
 543   else
 544     {
 545       /* Full double precision division,
 546          with thanks to Don Knuth's "Seminumerical Algorithms".  */
 547     int num_hi_sig, den_hi_sig;
 548     unsigned HOST_WIDE_INT quo_est, scale;
 549
 550     /* Find the highest non-zero divisor digit.  */
 551     for (i = 4 - 1; ; i--)
 552       if (den[i] != 0) {
 553         den_hi_sig = i;
 554         break;
 555       }
 556
 557     /* Insure that the first digit of the divisor is at least BASE/2.
 558        This is required by the quotient digit estimation algorithm.  */
 559
 560     scale = BASE / (den[den_hi_sig] + 1);
 561     if (scale > 1) {            /* scale divisor and dividend */
 562       carry = 0;
 563       for (i = 0; i <= 4 - 1; i++) {
 564         work = (num[i] * scale) + carry;
 565         num[i] = LOWPART (work);
 566         carry = HIGHPART (work);
 567       } num[4] = carry;
 568       carry = 0;
 569       for (i = 0; i <= 4 - 1; i++) {
 570         work = (den[i] * scale) + carry;
 571         den[i] = LOWPART (work);
 572         carry = HIGHPART (work);
 573         if (den[i] != 0) den_hi_sig = i;
 574       }
 575     }
 576
 577     num_hi_sig = 4;
 578
 579     /* Main loop */
 580     for (i = num_hi_sig - den_hi_sig - 1; i >= 0; i--) {
 581       /* guess the next quotient digit, quo_est, by dividing the first
 582          two remaining dividend digits by the high order quotient digit.
 583          quo_est is never low and is at most 2 high.  */
 584       unsigned HOST_WIDE_INT tmp;
 585
 586       num_hi_sig = i + den_hi_sig + 1;
 587       work = num[num_hi_sig] * BASE + num[num_hi_sig - 1];
 588       if (num[num_hi_sig] != den[den_hi_sig])
 589         quo_est = work / den[den_hi_sig];
 590       else
 591         quo_est = BASE - 1;
 592
 593       /* refine quo_est so it's usually correct, and at most one high.   */
 594       tmp = work - quo_est * den[den_hi_sig];
 595       if (tmp < BASE
 596           && den[den_hi_sig - 1] * quo_est > (tmp * BASE + num[num_hi_sig - 2]))
 597         quo_est--;
 598
 599       /* Try QUO_EST as the quotient digit, by multiplying the
 600          divisor by QUO_EST and subtracting from the remaining dividend.
 601          Keep in mind that QUO_EST is the I - 1st digit.  */
 602
 603       carry = 0;
 604       for (j = 0; j <= den_hi_sig; j++)
 605         {
 606           work = quo_est * den[j] + carry;
 607           carry = HIGHPART (work);
 608           work = num[i + j] - LOWPART (work);
 609           num[i + j] = LOWPART (work);
 610           carry += HIGHPART (work) != 0;
 611         }
 612
 613       /* if quo_est was high by one, then num[i] went negative and
 614          we need to correct things.  */
 615
 616       if (num[num_hi_sig] < carry)
 617         {
 618           quo_est--;
 619           carry = 0;            /* add divisor back in */
 620           for (j = 0; j <= den_hi_sig; j++)
 621             {
 622               work = num[i + j] + den[j] + carry;
 623               carry = HIGHPART (work);
 624               num[i + j] = LOWPART (work);
 625             }
 626           num [num_hi_sig] += carry;
 627         }
 628
 629       /* store the quotient digit.  */
 630       quo[i] = quo_est;
 631     }
 632   }
 633
 634   decode (quo, lquo, hquo);
 635
 636  finish_up:
 637   /* if result is negative, make it so.  */
 638   if (quo_neg)
 639     neg_double (*lquo, *hquo, lquo, hquo);
 640
 641   /* compute trial remainder:  rem = num - (quo * den)  */
 642   mul_double (*lquo, *hquo, lden_orig, hden_orig, lrem, hrem);
 643   neg_double (*lrem, *hrem, lrem, hrem);
 644   add_double (lnum_orig, hnum_orig, *lrem, *hrem, lrem, hrem);
 645
 646   switch (code)
 647     {
 648     case TRUNC_DIV_EXPR:
 649     case TRUNC_MOD_EXPR:        /* round toward zero */
 650     case EXACT_DIV_EXPR:        /* for this one, it shouldn't matter */
 651       return overflow;
 652
 653     case FLOOR_DIV_EXPR:
 654     case FLOOR_MOD_EXPR:        /* round toward negative infinity */
 655       if (quo_neg && (*lrem != 0 || *hrem != 0))   /* ratio < 0 && rem != 0 */
 656         {
 657           /* quo = quo - 1;  */
 658           add_double (*lquo, *hquo, (HOST_WIDE_INT) -1, (HOST_WIDE_INT)  -1,
 659                       lquo, hquo);
 660         }
 661       else return overflow;
 662       break;
 663
 664     case CEIL_DIV_EXPR:
 665     case CEIL_MOD_EXPR:         /* round toward positive infinity */
 666       if (!quo_neg && (*lrem != 0 || *hrem != 0))  /* ratio > 0 && rem != 0 */
 667         {
 668           add_double (*lquo, *hquo, (HOST_WIDE_INT) 1, (HOST_WIDE_INT) 0,
 669                       lquo, hquo);
 670         }
 671       else return overflow;
 672       break;
 673
 674     case ROUND_DIV_EXPR:
 675     case ROUND_MOD_EXPR:        /* round to closest integer */
 676       {
 677         HOST_WIDE_INT labs_rem = *lrem, habs_rem = *hrem;
 678         HOST_WIDE_INT labs_den = lden, habs_den = hden, ltwice, htwice;
 679
 680         /* get absolute values */
 681         if (*hrem < 0) neg_double (*lrem, *hrem, &labs_rem, &habs_rem);
 682         if (hden < 0) neg_double (lden, hden, &labs_den, &habs_den);
 683
 684         /* if (2 * abs (lrem) >= abs (lden)) */
 685         mul_double ((HOST_WIDE_INT) 2, (HOST_WIDE_INT) 0,
 686                     labs_rem, habs_rem, &ltwice, &htwice);
 687         if (((unsigned HOST_WIDE_INT) habs_den
 688              < (unsigned HOST_WIDE_INT) htwice)
 689             || (((unsigned HOST_WIDE_INT) habs_den
 690                  == (unsigned HOST_WIDE_INT) htwice)
 691                 && ((HOST_WIDE_INT unsigned) labs_den
 692                     < (unsigned HOST_WIDE_INT) ltwice)))
 693           {
 694             if (*hquo < 0)
 695               /* quo = quo - 1;  */
 696               add_double (*lquo, *hquo,
 697                           (HOST_WIDE_INT) -1, (HOST_WIDE_INT) -1, lquo, hquo);
 698             else
 699               /* quo = quo + 1; */
 700               add_double (*lquo, *hquo, (HOST_WIDE_INT) 1, (HOST_WIDE_INT) 0,
 701                           lquo, hquo);
 702           }
 703         else return overflow;
 704       }
 705       break;
 706
 707     default:
 708       abort ();
 709     }
 710
 711   /* compute true remainder:  rem = num - (quo * den)  */
 712   mul_double (*lquo, *hquo, lden_orig, hden_orig, lrem, hrem);
 713   neg_double (*lrem, *hrem, lrem, hrem);
 714   add_double (lnum_orig, hnum_orig, *lrem, *hrem, lrem, hrem);
 715   return overflow;
 716 }
 717 \f
 718 #ifndef REAL_ARITHMETIC
 719 /* Effectively truncate a real value to represent the nearest possible value
 720    in a narrower mode.  The result is actually represented in the same data
 721    type as the argument, but its value is usually different.
 722
 723    A trap may occur during the FP operations and it is the responsibility
 724    of the calling function to have a handler established.  */
 725
 726 REAL_VALUE_TYPE
 727 real_value_truncate (mode, arg)
 728      enum machine_mode mode;
 729      REAL_VALUE_TYPE arg;
 730 {
 731   return REAL_VALUE_TRUNCATE (mode, arg);
 732 }
 733
 734 #if TARGET_FLOAT_FORMAT == IEEE_FLOAT_FORMAT
 735
 736 /* Check for infinity in an IEEE double precision number.  */
 737
 738 int
 739 target_isinf (x)
 740      REAL_VALUE_TYPE x;
 741 {
 742   /* The IEEE 64-bit double format.  */
 743   union {
 744     REAL_VALUE_TYPE d;
 745     struct {
 746       unsigned sign      :  1;
 747       unsigned exponent  : 11;
 748       unsigned mantissa1 : 20;
 749       unsigned mantissa2;
 750     } little_endian;
 751     struct {
 752       unsigned mantissa2;
 753       unsigned mantissa1 : 20;
 754       unsigned exponent  : 11;
 755       unsigned sign      :  1;
 756     } big_endian;
 757   } u;
 758
 759   u.d = dconstm1;
 760   if (u.big_endian.sign == 1)
 761     {
 762       u.d = x;
 763       return (u.big_endian.exponent == 2047
 764               && u.big_endian.mantissa1 == 0
 765               && u.big_endian.mantissa2 == 0);
 766     }
 767   else
 768     {
 769       u.d = x;
 770       return (u.little_endian.exponent == 2047
 771               && u.little_endian.mantissa1 == 0
 772               && u.little_endian.mantissa2 == 0);
 773     }
 774 }
 775
 776 /* Check whether an IEEE double precision number is a NaN.  */
 777
 778 int
 779 target_isnan (x)
 780      REAL_VALUE_TYPE x;
 781 {
 782   /* The IEEE 64-bit double format.  */
 783   union {
 784     REAL_VALUE_TYPE d;
 785     struct {
 786       unsigned sign      :  1;
 787       unsigned exponent  : 11;
 788       unsigned mantissa1 : 20;
 789       unsigned mantissa2;
 790     } little_endian;
 791     struct {
 792       unsigned mantissa2;
 793       unsigned mantissa1 : 20;
 794       unsigned exponent  : 11;
 795       unsigned sign      :  1;
 796     } big_endian;
 797   } u;
 798
 799   u.d = dconstm1;
 800   if (u.big_endian.sign == 1)
 801     {
 802       u.d = x;
 803       return (u.big_endian.exponent == 2047
 804               && (u.big_endian.mantissa1 != 0
 805                   || u.big_endian.mantissa2 != 0));
 806     }
 807   else
 808     {
 809       u.d = x;
 810       return (u.little_endian.exponent == 2047
 811               && (u.little_endian.mantissa1 != 0
 812                   || u.little_endian.mantissa2 != 0));
 813     }
 814 }
 815
 816 /* Check for a negative IEEE double precision number.  */
 817
 818 int
 819 target_negative (x)
 820      REAL_VALUE_TYPE x;
 821 {
 822   /* The IEEE 64-bit double format.  */
 823   union {
 824     REAL_VALUE_TYPE d;
 825     struct {
 826       unsigned sign      :  1;
 827       unsigned exponent  : 11;
 828       unsigned mantissa1 : 20;
 829       unsigned mantissa2;
 830     } little_endian;
 831     struct {
 832       unsigned mantissa2;
 833       unsigned mantissa1 : 20;
 834       unsigned exponent  : 11;
 835       unsigned sign      :  1;
 836     } big_endian;
 837   } u;
 838
 839   u.d = dconstm1;
 840   if (u.big_endian.sign == 1)
 841     {
 842       u.d = x;
 843       return u.big_endian.sign;
 844     }
 845   else
 846     {
 847       u.d = x;
 848       return u.little_endian.sign;
 849     }
 850 }
 851 #else /* Target not IEEE */
 852
 853 /* Let's assume other float formats don't have infinity.
 854    (This can be overridden by redefining REAL_VALUE_ISINF.)  */
 855
 856 target_isinf (x)
 857      REAL_VALUE_TYPE x;
 858 {
 859   return 0;
 860 }
 861
 862 /* Let's assume other float formats don't have NaNs.
 863    (This can be overridden by redefining REAL_VALUE_ISNAN.)  */
 864
 865 target_isnan (x)
 866      REAL_VALUE_TYPE x;
 867 {
 868   return 0;
 869 }
 870
 871 /* Let's assume other float formats don't have minus zero.
 872    (This can be overridden by redefining REAL_VALUE_NEGATIVE.)  */
 873
 874 target_negative (x)
 875      REAL_VALUE_TYPE x;
 876 {
 877   return x < 0;
 878 }
 879 #endif /* Target not IEEE */
 880
 881 /* Try to change R into its exact multiplicative inverse in machine mode
 882    MODE.  Return nonzero function value if successful.  */
 883
 884 int
 885 exact_real_inverse (mode, r)
 886      enum machine_mode mode;
 887      REAL_VALUE_TYPE *r;
 888 {
 889   jmp_buf float_error;
 890   union
 891     {
 892       double d;
 893       unsigned short i[4];
 894     }x, t, y;
 895   int i;
 896
 897   /* Usually disable if bounds checks are not reliable.  */
 898   if ((HOST_FLOAT_FORMAT != TARGET_FLOAT_FORMAT) && !flag_pretend_float)
 899     return 0;
 900
 901   /* Set array index to the less significant bits in the unions, depending
 902      on the endian-ness of the host doubles.
 903      Disable if insufficient information on the data structure.  */
 904 #if HOST_FLOAT_FORMAT == UNKNOWN_FLOAT_FORMAT
 905   return 0;
 906 #else
 907 #if HOST_FLOAT_FORMAT == VAX_FLOAT_FORMAT
 908 #define K 2
 909 #else
 910 #if HOST_FLOAT_FORMAT == IBM_FLOAT_FORMAT
 911 #define K 2
 912 #else
 913 #define K (2 * HOST_FLOAT_WORDS_BIG_ENDIAN)
 914 #endif
 915 #endif
 916 #endif
 917
 918   if (setjmp (float_error))
 919     {
 920       /* Don't do the optimization if there was an arithmetic error.  */
 921 fail:
 922       set_float_handler (NULL_PTR);
 923       return 0;
 924     }
 925   set_float_handler (float_error);
 926
 927   /* Domain check the argument.  */
 928   x.d = *r;
 929   if (x.d == 0.0)
 930     goto fail;
 931
 932 #ifdef REAL_INFINITY
 933   if (REAL_VALUE_ISINF (x.d) || REAL_VALUE_ISNAN (x.d))
 934     goto fail;
 935 #endif
 936
 937   /* Compute the reciprocal and check for numerical exactness.
 938      It is unnecessary to check all the significand bits to determine
 939      whether X is a power of 2.  If X is not, then it is impossible for
 940      the bottom half significand of both X and 1/X to be all zero bits.
 941      Hence we ignore the data structure of the top half and examine only
 942      the low order bits of the two significands.  */
 943   t.d = 1.0 / x.d;
 944   if (x.i[K] != 0 || x.i[K + 1] != 0 || t.i[K] != 0 || t.i[K + 1] != 0)
 945     goto fail;
 946
 947   /* Truncate to the required mode and range-check the result.  */
 948   y.d = REAL_VALUE_TRUNCATE (mode, t.d);
 949 #ifdef CHECK_FLOAT_VALUE
 950   i = 0;
 951   if (CHECK_FLOAT_VALUE (mode, y.d, i))
 952     goto fail;
 953 #endif
 954
 955   /* Fail if truncation changed the value.  */
 956   if (y.d != t.d || y.d == 0.0)
 957     goto fail;
 958
 959 #ifdef REAL_INFINITY
 960   if (REAL_VALUE_ISINF (y.d) || REAL_VALUE_ISNAN (y.d))
 961     goto fail;
 962 #endif
 963
 964   /* Output the reciprocal and return success flag.  */
 965   set_float_handler (NULL_PTR);
 966   *r = y.d;
 967   return 1;
 968 }
 969
 970
 971 /* Convert C9X hexadecimal floating point string constant S.  Return
 972    real value type in mode MODE.  This function uses the host computer's
 973    fp arithmetic when there is no REAL_ARITHMETIC.  */
 974
 975 REAL_VALUE_TYPE
 976 real_hex_to_f (s, mode)
 977    char *s;
 978    enum machine_mode mode;
 979 {
 980    REAL_VALUE_TYPE ip;
 981    char *p = s;
 982    unsigned HOST_WIDE_INT low, high;
 983    int frexpon, expon, shcount, nrmcount, k;
 984    int sign, expsign, decpt, isfloat, isldouble, gotp, lost;
 985    char c;
 986
 987    isldouble = 0;
 988    isfloat = 0;
 989    frexpon = 0;
 990    expon = 0;
 991    expsign = 1;
 992    ip = 0.0;
 993
 994    while (*p == ' ' || *p == '\t')
 995      ++p;
 996
 997    /* Sign, if any, comes first.  */
 998    sign = 1;
 999    if (*p == '-')
1000      {
1001        sign = -1;
1002        ++p;
1003      }
1004
1005    /* The string is supposed to start with 0x or 0X .  */
1006    if (*p == '0')
1007      {
1008        ++p;
1009        if (*p == 'x' || *p == 'X')
1010          ++p;
1011        else
1012          abort ();
1013      }
1014    else
1015      abort ();
1016
1017    while (*p == '0')
1018      ++p;
1019
1020    high = 0;
1021    low = 0;
1022    lost = 0; /* Nonzero low order bits shifted out and discarded.  */
1023    frexpon = 0;  /* Bits after the decimal point.  */
1024    expon = 0;  /* Value of exponent.  */
1025    decpt = 0;  /* How many decimal points.  */
1026    gotp = 0;  /* How many P's.  */
1027    shcount = 0;
1028    while ((c = *p) != '\0')
1029      {
1030        if ((c >= '0' && c <= '9') || (c >= 'A' && c <= 'F')
1031            || (c >= 'a' && c <= 'f'))
1032          {
1033            k = c & 0x7f;
1034            if (k >= 'a')
1035              k = k - 'a' + 10;
1036            else if (k >= 'A')
1037              k = k - 'A' + 10;
1038            else
1039              k = k - '0';
1040
1041            if ((high & 0xf0000000) == 0)
1042              {
1043                high = (high << 4) + ((low >> 28) & 15);
1044                low = (low << 4) + k;
1045                shcount += 4;
1046                if (decpt)
1047                  frexpon += 4;
1048              }
1049            else
1050              {
1051                /* Record nonzero lost bits.  */
1052                lost |= k;
1053                if (!decpt)
1054                  frexpon -= 4;
1055              }
1056            ++p;
1057          }
1058        else if ( c == '.')
1059          {
1060            ++decpt;
1061            ++p;
1062          }
1063        else if (c == 'p' || c == 'P')
1064          {
1065            ++gotp;
1066            ++p;
1067            /* Sign of exponent.  */
1068            if (*p == '-')
1069              {
1070                expsign = -1;
1071                ++p;
1072              }
1073            /* Value of exponent.
1074               The exponent field is a decimal integer.  */
1075            while (ISDIGIT(*p))
1076              {
1077                k = (*p++ & 0x7f) - '0';
1078                expon = 10 * expon + k;
1079              }
1080            expon *= expsign;
1081            /* F suffix is ambiguous in the significand part
1082               so it must appear after the decimal exponent field.  */
1083            if (*p == 'f' || *p == 'F')
1084              {
1085                isfloat = 1;
1086                ++p;
1087                break;
1088              }
1089          }
1090        else if (c == 'l' || c == 'L')
1091          {
1092            isldouble = 1;
1093            ++p;
1094            break;
1095          }
1096        else
1097          break;
1098      }
1099    /* Abort if last character read was not legitimate.  */
1100    c = *p;
1101    if ((c != '\0' && c != ' ' && c != '\n' && c != '\r') || (decpt > 1))
1102      abort ();
1103    /* There must be either one decimal point or one p.  */
1104    if (decpt == 0 && gotp == 0)
1105      abort ();
1106    shcount -= 4;
1107    if ((high == 0) && (low == 0))
1108      {
1109        return dconst0;
1110      }
1111
1112    /* Normalize.  */
1113    nrmcount = 0;
1114    if (high == 0)
1115      {
1116        high = low;
1117        low = 0;
1118        nrmcount += 32;
1119      }
1120    /* Leave a high guard bit for carry-out.  */
1121    if ((high & 0x80000000) != 0)
1122      {
1123        lost |= low & 1;
1124        low = (low >> 1) | (high << 31);
1125        high = high >> 1;
1126        nrmcount -= 1;
1127      }
1128    if ((high & 0xffff8000) == 0)
1129      {
1130        high = (high << 16) + ((low >> 16) & 0xffff);
1131        low = low << 16;
1132        nrmcount += 16;
1133      }
1134    while ((high & 0xc0000000) == 0)
1135      {
1136        high = (high << 1) + ((low >> 31) & 1);
1137        low = low << 1;
1138        nrmcount += 1;
1139      }
1140    if (isfloat || GET_MODE_SIZE(mode) == UNITS_PER_WORD)
1141      {
1142        /* Keep 24 bits precision, bits 0x7fffff80.
1143           Rounding bit is 0x40.  */
1144        lost = lost | low | (high & 0x3f);
1145        low = 0;
1146        if (high & 0x40)
1147          {
1148            if ((high & 0x80) || lost)
1149              high += 0x40;
1150          }
1151        high &= 0xffffff80;
1152      }
1153    else
1154      {
1155        /* We need real.c to do long double formats, so here default
1156           to double precision.  */
1157 #if HOST_FLOAT_FORMAT == IEEE_FLOAT_FORMAT
1158        /* IEEE double.
1159           Keep 53 bits precision, bits 0x7fffffff fffffc00.
1160           Rounding bit is low word 0x200.  */
1161        lost = lost | (low & 0x1ff);
1162        if (low & 0x200)
1163          {
1164            if ((low & 0x400) || lost)
1165              {
1166                low = (low + 0x200) & 0xfffffc00;
1167                if (low == 0)
1168                  high += 1;
1169              }
1170          }
1171        low &= 0xfffffc00;
1172 #else
1173        /* Assume it's a VAX with 56-bit significand,
1174           bits 0x7fffffff ffffff80.  */
1175        lost = lost | (low & 0x7f);
1176        if (low & 0x40)
1177          {
1178            if ((low & 0x80) || lost)
1179              {
1180                low = (low + 0x40) & 0xffffff80;
1181                if (low == 0)
1182                  high += 1;
1183              }
1184          }
1185        low &= 0xffffff80;
1186 #endif
1187      }
1188    ip = (double) high;
1189    ip =  REAL_VALUE_LDEXP (ip, 32) + (double) low;
1190    /* Apply shifts and exponent value as power of 2.  */
1191    ip = REAL_VALUE_LDEXP (ip, expon - (nrmcount + frexpon));
1192
1193    if (sign < 0)
1194      ip = -ip;
1195    return ip;
1196 }
1197
1198 #endif /* no REAL_ARITHMETIC */
1199 \f
1200 /* Split a tree IN into a constant and a variable part
1201    that could be combined with CODE to make IN.
1202    CODE must be a commutative arithmetic operation.
1203    Store the constant part into *CONP and the variable in &VARP.
1204    Return 1 if this was done; zero means the tree IN did not decompose
1205    this way.
1206
1207    If CODE is PLUS_EXPR we also split trees that use MINUS_EXPR.
1208    Therefore, we must tell the caller whether the variable part
1209    was subtracted.  We do this by storing 1 or -1 into *VARSIGNP.
1210    The value stored is the coefficient for the variable term.
1211    The constant term we return should always be added;
1212    we negate it if necessary.  */
1213
1214 static int
1215 split_tree (in, code, varp, conp, varsignp)
1216      tree in;
1217      enum tree_code code;
1218      tree *varp, *conp;
1219      int *varsignp;
1220 {
1221   register tree outtype = TREE_TYPE (in);
1222   *varp = 0;
1223   *conp = 0;
1224
1225   /* Strip any conversions that don't change the machine mode.  */
1226   while ((TREE_CODE (in) == NOP_EXPR
1227           || TREE_CODE (in) == CONVERT_EXPR)
1228          && (TYPE_MODE (TREE_TYPE (in))
1229              == TYPE_MODE (TREE_TYPE (TREE_OPERAND (in, 0)))))
1230     in = TREE_OPERAND (in, 0);
1231
1232   if (TREE_CODE (in) == code
1233       || (! FLOAT_TYPE_P (TREE_TYPE (in))
1234           /* We can associate addition and subtraction together
1235              (even though the C standard doesn't say so)
1236              for integers because the value is not affected.
1237              For reals, the value might be affected, so we can't.  */
1238           && ((code == PLUS_EXPR && TREE_CODE (in) == MINUS_EXPR)
1239               || (code == MINUS_EXPR && TREE_CODE (in) == PLUS_EXPR))))
1240     {
1241       enum tree_code code = TREE_CODE (TREE_OPERAND (in, 0));
1242       if (code == INTEGER_CST)
1243         {
1244           *conp = TREE_OPERAND (in, 0);
1245           *varp = TREE_OPERAND (in, 1);
1246           if (TYPE_MODE (TREE_TYPE (*varp)) != TYPE_MODE (outtype)
1247               && TREE_TYPE (*varp) != outtype)
1248             *varp = convert (outtype, *varp);
1249           *varsignp = (TREE_CODE (in) == MINUS_EXPR) ? -1 : 1;
1250           return 1;
1251         }
1252       if (TREE_CONSTANT (TREE_OPERAND (in, 1)))
1253         {
1254           *conp = TREE_OPERAND (in, 1);
1255           *varp = TREE_OPERAND (in, 0);
1256           *varsignp = 1;
1257           if (TYPE_MODE (TREE_TYPE (*varp)) != TYPE_MODE (outtype)
1258               && TREE_TYPE (*varp) != outtype)
1259             *varp = convert (outtype, *varp);
1260           if (TREE_CODE (in) == MINUS_EXPR)
1261             {
1262               /* If operation is subtraction and constant is second,
1263                  must negate it to get an additive constant.
1264                  And this cannot be done unless it is a manifest constant.
1265                  It could also be the address of a static variable.
1266                  We cannot negate that, so give up.  */
1267               if (TREE_CODE (*conp) == INTEGER_CST)
1268                 /* Subtracting from integer_zero_node loses for long long.  */
1269                 *conp = fold (build1 (NEGATE_EXPR, TREE_TYPE (*conp), *conp));
1270               else
1271                 return 0;
1272             }
1273           return 1;
1274         }
1275       if (TREE_CONSTANT (TREE_OPERAND (in, 0)))
1276         {
1277           *conp = TREE_OPERAND (in, 0);
1278           *varp = TREE_OPERAND (in, 1);
1279           if (TYPE_MODE (TREE_TYPE (*varp)) != TYPE_MODE (outtype)
1280               && TREE_TYPE (*varp) != outtype)
1281             *varp = convert (outtype, *varp);
1282           *varsignp = (TREE_CODE (in) == MINUS_EXPR) ? -1 : 1;
1283           return 1;
1284         }
1285     }
1286   return 0;
1287 }
1288 \f
1289 /* Combine two integer constants ARG1 and ARG2 under operation CODE
1290    to produce a new constant.
1291
1292    If NOTRUNC is nonzero, do not truncate the result to fit the data type.
1293    If FORSIZE is nonzero, compute overflow for unsigned types.  */
1294
1295 static tree
1296 int_const_binop (code, arg1, arg2, notrunc, forsize)
1297      enum tree_code code;
1298      register tree arg1, arg2;
1299      int notrunc, forsize;
1300 {
1301   HOST_WIDE_INT int1l, int1h, int2l, int2h;
1302   HOST_WIDE_INT low, hi;
1303   HOST_WIDE_INT garbagel, garbageh;
1304   register tree t;
1305   int uns = TREE_UNSIGNED (TREE_TYPE (arg1));
1306   int overflow = 0;
1307   int no_overflow = 0;
1308
1309   int1l = TREE_INT_CST_LOW (arg1);
1310   int1h = TREE_INT_CST_HIGH (arg1);
1311   int2l = TREE_INT_CST_LOW (arg2);
1312   int2h = TREE_INT_CST_HIGH (arg2);
1313
1314   switch (code)
1315     {
1316     case BIT_IOR_EXPR:
1317       low = int1l | int2l, hi = int1h | int2h;
1318       break;
1319
1320     case BIT_XOR_EXPR:
1321       low = int1l ^ int2l, hi = int1h ^ int2h;
1322       break;
1323
1324     case BIT_AND_EXPR:
1325       low = int1l & int2l, hi = int1h & int2h;
1326       break;
1327
1328     case BIT_ANDTC_EXPR:
1329       low = int1l & ~int2l, hi = int1h & ~int2h;
1330       break;
1331
1332     case RSHIFT_EXPR:
1333       int2l = - int2l;
1334     case LSHIFT_EXPR:
1335       /* It's unclear from the C standard whether shifts can overflow.
1336          The following code ignores overflow; perhaps a C standard
1337          interpretation ruling is needed.  */
1338       lshift_double (int1l, int1h, int2l,
1339                      TYPE_PRECISION (TREE_TYPE (arg1)),
1340                      &low, &hi,
1341                      !uns);
1342       no_overflow = 1;
1343       break;
1344
1345     case RROTATE_EXPR:
1346       int2l = - int2l;
1347     case LROTATE_EXPR:
1348       lrotate_double (int1l, int1h, int2l,
1349                       TYPE_PRECISION (TREE_TYPE (arg1)),
1350                       &low, &hi);
1351       break;
1352
1353     case PLUS_EXPR:
1354       overflow = add_double (int1l, int1h, int2l, int2h, &low, &hi);
1355       break;
1356
1357     case MINUS_EXPR:
1358       neg_double (int2l, int2h, &low, &hi);
1359       add_double (int1l, int1h, low, hi, &low, &hi);
1360       overflow = overflow_sum_sign (hi, int2h, int1h);
1361       break;
1362
1363     case MULT_EXPR:
1364       overflow = mul_double (int1l, int1h, int2l, int2h, &low, &hi);
1365       break;
1366
1367     case TRUNC_DIV_EXPR:
1368     case FLOOR_DIV_EXPR: case CEIL_DIV_EXPR:
1369     case EXACT_DIV_EXPR:
1370       /* This is a shortcut for a common special case.  */
1371       if (int2h == 0 && int2l > 0
1372           && ! TREE_CONSTANT_OVERFLOW (arg1)
1373           && ! TREE_CONSTANT_OVERFLOW (arg2)
1374           && int1h == 0 && int1l >= 0)
1375         {
1376           if (code == CEIL_DIV_EXPR)
1377             int1l += int2l - 1;
1378           low = int1l / int2l, hi = 0;
1379           break;
1380         }
1381
1382       /* ... fall through ... */
1383
1384     case ROUND_DIV_EXPR:
1385       if (int2h == 0 && int2l == 1)
1386         {
1387           low = int1l, hi = int1h;
1388           break;
1389         }
1390       if (int1l == int2l && int1h == int2h
1391           && ! (int1l == 0 && int1h == 0))
1392         {
1393           low = 1, hi = 0;
1394           break;
1395         }
1396       overflow = div_and_round_double (code, uns,
1397                                        int1l, int1h, int2l, int2h,
1398                                        &low, &hi, &garbagel, &garbageh);
1399       break;
1400
1401     case TRUNC_MOD_EXPR:
1402     case FLOOR_MOD_EXPR: case CEIL_MOD_EXPR:
1403       /* This is a shortcut for a common special case.  */
1404       if (int2h == 0 && int2l > 0
1405           && ! TREE_CONSTANT_OVERFLOW (arg1)
1406           && ! TREE_CONSTANT_OVERFLOW (arg2)
1407           && int1h == 0 && int1l >= 0)
1408         {
1409           if (code == CEIL_MOD_EXPR)
1410             int1l += int2l - 1;
1411           low = int1l % int2l, hi = 0;
1412           break;
1413         }
1414
1415       /* ... fall through ... */
1416
1417     case ROUND_MOD_EXPR:
1418       overflow = div_and_round_double (code, uns,
1419                                        int1l, int1h, int2l, int2h,
1420                                        &garbagel, &garbageh, &low, &hi);
1421       break;
1422
1423     case MIN_EXPR:
1424     case MAX_EXPR:
1425       if (uns)
1426         {
1427           low = (((unsigned HOST_WIDE_INT) int1h
1428                   < (unsigned HOST_WIDE_INT) int2h)
1429                  || (((unsigned HOST_WIDE_INT) int1h
1430                       == (unsigned HOST_WIDE_INT) int2h)
1431                      && ((unsigned HOST_WIDE_INT) int1l
1432                          < (unsigned HOST_WIDE_INT) int2l)));
1433         }
1434       else
1435         {
1436           low = ((int1h < int2h)
1437                  || ((int1h == int2h)
1438                      && ((unsigned HOST_WIDE_INT) int1l
1439                          < (unsigned HOST_WIDE_INT) int2l)));
1440         }
1441       if (low == (code == MIN_EXPR))
1442         low = int1l, hi = int1h;
1443       else
1444         low = int2l, hi = int2h;
1445       break;
1446
1447     default:
1448       abort ();
1449     }
1450
1451   if (TREE_TYPE (arg1) == sizetype && hi == 0
1452       && low >= 0
1453       && (TYPE_MAX_VALUE (sizetype) == NULL
1454           || low <= TREE_INT_CST_LOW (TYPE_MAX_VALUE (sizetype)))
1455       && ! overflow
1456       && ! TREE_OVERFLOW (arg1) && ! TREE_OVERFLOW (arg2))
1457     t = size_int (low);
1458   else
1459     {
1460       t = build_int_2 (low, hi);
1461       TREE_TYPE (t) = TREE_TYPE (arg1);
1462     }
1463
1464   TREE_OVERFLOW (t)
1465     = ((notrunc ? (!uns || forsize) && overflow
1466         : force_fit_type (t, (!uns || forsize) && overflow) && ! no_overflow)
1467        | TREE_OVERFLOW (arg1)
1468        | TREE_OVERFLOW (arg2));
1469   /* If we're doing a size calculation, unsigned arithmetic does overflow.
1470      So check if force_fit_type truncated the value.  */
1471   if (forsize
1472       && ! TREE_OVERFLOW (t)
1473       && (TREE_INT_CST_HIGH (t) != hi
1474           || TREE_INT_CST_LOW (t) != low))
1475     TREE_OVERFLOW (t) = 1;
1476   TREE_CONSTANT_OVERFLOW (t) = (TREE_OVERFLOW (t)
1477                                 | TREE_CONSTANT_OVERFLOW (arg1)
1478                                 | TREE_CONSTANT_OVERFLOW (arg2));
1479   return t;
1480 }
1481
1482 struct cb_args
1483 {
1484   /* Input */
1485   tree arg1;
1486   REAL_VALUE_TYPE d1, d2;
1487   enum tree_code code;
1488   /* Output */
1489   tree t;
1490 };
1491
1492 static void
1493 const_binop_1 (data)
1494   PTR data;
1495 {
1496   struct cb_args * args = (struct cb_args *) data;
1497   REAL_VALUE_TYPE value;
1498
1499 #ifdef REAL_ARITHMETIC
1500   REAL_ARITHMETIC (value, args->code, args->d1, args->d2);
1501 #else
1502   switch (args->code)
1503     {
1504     case PLUS_EXPR:
1505       value = args->d1 + args->d2;
1506       break;
1507
1508     case MINUS_EXPR:
1509       value = args->d1 - args->d2;
1510       break;
1511
1512     case MULT_EXPR:
1513       value = args->d1 * args->d2;
1514       break;
1515
1516     case RDIV_EXPR:
1517 #ifndef REAL_INFINITY
1518       if (args->d2 == 0)
1519         abort ();
1520 #endif
1521
1522       value = args->d1 / args->d2;
1523       break;
1524
1525     case MIN_EXPR:
1526       value = MIN (args->d1, args->d2);
1527       break;
1528
1529     case MAX_EXPR:
1530       value = MAX (args->d1, args->d2);
1531       break;
1532
1533     default:
1534       abort ();
1535     }
1536 #endif /* no REAL_ARITHMETIC */
1537   args->t =
1538     build_real (TREE_TYPE (args->arg1),
1539                 real_value_truncate (TYPE_MODE (TREE_TYPE (args->arg1)),
1540                                      value));
1541 }
1542
1543 /* Combine two constants ARG1 and ARG2 under operation CODE
1544    to produce a new constant.
1545    We assume ARG1 and ARG2 have the same data type,
1546    or at least are the same kind of constant and the same machine mode.
1547
1548    If NOTRUNC is nonzero, do not truncate the result to fit the data type.  */
1549
1550 static tree
1551 const_binop (code, arg1, arg2, notrunc)
1552      enum tree_code code;
1553      register tree arg1, arg2;
1554      int notrunc;
1555 {
1556   STRIP_NOPS (arg1); STRIP_NOPS (arg2);
1557
1558   if (TREE_CODE (arg1) == INTEGER_CST)
1559     return int_const_binop (code, arg1, arg2, notrunc, 0);
1560
1561 #if ! defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
1562   if (TREE_CODE (arg1) == REAL_CST)
1563     {
1564       REAL_VALUE_TYPE d1;
1565       REAL_VALUE_TYPE d2;
1566       int overflow = 0;
1567       tree t;
1568       struct cb_args args;
1569
1570       d1 = TREE_REAL_CST (arg1);
1571       d2 = TREE_REAL_CST (arg2);
1572
1573       /* If either operand is a NaN, just return it.  Otherwise, set up
1574          for floating-point trap; we return an overflow.  */
1575       if (REAL_VALUE_ISNAN (d1))
1576         return arg1;
1577       else if (REAL_VALUE_ISNAN (d2))
1578         return arg2;
1579
1580       /* Setup input for const_binop_1() */
1581       args.arg1 = arg1;
1582       args.d1 = d1;
1583       args.d2 = d2;
1584       args.code = code;
1585
1586       if (do_float_handler (const_binop_1, (PTR) &args))
1587         {
1588           /* Receive output from const_binop_1() */
1589           t = args.t;
1590         }
1591       else
1592         {
1593           /* We got an exception from const_binop_1() */
1594           t = copy_node (arg1);
1595           overflow = 1;
1596         }
1597
1598       TREE_OVERFLOW (t)
1599         = (force_fit_type (t, overflow)
1600            | TREE_OVERFLOW (arg1) | TREE_OVERFLOW (arg2));
1601       TREE_CONSTANT_OVERFLOW (t)
1602         = TREE_OVERFLOW (t)
1603           | TREE_CONSTANT_OVERFLOW (arg1)
1604           | TREE_CONSTANT_OVERFLOW (arg2);
1605       return t;
1606     }
1607 #endif /* not REAL_IS_NOT_DOUBLE, or REAL_ARITHMETIC */
1608   if (TREE_CODE (arg1) == COMPLEX_CST)
1609     {
1610       register tree type = TREE_TYPE (arg1);
1611       register tree r1 = TREE_REALPART (arg1);
1612       register tree i1 = TREE_IMAGPART (arg1);
1613       register tree r2 = TREE_REALPART (arg2);
1614       register tree i2 = TREE_IMAGPART (arg2);
1615       register tree t;
1616
1617       switch (code)
1618         {
1619         case PLUS_EXPR:
1620           t = build_complex (type,
1621                              const_binop (PLUS_EXPR, r1, r2, notrunc),
1622                              const_binop (PLUS_EXPR, i1, i2, notrunc));
1623           break;
1624
1625         case MINUS_EXPR:
1626           t = build_complex (type,
1627                              const_binop (MINUS_EXPR, r1, r2, notrunc),
1628                              const_binop (MINUS_EXPR, i1, i2, notrunc));
1629           break;
1630
1631         case MULT_EXPR:
1632           t = build_complex (type,
1633                              const_binop (MINUS_EXPR,
1634                                           const_binop (MULT_EXPR,
1635                                                        r1, r2, notrunc),
1636                                           const_binop (MULT_EXPR,
1637                                                        i1, i2, notrunc),
1638                                           notrunc),
1639                              const_binop (PLUS_EXPR,
1640                                           const_binop (MULT_EXPR,
1641                                                        r1, i2, notrunc),
1642                                           const_binop (MULT_EXPR,
1643                                                        i1, r2, notrunc),
1644                                           notrunc));
1645           break;
1646
1647         case RDIV_EXPR:
1648           {
1649             register tree magsquared
1650               = const_binop (PLUS_EXPR,
1651                              const_binop (MULT_EXPR, r2, r2, notrunc),
1652                              const_binop (MULT_EXPR, i2, i2, notrunc),
1653                              notrunc);
1654
1655             t = build_complex (type,
1656                                const_binop
1657                                (INTEGRAL_TYPE_P (TREE_TYPE (r1))
1658                                 ? TRUNC_DIV_EXPR : RDIV_EXPR,
1659                                 const_binop (PLUS_EXPR,
1660                                              const_binop (MULT_EXPR, r1, r2,
1661                                                           notrunc),
1662                                              const_binop (MULT_EXPR, i1, i2,
1663                                                           notrunc),
1664                                              notrunc),
1665                                 magsquared, notrunc),
1666                                const_binop
1667                                (INTEGRAL_TYPE_P (TREE_TYPE (r1))
1668                                 ? TRUNC_DIV_EXPR : RDIV_EXPR,
1669                                 const_binop (MINUS_EXPR,
1670                                              const_binop (MULT_EXPR, i1, r2,
1671                                                           notrunc),
1672                                              const_binop (MULT_EXPR, r1, i2,
1673                                                           notrunc),
1674                                              notrunc),
1675                                 magsquared, notrunc));
1676           }
1677           break;
1678
1679         default:
1680           abort ();
1681         }
1682       return t;
1683     }
1684   return 0;
1685 }
1686 \f
1687 /* Return an INTEGER_CST with value V .  The type is determined by bit_p:
1688    if it is zero, the type is taken from sizetype; if it is one, the type
1689    is taken from bitsizetype.  */
1690
1691 tree
1692 size_int_wide (number, high, bit_p)
1693      unsigned HOST_WIDE_INT number, high;
1694      int bit_p;
1695 {
1696   tree t;
1697
1698   if (!ggc_p)
1699     {
1700       /* Type-size nodes already made for small sizes.  */
1701       static tree size_table[2*HOST_BITS_PER_WIDE_INT + 1][2];
1702
1703       if (number < 2*HOST_BITS_PER_WIDE_INT + 1 && ! high
1704           && size_table[number][bit_p] != 0)
1705         return size_table[number][bit_p];
1706       if (number < 2*HOST_BITS_PER_WIDE_INT + 1 && ! high)
1707         {
1708           push_obstacks_nochange ();
1709           /* Make this a permanent node.  */
1710           end_temporary_allocation ();
1711           t = build_int_2 (number, 0);
1712           TREE_TYPE (t) = bit_p ? bitsizetype : sizetype;
1713           size_table[number][bit_p] = t;
1714           pop_obstacks ();
1715           return t;
1716         }
1717     }
1718
1719   t = build_int_2 (number, high);
1720   TREE_TYPE (t) = bit_p ? bitsizetype : sizetype;
1721   TREE_OVERFLOW (t) = TREE_CONSTANT_OVERFLOW (t) = force_fit_type (t, 0);
1722   return t;
1723 }
1724
1725 /* Combine operands OP1 and OP2 with arithmetic operation CODE.
1726    CODE is a tree code.  Data type is taken from `sizetype',
1727    If the operands are constant, so is the result.  */
1728
1729 tree
1730 size_binop (code, arg0, arg1)
1731      enum tree_code code;
1732      tree arg0, arg1;
1733 {
1734   /* Handle the special case of two integer constants faster.  */
1735   if (TREE_CODE (arg0) == INTEGER_CST && TREE_CODE (arg1) == INTEGER_CST)
1736     {
1737       /* And some specific cases even faster than that.  */
1738       if (code == PLUS_EXPR && integer_zerop (arg0))
1739         return arg1;
1740       else if ((code == MINUS_EXPR || code == PLUS_EXPR)
1741                && integer_zerop (arg1))
1742         return arg0;
1743       else if (code == MULT_EXPR && integer_onep (arg0))
1744         return arg1;
1745
1746       /* Handle general case of two integer constants.  */
1747       return int_const_binop (code, arg0, arg1, 0, 1);
1748     }
1749
1750   if (arg0 == error_mark_node || arg1 == error_mark_node)
1751     return error_mark_node;
1752
1753   return fold (build (code, sizetype, arg0, arg1));
1754 }
1755
1756 /* Combine operands OP1 and OP2 with arithmetic operation CODE.
1757    CODE is a tree code.  Data type is taken from `ssizetype',
1758    If the operands are constant, so is the result.  */
1759
1760 tree
1761 ssize_binop (code, arg0, arg1)
1762      enum tree_code code;
1763      tree arg0, arg1;
1764 {
1765   /* Handle the special case of two integer constants faster.  */
1766   if (TREE_CODE (arg0) == INTEGER_CST && TREE_CODE (arg1) == INTEGER_CST)
1767     {
1768       /* And some specific cases even faster than that.  */
1769       if (code == PLUS_EXPR && integer_zerop (arg0))
1770         return arg1;
1771       else if ((code == MINUS_EXPR || code == PLUS_EXPR)
1772                && integer_zerop (arg1))
1773         return arg0;
1774       else if (code == MULT_EXPR && integer_onep (arg0))
1775         return arg1;
1776
1777       /* Handle general case of two integer constants.  We convert
1778          arg0 to ssizetype because int_const_binop uses its type for the
1779          return value.  */
1780       arg0 = convert (ssizetype, arg0);
1781       return int_const_binop (code, arg0, arg1, 0, 0);
1782     }
1783
1784   if (arg0 == error_mark_node || arg1 == error_mark_node)
1785     return error_mark_node;
1786
1787   return fold (build (code, ssizetype, arg0, arg1));
1788 }
1789 \f
1790 struct fc_args
1791 {
1792   /* Input */
1793   tree arg1, type;
1794   /* Output */
1795   tree t;
1796 };
1797
1798 static void
1799 fold_convert_1 (data)
1800   PTR data;
1801 {
1802   struct fc_args * args = (struct fc_args *) data;
1803
1804   args->t = build_real (args->type,
1805                         real_value_truncate (TYPE_MODE (args->type),
1806                                              TREE_REAL_CST (args->arg1)));
1807 }
1808
1809 /* Given T, a tree representing type conversion of ARG1, a constant,
1810    return a constant tree representing the result of conversion.  */
1811
1812 static tree
1813 fold_convert (t, arg1)
1814      register tree t;
1815      register tree arg1;
1816 {
1817   register tree type = TREE_TYPE (t);
1818   int overflow = 0;
1819
1820   if (POINTER_TYPE_P (type) || INTEGRAL_TYPE_P (type))
1821     {
1822       if (TREE_CODE (arg1) == INTEGER_CST)
1823         {
1824           /* If we would build a constant wider than GCC supports,
1825              leave the conversion unfolded.  */
1826           if (TYPE_PRECISION (type) > 2 * HOST_BITS_PER_WIDE_INT)
1827             return t;
1828
1829           /* Given an integer constant, make new constant with new type,
1830              appropriately sign-extended or truncated.  */
1831           t = build_int_2 (TREE_INT_CST_LOW (arg1),
1832                            TREE_INT_CST_HIGH (arg1));
1833           TREE_TYPE (t) = type;
1834           /* Indicate an overflow if (1) ARG1 already overflowed,
1835              or (2) force_fit_type indicates an overflow.
1836              Tell force_fit_type that an overflow has already occurred
1837              if ARG1 is a too-large unsigned value and T is signed.
1838              But don't indicate an overflow if converting a pointer.  */
1839           TREE_OVERFLOW (t)
1840             = ((force_fit_type (t,
1841                                 (TREE_INT_CST_HIGH (arg1) < 0
1842                                  && (TREE_UNSIGNED (type)
1843                                     < TREE_UNSIGNED (TREE_TYPE (arg1)))))
1844                 && ! POINTER_TYPE_P (TREE_TYPE (arg1)))
1845                || TREE_OVERFLOW (arg1));
1846           TREE_CONSTANT_OVERFLOW (t)
1847             = TREE_OVERFLOW (t) | TREE_CONSTANT_OVERFLOW (arg1);
1848         }
1849 #if !defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
1850       else if (TREE_CODE (arg1) == REAL_CST)
1851         {
1852           /* Don't initialize these, use assignments.
1853              Initialized local aggregates don't work on old compilers.  */
1854           REAL_VALUE_TYPE x;
1855           REAL_VALUE_TYPE l;
1856           REAL_VALUE_TYPE u;
1857           tree type1 = TREE_TYPE (arg1);
1858           int no_upper_bound;
1859
1860           x = TREE_REAL_CST (arg1);
1861           l = real_value_from_int_cst (type1, TYPE_MIN_VALUE (type));
1862
1863           no_upper_bound = (TYPE_MAX_VALUE (type) == NULL);
1864           if (!no_upper_bound)
1865             u = real_value_from_int_cst (type1, TYPE_MAX_VALUE (type));
1866
1867           /* See if X will be in range after truncation towards 0.
1868              To compensate for truncation, move the bounds away from 0,
1869              but reject if X exactly equals the adjusted bounds.  */
1870 #ifdef REAL_ARITHMETIC
1871           REAL_ARITHMETIC (l, MINUS_EXPR, l, dconst1);
1872           if (!no_upper_bound)
1873             REAL_ARITHMETIC (u, PLUS_EXPR, u, dconst1);
1874 #else
1875           l--;
1876           if (!no_upper_bound)
1877             u++;
1878 #endif
1879           /* If X is a NaN, use zero instead and show we have an overflow.
1880              Otherwise, range check.  */
1881           if (REAL_VALUE_ISNAN (x))
1882             overflow = 1, x = dconst0;
1883           else if (! (REAL_VALUES_LESS (l, x)
1884                       && !no_upper_bound
1885                       && REAL_VALUES_LESS (x, u)))
1886             overflow = 1;
1887
1888 #ifndef REAL_ARITHMETIC
1889           {
1890             HOST_WIDE_INT low, high;
1891             HOST_WIDE_INT half_word
1892               = (HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT / 2);
1893
1894             if (x < 0)
1895               x = -x;
1896
1897             high = (HOST_WIDE_INT) (x / half_word / half_word);
1898             x -= (REAL_VALUE_TYPE) high * half_word * half_word;
1899             if (x >= (REAL_VALUE_TYPE) half_word * half_word / 2)
1900               {
1901                 low = x - (REAL_VALUE_TYPE) half_word * half_word / 2;
1902                 low |= (HOST_WIDE_INT) -1 << (HOST_BITS_PER_WIDE_INT - 1);
1903               }
1904             else
1905               low = (HOST_WIDE_INT) x;
1906             if (TREE_REAL_CST (arg1) < 0)
1907               neg_double (low, high, &low, &high);
1908             t = build_int_2 (low, high);
1909           }
1910 #else
1911           {
1912             HOST_WIDE_INT low, high;
1913             REAL_VALUE_TO_INT (&low, &high, x);
1914             t = build_int_2 (low, high);
1915           }
1916 #endif
1917           TREE_TYPE (t) = type;
1918           TREE_OVERFLOW (t)
1919             = TREE_OVERFLOW (arg1) | force_fit_type (t, overflow);
1920           TREE_CONSTANT_OVERFLOW (t)
1921             = TREE_OVERFLOW (t) | TREE_CONSTANT_OVERFLOW (arg1);
1922         }
1923 #endif /* not REAL_IS_NOT_DOUBLE, or REAL_ARITHMETIC */
1924       TREE_TYPE (t) = type;
1925     }
1926   else if (TREE_CODE (type) == REAL_TYPE)
1927     {
1928 #if !defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
1929       if (TREE_CODE (arg1) == INTEGER_CST)
1930         return build_real_from_int_cst (type, arg1);
1931 #endif /* not REAL_IS_NOT_DOUBLE, or REAL_ARITHMETIC */
1932       if (TREE_CODE (arg1) == REAL_CST)
1933         {
1934           struct fc_args args;
1935
1936           if (REAL_VALUE_ISNAN (TREE_REAL_CST (arg1)))
1937             {
1938               t = arg1;
1939               TREE_TYPE (arg1) = type;
1940               return t;
1941             }
1942
1943           /* Setup input for fold_convert_1() */
1944           args.arg1 = arg1;
1945           args.type = type;
1946
1947           if (do_float_handler (fold_convert_1, (PTR) &args))
1948             {
1949               /* Receive output from fold_convert_1() */
1950               t = args.t;
1951             }
1952           else
1953             {
1954               /* We got an exception from fold_convert_1() */
1955               overflow = 1;
1956               t = copy_node (arg1);
1957             }
1958
1959           TREE_OVERFLOW (t)
1960             = TREE_OVERFLOW (arg1) | force_fit_type (t, overflow);
1961           TREE_CONSTANT_OVERFLOW (t)
1962             = TREE_OVERFLOW (t) | TREE_CONSTANT_OVERFLOW (arg1);
1963           return t;
1964         }
1965     }
1966   TREE_CONSTANT (t) = 1;
1967   return t;
1968 }
1969 \f
1970 /* Return an expr equal to X but certainly not valid as an lvalue.  */
1971
1972 tree
1973 non_lvalue (x)
1974      tree x;
1975 {
1976   tree result;
1977
1978   /* These things are certainly not lvalues.  */
1979   if (TREE_CODE (x) == NON_LVALUE_EXPR
1980       || TREE_CODE (x) == INTEGER_CST
1981       || TREE_CODE (x) == REAL_CST
1982       || TREE_CODE (x) == STRING_CST
1983       || TREE_CODE (x) == ADDR_EXPR)
1984     return x;
1985
1986   result = build1 (NON_LVALUE_EXPR, TREE_TYPE (x), x);
1987   TREE_CONSTANT (result) = TREE_CONSTANT (x);
1988   return result;
1989 }
1990
1991 /* Nonzero means lvalues are limited to those valid in pedantic ANSI C.
1992    Zero means allow extended lvalues.  */
1993
1994 int pedantic_lvalues;
1995
1996 /* When pedantic, return an expr equal to X but certainly not valid as a
1997    pedantic lvalue.  Otherwise, return X.  */
1998
1999 tree
2000 pedantic_non_lvalue (x)
2001      tree x;
2002 {
2003   if (pedantic_lvalues)
2004     return non_lvalue (x);
2005   else
2006     return x;
2007 }
2008 \f
2009 /* Given a tree comparison code, return the code that is the logical inverse
2010    of the given code.  It is not safe to do this for floating-point
2011    comparisons, except for NE_EXPR and EQ_EXPR.  */
2012
2013 static enum tree_code
2014 invert_tree_comparison (code)
2015      enum tree_code code;
2016 {
2017   switch (code)
2018     {
2019     case EQ_EXPR:
2020       return NE_EXPR;
2021     case NE_EXPR:
2022       return EQ_EXPR;
2023     case GT_EXPR:
2024       return LE_EXPR;
2025     case GE_EXPR:
2026       return LT_EXPR;
2027     case LT_EXPR:
2028       return GE_EXPR;
2029     case LE_EXPR:
2030       return GT_EXPR;
2031     default:
2032       abort ();
2033     }
2034 }
2035
2036 /* Similar, but return the comparison that results if the operands are
2037    swapped.  This is safe for floating-point.  */
2038
2039 static enum tree_code
2040 swap_tree_comparison (code)
2041      enum tree_code code;
2042 {
2043   switch (code)
2044     {
2045     case EQ_EXPR:
2046     case NE_EXPR:
2047       return code;
2048     case GT_EXPR:
2049       return LT_EXPR;
2050     case GE_EXPR:
2051       return LE_EXPR;
2052     case LT_EXPR:
2053       return GT_EXPR;
2054     case LE_EXPR:
2055       return GE_EXPR;
2056     default:
2057       abort ();
2058     }
2059 }
2060
2061 /* Return nonzero if CODE is a tree code that represents a truth value.  */
2062
2063 static int
2064 truth_value_p (code)
2065      enum tree_code code;
2066 {
2067   return (TREE_CODE_CLASS (code) == '<'
2068           || code == TRUTH_AND_EXPR || code == TRUTH_ANDIF_EXPR
2069           || code == TRUTH_OR_EXPR || code == TRUTH_ORIF_EXPR
2070           || code == TRUTH_XOR_EXPR || code == TRUTH_NOT_EXPR);
2071 }
2072 \f
2073 /* Return nonzero if two operands are necessarily equal.
2074    If ONLY_CONST is non-zero, only return non-zero for constants.
2075    This function tests whether the operands are indistinguishable;
2076    it does not test whether they are equal using C's == operation.
2077    The distinction is important for IEEE floating point, because
2078    (1) -0.0 and 0.0 are distinguishable, but -0.0==0.0, and
2079    (2) two NaNs may be indistinguishable, but NaN!=NaN.  */
2080
2081 int
2082 operand_equal_p (arg0, arg1, only_const)
2083      tree arg0, arg1;
2084      int only_const;
2085 {
2086   /* If both types don't have the same signedness, then we can't consider
2087      them equal.  We must check this before the STRIP_NOPS calls
2088      because they may change the signedness of the arguments.  */
2089   if (TREE_UNSIGNED (TREE_TYPE (arg0)) != TREE_UNSIGNED (TREE_TYPE (arg1)))
2090     return 0;
2091
2092   STRIP_NOPS (arg0);
2093   STRIP_NOPS (arg1);
2094
2095   if (TREE_CODE (arg0) != TREE_CODE (arg1)
2096       /* This is needed for conversions and for COMPONENT_REF.
2097          Might as well play it safe and always test this.  */
2098       || TREE_CODE (TREE_TYPE (arg0)) == ERROR_MARK
2099       || TREE_CODE (TREE_TYPE (arg1)) == ERROR_MARK
2100       || TYPE_MODE (TREE_TYPE (arg0)) != TYPE_MODE (TREE_TYPE (arg1)))
2101     return 0;
2102
2103   /* If ARG0 and ARG1 are the same SAVE_EXPR, they are necessarily equal.
2104      We don't care about side effects in that case because the SAVE_EXPR
2105      takes care of that for us. In all other cases, two expressions are
2106      equal if they have no side effects.  If we have two identical
2107      expressions with side effects that should be treated the same due
2108      to the only side effects being identical SAVE_EXPR's, that will
2109      be detected in the recursive calls below.  */
2110   if (arg0 == arg1 && ! only_const
2111       && (TREE_CODE (arg0) == SAVE_EXPR
2112           || (! TREE_SIDE_EFFECTS (arg0) && ! TREE_SIDE_EFFECTS (arg1))))
2113     return 1;
2114
2115   /* Next handle constant cases, those for which we can return 1 even
2116      if ONLY_CONST is set.  */
2117   if (TREE_CONSTANT (arg0) && TREE_CONSTANT (arg1))
2118     switch (TREE_CODE (arg0))
2119       {
2120       case INTEGER_CST:
2121         return (! TREE_CONSTANT_OVERFLOW (arg0)
2122                 && ! TREE_CONSTANT_OVERFLOW (arg1)
2123                 && TREE_INT_CST_LOW (arg0) == TREE_INT_CST_LOW (arg1)
2124                 && TREE_INT_CST_HIGH (arg0) == TREE_INT_CST_HIGH (arg1));
2125
2126       case REAL_CST:
2127         return (! TREE_CONSTANT_OVERFLOW (arg0)
2128                 && ! TREE_CONSTANT_OVERFLOW (arg1)
2129                 && REAL_VALUES_IDENTICAL (TREE_REAL_CST (arg0),
2130                                           TREE_REAL_CST (arg1)));
2131
2132       case COMPLEX_CST:
2133         return (operand_equal_p (TREE_REALPART (arg0), TREE_REALPART (arg1),
2134                                  only_const)
2135                 && operand_equal_p (TREE_IMAGPART (arg0), TREE_IMAGPART (arg1),
2136                                     only_const));
2137
2138       case STRING_CST:
2139         return (TREE_STRING_LENGTH (arg0) == TREE_STRING_LENGTH (arg1)
2140                 && ! strncmp (TREE_STRING_POINTER (arg0),
2141                               TREE_STRING_POINTER (arg1),
2142                               TREE_STRING_LENGTH (arg0)));
2143
2144       case ADDR_EXPR:
2145         return operand_equal_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg1, 0),
2146                                 0);
2147       default:
2148         break;
2149       }
2150
2151   if (only_const)
2152     return 0;
2153
2154   switch (TREE_CODE_CLASS (TREE_CODE (arg0)))
2155     {
2156     case '1':
2157       /* Two conversions are equal only if signedness and modes match.  */
2158       if ((TREE_CODE (arg0) == NOP_EXPR || TREE_CODE (arg0) == CONVERT_EXPR)
2159           && (TREE_UNSIGNED (TREE_TYPE (arg0))
2160               != TREE_UNSIGNED (TREE_TYPE (arg1))))
2161         return 0;
2162
2163       return operand_equal_p (TREE_OPERAND (arg0, 0),
2164                               TREE_OPERAND (arg1, 0), 0);
2165
2166     case '<':
2167     case '2':
2168       if (operand_equal_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg1, 0), 0)
2169           && operand_equal_p (TREE_OPERAND (arg0, 1), TREE_OPERAND (arg1, 1),
2170                               0))
2171         return 1;
2172
2173       /* For commutative ops, allow the other order.  */
2174       return ((TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MULT_EXPR
2175                || TREE_CODE (arg0) == MIN_EXPR || TREE_CODE (arg0) == MAX_EXPR
2176                || TREE_CODE (arg0) == BIT_IOR_EXPR
2177                || TREE_CODE (arg0) == BIT_XOR_EXPR
2178                || TREE_CODE (arg0) == BIT_AND_EXPR
2179                || TREE_CODE (arg0) == NE_EXPR || TREE_CODE (arg0) == EQ_EXPR)
2180               && operand_equal_p (TREE_OPERAND (arg0, 0),
2181                                   TREE_OPERAND (arg1, 1), 0)
2182               && operand_equal_p (TREE_OPERAND (arg0, 1),
2183                                   TREE_OPERAND (arg1, 0), 0));
2184
2185     case 'r':
2186       /* If either of the pointer (or reference) expressions we are dereferencing
2187          contain a side effect, these cannot be equal. */
2188       if (TREE_SIDE_EFFECTS (arg0)
2189           || TREE_SIDE_EFFECTS (arg1))
2190         return 0;
2191
2192       switch (TREE_CODE (arg0))
2193         {
2194         case INDIRECT_REF:
2195           return operand_equal_p (TREE_OPERAND (arg0, 0),
2196                                   TREE_OPERAND (arg1, 0), 0);
2197
2198         case COMPONENT_REF:
2199         case ARRAY_REF:
2200           return (operand_equal_p (TREE_OPERAND (arg0, 0),
2201                                    TREE_OPERAND (arg1, 0), 0)
2202                   && operand_equal_p (TREE_OPERAND (arg0, 1),
2203                                       TREE_OPERAND (arg1, 1), 0));
2204
2205         case BIT_FIELD_REF:
2206           return (operand_equal_p (TREE_OPERAND (arg0, 0),
2207                                    TREE_OPERAND (arg1, 0), 0)
2208                   && operand_equal_p (TREE_OPERAND (arg0, 1),
2209                                       TREE_OPERAND (arg1, 1), 0)
2210                   && operand_equal_p (TREE_OPERAND (arg0, 2),
2211                                       TREE_OPERAND (arg1, 2), 0));
2212         default:
2213           return 0;
2214         }
2215
2216     case 'e':
2217       if (TREE_CODE (arg0) == RTL_EXPR)
2218         return rtx_equal_p (RTL_EXPR_RTL (arg0), RTL_EXPR_RTL (arg1));
2219       return 0;
2220
2221     default:
2222       return 0;
2223     }
2224 }
2225 \f
2226 /* Similar to operand_equal_p, but see if ARG0 might have been made by
2227    shorten_compare from ARG1 when ARG1 was being compared with OTHER.
2228
2229    When in doubt, return 0.  */
2230
2231 static int
2232 operand_equal_for_comparison_p (arg0, arg1, other)
2233      tree arg0, arg1;
2234      tree other;
2235 {
2236   int unsignedp1, unsignedpo;
2237   tree primarg0, primarg1, primother;
2238   unsigned correct_width;
2239
2240   if (operand_equal_p (arg0, arg1, 0))
2241     return 1;
2242
2243   if (! INTEGRAL_TYPE_P (TREE_TYPE (arg0))
2244       || ! INTEGRAL_TYPE_P (TREE_TYPE (arg1)))
2245     return 0;
2246
2247   /* Discard any conversions that don't change the modes of ARG0 and ARG1
2248      and see if the inner values are the same.  This removes any
2249      signedness comparison, which doesn't matter here.  */
2250   primarg0 = arg0, primarg1 = arg1;
2251   STRIP_NOPS (primarg0);  STRIP_NOPS (primarg1);
2252   if (operand_equal_p (primarg0, primarg1, 0))
2253     return 1;
2254
2255   /* Duplicate what shorten_compare does to ARG1 and see if that gives the
2256      actual comparison operand, ARG0.
2257
2258      First throw away any conversions to wider types
2259      already present in the operands.  */
2260
2261   primarg1 = get_narrower (arg1, &unsignedp1);
2262   primother = get_narrower (other, &unsignedpo);
2263
2264   correct_width = TYPE_PRECISION (TREE_TYPE (arg1));
2265   if (unsignedp1 == unsignedpo
2266       && TYPE_PRECISION (TREE_TYPE (primarg1)) < correct_width
2267       && TYPE_PRECISION (TREE_TYPE (primother)) < correct_width)
2268     {
2269       tree type = TREE_TYPE (arg0);
2270
2271       /* Make sure shorter operand is extended the right way
2272          to match the longer operand.  */
2273       primarg1 = convert (signed_or_unsigned_type (unsignedp1,
2274                                                   TREE_TYPE (primarg1)),
2275                          primarg1);
2276
2277       if (operand_equal_p (arg0, convert (type, primarg1), 0))
2278         return 1;
2279     }
2280
2281   return 0;
2282 }
2283 \f
2284 /* See if ARG is an expression that is either a comparison or is performing
2285    arithmetic on comparisons.  The comparisons must only be comparing
2286    two different values, which will be stored in *CVAL1 and *CVAL2; if
2287    they are non-zero it means that some operands have already been found.
2288    No variables may be used anywhere else in the expression except in the
2289    comparisons.  If SAVE_P is true it means we removed a SAVE_EXPR around
2290    the expression and save_expr needs to be called with CVAL1 and CVAL2.
2291
2292    If this is true, return 1.  Otherwise, return zero.  */
2293
2294 static int
2295 twoval_comparison_p (arg, cval1, cval2, save_p)
2296      tree arg;
2297      tree *cval1, *cval2;
2298      int *save_p;
2299 {
2300   enum tree_code code = TREE_CODE (arg);
2301   char class = TREE_CODE_CLASS (code);
2302
2303   /* We can handle some of the 'e' cases here.  */
2304   if (class == 'e' && code == TRUTH_NOT_EXPR)
2305     class = '1';
2306   else if (class == 'e'
2307            && (code == TRUTH_ANDIF_EXPR || code == TRUTH_ORIF_EXPR
2308                || code == COMPOUND_EXPR))
2309     class = '2';
2310
2311   /* ??? Disable this since the SAVE_EXPR might already be in use outside
2312      the expression.  There may be no way to make this work, but it needs
2313      to be looked at again for 2.6.  */
2314 #if 0
2315   else if (class == 'e' && code == SAVE_EXPR && SAVE_EXPR_RTL (arg) == 0)
2316     {
2317       /* If we've already found a CVAL1 or CVAL2, this expression is
2318          two complex to handle.  */
2319       if (*cval1 || *cval2)
2320         return 0;
2321
2322       class = '1';
2323       *save_p = 1;
2324     }
2325 #endif
2326
2327   switch (class)
2328     {
2329     case '1':
2330       return twoval_comparison_p (TREE_OPERAND (arg, 0), cval1, cval2, save_p);
2331
2332     case '2':
2333       return (twoval_comparison_p (TREE_OPERAND (arg, 0), cval1, cval2, save_p)
2334               && twoval_comparison_p (TREE_OPERAND (arg, 1),
2335                                       cval1, cval2, save_p));
2336
2337     case 'c':
2338       return 1;
2339
2340     case 'e':
2341       if (code == COND_EXPR)
2342         return (twoval_comparison_p (TREE_OPERAND (arg, 0),
2343                                      cval1, cval2, save_p)
2344                 && twoval_comparison_p (TREE_OPERAND (arg, 1),
2345                                         cval1, cval2, save_p)
2346                 && twoval_comparison_p (TREE_OPERAND (arg, 2),
2347                                         cval1, cval2, save_p));
2348       return 0;
2349
2350     case '<':
2351       /* First see if we can handle the first operand, then the second.  For
2352          the second operand, we know *CVAL1 can't be zero.  It must be that
2353          one side of the comparison is each of the values; test for the
2354          case where this isn't true by failing if the two operands
2355          are the same.  */
2356
2357       if (operand_equal_p (TREE_OPERAND (arg, 0),
2358                            TREE_OPERAND (arg, 1), 0))
2359         return 0;
2360
2361       if (*cval1 == 0)
2362         *cval1 = TREE_OPERAND (arg, 0);
2363       else if (operand_equal_p (*cval1, TREE_OPERAND (arg, 0), 0))
2364         ;
2365       else if (*cval2 == 0)
2366         *cval2 = TREE_OPERAND (arg, 0);
2367       else if (operand_equal_p (*cval2, TREE_OPERAND (arg, 0), 0))
2368         ;
2369       else
2370         return 0;
2371
2372       if (operand_equal_p (*cval1, TREE_OPERAND (arg, 1), 0))
2373         ;
2374       else if (*cval2 == 0)
2375         *cval2 = TREE_OPERAND (arg, 1);
2376       else if (operand_equal_p (*cval2, TREE_OPERAND (arg, 1), 0))
2377         ;
2378       else
2379         return 0;
2380
2381       return 1;
2382
2383     default:
2384       return 0;
2385     }
2386 }
2387 \f
2388 /* ARG is a tree that is known to contain just arithmetic operations and
2389    comparisons.  Evaluate the operations in the tree substituting NEW0 for
2390    any occurrence of OLD0 as an operand of a comparison and likewise for
2391    NEW1 and OLD1.  */
2392
2393 static tree
2394 eval_subst (arg, old0, new0, old1, new1)
2395      tree arg;
2396      tree old0, new0, old1, new1;
2397 {
2398   tree type = TREE_TYPE (arg);
2399   enum tree_code code = TREE_CODE (arg);
2400   char class = TREE_CODE_CLASS (code);
2401
2402   /* We can handle some of the 'e' cases here.  */
2403   if (class == 'e' && code == TRUTH_NOT_EXPR)
2404     class = '1';
2405   else if (class == 'e'
2406            && (code == TRUTH_ANDIF_EXPR || code == TRUTH_ORIF_EXPR))
2407     class = '2';
2408
2409   switch (class)
2410     {
2411     case '1':
2412       return fold (build1 (code, type,
2413                            eval_subst (TREE_OPERAND (arg, 0),
2414                                        old0, new0, old1, new1)));
2415
2416     case '2':
2417       return fold (build (code, type,
2418                           eval_subst (TREE_OPERAND (arg, 0),
2419                                       old0, new0, old1, new1),
2420                           eval_subst (TREE_OPERAND (arg, 1),
2421                                       old0, new0, old1, new1)));
2422
2423     case 'e':
2424       switch (code)
2425         {
2426         case SAVE_EXPR:
2427           return eval_subst (TREE_OPERAND (arg, 0), old0, new0, old1, new1);
2428
2429         case COMPOUND_EXPR:
2430           return eval_subst (TREE_OPERAND (arg, 1), old0, new0, old1, new1);
2431
2432         case COND_EXPR:
2433           return fold (build (code, type,
2434                               eval_subst (TREE_OPERAND (arg, 0),
2435                                           old0, new0, old1, new1),
2436                               eval_subst (TREE_OPERAND (arg, 1),
2437                                           old0, new0, old1, new1),
2438                               eval_subst (TREE_OPERAND (arg, 2),
2439                                           old0, new0, old1, new1)));
2440         default:
2441           break;
2442         }
2443       /* fall through - ??? */
2444
2445     case '<':
2446       {
2447         tree arg0 = TREE_OPERAND (arg, 0);
2448         tree arg1 = TREE_OPERAND (arg, 1);
2449
2450         /* We need to check both for exact equality and tree equality.  The
2451            former will be true if the operand has a side-effect.  In that
2452            case, we know the operand occurred exactly once.  */
2453
2454         if (arg0 == old0 || operand_equal_p (arg0, old0, 0))
2455           arg0 = new0;
2456         else if (arg0 == old1 || operand_equal_p (arg0, old1, 0))
2457           arg0 = new1;
2458
2459         if (arg1 == old0 || operand_equal_p (arg1, old0, 0))
2460           arg1 = new0;
2461         else if (arg1 == old1 || operand_equal_p (arg1, old1, 0))
2462           arg1 = new1;
2463
2464         return fold (build (code, type, arg0, arg1));
2465       }
2466
2467     default:
2468       return arg;
2469     }
2470 }
2471 \f
2472 /* Return a tree for the case when the result of an expression is RESULT
2473    converted to TYPE and OMITTED was previously an operand of the expression
2474    but is now not needed (e.g., we folded OMITTED * 0).
2475
2476    If OMITTED has side effects, we must evaluate it.  Otherwise, just do
2477    the conversion of RESULT to TYPE.  */
2478
2479 static tree
2480 omit_one_operand (type, result, omitted)
2481      tree type, result, omitted;
2482 {
2483   tree t = convert (type, result);
2484
2485   if (TREE_SIDE_EFFECTS (omitted))
2486     return build (COMPOUND_EXPR, type, omitted, t);
2487
2488   return non_lvalue (t);
2489 }
2490
2491 /* Similar, but call pedantic_non_lvalue instead of non_lvalue.  */
2492
2493 static tree
2494 pedantic_omit_one_operand (type, result, omitted)
2495      tree type, result, omitted;
2496 {
2497   tree t = convert (type, result);
2498
2499   if (TREE_SIDE_EFFECTS (omitted))
2500     return build (COMPOUND_EXPR, type, omitted, t);
2501
2502   return pedantic_non_lvalue (t);
2503 }
2504
2505
2506 \f
2507 /* Return a simplified tree node for the truth-negation of ARG.  This
2508    never alters ARG itself.  We assume that ARG is an operation that
2509    returns a truth value (0 or 1).  */
2510
2511 tree
2512 invert_truthvalue (arg)
2513      tree arg;
2514 {
2515   tree type = TREE_TYPE (arg);
2516   enum tree_code code = TREE_CODE (arg);
2517
2518   if (code == ERROR_MARK)
2519     return arg;
2520
2521   /* If this is a comparison, we can simply invert it, except for
2522      floating-point non-equality comparisons, in which case we just
2523      enclose a TRUTH_NOT_EXPR around what we have.  */
2524
2525   if (TREE_CODE_CLASS (code) == '<')
2526     {
2527       if (FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (arg, 0)))
2528           && !flag_fast_math && code != NE_EXPR && code != EQ_EXPR)
2529         return build1 (TRUTH_NOT_EXPR, type, arg);
2530       else
2531         return build (invert_tree_comparison (code), type,
2532                       TREE_OPERAND (arg, 0), TREE_OPERAND (arg, 1));
2533     }
2534
2535   switch (code)
2536     {
2537     case INTEGER_CST:
2538       return convert (type, build_int_2 (TREE_INT_CST_LOW (arg) == 0
2539                                          && TREE_INT_CST_HIGH (arg) == 0, 0));
2540
2541     case TRUTH_AND_EXPR:
2542       return build (TRUTH_OR_EXPR, type,
2543                     invert_truthvalue (TREE_OPERAND (arg, 0)),
2544                     invert_truthvalue (TREE_OPERAND (arg, 1)));
2545
2546     case TRUTH_OR_EXPR:
2547       return build (TRUTH_AND_EXPR, type,
2548                     invert_truthvalue (TREE_OPERAND (arg, 0)),
2549                     invert_truthvalue (TREE_OPERAND (arg, 1)));
2550
2551     case TRUTH_XOR_EXPR:
2552       /* Here we can invert either operand.  We invert the first operand
2553          unless the second operand is a TRUTH_NOT_EXPR in which case our
2554          result is the XOR of the first operand with the inside of the
2555          negation of the second operand.  */
2556
2557       if (TREE_CODE (TREE_OPERAND (arg, 1)) == TRUTH_NOT_EXPR)
2558         return build (TRUTH_XOR_EXPR, type, TREE_OPERAND (arg, 0),
2559                       TREE_OPERAND (TREE_OPERAND (arg, 1), 0));
2560       else
2561         return build (TRUTH_XOR_EXPR, type,
2562                       invert_truthvalue (TREE_OPERAND (arg, 0)),
2563                       TREE_OPERAND (arg, 1));
2564
2565     case TRUTH_ANDIF_EXPR:
2566       return build (TRUTH_ORIF_EXPR, type,
2567                     invert_truthvalue (TREE_OPERAND (arg, 0)),
2568                     invert_truthvalue (TREE_OPERAND (arg, 1)));
2569
2570     case TRUTH_ORIF_EXPR:
2571       return build (TRUTH_ANDIF_EXPR, type,
2572                     invert_truthvalue (TREE_OPERAND (arg, 0)),
2573                     invert_truthvalue (TREE_OPERAND (arg, 1)));
2574
2575     case TRUTH_NOT_EXPR:
2576       return TREE_OPERAND (arg, 0);
2577
2578     case COND_EXPR:
2579       return build (COND_EXPR, type, TREE_OPERAND (arg, 0),
2580                     invert_truthvalue (TREE_OPERAND (arg, 1)),
2581                     invert_truthvalue (TREE_OPERAND (arg, 2)));
2582
2583     case COMPOUND_EXPR:
2584       return build (COMPOUND_EXPR, type, TREE_OPERAND (arg, 0),
2585                     invert_truthvalue (TREE_OPERAND (arg, 1)));
2586
2587     case NON_LVALUE_EXPR:
2588       return invert_truthvalue (TREE_OPERAND (arg, 0));
2589
2590     case NOP_EXPR:
2591     case CONVERT_EXPR:
2592     case FLOAT_EXPR:
2593       return build1 (TREE_CODE (arg), type,
2594                      invert_truthvalue (TREE_OPERAND (arg, 0)));
2595
2596     case BIT_AND_EXPR:
2597       if (!integer_onep (TREE_OPERAND (arg, 1)))
2598         break;
2599       return build (EQ_EXPR, type, arg, convert (type, integer_zero_node));
2600
2601     case SAVE_EXPR:
2602       return build1 (TRUTH_NOT_EXPR, type, arg);
2603
2604     case CLEANUP_POINT_EXPR:
2605       return build1 (CLEANUP_POINT_EXPR, type,
2606                      invert_truthvalue (TREE_OPERAND (arg, 0)));
2607
2608     default:
2609       break;
2610     }
2611   if (TREE_CODE (TREE_TYPE (arg)) != BOOLEAN_TYPE)
2612     abort ();
2613   return build1 (TRUTH_NOT_EXPR, type, arg);
2614 }
2615
2616 /* Given a bit-wise operation CODE applied to ARG0 and ARG1, see if both
2617    operands are another bit-wise operation with a common input.  If so,
2618    distribute the bit operations to save an operation and possibly two if
2619    constants are involved.  For example, convert
2620         (A | B) & (A | C) into A | (B & C)
2621    Further simplification will occur if B and C are constants.
2622
2623    If this optimization cannot be done, 0 will be returned.  */
2624
2625 static tree
2626 distribute_bit_expr (code, type, arg0, arg1)
2627      enum tree_code code;
2628      tree type;
2629      tree arg0, arg1;
2630 {
2631   tree common;
2632   tree left, right;
2633
2634   if (TREE_CODE (arg0) != TREE_CODE (arg1)
2635       || TREE_CODE (arg0) == code
2636       || (TREE_CODE (arg0) != BIT_AND_EXPR
2637           && TREE_CODE (arg0) != BIT_IOR_EXPR))
2638     return 0;
2639
2640   if (operand_equal_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg1, 0), 0))
2641     {
2642       common = TREE_OPERAND (arg0, 0);
2643       left = TREE_OPERAND (arg0, 1);
2644       right = TREE_OPERAND (arg1, 1);
2645     }
2646   else if (operand_equal_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg1, 1), 0))
2647     {
2648       common = TREE_OPERAND (arg0, 0);
2649       left = TREE_OPERAND (arg0, 1);
2650       right = TREE_OPERAND (arg1, 0);
2651     }
2652   else if (operand_equal_p (TREE_OPERAND (arg0, 1), TREE_OPERAND (arg1, 0), 0))
2653     {
2654       common = TREE_OPERAND (arg0, 1);
2655       left = TREE_OPERAND (arg0, 0);
2656       right = TREE_OPERAND (arg1, 1);
2657     }
2658   else if (operand_equal_p (TREE_OPERAND (arg0, 1), TREE_OPERAND (arg1, 1), 0))
2659     {
2660       common = TREE_OPERAND (arg0, 1);
2661       left = TREE_OPERAND (arg0, 0);
2662       right = TREE_OPERAND (arg1, 0);
2663     }
2664   else
2665     return 0;
2666
2667   return fold (build (TREE_CODE (arg0), type, common,
2668                       fold (build (code, type, left, right))));
2669 }
2670 \f
2671 /* Return a BIT_FIELD_REF of type TYPE to refer to BITSIZE bits of INNER
2672    starting at BITPOS.  The field is unsigned if UNSIGNEDP is non-zero.  */
2673
2674 static tree
2675 make_bit_field_ref (inner, type, bitsize, bitpos, unsignedp)
2676      tree inner;
2677      tree type;
2678      int bitsize, bitpos;
2679      int unsignedp;
2680 {
2681   tree result = build (BIT_FIELD_REF, type, inner,
2682                        size_int (bitsize), bitsize_int (bitpos, 0L));
2683
2684   TREE_UNSIGNED (result) = unsignedp;
2685
2686   return result;
2687 }
2688
2689 /* Optimize a bit-field compare.
2690
2691    There are two cases:  First is a compare against a constant and the
2692    second is a comparison of two items where the fields are at the same
2693    bit position relative to the start of a chunk (byte, halfword, word)
2694    large enough to contain it.  In these cases we can avoid the shift
2695    implicit in bitfield extractions.
2696
2697    For constants, we emit a compare of the shifted constant with the
2698    BIT_AND_EXPR of a mask and a byte, halfword, or word of the operand being
2699    compared.  For two fields at the same position, we do the ANDs with the
2700    similar mask and compare the result of the ANDs.
2701
2702    CODE is the comparison code, known to be either NE_EXPR or EQ_EXPR.
2703    COMPARE_TYPE is the type of the comparison, and LHS and RHS
2704    are the left and right operands of the comparison, respectively.
2705
2706    If the optimization described above can be done, we return the resulting
2707    tree.  Otherwise we return zero.  */
2708
2709 static tree
2710 optimize_bit_field_compare (code, compare_type, lhs, rhs)
2711      enum tree_code code;
2712      tree compare_type;
2713      tree lhs, rhs;
2714 {
2715   int lbitpos, lbitsize, rbitpos, rbitsize;
2716   int lnbitpos, lnbitsize, rnbitpos = 0, rnbitsize = 0;
2717   tree type = TREE_TYPE (lhs);
2718   tree signed_type, unsigned_type;
2719   int const_p = TREE_CODE (rhs) == INTEGER_CST;
2720   enum machine_mode lmode, rmode, lnmode, rnmode = VOIDmode;
2721   int lunsignedp, runsignedp;
2722   int lvolatilep = 0, rvolatilep = 0;
2723   int alignment;
2724   tree linner, rinner = NULL_TREE;
2725   tree mask;
2726   tree offset;
2727
2728   /* Get all the information about the extractions being done.  If the bit size
2729      if the same as the size of the underlying object, we aren't doing an
2730      extraction at all and so can do nothing.  */
2731   linner = get_inner_reference (lhs, &lbitsize, &lbitpos, &offset, &lmode,
2732                                 &lunsignedp, &lvolatilep, &alignment);
2733   if (linner == lhs || lbitsize == GET_MODE_BITSIZE (lmode) || lbitsize < 0
2734       || offset != 0)
2735     return 0;
2736
2737  if (!const_p)
2738    {
2739      /* If this is not a constant, we can only do something if bit positions,
2740         sizes, and signedness are the same.   */
2741      rinner = get_inner_reference (rhs, &rbitsize, &rbitpos, &offset, &rmode,
2742                                    &runsignedp, &rvolatilep, &alignment);
2743
2744      if (rinner == rhs || lbitpos != rbitpos || lbitsize != rbitsize
2745          || lunsignedp != runsignedp || offset != 0)
2746        return 0;
2747    }
2748
2749   /* See if we can find a mode to refer to this field.  We should be able to,
2750      but fail if we can't.  */
2751   lnmode = get_best_mode (lbitsize, lbitpos,
2752                           TYPE_ALIGN (TREE_TYPE (linner)), word_mode,
2753                           lvolatilep);
2754   if (lnmode == VOIDmode)
2755     return 0;
2756
2757   /* Set signed and unsigned types of the precision of this mode for the
2758      shifts below.  */
2759   signed_type = type_for_mode (lnmode, 0);
2760   unsigned_type = type_for_mode (lnmode, 1);
2761
2762   if (! const_p)
2763     {
2764       rnmode = get_best_mode (rbitsize, rbitpos,
2765                               TYPE_ALIGN (TREE_TYPE (rinner)), word_mode,
2766                               rvolatilep);
2767       if (rnmode == VOIDmode)
2768         return 0;
2769     }
2770
2771   /* Compute the bit position and size for the new reference and our offset
2772      within it. If the new reference is the same size as the original, we
2773      won't optimize anything, so return zero.  */
2774   lnbitsize = GET_MODE_BITSIZE (lnmode);
2775   lnbitpos = lbitpos & ~ (lnbitsize - 1);
2776   lbitpos -= lnbitpos;
2777   if (lnbitsize == lbitsize)
2778     return 0;
2779
2780   if (! const_p)
2781     {
2782       rnbitsize = GET_MODE_BITSIZE (rnmode);
2783       rnbitpos = rbitpos & ~ (rnbitsize - 1);
2784       rbitpos -= rnbitpos;
2785       if (rnbitsize == rbitsize)
2786         return 0;
2787     }
2788
2789   if (BYTES_BIG_ENDIAN)
2790     lbitpos = lnbitsize - lbitsize - lbitpos;
2791
2792   /* Make the mask to be used against the extracted field.  */
2793   mask = build_int_2 (~0, ~0);
2794   TREE_TYPE (mask) = unsigned_type;
2795   force_fit_type (mask, 0);
2796   mask = convert (unsigned_type, mask);
2797   mask = const_binop (LSHIFT_EXPR, mask, size_int (lnbitsize - lbitsize), 0);
2798   mask = const_binop (RSHIFT_EXPR, mask,
2799                       size_int (lnbitsize - lbitsize - lbitpos), 0);
2800
2801   if (! const_p)
2802     /* If not comparing with constant, just rework the comparison
2803        and return.  */
2804     return build (code, compare_type,
2805                   build (BIT_AND_EXPR, unsigned_type,
2806                          make_bit_field_ref (linner, unsigned_type,
2807                                              lnbitsize, lnbitpos, 1),
2808                          mask),
2809                   build (BIT_AND_EXPR, unsigned_type,
2810                          make_bit_field_ref (rinner, unsigned_type,
2811                                              rnbitsize, rnbitpos, 1),
2812                          mask));
2813
2814   /* Otherwise, we are handling the constant case. See if the constant is too
2815      big for the field.  Warn and return a tree of for 0 (false) if so.  We do
2816      this not only for its own sake, but to avoid having to test for this
2817      error case below.  If we didn't, we might generate wrong code.
2818
2819      For unsigned fields, the constant shifted right by the field length should
2820      be all zero.  For signed fields, the high-order bits should agree with
2821      the sign bit.  */
2822
2823   if (lunsignedp)
2824     {
2825       if (! integer_zerop (const_binop (RSHIFT_EXPR,
2826                                         convert (unsigned_type, rhs),
2827                                         size_int (lbitsize), 0)))
2828         {
2829           warning ("comparison is always %d due to width of bitfield",
2830                    code == NE_EXPR);
2831           return convert (compare_type,
2832                           (code == NE_EXPR
2833                            ? integer_one_node : integer_zero_node));
2834         }
2835     }
2836   else
2837     {
2838       tree tem = const_binop (RSHIFT_EXPR, convert (signed_type, rhs),
2839                               size_int (lbitsize - 1), 0);
2840       if (! integer_zerop (tem) && ! integer_all_onesp (tem))
2841         {
2842           warning ("comparison is always %d due to width of bitfield",
2843                    code == NE_EXPR);
2844           return convert (compare_type,
2845                           (code == NE_EXPR
2846                            ? integer_one_node : integer_zero_node));
2847         }
2848     }
2849
2850   /* Single-bit compares should always be against zero.  */
2851   if (lbitsize == 1 && ! integer_zerop (rhs))
2852     {
2853       code = code == EQ_EXPR ? NE_EXPR : EQ_EXPR;
2854       rhs = convert (type, integer_zero_node);
2855     }
2856
2857   /* Make a new bitfield reference, shift the constant over the
2858      appropriate number of bits and mask it with the computed mask
2859      (in case this was a signed field).  If we changed it, make a new one.  */
2860   lhs = make_bit_field_ref (linner, unsigned_type, lnbitsize, lnbitpos, 1);
2861   if (lvolatilep)
2862     {
2863       TREE_SIDE_EFFECTS (lhs) = 1;
2864       TREE_THIS_VOLATILE (lhs) = 1;
2865     }
2866
2867   rhs = fold (const_binop (BIT_AND_EXPR,
2868                            const_binop (LSHIFT_EXPR,
2869                                         convert (unsigned_type, rhs),
2870                                         size_int (lbitpos), 0),
2871                            mask, 0));
2872
2873   return build (code, compare_type,
2874                 build (BIT_AND_EXPR, unsigned_type, lhs, mask),
2875                 rhs);
2876 }
2877 \f
2878 /* Subroutine for fold_truthop: decode a field reference.
2879
2880    If EXP is a comparison reference, we return the innermost reference.
2881
2882    *PBITSIZE is set to the number of bits in the reference, *PBITPOS is
2883    set to the starting bit number.
2884
2885    If the innermost field can be completely contained in a mode-sized
2886    unit, *PMODE is set to that mode.  Otherwise, it is set to VOIDmode.
2887
2888    *PVOLATILEP is set to 1 if the any expression encountered is volatile;
2889    otherwise it is not changed.
2890
2891    *PUNSIGNEDP is set to the signedness of the field.
2892
2893    *PMASK is set to the mask used.  This is either contained in a
2894    BIT_AND_EXPR or derived from the width of the field.
2895
2896    *PAND_MASK is set to the mask found in a BIT_AND_EXPR, if any.
2897
2898    Return 0 if this is not a component reference or is one that we can't
2899    do anything with.  */
2900
2901 static tree
2902 decode_field_reference (exp, pbitsize, pbitpos, pmode, punsignedp,
2903                         pvolatilep, pmask, pand_mask)
2904      tree exp;
2905      int *pbitsize, *pbitpos;
2906      enum machine_mode *pmode;
2907      int *punsignedp, *pvolatilep;
2908      tree *pmask;
2909      tree *pand_mask;
2910 {
2911   tree and_mask = 0;
2912   tree mask, inner, offset;
2913   tree unsigned_type;
2914   int precision;
2915   int alignment;
2916
2917   /* All the optimizations using this function assume integer fields.
2918      There are problems with FP fields since the type_for_size call
2919      below can fail for, e.g., XFmode.  */
2920   if (! INTEGRAL_TYPE_P (TREE_TYPE (exp)))
2921     return 0;
2922
2923   STRIP_NOPS (exp);
2924
2925   if (TREE_CODE (exp) == BIT_AND_EXPR)
2926     {
2927       and_mask = TREE_OPERAND (exp, 1);
2928       exp = TREE_OPERAND (exp, 0);
2929       STRIP_NOPS (exp); STRIP_NOPS (and_mask);
2930       if (TREE_CODE (and_mask) != INTEGER_CST)
2931         return 0;
2932     }
2933
2934
2935   inner = get_inner_reference (exp, pbitsize, pbitpos, &offset, pmode,
2936                                punsignedp, pvolatilep, &alignment);
2937   if ((inner == exp && and_mask == 0)
2938       || *pbitsize < 0 || offset != 0)
2939     return 0;
2940
2941   /* Compute the mask to access the bitfield.  */
2942   unsigned_type = type_for_size (*pbitsize, 1);
2943   precision = TYPE_PRECISION (unsigned_type);
2944
2945   mask = build_int_2 (~0, ~0);
2946   TREE_TYPE (mask) = unsigned_type;
2947   force_fit_type (mask, 0);
2948   mask = const_binop (LSHIFT_EXPR, mask, size_int (precision - *pbitsize), 0);
2949   mask = const_binop (RSHIFT_EXPR, mask, size_int (precision - *pbitsize), 0);
2950
2951   /* Merge it with the mask we found in the BIT_AND_EXPR, if any.  */
2952   if (and_mask != 0)
2953     mask = fold (build (BIT_AND_EXPR, unsigned_type,
2954                         convert (unsigned_type, and_mask), mask));
2955
2956   *pmask = mask;
2957   *pand_mask = and_mask;
2958   return inner;
2959 }
2960
2961 /* Return non-zero if MASK represents a mask of SIZE ones in the low-order
2962    bit positions.  */
2963
2964 static int
2965 all_ones_mask_p (mask, size)
2966      tree mask;
2967      int size;
2968 {
2969   tree type = TREE_TYPE (mask);
2970   int precision = TYPE_PRECISION (type);
2971   tree tmask;
2972
2973   tmask = build_int_2 (~0, ~0);
2974   TREE_TYPE (tmask) = signed_type (type);
2975   force_fit_type (tmask, 0);
2976   return
2977     tree_int_cst_equal (mask,
2978                         const_binop (RSHIFT_EXPR,
2979                                      const_binop (LSHIFT_EXPR, tmask,
2980                                                   size_int (precision - size),
2981                                                   0),
2982                                      size_int (precision - size), 0));
2983 }
2984
2985 /* Subroutine for fold_truthop: determine if an operand is simple enough
2986    to be evaluated unconditionally.  */
2987
2988 static int
2989 simple_operand_p (exp)
2990      tree exp;
2991 {
2992   /* Strip any conversions that don't change the machine mode.  */
2993   while ((TREE_CODE (exp) == NOP_EXPR
2994           || TREE_CODE (exp) == CONVERT_EXPR)
2995          && (TYPE_MODE (TREE_TYPE (exp))
2996              == TYPE_MODE (TREE_TYPE (TREE_OPERAND (exp, 0)))))
2997     exp = TREE_OPERAND (exp, 0);
2998
2999   return (TREE_CODE_CLASS (TREE_CODE (exp)) == 'c'
3000           || (TREE_CODE_CLASS (TREE_CODE (exp)) == 'd'
3001               && ! TREE_ADDRESSABLE (exp)
3002               && ! TREE_THIS_VOLATILE (exp)
3003               && ! DECL_NONLOCAL (exp)
3004               /* Don't regard global variables as simple.  They may be
3005                  allocated in ways unknown to the compiler (shared memory,
3006                  #pragma weak, etc).  */
3007               && ! TREE_PUBLIC (exp)
3008               && ! DECL_EXTERNAL (exp)
3009               /* Loading a static variable is unduly expensive, but global
3010                  registers aren't expensive.  */
3011               && (! TREE_STATIC (exp) || DECL_REGISTER (exp))));
3012 }
3013 \f
3014 /* The following functions are subroutines to fold_range_test and allow it to
3015    try to change a logical combination of comparisons into a range test.
3016
3017    For example, both
3018         X == 2 && X == 3 && X == 4 && X == 5
3019    and
3020         X >= 2 && X <= 5
3021    are converted to
3022         (unsigned) (X - 2) <= 3
3023
3024    We describe each set of comparisons as being either inside or outside
3025    a range, using a variable named like IN_P, and then describe the
3026    range with a lower and upper bound.  If one of the bounds is omitted,
3027    it represents either the highest or lowest value of the type.
3028
3029    In the comments below, we represent a range by two numbers in brackets
3030    preceded by a "+" to designate being inside that range, or a "-" to
3031    designate being outside that range, so the condition can be inverted by
3032    flipping the prefix.  An omitted bound is represented by a "-".  For
3033    example, "- [-, 10]" means being outside the range starting at the lowest
3034    possible value and ending at 10, in other words, being greater than 10.
3035    The range "+ [-, -]" is always true and hence the range "- [-, -]" is
3036    always false.
3037
3038    We set up things so that the missing bounds are handled in a consistent
3039    manner so neither a missing bound nor "true" and "false" need to be
3040    handled using a special case.  */
3041
3042 /* Return the result of applying CODE to ARG0 and ARG1, but handle the case
3043    of ARG0 and/or ARG1 being omitted, meaning an unlimited range. UPPER0_P
3044    and UPPER1_P are nonzero if the respective argument is an upper bound
3045    and zero for a lower.  TYPE, if nonzero, is the type of the result; it
3046    must be specified for a comparison.  ARG1 will be converted to ARG0's
3047    type if both are specified.  */
3048
3049 static tree
3050 range_binop (code, type, arg0, upper0_p, arg1, upper1_p)
3051      enum tree_code code;
3052      tree type;
3053      tree arg0, arg1;
3054      int upper0_p, upper1_p;
3055 {
3056   tree tem;
3057   int result;
3058   int sgn0, sgn1;
3059
3060   /* If neither arg represents infinity, do the normal operation.
3061      Else, if not a comparison, return infinity.  Else handle the special
3062      comparison rules. Note that most of the cases below won't occur, but
3063      are handled for consistency.  */
3064
3065   if (arg0 != 0 && arg1 != 0)
3066     {
3067       tem = fold (build (code, type != 0 ? type : TREE_TYPE (arg0),
3068                          arg0, convert (TREE_TYPE (arg0), arg1)));
3069       STRIP_NOPS (tem);
3070       return TREE_CODE (tem) == INTEGER_CST ? tem : 0;
3071     }
3072
3073   if (TREE_CODE_CLASS (code) != '<')
3074     return 0;
3075
3076   /* Set SGN[01] to -1 if ARG[01] is a lower bound, 1 for upper, and 0
3077      for neither.  In real maths, we cannot assume open ended ranges are
3078      the same. But, this is computer arithmetic, where numbers are finite.
3079      We can therefore make the transformation of any unbounded range with
3080      the value Z, Z being greater than any representable number. This permits
3081      us to treat unbounded ranges as equal. */
3082   sgn0 = arg0 != 0 ? 0 : (upper0_p ? 1 : -1);
3083   sgn1 = arg1 != 0 ? 0 : (upper1_p ? 1 : -1);
3084   switch (code)
3085     {
3086     case EQ_EXPR:
3087       result = sgn0 == sgn1;
3088       break;
3089     case NE_EXPR:
3090       result = sgn0 != sgn1;
3091       break;
3092     case LT_EXPR:
3093       result = sgn0 < sgn1;
3094       break;
3095     case LE_EXPR:
3096       result = sgn0 <= sgn1;
3097       break;
3098     case GT_EXPR:
3099       result = sgn0 > sgn1;
3100       break;
3101     case GE_EXPR:
3102       result = sgn0 >= sgn1;
3103       break;
3104     default:
3105       abort ();
3106     }
3107
3108   return convert (type, result ? integer_one_node : integer_zero_node);
3109 }
3110 \f
3111 /* Given EXP, a logical expression, set the range it is testing into
3112    variables denoted by PIN_P, PLOW, and PHIGH.  Return the expression
3113    actually being tested.  *PLOW and *PHIGH will have be made the same type
3114    as the returned expression.  If EXP is not a comparison, we will most
3115    likely not be returning a useful value and range.  */
3116
3117 static tree
3118 make_range (exp, pin_p, plow, phigh)
3119      tree exp;
3120      int *pin_p;
3121      tree *plow, *phigh;
3122 {
3123   enum tree_code code;
3124   tree arg0 = NULL_TREE, arg1 = NULL_TREE, type = NULL_TREE;
3125   tree orig_type = NULL_TREE;
3126   int in_p, n_in_p;
3127   tree low, high, n_low, n_high;
3128
3129   /* Start with simply saying "EXP != 0" and then look at the code of EXP
3130      and see if we can refine the range.  Some of the cases below may not
3131      happen, but it doesn't seem worth worrying about this.  We "continue"
3132      the outer loop when we've changed something; otherwise we "break"
3133      the switch, which will "break" the while.  */
3134
3135   in_p = 0, low = high = convert (TREE_TYPE (exp), integer_zero_node);
3136
3137   while (1)
3138     {
3139       code = TREE_CODE (exp);
3140
3141       if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)))
3142         {
3143           arg0 = TREE_OPERAND (exp, 0);
3144           if (TREE_CODE_CLASS (code) == '<'
3145               || TREE_CODE_CLASS (code) == '1'
3146               || TREE_CODE_CLASS (code) == '2')
3147             type = TREE_TYPE (arg0);
3148           if (TREE_CODE_CLASS (code) == '2'
3149               || TREE_CODE_CLASS (code) == '<'
3150               || (TREE_CODE_CLASS (code) == 'e'
3151                   && tree_code_length[(int) code] > 1))
3152             arg1 = TREE_OPERAND (exp, 1);
3153         }
3154
3155       /* Set ORIG_TYPE as soon as TYPE is non-null so that we do not
3156          lose a cast by accident.  */
3157       if (type != NULL_TREE && orig_type == NULL_TREE)
3158         orig_type = type;
3159
3160       switch (code)
3161         {
3162         case TRUTH_NOT_EXPR:
3163           in_p = ! in_p, exp = arg0;
3164           continue;
3165
3166         case EQ_EXPR: case NE_EXPR:
3167         case LT_EXPR: case LE_EXPR: case GE_EXPR: case GT_EXPR:
3168           /* We can only do something if the range is testing for zero
3169              and if the second operand is an integer constant.  Note that
3170              saying something is "in" the range we make is done by
3171              complementing IN_P since it will set in the initial case of
3172              being not equal to zero; "out" is leaving it alone.  */
3173           if (low == 0 || high == 0
3174               || ! integer_zerop (low) || ! integer_zerop (high)
3175               || TREE_CODE (arg1) != INTEGER_CST)
3176             break;
3177
3178           switch (code)
3179             {
3180             case NE_EXPR:  /* - [c, c]  */
3181               low = high = arg1;
3182               break;
3183             case EQ_EXPR:  /* + [c, c]  */
3184               in_p = ! in_p, low = high = arg1;
3185               break;
3186             case GT_EXPR:  /* - [-, c] */
3187               low = 0, high = arg1;
3188               break;
3189             case GE_EXPR:  /* + [c, -] */
3190               in_p = ! in_p, low = arg1, high = 0;
3191               break;
3192             case LT_EXPR:  /* - [c, -] */
3193               low = arg1, high = 0;
3194               break;
3195             case LE_EXPR:  /* + [-, c] */
3196               in_p = ! in_p, low = 0, high = arg1;
3197               break;
3198             default:
3199               abort ();
3200             }
3201
3202           exp = arg0;
3203
3204           /* If this is an unsigned comparison, we also know that EXP is
3205              greater than or equal to zero.  We base the range tests we make
3206              on that fact, so we record it here so we can parse existing
3207              range tests.  */
3208           if (TREE_UNSIGNED (type) && (low == 0 || high == 0))
3209             {
3210               if (! merge_ranges (&n_in_p, &n_low, &n_high, in_p, low, high,
3211                                   1, convert (type, integer_zero_node),
3212                                   NULL_TREE))
3213                 break;
3214
3215               in_p = n_in_p, low = n_low, high = n_high;
3216
3217               /* If the high bound is missing, reverse the range so it
3218                  goes from zero to the low bound minus 1.  */
3219               if (high == 0)
3220                 {
3221                   in_p = ! in_p;
3222                   high = range_binop (MINUS_EXPR, NULL_TREE, low, 0,
3223                                       integer_one_node, 0);
3224                   low = convert (type, integer_zero_node);
3225                 }
3226             }
3227           continue;
3228
3229         case NEGATE_EXPR:
3230           /* (-x) IN [a,b] -> x in [-b, -a]  */
3231           n_low = range_binop (MINUS_EXPR, type,
3232                                convert (type, integer_zero_node), 0, high, 1);
3233           n_high = range_binop (MINUS_EXPR, type,
3234                                 convert (type, integer_zero_node), 0, low, 0);
3235           low = n_low, high = n_high;
3236           exp = arg0;
3237           continue;
3238
3239         case BIT_NOT_EXPR:
3240           /* ~ X -> -X - 1  */
3241           exp = build (MINUS_EXPR, type, build1 (NEGATE_EXPR, type, arg0),
3242                        convert (type, integer_one_node));
3243           continue;
3244
3245         case PLUS_EXPR:  case MINUS_EXPR:
3246           if (TREE_CODE (arg1) != INTEGER_CST)
3247             break;
3248
3249           /* If EXP is signed, any overflow in the computation is undefined,
3250              so we don't worry about it so long as our computations on
3251              the bounds don't overflow.  For unsigned, overflow is defined
3252              and this is exactly the right thing.  */
3253           n_low = range_binop (code == MINUS_EXPR ? PLUS_EXPR : MINUS_EXPR,
3254                                type, low, 0, arg1, 0);
3255           n_high = range_binop (code == MINUS_EXPR ? PLUS_EXPR : MINUS_EXPR,
3256                                 type, high, 1, arg1, 0);
3257           if ((n_low != 0 && TREE_OVERFLOW (n_low))
3258               || (n_high != 0 && TREE_OVERFLOW (n_high)))
3259             break;
3260
3261           /* Check for an unsigned range which has wrapped around the maximum
3262              value thus making n_high < n_low, and normalize it.  */
3263           if (n_low && n_high && tree_int_cst_lt (n_high, n_low))
3264             {
3265               low = range_binop (PLUS_EXPR, type, n_high, 0,
3266                                  integer_one_node, 0);
3267               high = range_binop (MINUS_EXPR, type, n_low, 0,
3268                                  integer_one_node, 0);
3269               in_p = ! in_p;
3270             }
3271           else
3272             low = n_low, high = n_high;
3273
3274           exp = arg0;
3275           continue;
3276
3277         case NOP_EXPR:  case NON_LVALUE_EXPR:  case CONVERT_EXPR:
3278           if (TYPE_PRECISION (type) > TYPE_PRECISION (orig_type))
3279             break;
3280
3281           if (! INTEGRAL_TYPE_P (type)
3282               || (low != 0 && ! int_fits_type_p (low, type))
3283               || (high != 0 && ! int_fits_type_p (high, type)))
3284             break;
3285
3286           n_low = low, n_high = high;
3287
3288           if (n_low != 0)
3289             n_low = convert (type, n_low);
3290
3291           if (n_high != 0)
3292             n_high = convert (type, n_high);
3293
3294           /* If we're converting from an unsigned to a signed type,
3295              we will be doing the comparison as unsigned.  The tests above
3296              have already verified that LOW and HIGH are both positive.
3297
3298              So we have to make sure that the original unsigned value will
3299              be interpreted as positive.  */
3300           if (TREE_UNSIGNED (type) && ! TREE_UNSIGNED (TREE_TYPE (exp)))
3301             {
3302               tree equiv_type = type_for_mode (TYPE_MODE (type), 1);
3303               tree high_positive;
3304
3305               /* A range without an upper bound is, naturally, unbounded.
3306                  Since convert would have cropped a very large value, use
3307                   the max value for the destination type.  */
3308
3309               high_positive = TYPE_MAX_VALUE (equiv_type);
3310               if (!high_positive)
3311                 {
3312                   high_positive = TYPE_MAX_VALUE (type);
3313                   if (!high_positive)
3314                     abort();
3315                 }
3316               high_positive = fold (build (RSHIFT_EXPR, type,
3317                                            convert (type, high_positive),
3318                                            convert (type, integer_one_node)));
3319
3320               /* If the low bound is specified, "and" the range with the
3321                  range for which the original unsigned value will be
3322                  positive.  */
3323               if (low != 0)
3324                 {
3325                   if (! merge_ranges (&n_in_p, &n_low, &n_high,
3326                                       1, n_low, n_high,
3327                                       1, convert (type, integer_zero_node),
3328                                       high_positive))
3329                     break;
3330
3331                   in_p = (n_in_p == in_p);
3332                 }
3333               else
3334                 {
3335                   /* Otherwise, "or" the range with the range of the input
3336                      that will be interpreted as negative.  */
3337                   if (! merge_ranges (&n_in_p, &n_low, &n_high,
3338                                       0, n_low, n_high,
3339                                       1, convert (type, integer_zero_node),
3340                                       high_positive))
3341                     break;
3342
3343                   in_p = (in_p != n_in_p);
3344                 }
3345             }
3346
3347           exp = arg0;
3348           low = n_low, high = n_high;
3349           continue;
3350
3351         default:
3352           break;
3353         }
3354
3355       break;
3356     }
3357
3358   /* If EXP is a constant, we can evaluate whether this is true or false.  */
3359   if (TREE_CODE (exp) == INTEGER_CST)
3360     {
3361       in_p = in_p == (integer_onep (range_binop (GE_EXPR, integer_type_node,
3362                                                  exp, 0, low, 0))
3363                       && integer_onep (range_binop (LE_EXPR, integer_type_node,
3364                                                     exp, 1, high, 1)));
3365       low = high = 0;
3366       exp = 0;
3367     }
3368
3369   *pin_p = in_p, *plow = low, *phigh = high;
3370   return exp;
3371 }
3372 \f
3373 /* Given a range, LOW, HIGH, and IN_P, an expression, EXP, and a result
3374    type, TYPE, return an expression to test if EXP is in (or out of, depending
3375    on IN_P) the range.  */
3376
3377 static tree
3378 build_range_check (type, exp, in_p, low, high)
3379      tree type;
3380      tree exp;
3381      int in_p;
3382      tree low, high;
3383 {
3384   tree etype = TREE_TYPE (exp);
3385   tree utype, value;
3386
3387   if (! in_p
3388       && (0 != (value = build_range_check (type, exp, 1, low, high))))
3389     return invert_truthvalue (value);
3390
3391   else if (low == 0 && high == 0)
3392     return convert (type, integer_one_node);
3393
3394   else if (low == 0)
3395     return fold (build (LE_EXPR, type, exp, high));
3396
3397   else if (high == 0)
3398     return fold (build (GE_EXPR, type, exp, low));
3399
3400   else if (operand_equal_p (low, high, 0))
3401     return fold (build (EQ_EXPR, type, exp, low));
3402
3403   else if (TREE_UNSIGNED (etype) && integer_zerop (low))
3404     return build_range_check (type, exp, 1, 0, high);
3405
3406   else if (integer_zerop (low))
3407     {
3408       utype = unsigned_type (etype);
3409       return build_range_check (type, convert (utype, exp), 1, 0,
3410                                 convert (utype, high));
3411     }
3412
3413   else if (0 != (value = const_binop (MINUS_EXPR, high, low, 0))
3414            && ! TREE_OVERFLOW (value))
3415     return build_range_check (type,
3416                               fold (build (MINUS_EXPR, etype, exp, low)),
3417                               1, convert (etype, integer_zero_node), value);
3418   else
3419     return 0;
3420 }
3421 \f
3422 /* Given two ranges, see if we can merge them into one.  Return 1 if we
3423    can, 0 if we can't.  Set the output range into the specified parameters.  */
3424
3425 static int
3426 merge_ranges (pin_p, plow, phigh, in0_p, low0, high0, in1_p, low1, high1)
3427      int *pin_p;
3428      tree *plow, *phigh;
3429      int in0_p, in1_p;
3430      tree low0, high0, low1, high1;
3431 {
3432   int no_overlap;
3433   int subset;
3434   int temp;
3435   tree tem;
3436   int in_p;
3437   tree low, high;
3438   int lowequal = ((low0 == 0 && low1 == 0)
3439                   || integer_onep (range_binop (EQ_EXPR, integer_type_node,
3440                                                 low0, 0, low1, 0)));
3441   int highequal = ((high0 == 0 && high1 == 0)
3442                    || integer_onep (range_binop (EQ_EXPR, integer_type_node,
3443                                                  high0, 1, high1, 1)));
3444
3445   /* Make range 0 be the range that starts first, or ends last if they
3446      start at the same value.  Swap them if it isn't.  */
3447   if (integer_onep (range_binop (GT_EXPR, integer_type_node,
3448                                  low0, 0, low1, 0))
3449       || (lowequal
3450           && integer_onep (range_binop (GT_EXPR, integer_type_node,
3451                                         high1, 1, high0, 1))))
3452     {
3453       temp = in0_p, in0_p = in1_p, in1_p = temp;
3454       tem = low0, low0 = low1, low1 = tem;
3455       tem = high0, high0 = high1, high1 = tem;
3456     }
3457
3458   /* Now flag two cases, whether the ranges are disjoint or whether the
3459      second range is totally subsumed in the first.  Note that the tests
3460      below are simplified by the ones above.  */
3461   no_overlap = integer_onep (range_binop (LT_EXPR, integer_type_node,
3462                                           high0, 1, low1, 0));
3463   subset = integer_onep (range_binop (LE_EXPR, integer_type_node,
3464                                       high1, 1, high0, 1));
3465
3466   /* We now have four cases, depending on whether we are including or
3467      excluding the two ranges.  */
3468   if (in0_p && in1_p)
3469     {
3470       /* If they don't overlap, the result is false.  If the second range
3471          is a subset it is the result.  Otherwise, the range is from the start
3472          of the second to the end of the first.  */
3473       if (no_overlap)
3474         in_p = 0, low = high = 0;
3475       else if (subset)
3476         in_p = 1, low = low1, high = high1;
3477       else
3478         in_p = 1, low = low1, high = high0;
3479     }
3480
3481   else if (in0_p && ! in1_p)
3482     {
3483       /* If they don't overlap, the result is the first range.  If they are
3484          equal, the result is false.  If the second range is a subset of the
3485          first, and the ranges begin at the same place, we go from just after
3486          the end of the first range to the end of the second.  If the second
3487          range is not a subset of the first, or if it is a subset and both
3488          ranges end at the same place, the range starts at the start of the
3489          first range and ends just before the second range.
3490          Otherwise, we can't describe this as a single range.  */
3491       if (no_overlap)
3492         in_p = 1, low = low0, high = high0;
3493       else if (lowequal && highequal)
3494         in_p = 0, low = high = 0;
3495       else if (subset && lowequal)
3496         {
3497           in_p = 1, high = high0;
3498           low = range_binop (PLUS_EXPR, NULL_TREE, high1, 0,
3499                              integer_one_node, 0);
3500         }
3501       else if (! subset || highequal)
3502         {
3503           in_p = 1, low = low0;
3504           high = range_binop (MINUS_EXPR, NULL_TREE, low1, 0,
3505                               integer_one_node, 0);
3506         }
3507       else
3508         return 0;
3509     }
3510
3511   else if (! in0_p && in1_p)
3512     {
3513       /* If they don't overlap, the result is the second range.  If the second
3514          is a subset of the first, the result is false.  Otherwise,
3515          the range starts just after the first range and ends at the
3516          end of the second.  */
3517       if (no_overlap)
3518         in_p = 1, low = low1, high = high1;
3519       else if (subset)
3520         in_p = 0, low = high = 0;
3521       else
3522         {
3523           in_p = 1, high = high1;
3524           low = range_binop (PLUS_EXPR, NULL_TREE, high0, 1,
3525                              integer_one_node, 0);
3526         }
3527     }
3528
3529   else
3530     {
3531       /* The case where we are excluding both ranges.  Here the complex case
3532          is if they don't overlap.  In that case, the only time we have a
3533          range is if they are adjacent.  If the second is a subset of the
3534          first, the result is the first.  Otherwise, the range to exclude
3535          starts at the beginning of the first range and ends at the end of the
3536          second.  */
3537       if (no_overlap)
3538         {
3539           if (integer_onep (range_binop (EQ_EXPR, integer_type_node,
3540                                          range_binop (PLUS_EXPR, NULL_TREE,
3541                                                       high0, 1,
3542                                                       integer_one_node, 1),
3543                                          1, low1, 0)))
3544             in_p = 0, low = low0, high = high1;
3545           else
3546             return 0;
3547         }
3548       else if (subset)
3549         in_p = 0, low = low0, high = high0;
3550       else
3551         in_p = 0, low = low0, high = high1;
3552     }
3553
3554   *pin_p = in_p, *plow = low, *phigh = high;
3555   return 1;
3556 }
3557 \f
3558 /* EXP is some logical combination of boolean tests.  See if we can
3559    merge it into some range test.  Return the new tree if so.  */
3560
3561 static tree
3562 fold_range_test (exp)
3563      tree exp;
3564 {
3565   int or_op = (TREE_CODE (exp) == TRUTH_ORIF_EXPR
3566                || TREE_CODE (exp) == TRUTH_OR_EXPR);
3567   int in0_p, in1_p, in_p;
3568   tree low0, low1, low, high0, high1, high;
3569   tree lhs = make_range (TREE_OPERAND (exp, 0), &in0_p, &low0, &high0);
3570   tree rhs = make_range (TREE_OPERAND (exp, 1), &in1_p, &low1, &high1);
3571   tree tem;
3572
3573   /* Fail if anything is volatile.  */
3574   if (TREE_SIDE_EFFECTS (lhs) || TREE_SIDE_EFFECTS (rhs))
3575     return 0;
3576
3577   /* If this is an OR operation, invert both sides; we will invert
3578      again at the end.  */
3579   if (or_op)
3580     in0_p = ! in0_p, in1_p = ! in1_p;
3581
3582   /* If both expressions are the same, if we can merge the ranges, and we
3583      can build the range test, return it or it inverted.  If one of the
3584      ranges is always true or always false, consider it to be the same
3585      expression as the other.  */
3586   if ((lhs == 0 || rhs == 0 || operand_equal_p (lhs, rhs, 0))
3587       && merge_ranges (&in_p, &low, &high, in0_p, low0, high0,
3588                        in1_p, low1, high1)
3589       && 0 != (tem = (build_range_check (TREE_TYPE (exp),
3590                                          lhs != 0 ? lhs
3591                                          : rhs != 0 ? rhs : integer_zero_node,
3592                                          in_p, low, high))))
3593     return or_op ? invert_truthvalue (tem) : tem;
3594
3595   /* On machines where the branch cost is expensive, if this is a
3596      short-circuited branch and the underlying object on both sides
3597      is the same, make a non-short-circuit operation.  */
3598   else if (BRANCH_COST >= 2
3599            && (TREE_CODE (exp) == TRUTH_ANDIF_EXPR
3600                || TREE_CODE (exp) == TRUTH_ORIF_EXPR)
3601            && operand_equal_p (lhs, rhs, 0))
3602     {
3603       /* If simple enough, just rewrite.  Otherwise, make a SAVE_EXPR
3604          unless we are at top level or LHS contains a PLACEHOLDER_EXPR, in
3605          which cases we can't do this.  */
3606       if (simple_operand_p (lhs))
3607         return build (TREE_CODE (exp) == TRUTH_ANDIF_EXPR
3608                       ? TRUTH_AND_EXPR : TRUTH_OR_EXPR,
3609                       TREE_TYPE (exp), TREE_OPERAND (exp, 0),
3610                       TREE_OPERAND (exp, 1));
3611
3612       else if (global_bindings_p () == 0
3613                && ! contains_placeholder_p (lhs))
3614         {
3615           tree common = save_expr (lhs);
3616
3617           if (0 != (lhs = build_range_check (TREE_TYPE (exp), common,
3618                                              or_op ? ! in0_p : in0_p,
3619                                              low0, high0))
3620               && (0 != (rhs = build_range_check (TREE_TYPE (exp), common,
3621                                                  or_op ? ! in1_p : in1_p,
3622                                                  low1, high1))))
3623             return build (TREE_CODE (exp) == TRUTH_ANDIF_EXPR
3624                           ? TRUTH_AND_EXPR : TRUTH_OR_EXPR,
3625                           TREE_TYPE (exp), lhs, rhs);
3626         }
3627     }
3628
3629   return 0;
3630 }
3631 \f
3632 /* Subroutine for fold_truthop: C is an INTEGER_CST interpreted as a P
3633    bit value.  Arrange things so the extra bits will be set to zero if and
3634    only if C is signed-extended to its full width.  If MASK is nonzero,
3635    it is an INTEGER_CST that should be AND'ed with the extra bits.  */
3636
3637 static tree
3638 unextend (c, p, unsignedp, mask)
3639      tree c;
3640      int p;
3641      int unsignedp;
3642      tree mask;
3643 {
3644   tree type = TREE_TYPE (c);
3645   int modesize = GET_MODE_BITSIZE (TYPE_MODE (type));
3646   tree temp;
3647
3648   if (p == modesize || unsignedp)
3649     return c;
3650
3651   /* We work by getting just the sign bit into the low-order bit, then
3652      into the high-order bit, then sign-extend.  We then XOR that value
3653      with C.  */
3654   temp = const_binop (RSHIFT_EXPR, c, size_int (p - 1), 0);
3655   temp = const_binop (BIT_AND_EXPR, temp, size_int (1), 0);
3656
3657   /* We must use a signed type in order to get an arithmetic right shift.
3658      However, we must also avoid introducing accidental overflows, so that
3659      a subsequent call to integer_zerop will work.  Hence we must
3660      do the type conversion here.  At this point, the constant is either
3661      zero or one, and the conversion to a signed type can never overflow.
3662      We could get an overflow if this conversion is done anywhere else.  */
3663   if (TREE_UNSIGNED (type))
3664     temp = convert (signed_type (type), temp);
3665
3666   temp = const_binop (LSHIFT_EXPR, temp, size_int (modesize - 1), 0);
3667   temp = const_binop (RSHIFT_EXPR, temp, size_int (modesize - p - 1), 0);
3668   if (mask != 0)
3669     temp = const_binop (BIT_AND_EXPR, temp, convert (TREE_TYPE (c), mask), 0);
3670   /* If necessary, convert the type back to match the type of C.  */
3671   if (TREE_UNSIGNED (type))
3672     temp = convert (type, temp);
3673
3674   return convert (type, const_binop (BIT_XOR_EXPR, c, temp, 0));
3675 }
3676 \f
3677 /* Find ways of folding logical expressions of LHS and RHS:
3678    Try to merge two comparisons to the same innermost item.
3679    Look for range tests like "ch >= '0' && ch <= '9'".
3680    Look for combinations of simple terms on machines with expensive branches
3681    and evaluate the RHS unconditionally.
3682
3683    For example, if we have p->a == 2 && p->b == 4 and we can make an
3684    object large enough to span both A and B, we can do this with a comparison
3685    against the object ANDed with the a mask.
3686
3687    If we have p->a == q->a && p->b == q->b, we may be able to use bit masking
3688    operations to do this with one comparison.
3689
3690    We check for both normal comparisons and the BIT_AND_EXPRs made this by
3691    function and the one above.
3692
3693    CODE is the logical operation being done.  It can be TRUTH_ANDIF_EXPR,
3694    TRUTH_AND_EXPR, TRUTH_ORIF_EXPR, or TRUTH_OR_EXPR.
3695
3696    TRUTH_TYPE is the type of the logical operand and LHS and RHS are its
3697    two operands.
3698
3699    We return the simplified tree or 0 if no optimization is possible.  */
3700
3701 static tree
3702 fold_truthop (code, truth_type, lhs, rhs)
3703      enum tree_code code;
3704      tree truth_type, lhs, rhs;
3705 {
3706   /* If this is the "or" of two comparisons, we can do something if we
3707      the comparisons are NE_EXPR.  If this is the "and", we can do something
3708      if the comparisons are EQ_EXPR.  I.e.,
3709         (a->b == 2 && a->c == 4) can become (a->new == NEW).
3710
3711      WANTED_CODE is this operation code.  For single bit fields, we can
3712      convert EQ_EXPR to NE_EXPR so we need not reject the "wrong"
3713      comparison for one-bit fields.  */
3714
3715   enum tree_code wanted_code;
3716   enum tree_code lcode, rcode;
3717   tree ll_arg, lr_arg, rl_arg, rr_arg;
3718   tree ll_inner, lr_inner, rl_inner, rr_inner;
3719   int ll_bitsize, ll_bitpos, lr_bitsize, lr_bitpos;
3720   int rl_bitsize, rl_bitpos, rr_bitsize, rr_bitpos;
3721   int xll_bitpos, xlr_bitpos, xrl_bitpos, xrr_bitpos;
3722   int lnbitsize, lnbitpos, rnbitsize, rnbitpos;
3723   int ll_unsignedp, lr_unsignedp, rl_unsignedp, rr_unsignedp;
3724   enum machine_mode ll_mode, lr_mode, rl_mode, rr_mode;
3725   enum machine_mode lnmode, rnmode;
3726   tree ll_mask, lr_mask, rl_mask, rr_mask;
3727   tree ll_and_mask, lr_and_mask, rl_and_mask, rr_and_mask;
3728   tree l_const, r_const;
3729   tree lntype, rntype, result;
3730   int first_bit, end_bit;
3731   int volatilep;
3732
3733   /* Start by getting the comparison codes.  Fail if anything is volatile.
3734      If one operand is a BIT_AND_EXPR with the constant one, treat it as if
3735      it were surrounded with a NE_EXPR.  */
3736
3737   if (TREE_SIDE_EFFECTS (lhs) || TREE_SIDE_EFFECTS (rhs))
3738     return 0;
3739
3740   lcode = TREE_CODE (lhs);
3741   rcode = TREE_CODE (rhs);
3742
3743   if (lcode == BIT_AND_EXPR && integer_onep (TREE_OPERAND (lhs, 1)))
3744     lcode = NE_EXPR, lhs = build (NE_EXPR, truth_type, lhs, integer_zero_node);
3745
3746   if (rcode == BIT_AND_EXPR && integer_onep (TREE_OPERAND (rhs, 1)))
3747     rcode = NE_EXPR, rhs = build (NE_EXPR, truth_type, rhs, integer_zero_node);
3748
3749   if (TREE_CODE_CLASS (lcode) != '<' || TREE_CODE_CLASS (rcode) != '<')
3750     return 0;
3751
3752   code = ((code == TRUTH_AND_EXPR || code == TRUTH_ANDIF_EXPR)
3753           ? TRUTH_AND_EXPR : TRUTH_OR_EXPR);
3754
3755   ll_arg = TREE_OPERAND (lhs, 0);
3756   lr_arg = TREE_OPERAND (lhs, 1);
3757   rl_arg = TREE_OPERAND (rhs, 0);
3758   rr_arg = TREE_OPERAND (rhs, 1);
3759
3760   /* If the RHS can be evaluated unconditionally and its operands are
3761      simple, it wins to evaluate the RHS unconditionally on machines
3762      with expensive branches.  In this case, this isn't a comparison
3763      that can be merged.  */
3764
3765   /* @@ I'm not sure it wins on the m88110 to do this if the comparisons
3766      are with zero (tmw).  */
3767
3768   if (BRANCH_COST >= 2
3769       && INTEGRAL_TYPE_P (TREE_TYPE (rhs))
3770       && simple_operand_p (rl_arg)
3771       && simple_operand_p (rr_arg))
3772     return build (code, truth_type, lhs, rhs);
3773
3774   /* See if the comparisons can be merged.  Then get all the parameters for
3775      each side.  */
3776
3777   if ((lcode != EQ_EXPR && lcode != NE_EXPR)
3778       || (rcode != EQ_EXPR && rcode != NE_EXPR))
3779     return 0;
3780
3781   volatilep = 0;
3782   ll_inner = decode_field_reference (ll_arg,
3783                                      &ll_bitsize, &ll_bitpos, &ll_mode,
3784                                      &ll_unsignedp, &volatilep, &ll_mask,
3785                                      &ll_and_mask);
3786   lr_inner = decode_field_reference (lr_arg,
3787                                      &lr_bitsize, &lr_bitpos, &lr_mode,
3788                                      &lr_unsignedp, &volatilep, &lr_mask,
3789                                      &lr_and_mask);
3790   rl_inner = decode_field_reference (rl_arg,
3791                                      &rl_bitsize, &rl_bitpos, &rl_mode,
3792                                      &rl_unsignedp, &volatilep, &rl_mask,
3793                                      &rl_and_mask);
3794   rr_inner = decode_field_reference (rr_arg,
3795                                      &rr_bitsize, &rr_bitpos, &rr_mode,
3796                                      &rr_unsignedp, &volatilep, &rr_mask,
3797                                      &rr_and_mask);
3798
3799   /* It must be true that the inner operation on the lhs of each
3800      comparison must be the same if we are to be able to do anything.
3801      Then see if we have constants.  If not, the same must be true for
3802      the rhs's.  */
3803   if (volatilep || ll_inner == 0 || rl_inner == 0
3804       || ! operand_equal_p (ll_inner, rl_inner, 0))
3805     return 0;
3806
3807   if (TREE_CODE (lr_arg) == INTEGER_CST
3808       && TREE_CODE (rr_arg) == INTEGER_CST)
3809     l_const = lr_arg, r_const = rr_arg;
3810   else if (lr_inner == 0 || rr_inner == 0
3811            || ! operand_equal_p (lr_inner, rr_inner, 0))
3812     return 0;
3813   else
3814     l_const = r_const = 0;
3815
3816   /* If either comparison code is not correct for our logical operation,
3817      fail.  However, we can convert a one-bit comparison against zero into
3818      the opposite comparison against that bit being set in the field.  */
3819
3820   wanted_code = (code == TRUTH_AND_EXPR ? EQ_EXPR : NE_EXPR);
3821   if (lcode != wanted_code)
3822     {
3823       if (l_const && integer_zerop (l_const) && integer_pow2p (ll_mask))
3824         {
3825           /* Make the left operand unsigned, since we are only interested
3826              in the value of one bit.  Otherwise we are doing the wrong
3827              thing below.  */
3828           ll_unsignedp = 1;
3829           l_const = ll_mask;
3830         }
3831       else
3832         return 0;
3833     }
3834
3835   /* This is analogous to the code for l_const above.  */
3836   if (rcode != wanted_code)
3837     {
3838       if (r_const && integer_zerop (r_const) && integer_pow2p (rl_mask))
3839         {
3840           rl_unsignedp = 1;
3841           r_const = rl_mask;
3842         }
3843       else
3844         return 0;
3845     }
3846
3847   /* See if we can find a mode that contains both fields being compared on
3848      the left.  If we can't, fail.  Otherwise, update all constants and masks
3849      to be relative to a field of that size.  */
3850   first_bit = MIN (ll_bitpos, rl_bitpos);
3851   end_bit = MAX (ll_bitpos + ll_bitsize, rl_bitpos + rl_bitsize);
3852   lnmode = get_best_mode (end_bit - first_bit, first_bit,
3853                           TYPE_ALIGN (TREE_TYPE (ll_inner)), word_mode,
3854                           volatilep);
3855   if (lnmode == VOIDmode)
3856     return 0;
3857
3858   lnbitsize = GET_MODE_BITSIZE (lnmode);
3859   lnbitpos = first_bit & ~ (lnbitsize - 1);
3860   lntype = type_for_size (lnbitsize, 1);
3861   xll_bitpos = ll_bitpos - lnbitpos, xrl_bitpos = rl_bitpos - lnbitpos;
3862
3863   if (BYTES_BIG_ENDIAN)
3864     {
3865       xll_bitpos = lnbitsize - xll_bitpos - ll_bitsize;
3866       xrl_bitpos = lnbitsize - xrl_bitpos - rl_bitsize;
3867     }
3868
3869   ll_mask = const_binop (LSHIFT_EXPR, convert (lntype, ll_mask),
3870                          size_int (xll_bitpos), 0);
3871   rl_mask = const_binop (LSHIFT_EXPR, convert (lntype, rl_mask),
3872                          size_int (xrl_bitpos), 0);
3873
3874   if (l_const)
3875     {
3876       l_const = convert (lntype, l_const);
3877       l_const = unextend (l_const,  ll_bitsize, ll_unsignedp, ll_and_mask);
3878       l_const = const_binop (LSHIFT_EXPR, l_const, size_int (xll_bitpos), 0);
3879       if (! integer_zerop (const_binop (BIT_AND_EXPR, l_const,
3880                                         fold (build1 (BIT_NOT_EXPR,
3881                                                       lntype, ll_mask)),
3882                                         0)))
3883         {
3884           warning ("comparison is always %d", wanted_code == NE_EXPR);
3885
3886           return convert (truth_type,
3887                           wanted_code == NE_EXPR
3888                           ? integer_one_node : integer_zero_node);
3889         }
3890     }
3891   if (r_const)
3892     {
3893       r_const = convert (lntype, r_const);
3894       r_const = unextend (r_const, rl_bitsize, rl_unsignedp, rl_and_mask);
3895       r_const = const_binop (LSHIFT_EXPR, r_const, size_int (xrl_bitpos), 0);
3896       if (! integer_zerop (const_binop (BIT_AND_EXPR, r_const,
3897                                         fold (build1 (BIT_NOT_EXPR,
3898                                                       lntype, rl_mask)),
3899                                         0)))
3900         {
3901           warning ("comparison is always %d", wanted_code == NE_EXPR);
3902
3903           return convert (truth_type,
3904                           wanted_code == NE_EXPR
3905                           ? integer_one_node : integer_zero_node);
3906         }
3907     }
3908
3909   /* If the right sides are not constant, do the same for it.  Also,
3910      disallow this optimization if a size or signedness mismatch occurs
3911      between the left and right sides.  */
3912   if (l_const == 0)
3913     {
3914       if (ll_bitsize != lr_bitsize || rl_bitsize != rr_bitsize
3915           || ll_unsignedp != lr_unsignedp || rl_unsignedp != rr_unsignedp
3916           /* Make sure the two fields on the right
3917              correspond to the left without being swapped.  */
3918           || ll_bitpos - rl_bitpos != lr_bitpos - rr_bitpos)
3919         return 0;
3920
3921       first_bit = MIN (lr_bitpos, rr_bitpos);
3922       end_bit = MAX (lr_bitpos + lr_bitsize, rr_bitpos + rr_bitsize);
3923       rnmode = get_best_mode (end_bit - first_bit, first_bit,
3924                               TYPE_ALIGN (TREE_TYPE (lr_inner)), word_mode,
3925                               volatilep);
3926       if (rnmode == VOIDmode)
3927         return 0;
3928
3929       rnbitsize = GET_MODE_BITSIZE (rnmode);
3930       rnbitpos = first_bit & ~ (rnbitsize - 1);
3931       rntype = type_for_size (rnbitsize, 1);
3932       xlr_bitpos = lr_bitpos - rnbitpos, xrr_bitpos = rr_bitpos - rnbitpos;
3933
3934       if (BYTES_BIG_ENDIAN)
3935         {
3936           xlr_bitpos = rnbitsize - xlr_bitpos - lr_bitsize;
3937           xrr_bitpos = rnbitsize - xrr_bitpos - rr_bitsize;
3938         }
3939
3940       lr_mask = const_binop (LSHIFT_EXPR, convert (rntype, lr_mask),
3941                              size_int (xlr_bitpos), 0);
3942       rr_mask = const_binop (LSHIFT_EXPR, convert (rntype, rr_mask),
3943                              size_int (xrr_bitpos), 0);
3944
3945       /* Make a mask that corresponds to both fields being compared.
3946          Do this for both items being compared.  If the operands are the
3947          same size and the bits being compared are in the same position
3948          then we can do this by masking both and comparing the masked
3949          results.  */
3950       ll_mask = const_binop (BIT_IOR_EXPR, ll_mask, rl_mask, 0);
3951       lr_mask = const_binop (BIT_IOR_EXPR, lr_mask, rr_mask, 0);
3952       if (lnbitsize == rnbitsize && xll_bitpos == xlr_bitpos)
3953         {
3954           lhs = make_bit_field_ref (ll_inner, lntype, lnbitsize, lnbitpos,
3955                                     ll_unsignedp || rl_unsignedp);
3956           if (! all_ones_mask_p (ll_mask, lnbitsize))
3957             lhs = build (BIT_AND_EXPR, lntype, lhs, ll_mask);
3958
3959           rhs = make_bit_field_ref (lr_inner, rntype, rnbitsize, rnbitpos,
3960                                     lr_unsignedp || rr_unsignedp);
3961           if (! all_ones_mask_p (lr_mask, rnbitsize))
3962             rhs = build (BIT_AND_EXPR, rntype, rhs, lr_mask);
3963
3964           return build (wanted_code, truth_type, lhs, rhs);
3965         }
3966
3967       /* There is still another way we can do something:  If both pairs of
3968          fields being compared are adjacent, we may be able to make a wider
3969          field containing them both.
3970
3971          Note that we still must mask the lhs/rhs expressions.  Furthermore,
3972          the mask must be shifted to account for the shift done by
3973          make_bit_field_ref.  */
3974       if ((ll_bitsize + ll_bitpos == rl_bitpos
3975            && lr_bitsize + lr_bitpos == rr_bitpos)
3976           || (ll_bitpos == rl_bitpos + rl_bitsize
3977               && lr_bitpos == rr_bitpos + rr_bitsize))
3978         {
3979           tree type;
3980
3981           lhs = make_bit_field_ref (ll_inner, lntype, ll_bitsize + rl_bitsize,
3982                                     MIN (ll_bitpos, rl_bitpos), ll_unsignedp);
3983           rhs = make_bit_field_ref (lr_inner, rntype, lr_bitsize + rr_bitsize,
3984                                     MIN (lr_bitpos, rr_bitpos), lr_unsignedp);
3985
3986           ll_mask = const_binop (RSHIFT_EXPR, ll_mask,
3987                                  size_int (MIN (xll_bitpos, xrl_bitpos)), 0);
3988           lr_mask = const_binop (RSHIFT_EXPR, lr_mask,
3989                                  size_int (MIN (xlr_bitpos, xrr_bitpos)), 0);
3990
3991           /* Convert to the smaller type before masking out unwanted bits.  */
3992           type = lntype;
3993           if (lntype != rntype)
3994             {
3995               if (lnbitsize > rnbitsize)
3996                 {
3997                   lhs = convert (rntype, lhs);
3998                   ll_mask = convert (rntype, ll_mask);
3999                   type = rntype;
4000                 }
4001               else if (lnbitsize < rnbitsize)
4002                 {
4003                   rhs = convert (lntype, rhs);
4004                   lr_mask = convert (lntype, lr_mask);
4005                   type = lntype;
4006                 }
4007             }
4008
4009           if (! all_ones_mask_p (ll_mask, ll_bitsize + rl_bitsize))
4010             lhs = build (BIT_AND_EXPR, type, lhs, ll_mask);
4011
4012           if (! all_ones_mask_p (lr_mask, lr_bitsize + rr_bitsize))
4013             rhs = build (BIT_AND_EXPR, type, rhs, lr_mask);
4014
4015           return build (wanted_code, truth_type, lhs, rhs);
4016         }
4017
4018       return 0;
4019     }
4020
4021   /* Handle the case of comparisons with constants.  If there is something in
4022      common between the masks, those bits of the constants must be the same.
4023      If not, the condition is always false.  Test for this to avoid generating
4024      incorrect code below.  */
4025   result = const_binop (BIT_AND_EXPR, ll_mask, rl_mask, 0);
4026   if (! integer_zerop (result)
4027       && simple_cst_equal (const_binop (BIT_AND_EXPR, result, l_const, 0),
4028                            const_binop (BIT_AND_EXPR, result, r_const, 0)) != 1)
4029     {
4030       if (wanted_code == NE_EXPR)
4031         {
4032           warning ("`or' of unmatched not-equal tests is always 1");
4033           return convert (truth_type, integer_one_node);
4034         }
4035       else
4036         {
4037           warning ("`and' of mutually exclusive equal-tests is always 0");
4038           return convert (truth_type, integer_zero_node);
4039         }
4040     }
4041
4042   /* Construct the expression we will return.  First get the component
4043      reference we will make.  Unless the mask is all ones the width of
4044      that field, perform the mask operation.  Then compare with the
4045      merged constant.  */
4046   result = make_bit_field_ref (ll_inner, lntype, lnbitsize, lnbitpos,
4047                                ll_unsignedp || rl_unsignedp);
4048
4049   ll_mask = const_binop (BIT_IOR_EXPR, ll_mask, rl_mask, 0);
4050   if (! all_ones_mask_p (ll_mask, lnbitsize))
4051     result = build (BIT_AND_EXPR, lntype, result, ll_mask);
4052
4053   return build (wanted_code, truth_type, result,
4054                 const_binop (BIT_IOR_EXPR, l_const, r_const, 0));
4055 }
4056 \f
4057 /* If T contains a COMPOUND_EXPR which was inserted merely to evaluate
4058    S, a SAVE_EXPR, return the expression actually being evaluated.   Note
4059    that we may sometimes modify the tree.  */
4060
4061 static tree
4062 strip_compound_expr (t, s)
4063      tree t;
4064      tree s;
4065 {
4066   enum tree_code code = TREE_CODE (t);
4067
4068   /* See if this is the COMPOUND_EXPR we want to eliminate.  */
4069   if (code == COMPOUND_EXPR && TREE_CODE (TREE_OPERAND (t, 0)) == CONVERT_EXPR
4070       && TREE_OPERAND (TREE_OPERAND (t, 0), 0) == s)
4071     return TREE_OPERAND (t, 1);
4072
4073   /* See if this is a COND_EXPR or a simple arithmetic operator.   We
4074      don't bother handling any other types.  */
4075   else if (code == COND_EXPR)
4076     {
4077       TREE_OPERAND (t, 0) = strip_compound_expr (TREE_OPERAND (t, 0), s);
4078       TREE_OPERAND (t, 1) = strip_compound_expr (TREE_OPERAND (t, 1), s);
4079       TREE_OPERAND (t, 2) = strip_compound_expr (TREE_OPERAND (t, 2), s);
4080     }
4081   else if (TREE_CODE_CLASS (code) == '1')
4082     TREE_OPERAND (t, 0) = strip_compound_expr (TREE_OPERAND (t, 0), s);
4083   else if (TREE_CODE_CLASS (code) == '<'
4084            || TREE_CODE_CLASS (code) == '2')
4085     {
4086       TREE_OPERAND (t, 0) = strip_compound_expr (TREE_OPERAND (t, 0), s);
4087       TREE_OPERAND (t, 1) = strip_compound_expr (TREE_OPERAND (t, 1), s);
4088     }
4089
4090   return t;
4091 }
4092 \f
4093 /* Return a node which has the indicated constant VALUE (either 0 or
4094    1), and is of the indicated TYPE.  */
4095
4096 static tree
4097 constant_boolean_node (value, type)
4098      int value;
4099      tree type;
4100 {
4101   if (type == integer_type_node)
4102     return value ? integer_one_node : integer_zero_node;
4103   else if (TREE_CODE (type) == BOOLEAN_TYPE)
4104     return truthvalue_conversion (value ? integer_one_node :
4105                                   integer_zero_node);
4106   else
4107     {
4108       tree t = build_int_2 (value, 0);
4109       TREE_TYPE (t) = type;
4110       return t;
4111     }
4112 }
4113
4114 /* Utility function for the following routine, to see how complex a nesting of
4115    COND_EXPRs can be.  EXPR is the expression and LIMIT is a count beyond which
4116    we don't care (to avoid spending too much time on complex expressions.).  */
4117
4118 static int
4119 count_cond (expr, lim)
4120      tree expr;
4121      int lim;
4122 {
4123   int true, false;
4124
4125   if (TREE_CODE (expr) != COND_EXPR)
4126     return 0;
4127   else if (lim <= 0)
4128     return 0;
4129
4130   true = count_cond (TREE_OPERAND (expr, 1), lim - 1);
4131   false = count_cond (TREE_OPERAND (expr, 2), lim - 1 - true);
4132   return MIN (lim, 1 + true + false);
4133 }
4134 \f
4135 /* Perform constant folding and related simplification of EXPR.
4136    The related simplifications include x*1 => x, x*0 => 0, etc.,
4137    and application of the associative law.
4138    NOP_EXPR conversions may be removed freely (as long as we
4139    are careful not to change the C type of the overall expression)
4140    We cannot simplify through a CONVERT_EXPR, FIX_EXPR or FLOAT_EXPR,
4141    but we can constant-fold them if they have constant operands.  */
4142
4143 tree
4144 fold (expr)
4145      tree expr;
4146 {
4147   register tree t = expr;
4148   tree t1 = NULL_TREE;
4149   tree tem;
4150   tree type = TREE_TYPE (expr);
4151   register tree arg0 = NULL_TREE, arg1 = NULL_TREE;
4152   register enum tree_code code = TREE_CODE (t);
4153   register int kind;
4154   int invert;
4155
4156   /* WINS will be nonzero when the switch is done
4157      if all operands are constant.  */
4158
4159   int wins = 1;
4160
4161   /* Don't try to process an RTL_EXPR since its operands aren't trees.
4162      Likewise for a SAVE_EXPR that's already been evaluated.  */
4163   if (code == RTL_EXPR || (code == SAVE_EXPR && SAVE_EXPR_RTL (t)) != 0)
4164     return t;
4165
4166   /* Return right away if already constant.  */
4167   if (TREE_CONSTANT (t))
4168     {
4169       if (code == CONST_DECL)
4170         return DECL_INITIAL (t);
4171       return t;
4172     }
4173
4174 #ifdef MAX_INTEGER_COMPUTATION_MODE
4175   check_max_integer_computation_mode (expr);
4176 #endif
4177
4178   kind = TREE_CODE_CLASS (code);
4179   if (code == NOP_EXPR || code == FLOAT_EXPR || code == CONVERT_EXPR)
4180     {
4181       tree subop;
4182
4183       /* Special case for conversion ops that can have fixed point args.  */
4184       arg0 = TREE_OPERAND (t, 0);
4185
4186       /* Don't use STRIP_NOPS, because signedness of argument type matters.  */
4187       if (arg0 != 0)
4188         STRIP_TYPE_NOPS (arg0);
4189
4190       if (arg0 != 0 && TREE_CODE (arg0) == COMPLEX_CST)
4191         subop = TREE_REALPART (arg0);
4192       else
4193         subop = arg0;
4194
4195       if (subop != 0 && TREE_CODE (subop) != INTEGER_CST
4196 #if ! defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
4197           && TREE_CODE (subop) != REAL_CST
4198 #endif /* not REAL_IS_NOT_DOUBLE, or REAL_ARITHMETIC */
4199           )
4200         /* Note that TREE_CONSTANT isn't enough:
4201            static var addresses are constant but we can't
4202            do arithmetic on them.  */
4203         wins = 0;
4204     }
4205   else if (kind == 'e' || kind == '<'
4206            || kind == '1' || kind == '2' || kind == 'r')
4207     {
4208       register int len = tree_code_length[(int) code];
4209       register int i;
4210       for (i = 0; i < len; i++)
4211         {
4212           tree op = TREE_OPERAND (t, i);
4213           tree subop;
4214
4215           if (op == 0)
4216             continue;           /* Valid for CALL_EXPR, at least.  */
4217
4218           if (kind == '<' || code == RSHIFT_EXPR)
4219             {
4220               /* Signedness matters here.  Perhaps we can refine this
4221                  later.  */
4222               STRIP_TYPE_NOPS (op);
4223             }
4224           else
4225             {
4226               /* Strip any conversions that don't change the mode.  */
4227               STRIP_NOPS (op);
4228             }
4229
4230           if (TREE_CODE (op) == COMPLEX_CST)
4231             subop = TREE_REALPART (op);
4232           else
4233             subop = op;
4234
4235           if (TREE_CODE (subop) != INTEGER_CST
4236 #if ! defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
4237               && TREE_CODE (subop) != REAL_CST
4238 #endif /* not REAL_IS_NOT_DOUBLE, or REAL_ARITHMETIC */
4239               )
4240             /* Note that TREE_CONSTANT isn't enough:
4241                static var addresses are constant but we can't
4242                do arithmetic on them.  */
4243             wins = 0;
4244
4245           if (i == 0)
4246             arg0 = op;
4247           else if (i == 1)
4248             arg1 = op;
4249         }
4250     }
4251
4252   /* If this is a commutative operation, and ARG0 is a constant, move it
4253      to ARG1 to reduce the number of tests below.  */
4254   if ((code == PLUS_EXPR || code == MULT_EXPR || code == MIN_EXPR
4255        || code == MAX_EXPR || code == BIT_IOR_EXPR || code == BIT_XOR_EXPR
4256        || code == BIT_AND_EXPR)
4257       && (TREE_CODE (arg0) == INTEGER_CST || TREE_CODE (arg0) == REAL_CST))
4258     {
4259       tem = arg0; arg0 = arg1; arg1 = tem;
4260
4261       tem = TREE_OPERAND (t, 0); TREE_OPERAND (t, 0) = TREE_OPERAND (t, 1);
4262       TREE_OPERAND (t, 1) = tem;
4263     }
4264
4265   /* Now WINS is set as described above,
4266      ARG0 is the first operand of EXPR,
4267      and ARG1 is the second operand (if it has more than one operand).
4268
4269      First check for cases where an arithmetic operation is applied to a
4270      compound, conditional, or comparison operation.  Push the arithmetic
4271      operation inside the compound or conditional to see if any folding
4272      can then be done.  Convert comparison to conditional for this purpose.
4273      The also optimizes non-constant cases that used to be done in
4274      expand_expr.
4275
4276      Before we do that, see if this is a BIT_AND_EXPR or a BIT_OR_EXPR,
4277      one of the operands is a comparison and the other is a comparison, a
4278      BIT_AND_EXPR with the constant 1, or a truth value.  In that case, the
4279      code below would make the expression more complex.  Change it to a
4280      TRUTH_{AND,OR}_EXPR.  Likewise, convert a similar NE_EXPR to
4281      TRUTH_XOR_EXPR and an EQ_EXPR to the inversion of a TRUTH_XOR_EXPR.  */
4282
4283   if ((code == BIT_AND_EXPR || code == BIT_IOR_EXPR
4284        || code == EQ_EXPR || code == NE_EXPR)
4285       && ((truth_value_p (TREE_CODE (arg0))
4286            && (truth_value_p (TREE_CODE (arg1))
4287                || (TREE_CODE (arg1) == BIT_AND_EXPR
4288                    && integer_onep (TREE_OPERAND (arg1, 1)))))
4289           || (truth_value_p (TREE_CODE (arg1))
4290               && (truth_value_p (TREE_CODE (arg0))
4291                   || (TREE_CODE (arg0) == BIT_AND_EXPR
4292                       && integer_onep (TREE_OPERAND (arg0, 1)))))))
4293     {
4294       t = fold (build (code == BIT_AND_EXPR ? TRUTH_AND_EXPR
4295                        : code == BIT_IOR_EXPR ? TRUTH_OR_EXPR
4296                        : TRUTH_XOR_EXPR,
4297                        type, arg0, arg1));
4298
4299       if (code == EQ_EXPR)
4300         t = invert_truthvalue (t);
4301
4302       return t;
4303     }
4304
4305   if (TREE_CODE_CLASS (code) == '1')
4306     {
4307       if (TREE_CODE (arg0) == COMPOUND_EXPR)
4308         return build (COMPOUND_EXPR, type, TREE_OPERAND (arg0, 0),
4309                       fold (build1 (code, type, TREE_OPERAND (arg0, 1))));
4310       else if (TREE_CODE (arg0) == COND_EXPR)
4311         {
4312           t = fold (build (COND_EXPR, type, TREE_OPERAND (arg0, 0),
4313                            fold (build1 (code, type, TREE_OPERAND (arg0, 1))),
4314                            fold (build1 (code, type, TREE_OPERAND (arg0, 2)))));
4315
4316           /* If this was a conversion, and all we did was to move into
4317              inside the COND_EXPR, bring it back out.  But leave it if
4318              it is a conversion from integer to integer and the
4319              result precision is no wider than a word since such a
4320              conversion is cheap and may be optimized away by combine,
4321              while it couldn't if it were outside the COND_EXPR.  Then return
4322              so we don't get into an infinite recursion loop taking the
4323              conversion out and then back in.  */
4324
4325           if ((code == NOP_EXPR || code == CONVERT_EXPR
4326                || code == NON_LVALUE_EXPR)
4327               && TREE_CODE (t) == COND_EXPR
4328               && TREE_CODE (TREE_OPERAND (t, 1)) == code
4329               && TREE_CODE (TREE_OPERAND (t, 2)) == code
4330               && (TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 1), 0))
4331                   == TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 2), 0)))
4332               && ! (INTEGRAL_TYPE_P (TREE_TYPE (t))
4333                     && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 1), 0)))
4334                     && TYPE_PRECISION (TREE_TYPE (t)) <= BITS_PER_WORD))
4335             t = build1 (code, type,
4336                         build (COND_EXPR,
4337                                TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 1), 0)),
4338                                TREE_OPERAND (t, 0),
4339                                TREE_OPERAND (TREE_OPERAND (t, 1), 0),
4340                                TREE_OPERAND (TREE_OPERAND (t, 2), 0)));
4341           return t;
4342         }
4343       else if (TREE_CODE_CLASS (TREE_CODE (arg0)) == '<')
4344         return fold (build (COND_EXPR, type, arg0,
4345                             fold (build1 (code, type, integer_one_node)),
4346                             fold (build1 (code, type, integer_zero_node))));
4347    }
4348   else if (TREE_CODE_CLASS (code) == '2'
4349            || TREE_CODE_CLASS (code) == '<')
4350     {
4351       if (TREE_CODE (arg1) == COMPOUND_EXPR)
4352         return build (COMPOUND_EXPR, type, TREE_OPERAND (arg1, 0),
4353                       fold (build (code, type,
4354                                    arg0, TREE_OPERAND (arg1, 1))));
4355       else if ((TREE_CODE (arg1) == COND_EXPR
4356                 || (TREE_CODE_CLASS (TREE_CODE (arg1)) == '<'
4357                     && TREE_CODE_CLASS (code) != '<'))
4358                && (TREE_CODE (arg0) != COND_EXPR
4359                    || count_cond (arg0, 25) + count_cond (arg1, 25) <= 25)
4360                && (! TREE_SIDE_EFFECTS (arg0)
4361                    || (global_bindings_p () == 0
4362                        && ! contains_placeholder_p (arg0))))
4363         {
4364           tree test, true_value, false_value;
4365           tree lhs = 0, rhs = 0;
4366
4367           if (TREE_CODE (arg1) == COND_EXPR)
4368             {
4369               test = TREE_OPERAND (arg1, 0);
4370               true_value = TREE_OPERAND (arg1, 1);
4371               false_value = TREE_OPERAND (arg1, 2);
4372             }
4373           else
4374             {
4375               tree testtype = TREE_TYPE (arg1);
4376               test = arg1;
4377               true_value = convert (testtype, integer_one_node);
4378               false_value = convert (testtype, integer_zero_node);
4379             }
4380
4381           /* If ARG0 is complex we want to make sure we only evaluate
4382              it once.  Though this is only required if it is volatile, it
4383              might be more efficient even if it is not.  However, if we
4384              succeed in folding one part to a constant, we do not need
4385              to make this SAVE_EXPR.  Since we do this optimization
4386              primarily to see if we do end up with constant and this
4387              SAVE_EXPR interferes with later optimizations, suppressing
4388              it when we can is important.
4389
4390              If we are not in a function, we can't make a SAVE_EXPR, so don't
4391              try to do so.  Don't try to see if the result is a constant
4392              if an arm is a COND_EXPR since we get exponential behavior
4393              in that case.  */
4394
4395           if (TREE_CODE (arg0) != SAVE_EXPR && ! TREE_CONSTANT (arg0)
4396               && global_bindings_p () == 0
4397               && ((TREE_CODE (arg0) != VAR_DECL
4398                    && TREE_CODE (arg0) != PARM_DECL)
4399                   || TREE_SIDE_EFFECTS (arg0)))
4400             {
4401               if (TREE_CODE (true_value) != COND_EXPR)
4402                 lhs = fold (build (code, type, arg0, true_value));
4403
4404               if (TREE_CODE (false_value) != COND_EXPR)
4405                 rhs = fold (build (code, type, arg0, false_value));
4406
4407               if ((lhs == 0 || ! TREE_CONSTANT (lhs))
4408                   && (rhs == 0 || !TREE_CONSTANT (rhs)))
4409                 arg0 = save_expr (arg0), lhs = rhs = 0;
4410             }
4411
4412           if (lhs == 0)
4413             lhs = fold (build (code, type, arg0, true_value));
4414           if (rhs == 0)
4415             rhs = fold (build (code, type, arg0, false_value));
4416
4417           test = fold (build (COND_EXPR, type, test, lhs, rhs));
4418
4419           if (TREE_CODE (arg0) == SAVE_EXPR)
4420             return build (COMPOUND_EXPR, type,
4421                           convert (void_type_node, arg0),
4422                           strip_compound_expr (test, arg0));
4423           else
4424             return convert (type, test);
4425         }
4426
4427       else if (TREE_CODE (arg0) == COMPOUND_EXPR)
4428         return build (COMPOUND_EXPR, type, TREE_OPERAND (arg0, 0),
4429                       fold (build (code, type, TREE_OPERAND (arg0, 1), arg1)));
4430       else if ((TREE_CODE (arg0) == COND_EXPR
4431                 || (TREE_CODE_CLASS (TREE_CODE (arg0)) == '<'
4432                     && TREE_CODE_CLASS (code) != '<'))
4433                && (TREE_CODE (arg1) != COND_EXPR
4434                    || count_cond (arg0, 25) + count_cond (arg1, 25) <= 25)
4435                && (! TREE_SIDE_EFFECTS (arg1)
4436                    || (global_bindings_p () == 0
4437                        && ! contains_placeholder_p (arg1))))
4438         {
4439           tree test, true_value, false_value;
4440           tree lhs = 0, rhs = 0;
4441
4442           if (TREE_CODE (arg0) == COND_EXPR)
4443             {
4444               test = TREE_OPERAND (arg0, 0);
4445               true_value = TREE_OPERAND (arg0, 1);
4446               false_value = TREE_OPERAND (arg0, 2);
4447             }
4448           else
4449             {
4450               tree testtype = TREE_TYPE (arg0);
4451               test = arg0;
4452               true_value = convert (testtype, integer_one_node);
4453               false_value = convert (testtype, integer_zero_node);
4454             }
4455
4456           if (TREE_CODE (arg1) != SAVE_EXPR && ! TREE_CONSTANT (arg0)
4457               && global_bindings_p () == 0
4458               && ((TREE_CODE (arg1) != VAR_DECL
4459                    && TREE_CODE (arg1) != PARM_DECL)
4460                   || TREE_SIDE_EFFECTS (arg1)))
4461             {
4462               if (TREE_CODE (true_value) != COND_EXPR)
4463                 lhs = fold (build (code, type, true_value, arg1));
4464
4465               if (TREE_CODE (false_value) != COND_EXPR)
4466                 rhs = fold (build (code, type, false_value, arg1));
4467
4468               if ((lhs == 0 || ! TREE_CONSTANT (lhs))
4469                   && (rhs == 0 || !TREE_CONSTANT (rhs)))
4470                 arg1 = save_expr (arg1), lhs = rhs = 0;
4471             }
4472
4473           if (lhs == 0)
4474             lhs = fold (build (code, type, true_value, arg1));
4475
4476           if (rhs == 0)
4477             rhs = fold (build (code, type, false_value, arg1));
4478
4479           test = fold (build (COND_EXPR, type, test, lhs, rhs));
4480           if (TREE_CODE (arg1) == SAVE_EXPR)
4481             return build (COMPOUND_EXPR, type,
4482                           convert (void_type_node, arg1),
4483                           strip_compound_expr (test, arg1));
4484           else
4485             return convert (type, test);
4486         }
4487     }
4488   else if (TREE_CODE_CLASS (code) == '<'
4489            && TREE_CODE (arg0) == COMPOUND_EXPR)
4490     return build (COMPOUND_EXPR, type, TREE_OPERAND (arg0, 0),
4491                   fold (build (code, type, TREE_OPERAND (arg0, 1), arg1)));
4492   else if (TREE_CODE_CLASS (code) == '<'
4493            && TREE_CODE (arg1) == COMPOUND_EXPR)
4494     return build (COMPOUND_EXPR, type, TREE_OPERAND (arg1, 0),
4495                   fold (build (code, type, arg0, TREE_OPERAND (arg1, 1))));
4496
4497   switch (code)
4498     {
4499     case INTEGER_CST:
4500     case REAL_CST:
4501     case STRING_CST:
4502     case COMPLEX_CST:
4503     case CONSTRUCTOR:
4504       return t;
4505
4506     case CONST_DECL:
4507       return fold (DECL_INITIAL (t));
4508
4509     case NOP_EXPR:
4510     case FLOAT_EXPR:
4511     case CONVERT_EXPR:
4512     case FIX_TRUNC_EXPR:
4513       /* Other kinds of FIX are not handled properly by fold_convert.  */
4514
4515       if (TREE_TYPE (TREE_OPERAND (t, 0)) == TREE_TYPE (t))
4516         return TREE_OPERAND (t, 0);
4517
4518       /* Handle cases of two conversions in a row.  */
4519       if (TREE_CODE (TREE_OPERAND (t, 0)) == NOP_EXPR
4520           || TREE_CODE (TREE_OPERAND (t, 0)) == CONVERT_EXPR)
4521         {
4522           tree inside_type = TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 0), 0));
4523           tree inter_type = TREE_TYPE (TREE_OPERAND (t, 0));
4524           tree final_type = TREE_TYPE (t);
4525           int inside_int = INTEGRAL_TYPE_P (inside_type);
4526           int inside_ptr = POINTER_TYPE_P (inside_type);
4527           int inside_float = FLOAT_TYPE_P (inside_type);
4528           int inside_prec = TYPE_PRECISION (inside_type);
4529           int inside_unsignedp = TREE_UNSIGNED (inside_type);
4530           int inter_int = INTEGRAL_TYPE_P (inter_type);
4531           int inter_ptr = POINTER_TYPE_P (inter_type);
4532           int inter_float = FLOAT_TYPE_P (inter_type);
4533           int inter_prec = TYPE_PRECISION (inter_type);
4534           int inter_unsignedp = TREE_UNSIGNED (inter_type);
4535           int final_int = INTEGRAL_TYPE_P (final_type);
4536           int final_ptr = POINTER_TYPE_P (final_type);
4537           int final_float = FLOAT_TYPE_P (final_type);
4538           int final_prec = TYPE_PRECISION (final_type);
4539           int final_unsignedp = TREE_UNSIGNED (final_type);
4540
4541           /* In addition to the cases of two conversions in a row
4542              handled below, if we are converting something to its own
4543              type via an object of identical or wider precision, neither
4544              conversion is needed.  */
4545           if (inside_type == final_type
4546               && ((inter_int && final_int) || (inter_float && final_float))
4547               && inter_prec >= final_prec)
4548             return TREE_OPERAND (TREE_OPERAND (t, 0), 0);
4549
4550           /* Likewise, if the intermediate and final types are either both
4551              float or both integer, we don't need the middle conversion if
4552              it is wider than the final type and doesn't change the signedness
4553              (for integers).  Avoid this if the final type is a pointer
4554              since then we sometimes need the inner conversion.  Likewise if
4555              the outer has a precision not equal to the size of its mode.  */
4556           if ((((inter_int || inter_ptr) && (inside_int || inside_ptr))
4557                || (inter_float && inside_float))
4558               && inter_prec >= inside_prec
4559               && (inter_float || inter_unsignedp == inside_unsignedp)
4560               && ! (final_prec != GET_MODE_BITSIZE (TYPE_MODE (final_type))
4561                     && TYPE_MODE (final_type) == TYPE_MODE (inter_type))
4562               && ! final_ptr)
4563             return convert (final_type, TREE_OPERAND (TREE_OPERAND (t, 0), 0));
4564
4565           /* If we have a sign-extension of a zero-extended value, we can
4566              replace that by a single zero-extension.  */
4567           if (inside_int && inter_int && final_int
4568               && inside_prec < inter_prec && inter_prec < final_prec
4569               && inside_unsignedp && !inter_unsignedp)
4570             return convert (final_type, TREE_OPERAND (TREE_OPERAND (t, 0), 0));
4571
4572           /* Two conversions in a row are not needed unless:
4573              - some conversion is floating-point (overstrict for now), or
4574              - the intermediate type is narrower than both initial and
4575                final, or
4576              - the intermediate type and innermost type differ in signedness,
4577                and the outermost type is wider than the intermediate, or
4578              - the initial type is a pointer type and the precisions of the
4579                intermediate and final types differ, or
4580              - the final type is a pointer type and the precisions of the
4581                initial and intermediate types differ.  */
4582           if (! inside_float && ! inter_float && ! final_float
4583               && (inter_prec > inside_prec || inter_prec > final_prec)
4584               && ! (inside_int && inter_int
4585                     && inter_unsignedp != inside_unsignedp
4586                     && inter_prec < final_prec)
4587               && ((inter_unsignedp && inter_prec > inside_prec)
4588                   == (final_unsignedp && final_prec > inter_prec))
4589               && ! (inside_ptr && inter_prec != final_prec)
4590               && ! (final_ptr && inside_prec != inter_prec)
4591               && ! (final_prec != GET_MODE_BITSIZE (TYPE_MODE (final_type))
4592                     && TYPE_MODE (final_type) == TYPE_MODE (inter_type))
4593               && ! final_ptr)
4594             return convert (final_type, TREE_OPERAND (TREE_OPERAND (t, 0), 0));
4595         }
4596
4597       if (TREE_CODE (TREE_OPERAND (t, 0)) == MODIFY_EXPR
4598           && TREE_CONSTANT (TREE_OPERAND (TREE_OPERAND (t, 0), 1))
4599           /* Detect assigning a bitfield.  */
4600           && !(TREE_CODE (TREE_OPERAND (TREE_OPERAND (t, 0), 0)) == COMPONENT_REF
4601                && DECL_BIT_FIELD (TREE_OPERAND (TREE_OPERAND (TREE_OPERAND (t, 0), 0), 1))))
4602         {
4603           /* Don't leave an assignment inside a conversion
4604              unless assigning a bitfield.  */
4605           tree prev = TREE_OPERAND (t, 0);
4606           TREE_OPERAND (t, 0) = TREE_OPERAND (prev, 1);
4607           /* First do the assignment, then return converted constant.  */
4608           t = build (COMPOUND_EXPR, TREE_TYPE (t), prev, fold (t));
4609           TREE_USED (t) = 1;
4610           return t;
4611         }
4612       if (!wins)
4613         {
4614           TREE_CONSTANT (t) = TREE_CONSTANT (arg0);
4615           return t;
4616         }
4617       return fold_convert (t, arg0);
4618
4619 #if 0  /* This loses on &"foo"[0].  */
4620     case ARRAY_REF:
4621         {
4622           int i;
4623
4624           /* Fold an expression like: "foo"[2] */
4625           if (TREE_CODE (arg0) == STRING_CST
4626               && TREE_CODE (arg1) == INTEGER_CST
4627               && !TREE_INT_CST_HIGH (arg1)
4628               && (i = TREE_INT_CST_LOW (arg1)) < TREE_STRING_LENGTH (arg0))
4629             {
4630               t = build_int_2 (TREE_STRING_POINTER (arg0)[i], 0);
4631               TREE_TYPE (t) = TREE_TYPE (TREE_TYPE (arg0));
4632               force_fit_type (t, 0);
4633             }
4634         }
4635       return t;
4636 #endif /* 0 */
4637
4638     case COMPONENT_REF:
4639       if (TREE_CODE (arg0) == CONSTRUCTOR)
4640         {
4641           tree m = purpose_member (arg1, CONSTRUCTOR_ELTS (arg0));
4642           if (m)
4643             t = TREE_VALUE (m);
4644         }
4645       return t;
4646
4647     case RANGE_EXPR:
4648       TREE_CONSTANT (t) = wins;
4649       return t;
4650
4651     case NEGATE_EXPR:
4652       if (wins)
4653         {
4654           if (TREE_CODE (arg0) == INTEGER_CST)
4655             {
4656               HOST_WIDE_INT low, high;
4657               int overflow = neg_double (TREE_INT_CST_LOW (arg0),
4658                                          TREE_INT_CST_HIGH (arg0),
4659                                          &low, &high);
4660               t = build_int_2 (low, high);
4661               TREE_TYPE (t) = type;
4662               TREE_OVERFLOW (t)
4663                 = (TREE_OVERFLOW (arg0)
4664                    | force_fit_type (t, overflow && !TREE_UNSIGNED (type)));
4665               TREE_CONSTANT_OVERFLOW (t)
4666                 = TREE_OVERFLOW (t) | TREE_CONSTANT_OVERFLOW (arg0);
4667             }
4668           else if (TREE_CODE (arg0) == REAL_CST)
4669             t = build_real (type, REAL_VALUE_NEGATE (TREE_REAL_CST (arg0)));
4670         }
4671       else if (TREE_CODE (arg0) == NEGATE_EXPR)
4672         return TREE_OPERAND (arg0, 0);
4673
4674       /* Convert - (a - b) to (b - a) for non-floating-point.  */
4675       else if (TREE_CODE (arg0) == MINUS_EXPR && ! FLOAT_TYPE_P (type))
4676         return build (MINUS_EXPR, type, TREE_OPERAND (arg0, 1),
4677                       TREE_OPERAND (arg0, 0));
4678
4679       return t;
4680
4681     case ABS_EXPR:
4682       if (wins)
4683         {
4684           if (TREE_CODE (arg0) == INTEGER_CST)
4685             {
4686               if (! TREE_UNSIGNED (type)
4687                   && TREE_INT_CST_HIGH (arg0) < 0)
4688                 {
4689                   HOST_WIDE_INT low, high;
4690                   int overflow = neg_double (TREE_INT_CST_LOW (arg0),
4691                                              TREE_INT_CST_HIGH (arg0),
4692                                              &low, &high);
4693                   t = build_int_2 (low, high);
4694                   TREE_TYPE (t) = type;
4695                   TREE_OVERFLOW (t)
4696                     = (TREE_OVERFLOW (arg0)
4697                        | force_fit_type (t, overflow));
4698                   TREE_CONSTANT_OVERFLOW (t)
4699                     = TREE_OVERFLOW (t) | TREE_CONSTANT_OVERFLOW (arg0);
4700                 }
4701             }
4702           else if (TREE_CODE (arg0) == REAL_CST)
4703             {
4704               if (REAL_VALUE_NEGATIVE (TREE_REAL_CST (arg0)))
4705                 t = build_real (type,
4706                                 REAL_VALUE_NEGATE (TREE_REAL_CST (arg0)));
4707             }
4708         }
4709       else if (TREE_CODE (arg0) == ABS_EXPR || TREE_CODE (arg0) == NEGATE_EXPR)
4710         return build1 (ABS_EXPR, type, TREE_OPERAND (arg0, 0));
4711       return t;
4712
4713     case CONJ_EXPR:
4714       if (TREE_CODE (TREE_TYPE (arg0)) != COMPLEX_TYPE)
4715         return arg0;
4716       else if (TREE_CODE (arg0) == COMPLEX_EXPR)
4717         return build (COMPLEX_EXPR, TREE_TYPE (arg0),
4718                       TREE_OPERAND (arg0, 0),
4719                       fold (build1 (NEGATE_EXPR,
4720                                     TREE_TYPE (TREE_TYPE (arg0)),
4721                                     TREE_OPERAND (arg0, 1))));
4722       else if (TREE_CODE (arg0) == COMPLEX_CST)
4723         return build_complex (type, TREE_OPERAND (arg0, 0),
4724                               fold (build1 (NEGATE_EXPR,
4725                                             TREE_TYPE (TREE_TYPE (arg0)),
4726                                             TREE_OPERAND (arg0, 1))));
4727       else if (TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MINUS_EXPR)
4728         return fold (build (TREE_CODE (arg0), type,
4729                             fold (build1 (CONJ_EXPR, type,
4730                                           TREE_OPERAND (arg0, 0))),
4731                             fold (build1 (CONJ_EXPR,
4732                                           type, TREE_OPERAND (arg0, 1)))));
4733       else if (TREE_CODE (arg0) == CONJ_EXPR)
4734         return TREE_OPERAND (arg0, 0);
4735       return t;
4736
4737     case BIT_NOT_EXPR:
4738       if (wins)
4739         {
4740           t = build_int_2 (~ TREE_INT_CST_LOW (arg0),
4741                            ~ TREE_INT_CST_HIGH (arg0));
4742           TREE_TYPE (t) = type;
4743           force_fit_type (t, 0);
4744           TREE_OVERFLOW (t) = TREE_OVERFLOW (arg0);
4745           TREE_CONSTANT_OVERFLOW (t) = TREE_CONSTANT_OVERFLOW (arg0);
4746         }
4747       else if (TREE_CODE (arg0) == BIT_NOT_EXPR)
4748         return TREE_OPERAND (arg0, 0);
4749       return t;
4750
4751     case PLUS_EXPR:
4752       /* A + (-B) -> A - B */
4753       if (TREE_CODE (arg1) == NEGATE_EXPR)
4754         return fold (build (MINUS_EXPR, type, arg0, TREE_OPERAND (arg1, 0)));
4755       else if (! FLOAT_TYPE_P (type))
4756         {
4757           if (integer_zerop (arg1))
4758             return non_lvalue (convert (type, arg0));
4759
4760           /* If we are adding two BIT_AND_EXPR's, both of which are and'ing
4761              with a constant, and the two constants have no bits in common,
4762              we should treat this as a BIT_IOR_EXPR since this may produce more
4763              simplifications.  */
4764           if (TREE_CODE (arg0) == BIT_AND_EXPR
4765               && TREE_CODE (arg1) == BIT_AND_EXPR
4766               && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
4767               && TREE_CODE (TREE_OPERAND (arg1, 1)) == INTEGER_CST
4768               && integer_zerop (const_binop (BIT_AND_EXPR,
4769                                              TREE_OPERAND (arg0, 1),
4770                                              TREE_OPERAND (arg1, 1), 0)))
4771             {
4772               code = BIT_IOR_EXPR;
4773               goto bit_ior;
4774             }
4775
4776           /* Reassociate (plus (plus (mult) (foo)) (mult)) as
4777              (plus (plus (mult) (mult)) (foo)) so that we can
4778              take advantage of the factoring cases below.  */
4779           if ((TREE_CODE (arg0) == PLUS_EXPR
4780                && TREE_CODE (arg1) == MULT_EXPR)
4781               || (TREE_CODE (arg1) == PLUS_EXPR
4782                   && TREE_CODE (arg0) == MULT_EXPR))
4783             {
4784               tree parg0, parg1, parg, marg;
4785
4786               if (TREE_CODE (arg0) == PLUS_EXPR)
4787                 parg = arg0, marg = arg1;
4788               else
4789                 parg = arg1, marg = arg0;
4790               parg0 = TREE_OPERAND (parg, 0);
4791               parg1 = TREE_OPERAND (parg, 1);
4792               STRIP_NOPS (parg0);
4793               STRIP_NOPS (parg1);
4794
4795               if (TREE_CODE (parg0) == MULT_EXPR
4796                   && TREE_CODE (parg1) != MULT_EXPR)
4797                 return fold (build (PLUS_EXPR, type,
4798                                     fold (build (PLUS_EXPR, type, parg0, marg)),
4799                                     parg1));
4800               if (TREE_CODE (parg0) != MULT_EXPR
4801                   && TREE_CODE (parg1) == MULT_EXPR)
4802                 return fold (build (PLUS_EXPR, type,
4803                                     fold (build (PLUS_EXPR, type, parg1, marg)),
4804                                     parg0));
4805             }
4806
4807           if (TREE_CODE (arg0) == MULT_EXPR && TREE_CODE (arg1) == MULT_EXPR)
4808             {
4809               tree arg00, arg01, arg10, arg11;
4810               tree alt0 = NULL_TREE, alt1 = NULL_TREE, same;
4811
4812               /* (A * C) + (B * C) -> (A+B) * C.
4813                  We are most concerned about the case where C is a constant,
4814                  but other combinations show up during loop reduction.  Since
4815                  it is not difficult, try all four possibilities.  */
4816
4817               arg00 = TREE_OPERAND (arg0, 0);
4818               arg01 = TREE_OPERAND (arg0, 1);
4819               arg10 = TREE_OPERAND (arg1, 0);
4820               arg11 = TREE_OPERAND (arg1, 1);
4821               same = NULL_TREE;
4822
4823               if (operand_equal_p (arg01, arg11, 0))
4824                 same = arg01, alt0 = arg00, alt1 = arg10;
4825               else if (operand_equal_p (arg00, arg10, 0))
4826                 same = arg00, alt0 = arg01, alt1 = arg11;
4827               else if (operand_equal_p (arg00, arg11, 0))
4828                 same = arg00, alt0 = arg01, alt1 = arg10;
4829               else if (operand_equal_p (arg01, arg10, 0))
4830                 same = arg01, alt0 = arg00, alt1 = arg11;
4831
4832               /* No identical multiplicands; see if we can find a common
4833                  power-of-two factor in non-power-of-two multiplies.  This
4834                  can help in multi-dimensional array access.  */
4835               else if (TREE_CODE (arg01) == INTEGER_CST
4836                        && TREE_CODE (arg11) == INTEGER_CST
4837                        && TREE_INT_CST_HIGH (arg01) == 0
4838                        && TREE_INT_CST_HIGH (arg11) == 0)
4839                 {
4840                   HOST_WIDE_INT int01, int11, tmp;
4841                   int01 = TREE_INT_CST_LOW (arg01);
4842                   int11 = TREE_INT_CST_LOW (arg11);
4843
4844                   /* Move min of absolute values to int11.  */
4845                   if ((int01 >= 0 ? int01 : -int01)
4846                       < (int11 >= 0 ? int11 : -int11))
4847                     {
4848                       tmp = int01, int01 = int11, int11 = tmp;
4849                       alt0 = arg00, arg00 = arg10, arg10 = alt0;
4850                       alt0 = arg01, arg01 = arg11, arg11 = alt0;
4851                     }
4852
4853                   if (exact_log2 (int11) > 0 && int01 % int11 == 0)
4854                     {
4855                       alt0 = fold (build (MULT_EXPR, type, arg00,
4856                                           build_int_2 (int01 / int11, 0)));
4857                       alt1 = arg10;
4858                       same = arg11;
4859                     }
4860                 }
4861
4862               if (same)
4863                 return fold (build (MULT_EXPR, type,
4864                                     fold (build (PLUS_EXPR, type, alt0, alt1)),
4865                                     same));
4866             }
4867         }
4868       /* In IEEE floating point, x+0 may not equal x.  */
4869       else if ((TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
4870                 || flag_fast_math)
4871                && real_zerop (arg1))
4872         return non_lvalue (convert (type, arg0));
4873     associate:
4874       /* In most languages, can't associate operations on floats
4875          through parentheses.  Rather than remember where the parentheses
4876          were, we don't associate floats at all.  It shouldn't matter much.
4877          However, associating multiplications is only very slightly
4878          inaccurate, so do that if -ffast-math is specified.  */
4879       if (FLOAT_TYPE_P (type)
4880           && ! (flag_fast_math && code == MULT_EXPR))
4881         goto binary;
4882
4883       /* The varsign == -1 cases happen only for addition and subtraction.
4884          It says that the arg that was split was really CON minus VAR.
4885          The rest of the code applies to all associative operations.  */
4886       if (!wins)
4887         {
4888           tree var, con;
4889           int varsign;
4890
4891           if (split_tree (arg0, code, &var, &con, &varsign))
4892             {
4893               if (varsign == -1)
4894                 {
4895                   /* EXPR is (CON-VAR) +- ARG1.  */
4896                   /* If it is + and VAR==ARG1, return just CONST.  */
4897                   if (code == PLUS_EXPR && operand_equal_p (var, arg1, 0))
4898                     return convert (TREE_TYPE (t), con);
4899
4900                   /* If ARG0 is a constant, don't change things around;
4901                      instead keep all the constant computations together.  */
4902
4903                   if (TREE_CONSTANT (arg0))
4904                     return t;
4905
4906                   /* Otherwise return (CON +- ARG1) - VAR.  */
4907                   t = build (MINUS_EXPR, type,
4908                              fold (build (code, type, con, arg1)), var);
4909                 }
4910               else
4911                 {
4912                   /* EXPR is (VAR+CON) +- ARG1.  */
4913                   /* If it is - and VAR==ARG1, return just CONST.  */
4914                   if (code == MINUS_EXPR && operand_equal_p (var, arg1, 0))
4915                     return convert (TREE_TYPE (t), con);
4916
4917                   /* If ARG0 is a constant, don't change things around;
4918                      instead keep all the constant computations together.  */
4919
4920                   if (TREE_CONSTANT (arg0))
4921                     return t;
4922
4923                   /* Otherwise return VAR +- (ARG1 +- CON).  */
4924                   tem = fold (build (code, type, arg1, con));
4925                   t = build (code, type, var, tem);
4926
4927                   if (integer_zerop (tem)
4928                       && (code == PLUS_EXPR || code == MINUS_EXPR))
4929                     return convert (type, var);
4930                   /* If we have x +/- (c - d) [c an explicit integer]
4931                      change it to x -/+ (d - c) since if d is relocatable
4932                      then the latter can be a single immediate insn
4933                      and the former cannot.  */
4934                   if (TREE_CODE (tem) == MINUS_EXPR
4935                       && TREE_CODE (TREE_OPERAND (tem, 0)) == INTEGER_CST)
4936                     {
4937                       tree tem1 = TREE_OPERAND (tem, 1);
4938                       TREE_OPERAND (tem, 1) = TREE_OPERAND (tem, 0);
4939                       TREE_OPERAND (tem, 0) = tem1;
4940                       TREE_SET_CODE (t,
4941                                      (code == PLUS_EXPR ? MINUS_EXPR : PLUS_EXPR));
4942                     }
4943                 }
4944               return t;
4945             }
4946
4947           if (split_tree (arg1, code, &var, &con, &varsign))
4948             {
4949               if (TREE_CONSTANT (arg1))
4950                 return t;
4951
4952               if (varsign == -1)
4953                 TREE_SET_CODE (t,
4954                                (code == PLUS_EXPR ? MINUS_EXPR : PLUS_EXPR));
4955
4956               /* EXPR is ARG0 +- (CON +- VAR).  */
4957               if (TREE_CODE (t) == MINUS_EXPR
4958                   && operand_equal_p (var, arg0, 0))
4959                 {
4960                   /* If VAR and ARG0 cancel, return just CON or -CON.  */
4961                   if (code == PLUS_EXPR)
4962                     return convert (TREE_TYPE (t), con);
4963                   return fold (build1 (NEGATE_EXPR, TREE_TYPE (t),
4964                                        convert (TREE_TYPE (t), con)));
4965                 }
4966
4967               t = build (TREE_CODE (t), type,
4968                          fold (build (code, TREE_TYPE (t), arg0, con)), var);
4969
4970               if (integer_zerop (TREE_OPERAND (t, 0))
4971                   && TREE_CODE (t) == PLUS_EXPR)
4972                 return convert (TREE_TYPE (t), var);
4973               return t;
4974             }
4975         }
4976     binary:
4977 #if defined (REAL_IS_NOT_DOUBLE) && ! defined (REAL_ARITHMETIC)
4978       if (TREE_CODE (arg1) == REAL_CST)
4979         return t;
4980 #endif /* REAL_IS_NOT_DOUBLE, and no REAL_ARITHMETIC */
4981       if (wins)
4982         t1 = const_binop (code, arg0, arg1, 0);
4983       if (t1 != NULL_TREE)
4984         {
4985           /* The return value should always have
4986              the same type as the original expression.  */
4987           if (TREE_TYPE (t1) != TREE_TYPE (t))
4988             t1 = convert (TREE_TYPE (t), t1);
4989
4990           return t1;
4991         }
4992       return t;
4993
4994     case MINUS_EXPR:
4995       if (! FLOAT_TYPE_P (type))
4996         {
4997           if (! wins && integer_zerop (arg0))
4998             return build1 (NEGATE_EXPR, type, arg1);
4999           if (integer_zerop (arg1))
5000             return non_lvalue (convert (type, arg0));
5001
5002           /* (A * C) - (B * C) -> (A-B) * C.  Since we are most concerned
5003              about the case where C is a constant, just try one of the
5004              four possibilities.  */
5005
5006           if (TREE_CODE (arg0) == MULT_EXPR && TREE_CODE (arg1) == MULT_EXPR
5007               && operand_equal_p (TREE_OPERAND (arg0, 1),
5008                                   TREE_OPERAND (arg1, 1), 0))
5009             return fold (build (MULT_EXPR, type,
5010                                 fold (build (MINUS_EXPR, type,
5011                                              TREE_OPERAND (arg0, 0),
5012                                              TREE_OPERAND (arg1, 0))),
5013                                 TREE_OPERAND (arg0, 1)));
5014         }
5015       /* Convert A - (-B) to A + B.  */
5016       else if (TREE_CODE (arg1) == NEGATE_EXPR)
5017         return fold (build (PLUS_EXPR, type, arg0, TREE_OPERAND (arg1, 0)));
5018
5019       else if (TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
5020                || flag_fast_math)
5021         {
5022           /* Except with IEEE floating point, 0-x equals -x.  */
5023           if (! wins && real_zerop (arg0))
5024             return build1 (NEGATE_EXPR, type, arg1);
5025           /* Except with IEEE floating point, x-0 equals x.  */
5026           if (real_zerop (arg1))
5027             return non_lvalue (convert (type, arg0));
5028         }
5029
5030       /* Fold &x - &x.  This can happen from &x.foo - &x.
5031          This is unsafe for certain floats even in non-IEEE formats.
5032          In IEEE, it is unsafe because it does wrong for NaNs.
5033          Also note that operand_equal_p is always false if an operand
5034          is volatile.  */
5035
5036       if ((! FLOAT_TYPE_P (type) || flag_fast_math)
5037           && operand_equal_p (arg0, arg1, 0))
5038         return convert (type, integer_zero_node);
5039
5040       goto associate;
5041
5042     case MULT_EXPR:
5043       if (! FLOAT_TYPE_P (type))
5044         {
5045           if (integer_zerop (arg1))
5046             return omit_one_operand (type, arg1, arg0);
5047           if (integer_onep (arg1))
5048             return non_lvalue (convert (type, arg0));
5049
5050           /* ((A / C) * C) is A if the division is an
5051              EXACT_DIV_EXPR.   Since C is normally a constant,
5052              just check for one of the four possibilities.  */
5053
5054           if (TREE_CODE (arg0) == EXACT_DIV_EXPR
5055               && operand_equal_p (TREE_OPERAND (arg0, 1), arg1, 0))
5056             return TREE_OPERAND (arg0, 0);
5057
5058           /* (a * (1 << b)) is (a << b)  */
5059           if (TREE_CODE (arg1) == LSHIFT_EXPR
5060               && integer_onep (TREE_OPERAND (arg1, 0)))
5061             return fold (build (LSHIFT_EXPR, type, arg0,
5062                                 TREE_OPERAND (arg1, 1)));
5063           if (TREE_CODE (arg0) == LSHIFT_EXPR
5064               && integer_onep (TREE_OPERAND (arg0, 0)))
5065             return fold (build (LSHIFT_EXPR, type, arg1,
5066                                 TREE_OPERAND (arg0, 1)));
5067         }
5068       else
5069         {
5070           /* x*0 is 0, except for IEEE floating point.  */
5071           if ((TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
5072                || flag_fast_math)
5073               && real_zerop (arg1))
5074             return omit_one_operand (type, arg1, arg0);
5075           /* In IEEE floating point, x*1 is not equivalent to x for snans.
5076              However, ANSI says we can drop signals,
5077              so we can do this anyway.  */
5078           if (real_onep (arg1))
5079             return non_lvalue (convert (type, arg0));
5080           /* x*2 is x+x */
5081           if (! wins && real_twop (arg1) && global_bindings_p () == 0
5082               && ! contains_placeholder_p (arg0))
5083             {
5084               tree arg = save_expr (arg0);
5085               return build (PLUS_EXPR, type, arg, arg);
5086             }
5087         }
5088       goto associate;
5089
5090     case BIT_IOR_EXPR:
5091     bit_ior:
5092       {
5093       register enum tree_code code0, code1;
5094
5095       if (integer_all_onesp (arg1))
5096         return omit_one_operand (type, arg1, arg0);
5097       if (integer_zerop (arg1))
5098         return non_lvalue (convert (type, arg0));
5099       t1 = distribute_bit_expr (code, type, arg0, arg1);
5100       if (t1 != NULL_TREE)
5101         return t1;
5102
5103       /* (A << C1) | (A >> C2) if A is unsigned and C1+C2 is the size of A
5104          is a rotate of A by C1 bits.  */
5105       /* (A << B) | (A >> (Z - B)) if A is unsigned and Z is the size of A
5106          is a rotate of A by B bits.  */
5107
5108       code0 = TREE_CODE (arg0);
5109       code1 = TREE_CODE (arg1);
5110       if (((code0 == RSHIFT_EXPR && code1 == LSHIFT_EXPR)
5111           || (code1 == RSHIFT_EXPR && code0 == LSHIFT_EXPR))
5112           && operand_equal_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg1,0), 0)
5113           && TREE_UNSIGNED (TREE_TYPE (TREE_OPERAND (arg0, 0))))
5114         {
5115           register tree tree01, tree11;
5116           register enum tree_code code01, code11;
5117
5118           tree01 = TREE_OPERAND (arg0, 1);
5119           tree11 = TREE_OPERAND (arg1, 1);
5120           STRIP_NOPS (tree01);
5121           STRIP_NOPS (tree11);
5122           code01 = TREE_CODE (tree01);
5123           code11 = TREE_CODE (tree11);
5124           if (code01 == INTEGER_CST
5125             && code11 == INTEGER_CST
5126             && TREE_INT_CST_HIGH (tree01) == 0
5127             && TREE_INT_CST_HIGH (tree11) == 0
5128             && ((TREE_INT_CST_LOW (tree01) + TREE_INT_CST_LOW (tree11))
5129               == TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (arg0, 0)))))
5130             return build (LROTATE_EXPR, type, TREE_OPERAND (arg0, 0),
5131                       code0 == LSHIFT_EXPR ? tree01 : tree11);
5132           else if (code11 == MINUS_EXPR)
5133             {
5134               tree tree110, tree111;
5135               tree110 = TREE_OPERAND (tree11, 0);
5136               tree111 = TREE_OPERAND (tree11, 1);
5137               STRIP_NOPS (tree110);
5138               STRIP_NOPS (tree111);
5139               if (TREE_CODE (tree110) == INTEGER_CST
5140                   && TREE_INT_CST_HIGH (tree110) == 0
5141                   && (TREE_INT_CST_LOW (tree110)
5142                       == TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (arg0, 0))))
5143                   && operand_equal_p (tree01, tree111, 0))
5144                 return build ((code0 == LSHIFT_EXPR
5145                                ? LROTATE_EXPR
5146                                : RROTATE_EXPR),
5147                               type, TREE_OPERAND (arg0, 0), tree01);
5148             }
5149           else if (code01 == MINUS_EXPR)
5150             {
5151               tree tree010, tree011;
5152               tree010 = TREE_OPERAND (tree01, 0);
5153               tree011 = TREE_OPERAND (tree01, 1);
5154               STRIP_NOPS (tree010);
5155               STRIP_NOPS (tree011);
5156               if (TREE_CODE (tree010) == INTEGER_CST
5157                   && TREE_INT_CST_HIGH (tree010) == 0
5158                   && (TREE_INT_CST_LOW (tree010)
5159                       == TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (arg0, 0))))
5160                   && operand_equal_p (tree11, tree011, 0))
5161                 return build ((code0 != LSHIFT_EXPR
5162                                ? LROTATE_EXPR
5163                                : RROTATE_EXPR),
5164                                type, TREE_OPERAND (arg0, 0), tree11);
5165             }
5166         }
5167
5168       goto associate;
5169       }
5170
5171     case BIT_XOR_EXPR:
5172       if (integer_zerop (arg1))
5173         return non_lvalue (convert (type, arg0));
5174       if (integer_all_onesp (arg1))
5175         return fold (build1 (BIT_NOT_EXPR, type, arg0));
5176       goto associate;
5177
5178     case BIT_AND_EXPR:
5179     bit_and:
5180       if (integer_all_onesp (arg1))
5181         return non_lvalue (convert (type, arg0));
5182       if (integer_zerop (arg1))
5183         return omit_one_operand (type, arg1, arg0);
5184       t1 = distribute_bit_expr (code, type, arg0, arg1);
5185       if (t1 != NULL_TREE)
5186         return t1;
5187       /* Simplify ((int)c & 0x377) into (int)c, if c is unsigned char.  */
5188       if (TREE_CODE (arg0) == INTEGER_CST && TREE_CODE (arg1) == NOP_EXPR
5189           && TREE_UNSIGNED (TREE_TYPE (TREE_OPERAND (arg1, 0))))
5190         {
5191           int prec = TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (arg1, 0)));
5192           if (prec < BITS_PER_WORD && prec < HOST_BITS_PER_WIDE_INT
5193               && (~TREE_INT_CST_LOW (arg0)
5194                   & (((HOST_WIDE_INT) 1 << prec) - 1)) == 0)
5195             return build1 (NOP_EXPR, type, TREE_OPERAND (arg1, 0));
5196         }
5197       if (TREE_CODE (arg1) == INTEGER_CST && TREE_CODE (arg0) == NOP_EXPR
5198           && TREE_UNSIGNED (TREE_TYPE (TREE_OPERAND (arg0, 0))))
5199         {
5200           int prec = TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (arg0, 0)));
5201           if (prec < BITS_PER_WORD && prec < HOST_BITS_PER_WIDE_INT
5202               && (~TREE_INT_CST_LOW (arg1)
5203                   & (((HOST_WIDE_INT) 1 << prec) - 1)) == 0)
5204             return build1 (NOP_EXPR, type, TREE_OPERAND (arg0, 0));
5205         }
5206       goto associate;
5207
5208     case BIT_ANDTC_EXPR:
5209       if (integer_all_onesp (arg0))
5210         return non_lvalue (convert (type, arg1));
5211       if (integer_zerop (arg0))
5212         return omit_one_operand (type, arg0, arg1);
5213       if (TREE_CODE (arg1) == INTEGER_CST)
5214         {
5215           arg1 = fold (build1 (BIT_NOT_EXPR, type, arg1));
5216           code = BIT_AND_EXPR;
5217           goto bit_and;
5218         }
5219       goto binary;
5220
5221     case RDIV_EXPR:
5222       /* In most cases, do nothing with a divide by zero.  */
5223 #if !defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
5224 #ifndef REAL_INFINITY
5225       if (TREE_CODE (arg1) == REAL_CST && real_zerop (arg1))
5226         return t;
5227 #endif
5228 #endif /* not REAL_IS_NOT_DOUBLE, or REAL_ARITHMETIC */
5229
5230       /* In IEEE floating point, x/1 is not equivalent to x for snans.
5231          However, ANSI says we can drop signals, so we can do this anyway.  */
5232       if (real_onep (arg1))
5233         return non_lvalue (convert (type, arg0));
5234
5235       /* If ARG1 is a constant, we can convert this to a multiply by the
5236          reciprocal.  This does not have the same rounding properties,
5237          so only do this if -ffast-math.  We can actually always safely
5238          do it if ARG1 is a power of two, but it's hard to tell if it is
5239          or not in a portable manner.  */
5240       if (TREE_CODE (arg1) == REAL_CST)
5241         {
5242           if (flag_fast_math
5243               && 0 != (tem = const_binop (code, build_real (type, dconst1),
5244                                           arg1, 0)))
5245             return fold (build (MULT_EXPR, type, arg0, tem));
5246           /* Find the reciprocal if optimizing and the result is exact. */
5247           else if (optimize)
5248             {
5249               REAL_VALUE_TYPE r;
5250               r = TREE_REAL_CST (arg1);
5251               if (exact_real_inverse (TYPE_MODE(TREE_TYPE(arg0)), &r))
5252                   {
5253                     tem = build_real (type, r);
5254                     return fold (build (MULT_EXPR, type, arg0, tem));
5255                   }
5256             }
5257         }
5258       goto binary;
5259
5260     case TRUNC_DIV_EXPR:
5261     case ROUND_DIV_EXPR:
5262     case FLOOR_DIV_EXPR:
5263     case CEIL_DIV_EXPR:
5264     case EXACT_DIV_EXPR:
5265       if (integer_onep (arg1))
5266         return non_lvalue (convert (type, arg0));
5267       if (integer_zerop (arg1))
5268         return t;
5269
5270       /* If arg0 is a multiple of arg1, then rewrite to the fastest div
5271          operation, EXACT_DIV_EXPR.
5272
5273          Note that only CEIL_DIV_EXPR and FLOOR_DIV_EXPR are rewritten now.
5274          At one time others generated faster code, it's not clear if they do
5275          after the last round to changes to the DIV code in expmed.c.  */
5276       if ((code == CEIL_DIV_EXPR || code == FLOOR_DIV_EXPR)
5277           && multiple_of_p (type, arg0, arg1))
5278         return fold (build (EXACT_DIV_EXPR, type, arg0, arg1));
5279
5280       /* If we have ((a / C1) / C2) where both division are the same type, try
5281          to simplify.  First see if C1 * C2 overflows or not.  */
5282       if (TREE_CODE (arg0) == code && TREE_CODE (arg1) == INTEGER_CST
5283           && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST)
5284         {
5285           tree new_divisor;
5286
5287           new_divisor = const_binop (MULT_EXPR, TREE_OPERAND (arg0, 1), arg1, 0);
5288           tem = const_binop (FLOOR_DIV_EXPR, new_divisor, arg1, 0);
5289
5290           if (TREE_INT_CST_LOW (TREE_OPERAND (arg0, 1)) == TREE_INT_CST_LOW (tem)
5291               && TREE_INT_CST_HIGH (TREE_OPERAND (arg0, 1)) == TREE_INT_CST_HIGH (tem))
5292             {
5293               /* If no overflow, divide by C1*C2.  */
5294               return fold (build (code, type, TREE_OPERAND (arg0, 0), new_divisor));
5295             }
5296         }
5297
5298       /* Look for ((a * C1) / C3) or (((a * C1) + C2) / C3),
5299          where C1 % C3 == 0 or C3 % C1 == 0.  We can simplify these
5300          expressions, which often appear in the offsets or sizes of
5301          objects with a varying size.  Only deal with positive divisors
5302          and multiplicands.   If C2 is negative, we must have C2 % C3 == 0.
5303
5304          Look for NOPs and SAVE_EXPRs inside.  */
5305
5306       if (TREE_CODE (arg1) == INTEGER_CST
5307           && tree_int_cst_sgn (arg1) >= 0)
5308         {
5309           int have_save_expr = 0;
5310           tree c2 = integer_zero_node;
5311           tree xarg0 = arg0;
5312
5313           if (TREE_CODE (xarg0) == SAVE_EXPR && SAVE_EXPR_RTL (xarg0) == 0)
5314             have_save_expr = 1, xarg0 = TREE_OPERAND (xarg0, 0);
5315
5316           STRIP_NOPS (xarg0);
5317
5318           /* Look inside the dividend and simplify using EXACT_DIV_EXPR
5319              if possible.  */
5320           if (TREE_CODE (xarg0) == MULT_EXPR
5321               && multiple_of_p (type, TREE_OPERAND (xarg0, 0), arg1))
5322             {
5323               tree t;
5324
5325               t = fold (build (MULT_EXPR, type,
5326                                fold (build (EXACT_DIV_EXPR, type,
5327                                             TREE_OPERAND (xarg0, 0), arg1)),
5328                                TREE_OPERAND (xarg0, 1)));
5329               if (have_save_expr)
5330                 t = save_expr (t);
5331               return t;
5332
5333             }
5334
5335           if (TREE_CODE (xarg0) == MULT_EXPR
5336               && multiple_of_p (type, TREE_OPERAND (xarg0, 1), arg1))
5337             {
5338               tree t;
5339
5340               t = fold (build (MULT_EXPR, type,
5341                                fold (build (EXACT_DIV_EXPR, type,
5342                                             TREE_OPERAND (xarg0, 1), arg1)),
5343                                TREE_OPERAND (xarg0, 0)));
5344               if (have_save_expr)
5345                 t = save_expr (t);
5346               return t;
5347             }
5348
5349           if (TREE_CODE (xarg0) == PLUS_EXPR
5350               && TREE_CODE (TREE_OPERAND (xarg0, 1)) == INTEGER_CST)
5351             c2 = TREE_OPERAND (xarg0, 1), xarg0 = TREE_OPERAND (xarg0, 0);
5352           else if (TREE_CODE (xarg0) == MINUS_EXPR
5353                    && TREE_CODE (TREE_OPERAND (xarg0, 1)) == INTEGER_CST
5354                    /* If we are doing this computation unsigned, the negate
5355                       is incorrect.  */
5356                    && ! TREE_UNSIGNED (type))
5357             {
5358               c2 = fold (build1 (NEGATE_EXPR, type, TREE_OPERAND (xarg0, 1)));
5359               xarg0 = TREE_OPERAND (xarg0, 0);
5360             }
5361
5362           if (TREE_CODE (xarg0) == SAVE_EXPR && SAVE_EXPR_RTL (xarg0) == 0)
5363             have_save_expr = 1, xarg0 = TREE_OPERAND (xarg0, 0);
5364
5365           STRIP_NOPS (xarg0);
5366
5367           if (TREE_CODE (xarg0) == MULT_EXPR
5368               && TREE_CODE (TREE_OPERAND (xarg0, 1)) == INTEGER_CST
5369               && tree_int_cst_sgn (TREE_OPERAND (xarg0, 1)) >= 0
5370               && (integer_zerop (const_binop (TRUNC_MOD_EXPR,
5371                                               TREE_OPERAND (xarg0, 1), arg1, 1))
5372                   || integer_zerop (const_binop (TRUNC_MOD_EXPR, arg1,
5373                                                  TREE_OPERAND (xarg0, 1), 1)))
5374               && (tree_int_cst_sgn (c2) >= 0
5375                   || integer_zerop (const_binop (TRUNC_MOD_EXPR, c2,
5376                                                  arg1, 1))))
5377             {
5378               tree outer_div = integer_one_node;
5379               tree c1 = TREE_OPERAND (xarg0, 1);
5380               tree c3 = arg1;
5381
5382               /* If C3 > C1, set them equal and do a divide by
5383                  C3/C1 at the end of the operation.  */
5384               if (tree_int_cst_lt (c1, c3))
5385                 outer_div = const_binop (code, c3, c1, 0), c3 = c1;
5386
5387               /* The result is A * (C1/C3) + (C2/C3).  */
5388               t = fold (build (PLUS_EXPR, type,
5389                                fold (build (MULT_EXPR, type,
5390                                             TREE_OPERAND (xarg0, 0),
5391                                             const_binop (code, c1, c3, 1))),
5392                                const_binop (code, c2, c3, 1)));
5393
5394               if (! integer_onep (outer_div))
5395                 t = fold (build (code, type, t, convert (type, outer_div)));
5396
5397               if (have_save_expr)
5398                 t = save_expr (t);
5399
5400               return t;
5401             }
5402         }
5403
5404       goto binary;
5405
5406     case CEIL_MOD_EXPR:
5407     case FLOOR_MOD_EXPR:
5408     case ROUND_MOD_EXPR:
5409     case TRUNC_MOD_EXPR:
5410       if (integer_onep (arg1))
5411         return omit_one_operand (type, integer_zero_node, arg0);
5412       if (integer_zerop (arg1))
5413         return t;
5414
5415       /* Look for ((a * C1) % C3) or (((a * C1) + C2) % C3),
5416          where C1 % C3 == 0.  Handle similarly to the division case,
5417          but don't bother with SAVE_EXPRs.  */
5418
5419       if (TREE_CODE (arg1) == INTEGER_CST
5420           && ! integer_zerop (arg1))
5421         {
5422           tree c2 = integer_zero_node;
5423           tree xarg0 = arg0;
5424
5425           if (TREE_CODE (xarg0) == PLUS_EXPR
5426               && TREE_CODE (TREE_OPERAND (xarg0, 1)) == INTEGER_CST)
5427             c2 = TREE_OPERAND (xarg0, 1), xarg0 = TREE_OPERAND (xarg0, 0);
5428           else if (TREE_CODE (xarg0) == MINUS_EXPR
5429                    && TREE_CODE (TREE_OPERAND (xarg0, 1)) == INTEGER_CST
5430                    && ! TREE_UNSIGNED (type))
5431             {
5432               c2 = fold (build1 (NEGATE_EXPR, type, TREE_OPERAND (xarg0, 1)));
5433               xarg0 = TREE_OPERAND (xarg0, 0);
5434             }
5435
5436           STRIP_NOPS (xarg0);
5437
5438           if (TREE_CODE (xarg0) == MULT_EXPR
5439               && TREE_CODE (TREE_OPERAND (xarg0, 1)) == INTEGER_CST
5440               && integer_zerop (const_binop (TRUNC_MOD_EXPR,
5441                                              TREE_OPERAND (xarg0, 1),
5442                                              arg1, 1))
5443               && tree_int_cst_sgn (c2) >= 0)
5444             /* The result is (C2%C3).  */
5445             return omit_one_operand (type, const_binop (code, c2, arg1, 1),
5446                                      TREE_OPERAND (xarg0, 0));
5447         }
5448
5449       goto binary;
5450
5451     case LSHIFT_EXPR:
5452     case RSHIFT_EXPR:
5453     case LROTATE_EXPR:
5454     case RROTATE_EXPR:
5455       if (integer_zerop (arg1))
5456         return non_lvalue (convert (type, arg0));
5457       /* Since negative shift count is not well-defined,
5458          don't try to compute it in the compiler.  */
5459       if (TREE_CODE (arg1) == INTEGER_CST && tree_int_cst_sgn (arg1) < 0)
5460         return t;
5461       /* Rewrite an LROTATE_EXPR by a constant into an
5462          RROTATE_EXPR by a new constant.  */
5463       if (code == LROTATE_EXPR && TREE_CODE (arg1) == INTEGER_CST)
5464         {
5465           TREE_SET_CODE (t, RROTATE_EXPR);
5466           code = RROTATE_EXPR;
5467           TREE_OPERAND (t, 1) = arg1
5468             = const_binop
5469               (MINUS_EXPR,
5470                convert (TREE_TYPE (arg1),
5471                         build_int_2 (GET_MODE_BITSIZE (TYPE_MODE (type)), 0)),
5472                arg1, 0);
5473           if (tree_int_cst_sgn (arg1) < 0)
5474             return t;
5475         }
5476
5477       /* If we have a rotate of a bit operation with the rotate count and
5478          the second operand of the bit operation both constant,
5479          permute the two operations.  */
5480       if (code == RROTATE_EXPR && TREE_CODE (arg1) == INTEGER_CST
5481           && (TREE_CODE (arg0) == BIT_AND_EXPR
5482               || TREE_CODE (arg0) == BIT_ANDTC_EXPR
5483               || TREE_CODE (arg0) == BIT_IOR_EXPR
5484               || TREE_CODE (arg0) == BIT_XOR_EXPR)
5485           && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST)
5486         return fold (build (TREE_CODE (arg0), type,
5487                             fold (build (code, type,
5488                                          TREE_OPERAND (arg0, 0), arg1)),
5489                             fold (build (code, type,
5490                                          TREE_OPERAND (arg0, 1), arg1))));
5491
5492       /* Two consecutive rotates adding up to the width of the mode can
5493          be ignored.  */
5494       if (code == RROTATE_EXPR && TREE_CODE (arg1) == INTEGER_CST
5495           && TREE_CODE (arg0) == RROTATE_EXPR
5496           && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
5497           && TREE_INT_CST_HIGH (arg1) == 0
5498           && TREE_INT_CST_HIGH (TREE_OPERAND (arg0, 1)) == 0
5499           && ((TREE_INT_CST_LOW (arg1)
5500                + TREE_INT_CST_LOW (TREE_OPERAND (arg0, 1)))
5501               == GET_MODE_BITSIZE (TYPE_MODE (type))))
5502         return TREE_OPERAND (arg0, 0);
5503
5504       goto binary;
5505
5506     case MIN_EXPR:
5507       if (operand_equal_p (arg0, arg1, 0))
5508         return arg0;
5509       if (INTEGRAL_TYPE_P (type)
5510           && operand_equal_p (arg1, TYPE_MIN_VALUE (type), 1))
5511         return omit_one_operand (type, arg1, arg0);
5512       goto associate;
5513
5514     case MAX_EXPR:
5515       if (operand_equal_p (arg0, arg1, 0))
5516         return arg0;
5517       if (INTEGRAL_TYPE_P (type)
5518           && TYPE_MAX_VALUE (type)
5519           && operand_equal_p (arg1, TYPE_MAX_VALUE (type), 1))
5520         return omit_one_operand (type, arg1, arg0);
5521       goto associate;
5522
5523     case TRUTH_NOT_EXPR:
5524       /* Note that the operand of this must be an int
5525          and its values must be 0 or 1.
5526          ("true" is a fixed value perhaps depending on the language,
5527          but we don't handle values other than 1 correctly yet.)  */
5528       tem = invert_truthvalue (arg0);
5529       /* Avoid infinite recursion.  */
5530       if (TREE_CODE (tem) == TRUTH_NOT_EXPR)
5531         return t;
5532       return convert (type, tem);
5533
5534     case TRUTH_ANDIF_EXPR:
5535       /* Note that the operands of this must be ints
5536          and their values must be 0 or 1.
5537          ("true" is a fixed value perhaps depending on the language.)  */
5538       /* If first arg is constant zero, return it.  */
5539       if (integer_zerop (arg0))
5540         return arg0;
5541     case TRUTH_AND_EXPR:
5542       /* If either arg is constant true, drop it.  */
5543       if (TREE_CODE (arg0) == INTEGER_CST && ! integer_zerop (arg0))
5544         return non_lvalue (arg1);
5545       if (TREE_CODE (arg1) == INTEGER_CST && ! integer_zerop (arg1))
5546         return non_lvalue (arg0);
5547       /* If second arg is constant zero, result is zero, but first arg
5548          must be evaluated.  */
5549       if (integer_zerop (arg1))
5550         return omit_one_operand (type, arg1, arg0);
5551       /* Likewise for first arg, but note that only the TRUTH_AND_EXPR
5552          case will be handled here.  */
5553       if (integer_zerop (arg0))
5554         return omit_one_operand (type, arg0, arg1);
5555
5556     truth_andor:
5557       /* We only do these simplifications if we are optimizing.  */
5558       if (!optimize)
5559         return t;
5560
5561       /* Check for things like (A || B) && (A || C).  We can convert this
5562          to A || (B && C).  Note that either operator can be any of the four
5563          truth and/or operations and the transformation will still be
5564          valid.   Also note that we only care about order for the
5565          ANDIF and ORIF operators.  If B contains side effects, this
5566          might change the truth-value of A. */
5567       if (TREE_CODE (arg0) == TREE_CODE (arg1)
5568           && (TREE_CODE (arg0) == TRUTH_ANDIF_EXPR
5569               || TREE_CODE (arg0) == TRUTH_ORIF_EXPR
5570               || TREE_CODE (arg0) == TRUTH_AND_EXPR
5571               || TREE_CODE (arg0) == TRUTH_OR_EXPR)
5572           && ! TREE_SIDE_EFFECTS (TREE_OPERAND (arg0, 1)))
5573         {
5574           tree a00 = TREE_OPERAND (arg0, 0);
5575           tree a01 = TREE_OPERAND (arg0, 1);
5576           tree a10 = TREE_OPERAND (arg1, 0);
5577           tree a11 = TREE_OPERAND (arg1, 1);
5578           int commutative = ((TREE_CODE (arg0) == TRUTH_OR_EXPR
5579                               || TREE_CODE (arg0) == TRUTH_AND_EXPR)
5580                              && (code == TRUTH_AND_EXPR
5581                                  || code == TRUTH_OR_EXPR));
5582
5583           if (operand_equal_p (a00, a10, 0))
5584             return fold (build (TREE_CODE (arg0), type, a00,
5585                                 fold (build (code, type, a01, a11))));
5586           else if (commutative && operand_equal_p (a00, a11, 0))
5587             return fold (build (TREE_CODE (arg0), type, a00,
5588                                 fold (build (code, type, a01, a10))));
5589           else if (commutative && operand_equal_p (a01, a10, 0))
5590             return fold (build (TREE_CODE (arg0), type, a01,
5591                                 fold (build (code, type, a00, a11))));
5592
5593           /* This case if tricky because we must either have commutative
5594              operators or else A10 must not have side-effects.  */
5595
5596           else if ((commutative || ! TREE_SIDE_EFFECTS (a10))
5597                    && operand_equal_p (a01, a11, 0))
5598             return fold (build (TREE_CODE (arg0), type,
5599                                 fold (build (code, type, a00, a10)),
5600                                 a01));
5601         }
5602
5603       /* See if we can build a range comparison.  */
5604       if (0 != (tem = fold_range_test (t)))
5605         return tem;
5606
5607       /* Check for the possibility of merging component references.  If our
5608          lhs is another similar operation, try to merge its rhs with our
5609          rhs.  Then try to merge our lhs and rhs.  */
5610       if (TREE_CODE (arg0) == code
5611           && 0 != (tem = fold_truthop (code, type,
5612                                        TREE_OPERAND (arg0, 1), arg1)))
5613         return fold (build (code, type, TREE_OPERAND (arg0, 0), tem));
5614
5615       if ((tem = fold_truthop (code, type, arg0, arg1)) != 0)
5616         return tem;
5617
5618       return t;
5619
5620     case TRUTH_ORIF_EXPR:
5621       /* Note that the operands of this must be ints
5622          and their values must be 0 or true.
5623          ("true" is a fixed value perhaps depending on the language.)  */
5624       /* If first arg is constant true, return it.  */
5625       if (TREE_CODE (arg0) == INTEGER_CST && ! integer_zerop (arg0))
5626         return arg0;
5627     case TRUTH_OR_EXPR:
5628       /* If either arg is constant zero, drop it.  */
5629       if (TREE_CODE (arg0) == INTEGER_CST && integer_zerop (arg0))
5630         return non_lvalue (arg1);
5631       if (TREE_CODE (arg1) == INTEGER_CST && integer_zerop (arg1))
5632         return non_lvalue (arg0);
5633       /* If second arg is constant true, result is true, but we must
5634          evaluate first arg.  */
5635       if (TREE_CODE (arg1) == INTEGER_CST && ! integer_zerop (arg1))
5636         return omit_one_operand (type, arg1, arg0);
5637       /* Likewise for first arg, but note this only occurs here for
5638          TRUTH_OR_EXPR.  */
5639       if (TREE_CODE (arg0) == INTEGER_CST && ! integer_zerop (arg0))
5640         return omit_one_operand (type, arg0, arg1);
5641       goto truth_andor;
5642
5643     case TRUTH_XOR_EXPR:
5644       /* If either arg is constant zero, drop it.  */
5645       if (integer_zerop (arg0))
5646         return non_lvalue (arg1);
5647       if (integer_zerop (arg1))
5648         return non_lvalue (arg0);
5649       /* If either arg is constant true, this is a logical inversion.  */
5650       if (integer_onep (arg0))
5651         return non_lvalue (invert_truthvalue (arg1));
5652       if (integer_onep (arg1))
5653         return non_lvalue (invert_truthvalue (arg0));
5654       return t;
5655
5656     case EQ_EXPR:
5657     case NE_EXPR:
5658     case LT_EXPR:
5659     case GT_EXPR:
5660     case LE_EXPR:
5661     case GE_EXPR:
5662       /* If one arg is a constant integer, put it last.  */
5663       if (TREE_CODE (arg0) == INTEGER_CST
5664           && TREE_CODE (arg1) != INTEGER_CST)
5665         {
5666           TREE_OPERAND (t, 0) = arg1;
5667           TREE_OPERAND (t, 1) = arg0;
5668           arg0 = TREE_OPERAND (t, 0);
5669           arg1 = TREE_OPERAND (t, 1);
5670           code = swap_tree_comparison (code);
5671           TREE_SET_CODE (t, code);
5672         }
5673
5674       /* Convert foo++ == CONST into ++foo == CONST + INCR.
5675          First, see if one arg is constant; find the constant arg
5676          and the other one.  */
5677       {
5678         tree constop = 0, varop = NULL_TREE;
5679         int constopnum = -1;
5680
5681         if (TREE_CONSTANT (arg1))
5682           constopnum = 1, constop = arg1, varop = arg0;
5683         if (TREE_CONSTANT (arg0))
5684           constopnum = 0, constop = arg0, varop = arg1;
5685
5686         if (constop && TREE_CODE (varop) == POSTINCREMENT_EXPR)
5687           {
5688             /* This optimization is invalid for ordered comparisons
5689                if CONST+INCR overflows or if foo+incr might overflow.
5690                This optimization is invalid for floating point due to rounding.
5691                For pointer types we assume overflow doesn't happen.  */
5692             if (POINTER_TYPE_P (TREE_TYPE (varop))
5693                 || (! FLOAT_TYPE_P (TREE_TYPE (varop))
5694                     && (code == EQ_EXPR || code == NE_EXPR)))
5695               {
5696                 tree newconst
5697                   = fold (build (PLUS_EXPR, TREE_TYPE (varop),
5698                                  constop, TREE_OPERAND (varop, 1)));
5699                 TREE_SET_CODE (varop, PREINCREMENT_EXPR);
5700
5701                 /* If VAROP is a reference to a bitfield, we must mask
5702                    the constant by the width of the field.  */
5703                 if (TREE_CODE (TREE_OPERAND (varop, 0)) == COMPONENT_REF
5704                     && DECL_BIT_FIELD(TREE_OPERAND
5705                                       (TREE_OPERAND (varop, 0), 1)))
5706                   {
5707                     int size
5708                       = TREE_INT_CST_LOW (DECL_SIZE
5709                                           (TREE_OPERAND
5710                                            (TREE_OPERAND (varop, 0), 1)));
5711                     tree mask, unsigned_type;
5712                     int precision;
5713                     tree folded_compare;
5714
5715                     /* First check whether the comparison would come out
5716                        always the same.  If we don't do that we would
5717                        change the meaning with the masking.  */
5718                     if (constopnum == 0)
5719                       folded_compare = fold (build (code, type, constop,
5720                                                     TREE_OPERAND (varop, 0)));
5721                     else
5722                       folded_compare = fold (build (code, type,
5723                                                     TREE_OPERAND (varop, 0),
5724                                                     constop));
5725                     if (integer_zerop (folded_compare)
5726                         || integer_onep (folded_compare))
5727                       return omit_one_operand (type, folded_compare, varop);
5728
5729                     unsigned_type = type_for_size (size, 1);
5730                     precision = TYPE_PRECISION (unsigned_type);
5731                     mask = build_int_2 (~0, ~0);
5732                     TREE_TYPE (mask) = unsigned_type;
5733                     force_fit_type (mask, 0);
5734                     mask = const_binop (RSHIFT_EXPR, mask,
5735                                         size_int (precision - size), 0);
5736                     newconst = fold (build (BIT_AND_EXPR,
5737                                             TREE_TYPE (varop), newconst,
5738                                             convert (TREE_TYPE (varop),
5739                                                      mask)));
5740                   }
5741
5742
5743                 t = build (code, type, TREE_OPERAND (t, 0),
5744                            TREE_OPERAND (t, 1));
5745                 TREE_OPERAND (t, constopnum) = newconst;
5746                 return t;
5747               }
5748           }
5749         else if (constop && TREE_CODE (varop) == POSTDECREMENT_EXPR)
5750           {
5751             if (POINTER_TYPE_P (TREE_TYPE (varop))
5752                 || (! FLOAT_TYPE_P (TREE_TYPE (varop))
5753                     && (code == EQ_EXPR || code == NE_EXPR)))
5754               {
5755                 tree newconst
5756                   = fold (build (MINUS_EXPR, TREE_TYPE (varop),
5757                                  constop, TREE_OPERAND (varop, 1)));
5758                 TREE_SET_CODE (varop, PREDECREMENT_EXPR);
5759
5760                 if (TREE_CODE (TREE_OPERAND (varop, 0)) == COMPONENT_REF
5761                     && DECL_BIT_FIELD(TREE_OPERAND
5762                                       (TREE_OPERAND (varop, 0), 1)))
5763                   {
5764                     int size
5765                       = TREE_INT_CST_LOW (DECL_SIZE
5766                                           (TREE_OPERAND
5767                                            (TREE_OPERAND (varop, 0), 1)));
5768                     tree mask, unsigned_type;
5769                     int precision;
5770                     tree folded_compare;
5771
5772                     if (constopnum == 0)
5773                       folded_compare = fold (build (code, type, constop,
5774                                                     TREE_OPERAND (varop, 0)));
5775                     else
5776                       folded_compare = fold (build (code, type,
5777                                                     TREE_OPERAND (varop, 0),
5778                                                     constop));
5779                     if (integer_zerop (folded_compare)
5780                         || integer_onep (folded_compare))
5781                       return omit_one_operand (type, folded_compare, varop);
5782
5783                     unsigned_type = type_for_size (size, 1);
5784                     precision = TYPE_PRECISION (unsigned_type);
5785                     mask = build_int_2 (~0, ~0);
5786                     TREE_TYPE (mask) = TREE_TYPE (varop);
5787                     force_fit_type (mask, 0);
5788                     mask = const_binop (RSHIFT_EXPR, mask,
5789                                         size_int (precision - size), 0);
5790                     newconst = fold (build (BIT_AND_EXPR,
5791                                             TREE_TYPE (varop), newconst,
5792                                             convert (TREE_TYPE (varop),
5793                                                      mask)));
5794                   }
5795
5796
5797                 t = build (code, type, TREE_OPERAND (t, 0),
5798                            TREE_OPERAND (t, 1));
5799                 TREE_OPERAND (t, constopnum) = newconst;
5800                 return t;
5801               }
5802           }
5803       }
5804
5805       /* Change X >= CST to X > (CST - 1) if CST is positive.  */
5806       if (TREE_CODE (arg1) == INTEGER_CST
5807           && TREE_CODE (arg0) != INTEGER_CST
5808           && tree_int_cst_sgn (arg1) > 0)
5809         {
5810           switch (TREE_CODE (t))
5811             {
5812             case GE_EXPR:
5813               code = GT_EXPR;
5814               arg1 = const_binop (MINUS_EXPR, arg1, integer_one_node, 0);
5815               t = build (code, type, TREE_OPERAND (t, 0), arg1);
5816               break;
5817
5818             case LT_EXPR:
5819               code = LE_EXPR;
5820               arg1 = const_binop (MINUS_EXPR, arg1, integer_one_node, 0);
5821               t = build (code, type, TREE_OPERAND (t, 0), arg1);
5822               break;
5823
5824             default:
5825               break;
5826             }
5827         }
5828
5829       /* If this is an EQ or NE comparison with zero and ARG0 is
5830          (1 << foo) & bar, convert it to (bar >> foo) & 1.  Both require
5831          two operations, but the latter can be done in one less insn
5832          on machines that have only two-operand insns or on which a
5833          constant cannot be the first operand.  */
5834       if (integer_zerop (arg1) && (code == EQ_EXPR || code == NE_EXPR)
5835           && TREE_CODE (arg0) == BIT_AND_EXPR)
5836         {
5837           if (TREE_CODE (TREE_OPERAND (arg0, 0)) == LSHIFT_EXPR
5838               && integer_onep (TREE_OPERAND (TREE_OPERAND (arg0, 0), 0)))
5839             return
5840               fold (build (code, type,
5841                            build (BIT_AND_EXPR, TREE_TYPE (arg0),
5842                                   build (RSHIFT_EXPR,
5843                                          TREE_TYPE (TREE_OPERAND (arg0, 0)),
5844                                          TREE_OPERAND (arg0, 1),
5845                                          TREE_OPERAND (TREE_OPERAND (arg0, 0), 1)),
5846                                   convert (TREE_TYPE (arg0),
5847                                            integer_one_node)),
5848                            arg1));
5849           else if (TREE_CODE (TREE_OPERAND (arg0, 1)) == LSHIFT_EXPR
5850                    && integer_onep (TREE_OPERAND (TREE_OPERAND (arg0, 1), 0)))
5851             return
5852               fold (build (code, type,
5853                            build (BIT_AND_EXPR, TREE_TYPE (arg0),
5854                                   build (RSHIFT_EXPR,
5855                                          TREE_TYPE (TREE_OPERAND (arg0, 1)),
5856                                          TREE_OPERAND (arg0, 0),
5857                                          TREE_OPERAND (TREE_OPERAND (arg0, 1), 1)),
5858                                   convert (TREE_TYPE (arg0),
5859                                            integer_one_node)),
5860                            arg1));
5861         }
5862
5863       /* If this is an NE or EQ comparison of zero against the result of a
5864          signed MOD operation whose second operand is a power of 2, make
5865          the MOD operation unsigned since it is simpler and equivalent.  */
5866       if ((code == NE_EXPR || code == EQ_EXPR)
5867           && integer_zerop (arg1)
5868           && ! TREE_UNSIGNED (TREE_TYPE (arg0))
5869           && (TREE_CODE (arg0) == TRUNC_MOD_EXPR
5870               || TREE_CODE (arg0) == CEIL_MOD_EXPR
5871               || TREE_CODE (arg0) == FLOOR_MOD_EXPR
5872               || TREE_CODE (arg0) == ROUND_MOD_EXPR)
5873           && integer_pow2p (TREE_OPERAND (arg0, 1)))
5874         {
5875           tree newtype = unsigned_type (TREE_TYPE (arg0));
5876           tree newmod = build (TREE_CODE (arg0), newtype,
5877                                convert (newtype, TREE_OPERAND (arg0, 0)),
5878                                convert (newtype, TREE_OPERAND (arg0, 1)));
5879
5880           return build (code, type, newmod, convert (newtype, arg1));
5881         }
5882
5883       /* If this is an NE comparison of zero with an AND of one, remove the
5884          comparison since the AND will give the correct value.  */
5885       if (code == NE_EXPR && integer_zerop (arg1)
5886           && TREE_CODE (arg0) == BIT_AND_EXPR
5887           && integer_onep (TREE_OPERAND (arg0, 1)))
5888         return convert (type, arg0);
5889
5890       /* If we have (A & C) == C where C is a power of 2, convert this into
5891          (A & C) != 0.  Similarly for NE_EXPR.  */
5892       if ((code == EQ_EXPR || code == NE_EXPR)
5893           && TREE_CODE (arg0) == BIT_AND_EXPR
5894           && integer_pow2p (TREE_OPERAND (arg0, 1))
5895           && operand_equal_p (TREE_OPERAND (arg0, 1), arg1, 0))
5896         return build (code == EQ_EXPR ? NE_EXPR : EQ_EXPR, type,
5897                       arg0, integer_zero_node);
5898
5899       /* If X is unsigned, convert X < (1 << Y) into X >> Y == 0
5900          and similarly for >= into !=.  */
5901       if ((code == LT_EXPR || code == GE_EXPR)
5902           && TREE_UNSIGNED (TREE_TYPE (arg0))
5903           && TREE_CODE (arg1) == LSHIFT_EXPR
5904           && integer_onep (TREE_OPERAND (arg1, 0)))
5905         return build (code == LT_EXPR ? EQ_EXPR : NE_EXPR, type,
5906                       build (RSHIFT_EXPR, TREE_TYPE (arg0), arg0,
5907                              TREE_OPERAND (arg1, 1)),
5908                       convert (TREE_TYPE (arg0), integer_zero_node));
5909
5910       else if ((code == LT_EXPR || code == GE_EXPR)
5911                && TREE_UNSIGNED (TREE_TYPE (arg0))
5912                && (TREE_CODE (arg1) == NOP_EXPR
5913                    || TREE_CODE (arg1) == CONVERT_EXPR)
5914                && TREE_CODE (TREE_OPERAND (arg1, 0)) == LSHIFT_EXPR
5915                && integer_onep (TREE_OPERAND (TREE_OPERAND (arg1, 0), 0)))
5916         return
5917           build (code == LT_EXPR ? EQ_EXPR : NE_EXPR, type,
5918                  convert (TREE_TYPE (arg0),
5919                           build (RSHIFT_EXPR, TREE_TYPE (arg0), arg0,
5920                                  TREE_OPERAND (TREE_OPERAND (arg1, 0), 1))),
5921                  convert (TREE_TYPE (arg0), integer_zero_node));
5922
5923       /* Simplify comparison of something with itself.  (For IEEE
5924          floating-point, we can only do some of these simplifications.)  */
5925       if (operand_equal_p (arg0, arg1, 0))
5926         {
5927           switch (code)
5928             {
5929             case EQ_EXPR:
5930             case GE_EXPR:
5931             case LE_EXPR:
5932               if (INTEGRAL_TYPE_P (TREE_TYPE (arg0)))
5933                 return constant_boolean_node (1, type);
5934               code = EQ_EXPR;
5935               TREE_SET_CODE (t, code);
5936               break;
5937
5938             case NE_EXPR:
5939               /* For NE, we can only do this simplification if integer.  */
5940               if (! INTEGRAL_TYPE_P (TREE_TYPE (arg0)))
5941                 break;
5942               /* ... fall through ...  */
5943             case GT_EXPR:
5944             case LT_EXPR:
5945               return constant_boolean_node (0, type);
5946             default:
5947               abort ();
5948             }
5949         }
5950
5951       /* An unsigned comparison against 0 can be simplified.  */
5952       if (integer_zerop (arg1)
5953           && (INTEGRAL_TYPE_P (TREE_TYPE (arg1))
5954               || POINTER_TYPE_P (TREE_TYPE (arg1)))
5955           && TREE_UNSIGNED (TREE_TYPE (arg1)))
5956         {
5957           switch (TREE_CODE (t))
5958             {
5959             case GT_EXPR:
5960               code = NE_EXPR;
5961               TREE_SET_CODE (t, NE_EXPR);
5962               break;
5963             case LE_EXPR:
5964               code = EQ_EXPR;
5965               TREE_SET_CODE (t, EQ_EXPR);
5966               break;
5967             case GE_EXPR:
5968               return omit_one_operand (type,
5969                                        convert (type, integer_one_node),
5970                                        arg0);
5971             case LT_EXPR:
5972               return omit_one_operand (type,
5973                                        convert (type, integer_zero_node),
5974                                        arg0);
5975             default:
5976               break;
5977             }
5978         }
5979
5980       /* An unsigned <= 0x7fffffff can be simplified.  */
5981       {
5982         int width = TYPE_PRECISION (TREE_TYPE (arg1));
5983         if (TREE_CODE (arg1) == INTEGER_CST
5984             && ! TREE_CONSTANT_OVERFLOW (arg1)
5985             && width <= HOST_BITS_PER_WIDE_INT
5986             && TREE_INT_CST_LOW (arg1) == ((HOST_WIDE_INT) 1 << (width - 1)) - 1
5987             && TREE_INT_CST_HIGH (arg1) == 0
5988             && (INTEGRAL_TYPE_P (TREE_TYPE (arg1))
5989                 || POINTER_TYPE_P (TREE_TYPE (arg1)))
5990             && TREE_UNSIGNED (TREE_TYPE (arg1)))
5991           {
5992             switch (TREE_CODE (t))
5993               {
5994               case LE_EXPR:
5995                 return fold (build (GE_EXPR, type,
5996                                     convert (signed_type (TREE_TYPE (arg0)),
5997                                              arg0),
5998                                     convert (signed_type (TREE_TYPE (arg1)),
5999                                              integer_zero_node)));
6000               case GT_EXPR:
6001                 return fold (build (LT_EXPR, type,
6002                                     convert (signed_type (TREE_TYPE (arg0)),
6003                                              arg0),
6004                                     convert (signed_type (TREE_TYPE (arg1)),
6005                                              integer_zero_node)));
6006               default:
6007                 break;
6008               }
6009           }
6010       }
6011
6012       /* If we are comparing an expression that just has comparisons
6013          of two integer values, arithmetic expressions of those comparisons,
6014          and constants, we can simplify it.  There are only three cases
6015          to check: the two values can either be equal, the first can be
6016          greater, or the second can be greater.  Fold the expression for
6017          those three values.  Since each value must be 0 or 1, we have
6018          eight possibilities, each of which corresponds to the constant 0
6019          or 1 or one of the six possible comparisons.
6020
6021          This handles common cases like (a > b) == 0 but also handles
6022          expressions like  ((x > y) - (y > x)) > 0, which supposedly
6023          occur in macroized code.  */
6024
6025       if (TREE_CODE (arg1) == INTEGER_CST && TREE_CODE (arg0) != INTEGER_CST)
6026         {
6027           tree cval1 = 0, cval2 = 0;
6028           int save_p = 0;
6029
6030           if (twoval_comparison_p (arg0, &cval1, &cval2, &save_p)
6031               /* Don't handle degenerate cases here; they should already
6032                  have been handled anyway.  */
6033               && cval1 != 0 && cval2 != 0
6034               && ! (TREE_CONSTANT (cval1) && TREE_CONSTANT (cval2))
6035               && TREE_TYPE (cval1) == TREE_TYPE (cval2)
6036               && INTEGRAL_TYPE_P (TREE_TYPE (cval1))
6037               && TYPE_MAX_VALUE (TREE_TYPE (cval1))
6038               && TYPE_MAX_VALUE (TREE_TYPE (cval2))
6039               && ! operand_equal_p (TYPE_MIN_VALUE (TREE_TYPE (cval1)),
6040                                     TYPE_MAX_VALUE (TREE_TYPE (cval2)), 0))
6041             {
6042               tree maxval = TYPE_MAX_VALUE (TREE_TYPE (cval1));
6043               tree minval = TYPE_MIN_VALUE (TREE_TYPE (cval1));
6044
6045               /* We can't just pass T to eval_subst in case cval1 or cval2
6046                  was the same as ARG1.  */
6047
6048               tree high_result
6049                 = fold (build (code, type,
6050                                eval_subst (arg0, cval1, maxval, cval2, minval),
6051                                arg1));
6052               tree equal_result
6053                 = fold (build (code, type,
6054                                eval_subst (arg0, cval1, maxval, cval2, maxval),
6055                                arg1));
6056               tree low_result
6057                 = fold (build (code, type,
6058                                eval_subst (arg0, cval1, minval, cval2, maxval),
6059                                arg1));
6060
6061               /* All three of these results should be 0 or 1.  Confirm they
6062                  are.  Then use those values to select the proper code
6063                  to use.  */
6064
6065               if ((integer_zerop (high_result)
6066                    || integer_onep (high_result))
6067                   && (integer_zerop (equal_result)
6068                       || integer_onep (equal_result))
6069                   && (integer_zerop (low_result)
6070                       || integer_onep (low_result)))
6071                 {
6072                   /* Make a 3-bit mask with the high-order bit being the
6073                      value for `>', the next for '=', and the low for '<'.  */
6074                   switch ((integer_onep (high_result) * 4)
6075                           + (integer_onep (equal_result) * 2)
6076                           + integer_onep (low_result))
6077                     {
6078                     case 0:
6079                       /* Always false.  */
6080                       return omit_one_operand (type, integer_zero_node, arg0);
6081                     case 1:
6082                       code = LT_EXPR;
6083                       break;
6084                     case 2:
6085                       code = EQ_EXPR;
6086                       break;
6087                     case 3:
6088                       code = LE_EXPR;
6089                       break;
6090                     case 4:
6091                       code = GT_EXPR;
6092                       break;
6093                     case 5:
6094                       code = NE_EXPR;
6095                       break;
6096                     case 6:
6097                       code = GE_EXPR;
6098                       break;
6099                     case 7:
6100                       /* Always true.  */
6101                       return omit_one_operand (type, integer_one_node, arg0);
6102                     }
6103
6104                   t = build (code, type, cval1, cval2);
6105                   if (save_p)
6106                     return save_expr (t);
6107                   else
6108                     return fold (t);
6109                 }
6110             }
6111         }
6112
6113       /* If this is a comparison of a field, we may be able to simplify it.  */
6114       if ((TREE_CODE (arg0) == COMPONENT_REF
6115            || TREE_CODE (arg0) == BIT_FIELD_REF)
6116           && (code == EQ_EXPR || code == NE_EXPR)
6117           /* Handle the constant case even without -O
6118              to make sure the warnings are given.  */
6119           && (optimize || TREE_CODE (arg1) == INTEGER_CST))
6120         {
6121           t1 = optimize_bit_field_compare (code, type, arg0, arg1);
6122           return t1 ? t1 : t;
6123         }
6124
6125       /* If this is a comparison of complex values and either or both sides
6126          are a COMPLEX_EXPR or COMPLEX_CST, it is best to split up the
6127          comparisons and join them with a TRUTH_ANDIF_EXPR or TRUTH_ORIF_EXPR.
6128          This may prevent needless evaluations.  */
6129       if ((code == EQ_EXPR || code == NE_EXPR)
6130           && TREE_CODE (TREE_TYPE (arg0)) == COMPLEX_TYPE
6131           && (TREE_CODE (arg0) == COMPLEX_EXPR
6132               || TREE_CODE (arg1) == COMPLEX_EXPR
6133               || TREE_CODE (arg0) == COMPLEX_CST
6134               || TREE_CODE (arg1) == COMPLEX_CST))
6135         {
6136           tree subtype = TREE_TYPE (TREE_TYPE (arg0));
6137           tree real0, imag0, real1, imag1;
6138
6139           arg0 = save_expr (arg0);
6140           arg1 = save_expr (arg1);
6141           real0 = fold (build1 (REALPART_EXPR, subtype, arg0));
6142           imag0 = fold (build1 (IMAGPART_EXPR, subtype, arg0));
6143           real1 = fold (build1 (REALPART_EXPR, subtype, arg1));
6144           imag1 = fold (build1 (IMAGPART_EXPR, subtype, arg1));
6145
6146           return fold (build ((code == EQ_EXPR ? TRUTH_ANDIF_EXPR
6147                                : TRUTH_ORIF_EXPR),
6148                               type,
6149                               fold (build (code, type, real0, real1)),
6150                               fold (build (code, type, imag0, imag1))));
6151         }
6152
6153       /* From here on, the only cases we handle are when the result is
6154          known to be a constant.
6155
6156          To compute GT, swap the arguments and do LT.
6157          To compute GE, do LT and invert the result.
6158          To compute LE, swap the arguments, do LT and invert the result.
6159          To compute NE, do EQ and invert the result.
6160
6161          Therefore, the code below must handle only EQ and LT.  */
6162
6163       if (code == LE_EXPR || code == GT_EXPR)
6164         {
6165           tem = arg0, arg0 = arg1, arg1 = tem;
6166           code = swap_tree_comparison (code);
6167         }
6168
6169       /* Note that it is safe to invert for real values here because we
6170          will check below in the one case that it matters.  */
6171
6172       invert = 0;
6173       if (code == NE_EXPR || code == GE_EXPR)
6174         {
6175           invert = 1;
6176           code = invert_tree_comparison (code);
6177         }
6178
6179       /* Compute a result for LT or EQ if args permit;
6180          otherwise return T.  */
6181       if (TREE_CODE (arg0) == INTEGER_CST && TREE_CODE (arg1) == INTEGER_CST)
6182         {
6183           if (code == EQ_EXPR)
6184             t1 = build_int_2 ((TREE_INT_CST_LOW (arg0)
6185                                == TREE_INT_CST_LOW (arg1))
6186                               && (TREE_INT_CST_HIGH (arg0)
6187                                   == TREE_INT_CST_HIGH (arg1)),
6188                               0);
6189           else
6190             t1 = build_int_2 ((TREE_UNSIGNED (TREE_TYPE (arg0))
6191                                ? INT_CST_LT_UNSIGNED (arg0, arg1)
6192                                : INT_CST_LT (arg0, arg1)),
6193                               0);
6194         }
6195
6196 #if 0 /* This is no longer useful, but breaks some real code.  */
6197       /* Assume a nonexplicit constant cannot equal an explicit one,
6198          since such code would be undefined anyway.
6199          Exception: on sysvr4, using #pragma weak,
6200          a label can come out as 0.  */
6201       else if (TREE_CODE (arg1) == INTEGER_CST
6202                && !integer_zerop (arg1)
6203                && TREE_CONSTANT (arg0)
6204                && TREE_CODE (arg0) == ADDR_EXPR
6205                && code == EQ_EXPR)
6206         t1 = build_int_2 (0, 0);
6207 #endif
6208       /* Two real constants can be compared explicitly.  */
6209       else if (TREE_CODE (arg0) == REAL_CST && TREE_CODE (arg1) == REAL_CST)
6210         {
6211           /* If either operand is a NaN, the result is false with two
6212              exceptions: First, an NE_EXPR is true on NaNs, but that case
6213              is already handled correctly since we will be inverting the
6214              result for NE_EXPR.  Second, if we had inverted a LE_EXPR
6215              or a GE_EXPR into a LT_EXPR, we must return true so that it
6216              will be inverted into false.  */
6217
6218           if (REAL_VALUE_ISNAN (TREE_REAL_CST (arg0))
6219               || REAL_VALUE_ISNAN (TREE_REAL_CST (arg1)))
6220             t1 = build_int_2 (invert && code == LT_EXPR, 0);
6221
6222           else if (code == EQ_EXPR)
6223             t1 = build_int_2 (REAL_VALUES_EQUAL (TREE_REAL_CST (arg0),
6224                                                  TREE_REAL_CST (arg1)),
6225                               0);
6226           else
6227             t1 = build_int_2 (REAL_VALUES_LESS (TREE_REAL_CST (arg0),
6228                                                 TREE_REAL_CST (arg1)),
6229                               0);
6230         }
6231
6232       if (t1 == NULL_TREE)
6233         return t;
6234
6235       if (invert)
6236         TREE_INT_CST_LOW (t1) ^= 1;
6237
6238       TREE_TYPE (t1) = type;
6239       if (TREE_CODE (type) == BOOLEAN_TYPE)
6240         return truthvalue_conversion (t1);
6241       return t1;
6242
6243     case COND_EXPR:
6244       /* Pedantic ANSI C says that a conditional expression is never an lvalue,
6245          so all simple results must be passed through pedantic_non_lvalue.  */
6246       if (TREE_CODE (arg0) == INTEGER_CST)
6247         return pedantic_non_lvalue
6248           (TREE_OPERAND (t, (integer_zerop (arg0) ? 2 : 1)));
6249       else if (operand_equal_p (arg1, TREE_OPERAND (expr, 2), 0))
6250         return pedantic_omit_one_operand (type, arg1, arg0);
6251
6252       /* If the second operand is zero, invert the comparison and swap
6253          the second and third operands.  Likewise if the second operand
6254          is constant and the third is not or if the third operand is
6255          equivalent to the first operand of the comparison.  */
6256
6257       if (integer_zerop (arg1)
6258           || (TREE_CONSTANT (arg1) && ! TREE_CONSTANT (TREE_OPERAND (t, 2)))
6259           || (TREE_CODE_CLASS (TREE_CODE (arg0)) == '<'
6260               && operand_equal_for_comparison_p (TREE_OPERAND (arg0, 0),
6261                                                  TREE_OPERAND (t, 2),
6262                                                  TREE_OPERAND (arg0, 1))))
6263         {
6264           /* See if this can be inverted.  If it can't, possibly because
6265              it was a floating-point inequality comparison, don't do
6266              anything.  */
6267           tem = invert_truthvalue (arg0);
6268
6269           if (TREE_CODE (tem) != TRUTH_NOT_EXPR)
6270             {
6271               t = build (code, type, tem,
6272                          TREE_OPERAND (t, 2), TREE_OPERAND (t, 1));
6273               arg0 = tem;
6274               /* arg1 should be the first argument of the new T.  */
6275               arg1 = TREE_OPERAND (t, 1);
6276               STRIP_NOPS (arg1);
6277             }
6278         }
6279
6280       /* If we have A op B ? A : C, we may be able to convert this to a
6281          simpler expression, depending on the operation and the values
6282          of B and C.  IEEE floating point prevents this though,
6283          because A or B might be -0.0 or a NaN.  */
6284
6285       if (TREE_CODE_CLASS (TREE_CODE (arg0)) == '<'
6286           && (TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
6287               || ! FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (arg0, 0)))
6288               || flag_fast_math)
6289           && operand_equal_for_comparison_p (TREE_OPERAND (arg0, 0),
6290                                              arg1, TREE_OPERAND (arg0, 1)))
6291         {
6292           tree arg2 = TREE_OPERAND (t, 2);
6293           enum tree_code comp_code = TREE_CODE (arg0);
6294
6295           STRIP_NOPS (arg2);
6296
6297           /* If we have A op 0 ? A : -A, this is A, -A, abs (A), or abs (-A),
6298              depending on the comparison operation.  */
6299           if ((FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (arg0, 1)))
6300                ? real_zerop (TREE_OPERAND (arg0, 1))
6301                : integer_zerop (TREE_OPERAND (arg0, 1)))
6302               && TREE_CODE (arg2) == NEGATE_EXPR
6303               && operand_equal_p (TREE_OPERAND (arg2, 0), arg1, 0))
6304             switch (comp_code)
6305               {
6306               case EQ_EXPR:
6307                 return pedantic_non_lvalue
6308                   (fold (build1 (NEGATE_EXPR, type, arg1)));
6309               case NE_EXPR:
6310                 return pedantic_non_lvalue (convert (type, arg1));
6311               case GE_EXPR:
6312               case GT_EXPR:
6313                 if (TREE_UNSIGNED (TREE_TYPE (arg1)))
6314                   arg1 = convert (signed_type (TREE_TYPE (arg1)), arg1);
6315                 return pedantic_non_lvalue
6316                   (convert (type, fold (build1 (ABS_EXPR,
6317                                                 TREE_TYPE (arg1), arg1))));
6318               case LE_EXPR:
6319               case LT_EXPR:
6320                 if (TREE_UNSIGNED (TREE_TYPE (arg1)))
6321                   arg1 = convert (signed_type (TREE_TYPE (arg1)), arg1);
6322                 return pedantic_non_lvalue
6323                   (fold (build1 (NEGATE_EXPR, type,
6324                                  convert (type,
6325                                           fold (build1 (ABS_EXPR,
6326                                                         TREE_TYPE (arg1),
6327                                                         arg1))))));
6328               default:
6329                 abort ();
6330               }
6331
6332           /* If this is A != 0 ? A : 0, this is simply A.  For ==, it is
6333              always zero.  */
6334
6335           if (integer_zerop (TREE_OPERAND (arg0, 1)) && integer_zerop (arg2))
6336             {
6337               if (comp_code == NE_EXPR)
6338                 return pedantic_non_lvalue (convert (type, arg1));
6339               else if (comp_code == EQ_EXPR)
6340                 return pedantic_non_lvalue (convert (type, integer_zero_node));
6341             }
6342
6343           /* If this is A op B ? A : B, this is either A, B, min (A, B),
6344              or max (A, B), depending on the operation.  */
6345
6346           if (operand_equal_for_comparison_p (TREE_OPERAND (arg0, 1),
6347                                               arg2, TREE_OPERAND (arg0, 0)))
6348             {
6349               tree comp_op0 = TREE_OPERAND (arg0, 0);
6350               tree comp_op1 = TREE_OPERAND (arg0, 1);
6351               tree comp_type = TREE_TYPE (comp_op0);
6352
6353               switch (comp_code)
6354                 {
6355                 case EQ_EXPR:
6356                   return pedantic_non_lvalue (convert (type, arg2));
6357                 case NE_EXPR:
6358                   return pedantic_non_lvalue (convert (type, arg1));
6359                 case LE_EXPR:
6360                 case LT_EXPR:
6361                   /* In C++ a ?: expression can be an lvalue, so put the
6362                      operand which will be used if they are equal first
6363                      so that we can convert this back to the
6364                      corresponding COND_EXPR.  */
6365                   return pedantic_non_lvalue
6366                     (convert (type, (fold (build (MIN_EXPR, comp_type,
6367                                                   (comp_code == LE_EXPR
6368                                                    ? comp_op0 : comp_op1),
6369                                                   (comp_code == LE_EXPR
6370                                                    ? comp_op1 : comp_op0))))));
6371                   break;
6372                 case GE_EXPR:
6373                 case GT_EXPR:
6374                   return pedantic_non_lvalue
6375                     (convert (type, fold (build (MAX_EXPR, comp_type,
6376                                                  (comp_code == GE_EXPR
6377                                                   ? comp_op0 : comp_op1),
6378                                                  (comp_code == GE_EXPR
6379                                                   ? comp_op1 : comp_op0)))));
6380                   break;
6381                 default:
6382                   abort ();
6383                 }
6384             }
6385
6386           /* If this is A op C1 ? A : C2 with C1 and C2 constant integers,
6387              we might still be able to simplify this.  For example,
6388              if C1 is one less or one more than C2, this might have started
6389              out as a MIN or MAX and been transformed by this function.
6390              Only good for INTEGER_TYPEs, because we need TYPE_MAX_VALUE.  */
6391
6392           if (INTEGRAL_TYPE_P (type)
6393               && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
6394               && TREE_CODE (arg2) == INTEGER_CST)
6395             switch (comp_code)
6396               {
6397               case EQ_EXPR:
6398                 /* We can replace A with C1 in this case.  */
6399                 arg1 = convert (type, TREE_OPERAND (arg0, 1));
6400                 t = build (code, type, TREE_OPERAND (t, 0), arg1,
6401                            TREE_OPERAND (t, 2));
6402                 break;
6403
6404               case LT_EXPR:
6405                 /* If C1 is C2 + 1, this is min(A, C2).  */
6406                 if (! operand_equal_p (arg2, TYPE_MAX_VALUE (type), 1)
6407                     && operand_equal_p (TREE_OPERAND (arg0, 1),
6408                                         const_binop (PLUS_EXPR, arg2,
6409                                                      integer_one_node, 0), 1))
6410                   return pedantic_non_lvalue
6411                     (fold (build (MIN_EXPR, type, arg1, arg2)));
6412                 break;
6413
6414               case LE_EXPR:
6415                 /* If C1 is C2 - 1, this is min(A, C2).  */
6416                 if (! operand_equal_p (arg2, TYPE_MIN_VALUE (type), 1)
6417                     && operand_equal_p (TREE_OPERAND (arg0, 1),
6418                                         const_binop (MINUS_EXPR, arg2,
6419                                                      integer_one_node, 0), 1))
6420                   return pedantic_non_lvalue
6421                     (fold (build (MIN_EXPR, type, arg1, arg2)));
6422                 break;
6423
6424               case GT_EXPR:
6425                 /* If C1 is C2 - 1, this is max(A, C2).  */
6426                 if (! operand_equal_p (arg2, TYPE_MIN_VALUE (type), 1)
6427                     && operand_equal_p (TREE_OPERAND (arg0, 1),
6428                                         const_binop (MINUS_EXPR, arg2,
6429                                                      integer_one_node, 0), 1))
6430                   return pedantic_non_lvalue
6431                     (fold (build (MAX_EXPR, type, arg1, arg2)));
6432                 break;
6433
6434               case GE_EXPR:
6435                 /* If C1 is C2 + 1, this is max(A, C2).  */
6436                 if (! operand_equal_p (arg2, TYPE_MAX_VALUE (type), 1)
6437                     && operand_equal_p (TREE_OPERAND (arg0, 1),
6438                                         const_binop (PLUS_EXPR, arg2,
6439                                                      integer_one_node, 0), 1))
6440                   return pedantic_non_lvalue
6441                     (fold (build (MAX_EXPR, type, arg1, arg2)));
6442                 break;
6443               case NE_EXPR:
6444                 break;
6445               default:
6446                 abort ();
6447               }
6448         }
6449
6450       /* If the second operand is simpler than the third, swap them
6451          since that produces better jump optimization results.  */
6452       if ((TREE_CONSTANT (arg1) || TREE_CODE_CLASS (TREE_CODE (arg1)) == 'd'
6453            || TREE_CODE (arg1) == SAVE_EXPR)
6454           && ! (TREE_CONSTANT (TREE_OPERAND (t, 2))
6455                 || TREE_CODE_CLASS (TREE_CODE (TREE_OPERAND (t, 2))) == 'd'
6456                 || TREE_CODE (TREE_OPERAND (t, 2)) == SAVE_EXPR))
6457         {
6458           /* See if this can be inverted.  If it can't, possibly because
6459              it was a floating-point inequality comparison, don't do
6460              anything.  */
6461           tem = invert_truthvalue (arg0);
6462
6463           if (TREE_CODE (tem) != TRUTH_NOT_EXPR)
6464             {
6465               t = build (code, type, tem,
6466                          TREE_OPERAND (t, 2), TREE_OPERAND (t, 1));
6467               arg0 = tem;
6468               /* arg1 should be the first argument of the new T.  */
6469               arg1 = TREE_OPERAND (t, 1);
6470               STRIP_NOPS (arg1);
6471             }
6472         }
6473
6474       /* Convert A ? 1 : 0 to simply A.  */
6475       if (integer_onep (TREE_OPERAND (t, 1))
6476           && integer_zerop (TREE_OPERAND (t, 2))
6477           /* If we try to convert TREE_OPERAND (t, 0) to our type, the
6478              call to fold will try to move the conversion inside
6479              a COND, which will recurse.  In that case, the COND_EXPR
6480              is probably the best choice, so leave it alone.  */
6481           && type == TREE_TYPE (arg0))
6482         return pedantic_non_lvalue (arg0);
6483
6484       /* Look for expressions of the form A & 2 ? 2 : 0.  The result of this
6485          operation is simply A & 2.  */
6486
6487       if (integer_zerop (TREE_OPERAND (t, 2))
6488           && TREE_CODE (arg0) == NE_EXPR
6489           && integer_zerop (TREE_OPERAND (arg0, 1))
6490           && integer_pow2p (arg1)
6491           && TREE_CODE (TREE_OPERAND (arg0, 0)) == BIT_AND_EXPR
6492           && operand_equal_p (TREE_OPERAND (TREE_OPERAND (arg0, 0), 1),
6493                               arg1, 1))
6494         return pedantic_non_lvalue (convert (type, TREE_OPERAND (arg0, 0)));
6495
6496       return t;
6497
6498     case COMPOUND_EXPR:
6499       /* When pedantic, a compound expression can be neither an lvalue
6500          nor an integer constant expression.  */
6501       if (TREE_SIDE_EFFECTS (arg0) || pedantic)
6502         return t;
6503       /* Don't let (0, 0) be null pointer constant.  */
6504       if (integer_zerop (arg1))
6505         return build1 (NOP_EXPR, TREE_TYPE (arg1), arg1);
6506       return arg1;
6507
6508     case COMPLEX_EXPR:
6509       if (wins)
6510         return build_complex (type, arg0, arg1);
6511       return t;
6512
6513     case REALPART_EXPR:
6514       if (TREE_CODE (TREE_TYPE (arg0)) != COMPLEX_TYPE)
6515         return t;
6516       else if (TREE_CODE (arg0) == COMPLEX_EXPR)
6517         return omit_one_operand (type, TREE_OPERAND (arg0, 0),
6518                                  TREE_OPERAND (arg0, 1));
6519       else if (TREE_CODE (arg0) == COMPLEX_CST)
6520         return TREE_REALPART (arg0);
6521       else if (TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MINUS_EXPR)
6522         return fold (build (TREE_CODE (arg0), type,
6523                             fold (build1 (REALPART_EXPR, type,
6524                                           TREE_OPERAND (arg0, 0))),
6525                             fold (build1 (REALPART_EXPR,
6526                                           type, TREE_OPERAND (arg0, 1)))));
6527       return t;
6528
6529     case IMAGPART_EXPR:
6530       if (TREE_CODE (TREE_TYPE (arg0)) != COMPLEX_TYPE)
6531         return convert (type, integer_zero_node);
6532       else if (TREE_CODE (arg0) == COMPLEX_EXPR)
6533         return omit_one_operand (type, TREE_OPERAND (arg0, 1),
6534                                  TREE_OPERAND (arg0, 0));
6535       else if (TREE_CODE (arg0) == COMPLEX_CST)
6536         return TREE_IMAGPART (arg0);
6537       else if (TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MINUS_EXPR)
6538         return fold (build (TREE_CODE (arg0), type,
6539                             fold (build1 (IMAGPART_EXPR, type,
6540                                           TREE_OPERAND (arg0, 0))),
6541                             fold (build1 (IMAGPART_EXPR, type,
6542                                           TREE_OPERAND (arg0, 1)))));
6543       return t;
6544
6545       /* Pull arithmetic ops out of the CLEANUP_POINT_EXPR where
6546          appropriate.  */
6547     case CLEANUP_POINT_EXPR:
6548       if (! has_cleanups (arg0))
6549         return TREE_OPERAND (t, 0);
6550
6551       {
6552         enum tree_code code0 = TREE_CODE (arg0);
6553         int kind0 = TREE_CODE_CLASS (code0);
6554         tree arg00 = TREE_OPERAND (arg0, 0);
6555         tree arg01;
6556
6557         if (kind0 == '1' || code0 == TRUTH_NOT_EXPR)
6558           return fold (build1 (code0, type,
6559                                fold (build1 (CLEANUP_POINT_EXPR,
6560                                              TREE_TYPE (arg00), arg00))));
6561
6562         if (kind0 == '<' || kind0 == '2'
6563             || code0 == TRUTH_ANDIF_EXPR || code0 == TRUTH_ORIF_EXPR
6564             || code0 == TRUTH_AND_EXPR   || code0 == TRUTH_OR_EXPR
6565             || code0 == TRUTH_XOR_EXPR)
6566           {
6567             arg01 = TREE_OPERAND (arg0, 1);
6568
6569             if (TREE_CONSTANT (arg00)
6570                 || ((code0 == TRUTH_ANDIF_EXPR || code0 == TRUTH_ORIF_EXPR)
6571                     && ! has_cleanups (arg00)))
6572               return fold (build (code0, type, arg00,
6573                                   fold (build1 (CLEANUP_POINT_EXPR,
6574                                                 TREE_TYPE (arg01), arg01))));
6575
6576             if (TREE_CONSTANT (arg01))
6577               return fold (build (code0, type,
6578                                   fold (build1 (CLEANUP_POINT_EXPR,
6579                                                 TREE_TYPE (arg00), arg00)),
6580                                   arg01));
6581           }
6582
6583         return t;
6584       }
6585
6586     default:
6587       return t;
6588     } /* switch (code) */
6589 }
6590
6591 /* Determine if first argument is a multiple of second argument.  Return 0 if
6592    it is not, or we cannot easily determined it to be.
6593
6594    An example of the sort of thing we care about (at this point; this routine
6595    could surely be made more general, and expanded to do what the *_DIV_EXPR's
6596    fold cases do now) is discovering that
6597
6598      SAVE_EXPR (I) * SAVE_EXPR (J * 8)
6599
6600    is a multiple of
6601
6602      SAVE_EXPR (J * 8)
6603
6604    when we know that the two SAVE_EXPR (J * 8) nodes are the same node.
6605
6606    This code also handles discovering that
6607
6608      SAVE_EXPR (I) * SAVE_EXPR (J * 8)
6609
6610    is a multiple of 8 so we don't have to worry about dealing with a
6611    possible remainder.
6612
6613    Note that we *look* inside a SAVE_EXPR only to determine how it was
6614    calculated; it is not safe for fold to do much of anything else with the
6615    internals of a SAVE_EXPR, since it cannot know when it will be evaluated
6616    at run time.  For example, the latter example above *cannot* be implemented
6617    as SAVE_EXPR (I) * J or any variant thereof, since the value of J at
6618    evaluation time of the original SAVE_EXPR is not necessarily the same at
6619    the time the new expression is evaluated.  The only optimization of this
6620    sort that would be valid is changing
6621
6622      SAVE_EXPR (I) * SAVE_EXPR (SAVE_EXPR (J) * 8)
6623
6624    divided by 8 to
6625
6626      SAVE_EXPR (I) * SAVE_EXPR (J)
6627
6628    (where the same SAVE_EXPR (J) is used in the original and the
6629    transformed version).  */
6630
6631 static int
6632 multiple_of_p (type, top, bottom)
6633      tree type;
6634      tree top;
6635      tree bottom;
6636 {
6637   if (operand_equal_p (top, bottom, 0))
6638     return 1;
6639
6640   if (TREE_CODE (type) != INTEGER_TYPE)
6641     return 0;
6642
6643   switch (TREE_CODE (top))
6644     {
6645     case MULT_EXPR:
6646       return (multiple_of_p (type, TREE_OPERAND (top, 0), bottom)
6647               || multiple_of_p (type, TREE_OPERAND (top, 1), bottom));
6648
6649     case PLUS_EXPR:
6650     case MINUS_EXPR:
6651       return (multiple_of_p (type, TREE_OPERAND (top, 0), bottom)
6652               && multiple_of_p (type, TREE_OPERAND (top, 1), bottom));
6653
6654     case NOP_EXPR:
6655       /* Can't handle conversions from non-integral or wider integral type.  */
6656       if ((TREE_CODE (TREE_TYPE (TREE_OPERAND (top, 0))) != INTEGER_TYPE)
6657           || (TYPE_PRECISION (type)
6658               < TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (top, 0)))))
6659         return 0;
6660
6661       /* .. fall through ... */
6662
6663     case SAVE_EXPR:
6664       return multiple_of_p (type, TREE_OPERAND (top, 0), bottom);
6665
6666     case INTEGER_CST:
6667       if ((TREE_CODE (bottom) != INTEGER_CST)
6668           || (tree_int_cst_sgn (top) < 0)
6669           || (tree_int_cst_sgn (bottom) < 0))
6670         return 0;
6671       return integer_zerop (const_binop (TRUNC_MOD_EXPR,
6672                                          top, bottom, 0));
6673
6674     default:
6675       return 0;
6676     }
6677 }