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