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, arg1, 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       switch (code)
3144         {
3145         case TRUTH_NOT_EXPR:
3146           in_p = ! in_p, exp = arg0;
3147           continue;
3148
3149         case EQ_EXPR: case NE_EXPR:
3150         case LT_EXPR: case LE_EXPR: case GE_EXPR: case GT_EXPR:
3151           /* We can only do something if the range is testing for zero
3152              and if the second operand is an integer constant.  Note that
3153              saying something is "in" the range we make is done by
3154              complementing IN_P since it will set in the initial case of
3155              being not equal to zero; "out" is leaving it alone.  */
3156           if (low == 0 || high == 0
3157               || ! integer_zerop (low) || ! integer_zerop (high)
3158               || TREE_CODE (arg1) != INTEGER_CST)
3159             break;
3160
3161           switch (code)
3162             {
3163             case NE_EXPR:  /* - [c, c]  */
3164               low = high = arg1;
3165               break;
3166             case EQ_EXPR:  /* + [c, c]  */
3167               in_p = ! in_p, low = high = arg1;
3168               break;
3169             case GT_EXPR:  /* - [-, c] */
3170               low = 0, high = arg1;
3171               break;
3172             case GE_EXPR:  /* + [c, -] */
3173               in_p = ! in_p, low = arg1, high = 0;
3174               break;
3175             case LT_EXPR:  /* - [c, -] */
3176               low = arg1, high = 0;
3177               break;
3178             case LE_EXPR:  /* + [-, c] */
3179               in_p = ! in_p, low = 0, high = arg1;
3180               break;
3181             default:
3182               abort ();
3183             }
3184
3185           exp = arg0;
3186
3187           /* If this is an unsigned comparison, we also know that EXP is
3188              greater than or equal to zero.  We base the range tests we make
3189              on that fact, so we record it here so we can parse existing
3190              range tests.  */
3191           if (TREE_UNSIGNED (type) && (low == 0 || high == 0))
3192             {
3193               if (! merge_ranges (&n_in_p, &n_low, &n_high, in_p, low, high,
3194                                   1, convert (type, integer_zero_node),
3195                                   NULL_TREE))
3196                 break;
3197
3198               in_p = n_in_p, low = n_low, high = n_high;
3199
3200               /* If the high bound is missing, reverse the range so it
3201                  goes from zero to the low bound minus 1.  */
3202               if (high == 0)
3203                 {
3204                   in_p = ! in_p;
3205                   high = range_binop (MINUS_EXPR, NULL_TREE, low, 0,
3206                                       integer_one_node, 0);
3207                   low = convert (type, integer_zero_node);
3208                 }
3209             }
3210           continue;
3211
3212         case NEGATE_EXPR:
3213           /* (-x) IN [a,b] -> x in [-b, -a]  */
3214           n_low = range_binop (MINUS_EXPR, type,
3215                                convert (type, integer_zero_node), 0, high, 1);
3216           n_high = range_binop (MINUS_EXPR, type,
3217                                 convert (type, integer_zero_node), 0, low, 0);
3218           low = n_low, high = n_high;
3219           exp = arg0;
3220           continue;
3221
3222         case BIT_NOT_EXPR:
3223           /* ~ X -> -X - 1  */
3224           exp = build (MINUS_EXPR, type, build1 (NEGATE_EXPR, type, arg0),
3225                        convert (type, integer_one_node));
3226           continue;
3227
3228         case PLUS_EXPR:  case MINUS_EXPR:
3229           if (TREE_CODE (arg1) != INTEGER_CST)
3230             break;
3231
3232           /* If EXP is signed, any overflow in the computation is undefined,
3233              so we don't worry about it so long as our computations on
3234              the bounds don't overflow.  For unsigned, overflow is defined
3235              and this is exactly the right thing.  */
3236           n_low = range_binop (code == MINUS_EXPR ? PLUS_EXPR : MINUS_EXPR,
3237                                type, low, 0, arg1, 0);
3238           n_high = range_binop (code == MINUS_EXPR ? PLUS_EXPR : MINUS_EXPR,
3239                                 type, high, 1, arg1, 0);
3240           if ((n_low != 0 && TREE_OVERFLOW (n_low))
3241               || (n_high != 0 && TREE_OVERFLOW (n_high)))
3242             break;
3243
3244           /* Check for an unsigned range which has wrapped around the maximum
3245              value thus making n_high < n_low, and normalize it.  */
3246           if (n_low && n_high && tree_int_cst_lt (n_high, n_low))
3247             {
3248               low = range_binop (PLUS_EXPR, type, n_high, 0,
3249                                  integer_one_node, 0);
3250               high = range_binop (MINUS_EXPR, type, n_low, 0,
3251                                  integer_one_node, 0);
3252               in_p = ! in_p;
3253             }
3254           else
3255             low = n_low, high = n_high;
3256
3257           exp = arg0;
3258           continue;
3259
3260         case NOP_EXPR:  case NON_LVALUE_EXPR:  case CONVERT_EXPR:
3261           if (orig_type == NULL_TREE)
3262             orig_type = type;
3263           if (TYPE_PRECISION (type) > TYPE_PRECISION (orig_type))
3264             break;
3265
3266           if (! INTEGRAL_TYPE_P (type)
3267               || (low != 0 && ! int_fits_type_p (low, type))
3268               || (high != 0 && ! int_fits_type_p (high, type)))
3269             break;
3270
3271           n_low = low, n_high = high;
3272
3273           if (n_low != 0)
3274             n_low = convert (type, n_low);
3275
3276           if (n_high != 0)
3277             n_high = convert (type, n_high);
3278
3279           /* If we're converting from an unsigned to a signed type,
3280              we will be doing the comparison as unsigned.  The tests above
3281              have already verified that LOW and HIGH are both positive.
3282
3283              So we have to make sure that the original unsigned value will
3284              be interpreted as positive.  */
3285           if (TREE_UNSIGNED (type) && ! TREE_UNSIGNED (TREE_TYPE (exp)))
3286             {
3287               tree equiv_type = type_for_mode (TYPE_MODE (type), 1);
3288               tree high_positive;
3289
3290               /* A range without an upper bound is, naturally, unbounded.
3291                  Since convert would have cropped a very large value, use
3292                   the max value for the destination type.  */
3293
3294               high_positive = TYPE_MAX_VALUE (equiv_type);
3295               if (!high_positive)
3296                 {
3297                   high_positive = TYPE_MAX_VALUE (type);
3298                   if (!high_positive)
3299                     abort();
3300                 }
3301               high_positive = fold (build (RSHIFT_EXPR, type,
3302                                            convert (type, high_positive),
3303                                            convert (type, integer_one_node)));
3304
3305               /* If the low bound is specified, "and" the range with the
3306                  range for which the original unsigned value will be
3307                  positive.  */
3308               if (low != 0)
3309                 {
3310                   if (! merge_ranges (&n_in_p, &n_low, &n_high,
3311                                       1, n_low, n_high,
3312                                       1, convert (type, integer_zero_node),
3313                                       high_positive))
3314                     break;
3315
3316                   in_p = (n_in_p == in_p);
3317                 }
3318               else
3319                 {
3320                   /* Otherwise, "or" the range with the range of the input
3321                      that will be interpreted as negative.  */
3322                   if (! merge_ranges (&n_in_p, &n_low, &n_high,
3323                                       0, n_low, n_high,
3324                                       1, convert (type, integer_zero_node),
3325                                       high_positive))
3326                     break;
3327
3328                   in_p = (in_p != n_in_p);
3329                 }
3330             }
3331
3332           exp = arg0;
3333           low = n_low, high = n_high;
3334           continue;
3335
3336         default:
3337           break;
3338         }
3339
3340       break;
3341     }
3342
3343   /* If EXP is a constant, we can evaluate whether this is true or false.  */
3344   if (TREE_CODE (exp) == INTEGER_CST)
3345     {
3346       in_p = in_p == (integer_onep (range_binop (GE_EXPR, integer_type_node,
3347                                                  exp, 0, low, 0))
3348                       && integer_onep (range_binop (LE_EXPR, integer_type_node,
3349                                                     exp, 1, high, 1)));
3350       low = high = 0;
3351       exp = 0;
3352     }
3353
3354   *pin_p = in_p, *plow = low, *phigh = high;
3355   return exp;
3356 }
3357 \f
3358 /* Given a range, LOW, HIGH, and IN_P, an expression, EXP, and a result
3359    type, TYPE, return an expression to test if EXP is in (or out of, depending
3360    on IN_P) the range.  */
3361
3362 static tree
3363 build_range_check (type, exp, in_p, low, high)
3364      tree type;
3365      tree exp;
3366      int in_p;
3367      tree low, high;
3368 {
3369   tree etype = TREE_TYPE (exp);
3370   tree utype, value;
3371
3372   if (! in_p
3373       && (0 != (value = build_range_check (type, exp, 1, low, high))))
3374     return invert_truthvalue (value);
3375
3376   else if (low == 0 && high == 0)
3377     return convert (type, integer_one_node);
3378
3379   else if (low == 0)
3380     return fold (build (LE_EXPR, type, exp, high));
3381
3382   else if (high == 0)
3383     return fold (build (GE_EXPR, type, exp, low));
3384
3385   else if (operand_equal_p (low, high, 0))
3386     return fold (build (EQ_EXPR, type, exp, low));
3387
3388   else if (TREE_UNSIGNED (etype) && integer_zerop (low))
3389     return build_range_check (type, exp, 1, 0, high);
3390
3391   else if (integer_zerop (low))
3392     {
3393       utype = unsigned_type (etype);
3394       return build_range_check (type, convert (utype, exp), 1, 0,
3395                                 convert (utype, high));
3396     }
3397
3398   else if (0 != (value = const_binop (MINUS_EXPR, high, low, 0))
3399            && ! TREE_OVERFLOW (value))
3400     return build_range_check (type,
3401                               fold (build (MINUS_EXPR, etype, exp, low)),
3402                               1, convert (etype, integer_zero_node), value);
3403   else
3404     return 0;
3405 }
3406 \f
3407 /* Given two ranges, see if we can merge them into one.  Return 1 if we
3408    can, 0 if we can't.  Set the output range into the specified parameters.  */
3409
3410 static int
3411 merge_ranges (pin_p, plow, phigh, in0_p, low0, high0, in1_p, low1, high1)
3412      int *pin_p;
3413      tree *plow, *phigh;
3414      int in0_p, in1_p;
3415      tree low0, high0, low1, high1;
3416 {
3417   int no_overlap;
3418   int subset;
3419   int temp;
3420   tree tem;
3421   int in_p;
3422   tree low, high;
3423   int lowequal = ((low0 == 0 && low1 == 0)
3424                   || integer_onep (range_binop (EQ_EXPR, integer_type_node,
3425                                                 low0, 0, low1, 0)));
3426   int highequal = ((high0 == 0 && high1 == 0)
3427                    || integer_onep (range_binop (EQ_EXPR, integer_type_node,
3428                                                  high0, 1, high1, 1)));
3429
3430   /* Make range 0 be the range that starts first, or ends last if they
3431      start at the same value.  Swap them if it isn't.  */
3432   if (integer_onep (range_binop (GT_EXPR, integer_type_node,
3433                                  low0, 0, low1, 0))
3434       || (lowequal
3435           && integer_onep (range_binop (GT_EXPR, integer_type_node,
3436                                         high1, 1, high0, 1))))
3437     {
3438       temp = in0_p, in0_p = in1_p, in1_p = temp;
3439       tem = low0, low0 = low1, low1 = tem;
3440       tem = high0, high0 = high1, high1 = tem;
3441     }
3442
3443   /* Now flag two cases, whether the ranges are disjoint or whether the
3444      second range is totally subsumed in the first.  Note that the tests
3445      below are simplified by the ones above.  */
3446   no_overlap = integer_onep (range_binop (LT_EXPR, integer_type_node,
3447                                           high0, 1, low1, 0));
3448   subset = integer_onep (range_binop (LE_EXPR, integer_type_node,
3449                                       high1, 1, high0, 1));
3450
3451   /* We now have four cases, depending on whether we are including or
3452      excluding the two ranges.  */
3453   if (in0_p && in1_p)
3454     {
3455       /* If they don't overlap, the result is false.  If the second range
3456          is a subset it is the result.  Otherwise, the range is from the start
3457          of the second to the end of the first.  */
3458       if (no_overlap)
3459         in_p = 0, low = high = 0;
3460       else if (subset)
3461         in_p = 1, low = low1, high = high1;
3462       else
3463         in_p = 1, low = low1, high = high0;
3464     }
3465
3466   else if (in0_p && ! in1_p)
3467     {
3468       /* If they don't overlap, the result is the first range.  If they are
3469          equal, the result is false.  If the second range is a subset of the
3470          first, and the ranges begin at the same place, we go from just after
3471          the end of the first range to the end of the second.  If the second
3472          range is not a subset of the first, or if it is a subset and both
3473          ranges end at the same place, the range starts at the start of the
3474          first range and ends just before the second range.
3475          Otherwise, we can't describe this as a single range.  */
3476       if (no_overlap)
3477         in_p = 1, low = low0, high = high0;
3478       else if (lowequal && highequal)
3479         in_p = 0, low = high = 0;
3480       else if (subset && lowequal)
3481         {
3482           in_p = 1, high = high0;
3483           low = range_binop (PLUS_EXPR, NULL_TREE, high1, 0,
3484                              integer_one_node, 0);
3485         }
3486       else if (! subset || highequal)
3487         {
3488           in_p = 1, low = low0;
3489           high = range_binop (MINUS_EXPR, NULL_TREE, low1, 0,
3490                               integer_one_node, 0);
3491         }
3492       else
3493         return 0;
3494     }
3495
3496   else if (! in0_p && in1_p)
3497     {
3498       /* If they don't overlap, the result is the second range.  If the second
3499          is a subset of the first, the result is false.  Otherwise,
3500          the range starts just after the first range and ends at the
3501          end of the second.  */
3502       if (no_overlap)
3503         in_p = 1, low = low1, high = high1;
3504       else if (subset)
3505         in_p = 0, low = high = 0;
3506       else
3507         {
3508           in_p = 1, high = high1;
3509           low = range_binop (PLUS_EXPR, NULL_TREE, high0, 1,
3510                              integer_one_node, 0);
3511         }
3512     }
3513
3514   else
3515     {
3516       /* The case where we are excluding both ranges.  Here the complex case
3517          is if they don't overlap.  In that case, the only time we have a
3518          range is if they are adjacent.  If the second is a subset of the
3519          first, the result is the first.  Otherwise, the range to exclude
3520          starts at the beginning of the first range and ends at the end of the
3521          second.  */
3522       if (no_overlap)
3523         {
3524           if (integer_onep (range_binop (EQ_EXPR, integer_type_node,
3525                                          range_binop (PLUS_EXPR, NULL_TREE,
3526                                                       high0, 1,
3527                                                       integer_one_node, 1),
3528                                          1, low1, 0)))
3529             in_p = 0, low = low0, high = high1;
3530           else
3531             return 0;
3532         }
3533       else if (subset)
3534         in_p = 0, low = low0, high = high0;
3535       else
3536         in_p = 0, low = low0, high = high1;
3537     }
3538
3539   *pin_p = in_p, *plow = low, *phigh = high;
3540   return 1;
3541 }
3542 \f
3543 /* EXP is some logical combination of boolean tests.  See if we can
3544    merge it into some range test.  Return the new tree if so.  */
3545
3546 static tree
3547 fold_range_test (exp)
3548      tree exp;
3549 {
3550   int or_op = (TREE_CODE (exp) == TRUTH_ORIF_EXPR
3551                || TREE_CODE (exp) == TRUTH_OR_EXPR);
3552   int in0_p, in1_p, in_p;
3553   tree low0, low1, low, high0, high1, high;
3554   tree lhs = make_range (TREE_OPERAND (exp, 0), &in0_p, &low0, &high0);
3555   tree rhs = make_range (TREE_OPERAND (exp, 1), &in1_p, &low1, &high1);
3556   tree tem;
3557
3558   /* If this is an OR operation, invert both sides; we will invert
3559      again at the end.  */
3560   if (or_op)
3561     in0_p = ! in0_p, in1_p = ! in1_p;
3562
3563   /* If both expressions are the same, if we can merge the ranges, and we
3564      can build the range test, return it or it inverted.  If one of the
3565      ranges is always true or always false, consider it to be the same
3566      expression as the other.  */
3567   if ((lhs == 0 || rhs == 0 || operand_equal_p (lhs, rhs, 0))
3568       && merge_ranges (&in_p, &low, &high, in0_p, low0, high0,
3569                        in1_p, low1, high1)
3570       && 0 != (tem = (build_range_check (TREE_TYPE (exp),
3571                                          lhs != 0 ? lhs
3572                                          : rhs != 0 ? rhs : integer_zero_node,
3573                                          in_p, low, high))))
3574     return or_op ? invert_truthvalue (tem) : tem;
3575
3576   /* On machines where the branch cost is expensive, if this is a
3577      short-circuited branch and the underlying object on both sides
3578      is the same, make a non-short-circuit operation.  */
3579   else if (BRANCH_COST >= 2
3580            && (TREE_CODE (exp) == TRUTH_ANDIF_EXPR
3581                || TREE_CODE (exp) == TRUTH_ORIF_EXPR)
3582            && operand_equal_p (lhs, rhs, 0))
3583     {
3584       /* If simple enough, just rewrite.  Otherwise, make a SAVE_EXPR
3585          unless we are at top level or LHS contains a PLACEHOLDER_EXPR, in
3586          which cases we can't do this.  */
3587       if (simple_operand_p (lhs))
3588         return build (TREE_CODE (exp) == TRUTH_ANDIF_EXPR
3589                       ? TRUTH_AND_EXPR : TRUTH_OR_EXPR,
3590                       TREE_TYPE (exp), TREE_OPERAND (exp, 0),
3591                       TREE_OPERAND (exp, 1));
3592
3593       else if (current_function_decl != 0
3594                && ! contains_placeholder_p (lhs))
3595         {
3596           tree common = save_expr (lhs);
3597
3598           if (0 != (lhs = build_range_check (TREE_TYPE (exp), common,
3599                                              or_op ? ! in0_p : in0_p,
3600                                              low0, high0))
3601               && (0 != (rhs = build_range_check (TREE_TYPE (exp), common,
3602                                                  or_op ? ! in1_p : in1_p,
3603                                                  low1, high1))))
3604             return build (TREE_CODE (exp) == TRUTH_ANDIF_EXPR
3605                           ? TRUTH_AND_EXPR : TRUTH_OR_EXPR,
3606                           TREE_TYPE (exp), lhs, rhs);
3607         }
3608     }
3609
3610   return 0;
3611 }
3612 \f
3613 /* Subroutine for fold_truthop: C is an INTEGER_CST interpreted as a P
3614    bit value.  Arrange things so the extra bits will be set to zero if and
3615    only if C is signed-extended to its full width.  If MASK is nonzero,
3616    it is an INTEGER_CST that should be AND'ed with the extra bits.  */
3617
3618 static tree
3619 unextend (c, p, unsignedp, mask)
3620      tree c;
3621      int p;
3622      int unsignedp;
3623      tree mask;
3624 {
3625   tree type = TREE_TYPE (c);
3626   int modesize = GET_MODE_BITSIZE (TYPE_MODE (type));
3627   tree temp;
3628
3629   if (p == modesize || unsignedp)
3630     return c;
3631
3632   /* We work by getting just the sign bit into the low-order bit, then
3633      into the high-order bit, then sign-extend.  We then XOR that value
3634      with C.  */
3635   temp = const_binop (RSHIFT_EXPR, c, size_int (p - 1), 0);
3636   temp = const_binop (BIT_AND_EXPR, temp, size_int (1), 0);
3637
3638   /* We must use a signed type in order to get an arithmetic right shift.
3639      However, we must also avoid introducing accidental overflows, so that
3640      a subsequent call to integer_zerop will work.  Hence we must
3641      do the type conversion here.  At this point, the constant is either
3642      zero or one, and the conversion to a signed type can never overflow.
3643      We could get an overflow if this conversion is done anywhere else.  */
3644   if (TREE_UNSIGNED (type))
3645     temp = convert (signed_type (type), temp);
3646
3647   temp = const_binop (LSHIFT_EXPR, temp, size_int (modesize - 1), 0);
3648   temp = const_binop (RSHIFT_EXPR, temp, size_int (modesize - p - 1), 0);
3649   if (mask != 0)
3650     temp = const_binop (BIT_AND_EXPR, temp, convert (TREE_TYPE (c), mask), 0);
3651   /* If necessary, convert the type back to match the type of C.  */
3652   if (TREE_UNSIGNED (type))
3653     temp = convert (type, temp);
3654
3655   return convert (type, const_binop (BIT_XOR_EXPR, c, temp, 0));
3656 }
3657 \f
3658 /* Find ways of folding logical expressions of LHS and RHS:
3659    Try to merge two comparisons to the same innermost item.
3660    Look for range tests like "ch >= '0' && ch <= '9'".
3661    Look for combinations of simple terms on machines with expensive branches
3662    and evaluate the RHS unconditionally.
3663
3664    For example, if we have p->a == 2 && p->b == 4 and we can make an
3665    object large enough to span both A and B, we can do this with a comparison
3666    against the object ANDed with the a mask.
3667
3668    If we have p->a == q->a && p->b == q->b, we may be able to use bit masking
3669    operations to do this with one comparison.
3670
3671    We check for both normal comparisons and the BIT_AND_EXPRs made this by
3672    function and the one above.
3673
3674    CODE is the logical operation being done.  It can be TRUTH_ANDIF_EXPR,
3675    TRUTH_AND_EXPR, TRUTH_ORIF_EXPR, or TRUTH_OR_EXPR.
3676
3677    TRUTH_TYPE is the type of the logical operand and LHS and RHS are its
3678    two operands.
3679
3680    We return the simplified tree or 0 if no optimization is possible.  */
3681
3682 static tree
3683 fold_truthop (code, truth_type, lhs, rhs)
3684      enum tree_code code;
3685      tree truth_type, lhs, rhs;
3686 {
3687   /* If this is the "or" of two comparisons, we can do something if we
3688      the comparisons are NE_EXPR.  If this is the "and", we can do something
3689      if the comparisons are EQ_EXPR.  I.e.,
3690         (a->b == 2 && a->c == 4) can become (a->new == NEW).
3691
3692      WANTED_CODE is this operation code.  For single bit fields, we can
3693      convert EQ_EXPR to NE_EXPR so we need not reject the "wrong"
3694      comparison for one-bit fields.  */
3695
3696   enum tree_code wanted_code;
3697   enum tree_code lcode, rcode;
3698   tree ll_arg, lr_arg, rl_arg, rr_arg;
3699   tree ll_inner, lr_inner, rl_inner, rr_inner;
3700   int ll_bitsize, ll_bitpos, lr_bitsize, lr_bitpos;
3701   int rl_bitsize, rl_bitpos, rr_bitsize, rr_bitpos;
3702   int xll_bitpos, xlr_bitpos, xrl_bitpos, xrr_bitpos;
3703   int lnbitsize, lnbitpos, rnbitsize, rnbitpos;
3704   int ll_unsignedp, lr_unsignedp, rl_unsignedp, rr_unsignedp;
3705   enum machine_mode ll_mode, lr_mode, rl_mode, rr_mode;
3706   enum machine_mode lnmode, rnmode;
3707   tree ll_mask, lr_mask, rl_mask, rr_mask;
3708   tree ll_and_mask, lr_and_mask, rl_and_mask, rr_and_mask;
3709   tree l_const, r_const;
3710   tree type, result;
3711   int first_bit, end_bit;
3712   int volatilep;
3713
3714   /* Start by getting the comparison codes.  Fail if anything is volatile.
3715      If one operand is a BIT_AND_EXPR with the constant one, treat it as if
3716      it were surrounded with a NE_EXPR.  */
3717
3718   if (TREE_SIDE_EFFECTS (lhs) || TREE_SIDE_EFFECTS (rhs))
3719     return 0;
3720
3721   lcode = TREE_CODE (lhs);
3722   rcode = TREE_CODE (rhs);
3723
3724   if (lcode == BIT_AND_EXPR && integer_onep (TREE_OPERAND (lhs, 1)))
3725     lcode = NE_EXPR, lhs = build (NE_EXPR, truth_type, lhs, integer_zero_node);
3726
3727   if (rcode == BIT_AND_EXPR && integer_onep (TREE_OPERAND (rhs, 1)))
3728     rcode = NE_EXPR, rhs = build (NE_EXPR, truth_type, rhs, integer_zero_node);
3729
3730   if (TREE_CODE_CLASS (lcode) != '<' || TREE_CODE_CLASS (rcode) != '<')
3731     return 0;
3732
3733   code = ((code == TRUTH_AND_EXPR || code == TRUTH_ANDIF_EXPR)
3734           ? TRUTH_AND_EXPR : TRUTH_OR_EXPR);
3735
3736   ll_arg = TREE_OPERAND (lhs, 0);
3737   lr_arg = TREE_OPERAND (lhs, 1);
3738   rl_arg = TREE_OPERAND (rhs, 0);
3739   rr_arg = TREE_OPERAND (rhs, 1);
3740
3741   /* If the RHS can be evaluated unconditionally and its operands are
3742      simple, it wins to evaluate the RHS unconditionally on machines
3743      with expensive branches.  In this case, this isn't a comparison
3744      that can be merged.  */
3745
3746   /* @@ I'm not sure it wins on the m88110 to do this if the comparisons
3747      are with zero (tmw).  */
3748
3749   if (BRANCH_COST >= 2
3750       && INTEGRAL_TYPE_P (TREE_TYPE (rhs))
3751       && simple_operand_p (rl_arg)
3752       && simple_operand_p (rr_arg))
3753     return build (code, truth_type, lhs, rhs);
3754
3755   /* See if the comparisons can be merged.  Then get all the parameters for
3756      each side.  */
3757
3758   if ((lcode != EQ_EXPR && lcode != NE_EXPR)
3759       || (rcode != EQ_EXPR && rcode != NE_EXPR))
3760     return 0;
3761
3762   volatilep = 0;
3763   ll_inner = decode_field_reference (ll_arg,
3764                                      &ll_bitsize, &ll_bitpos, &ll_mode,
3765                                      &ll_unsignedp, &volatilep, &ll_mask,
3766                                      &ll_and_mask);
3767   lr_inner = decode_field_reference (lr_arg,
3768                                      &lr_bitsize, &lr_bitpos, &lr_mode,
3769                                      &lr_unsignedp, &volatilep, &lr_mask,
3770                                      &lr_and_mask);
3771   rl_inner = decode_field_reference (rl_arg,
3772                                      &rl_bitsize, &rl_bitpos, &rl_mode,
3773                                      &rl_unsignedp, &volatilep, &rl_mask,
3774                                      &rl_and_mask);
3775   rr_inner = decode_field_reference (rr_arg,
3776                                      &rr_bitsize, &rr_bitpos, &rr_mode,
3777                                      &rr_unsignedp, &volatilep, &rr_mask,
3778                                      &rr_and_mask);
3779
3780   /* It must be true that the inner operation on the lhs of each
3781      comparison must be the same if we are to be able to do anything.
3782      Then see if we have constants.  If not, the same must be true for
3783      the rhs's.  */
3784   if (volatilep || ll_inner == 0 || rl_inner == 0
3785       || ! operand_equal_p (ll_inner, rl_inner, 0))
3786     return 0;
3787
3788   if (TREE_CODE (lr_arg) == INTEGER_CST
3789       && TREE_CODE (rr_arg) == INTEGER_CST)
3790     l_const = lr_arg, r_const = rr_arg;
3791   else if (lr_inner == 0 || rr_inner == 0
3792            || ! operand_equal_p (lr_inner, rr_inner, 0))
3793     return 0;
3794   else
3795     l_const = r_const = 0;
3796
3797   /* If either comparison code is not correct for our logical operation,
3798      fail.  However, we can convert a one-bit comparison against zero into
3799      the opposite comparison against that bit being set in the field.  */
3800
3801   wanted_code = (code == TRUTH_AND_EXPR ? EQ_EXPR : NE_EXPR);
3802   if (lcode != wanted_code)
3803     {
3804       if (l_const && integer_zerop (l_const) && integer_pow2p (ll_mask))
3805         {
3806           if (ll_unsignedp || tree_log2 (ll_mask) + 1 < ll_bitsize)
3807             l_const = ll_mask;
3808         else
3809           /* Since ll_arg is a single bit bit mask, we can sign extend
3810              it appropriately with a NEGATE_EXPR.
3811              l_const is made a signed value here, but since for l_const != NULL
3812              lr_unsignedp is not used, we don't need to clear the latter.  */
3813           l_const = fold (build1 (NEGATE_EXPR, TREE_TYPE (ll_arg),
3814                                   convert (TREE_TYPE (ll_arg), ll_mask)));
3815         }
3816       else
3817         return 0;
3818     }
3819
3820   if (rcode != wanted_code)
3821     {
3822       if (r_const && integer_zerop (r_const) && integer_pow2p (rl_mask))
3823         {
3824           if (rl_unsignedp || tree_log2 (rl_mask) + 1 < rl_bitsize)
3825             r_const = rl_mask;
3826         else
3827           /* This is analogous to the code for l_const above.  */
3828           r_const = fold (build1 (NEGATE_EXPR, TREE_TYPE (rl_arg),
3829                                   convert (TREE_TYPE (rl_arg), rl_mask)));
3830         }
3831       else
3832         return 0;
3833     }
3834
3835   /* See if we can find a mode that contains both fields being compared on
3836      the left.  If we can't, fail.  Otherwise, update all constants and masks
3837      to be relative to a field of that size.  */
3838   first_bit = MIN (ll_bitpos, rl_bitpos);
3839   end_bit = MAX (ll_bitpos + ll_bitsize, rl_bitpos + rl_bitsize);
3840   lnmode = get_best_mode (end_bit - first_bit, first_bit,
3841                           TYPE_ALIGN (TREE_TYPE (ll_inner)), word_mode,
3842                           volatilep);
3843   if (lnmode == VOIDmode)
3844     return 0;
3845
3846   lnbitsize = GET_MODE_BITSIZE (lnmode);
3847   lnbitpos = first_bit & ~ (lnbitsize - 1);
3848   type = type_for_size (lnbitsize, 1);
3849   xll_bitpos = ll_bitpos - lnbitpos, xrl_bitpos = rl_bitpos - lnbitpos;
3850
3851   if (BYTES_BIG_ENDIAN)
3852     {
3853       xll_bitpos = lnbitsize - xll_bitpos - ll_bitsize;
3854       xrl_bitpos = lnbitsize - xrl_bitpos - rl_bitsize;
3855     }
3856
3857   ll_mask = const_binop (LSHIFT_EXPR, convert (type, ll_mask),
3858                          size_int (xll_bitpos), 0);
3859   rl_mask = const_binop (LSHIFT_EXPR, convert (type, rl_mask),
3860                          size_int (xrl_bitpos), 0);
3861
3862   if (l_const)
3863     {
3864       l_const = convert (type, l_const);
3865       l_const = unextend (l_const,  ll_bitsize, ll_unsignedp, ll_and_mask);
3866       l_const = const_binop (LSHIFT_EXPR, l_const, size_int (xll_bitpos), 0);
3867       if (! integer_zerop (const_binop (BIT_AND_EXPR, l_const,
3868                                         fold (build1 (BIT_NOT_EXPR,
3869                                                       type, ll_mask)),
3870                                         0)))
3871         {
3872           warning ("comparison is always %d", wanted_code == NE_EXPR);
3873
3874           return convert (truth_type,
3875                           wanted_code == NE_EXPR
3876                           ? integer_one_node : integer_zero_node);
3877         }
3878     }
3879   if (r_const)
3880     {
3881       r_const = convert (type, r_const);
3882       r_const = unextend (r_const, rl_bitsize, rl_unsignedp, rl_and_mask);
3883       r_const = const_binop (LSHIFT_EXPR, r_const, size_int (xrl_bitpos), 0);
3884       if (! integer_zerop (const_binop (BIT_AND_EXPR, r_const,
3885                                         fold (build1 (BIT_NOT_EXPR,
3886                                                       type, rl_mask)),
3887                                         0)))
3888         {
3889           warning ("comparison is always %d", wanted_code == NE_EXPR);
3890
3891           return convert (truth_type,
3892                           wanted_code == NE_EXPR
3893                           ? integer_one_node : integer_zero_node);
3894         }
3895     }
3896
3897   /* If the right sides are not constant, do the same for it.  Also,
3898      disallow this optimization if a size or signedness mismatch occurs
3899      between the left and right sides.  */
3900   if (l_const == 0)
3901     {
3902       if (ll_bitsize != lr_bitsize || rl_bitsize != rr_bitsize
3903           || ll_unsignedp != lr_unsignedp || rl_unsignedp != rr_unsignedp
3904           /* Make sure the two fields on the right
3905              correspond to the left without being swapped.  */
3906           || ll_bitpos - rl_bitpos != lr_bitpos - rr_bitpos)
3907         return 0;
3908
3909       first_bit = MIN (lr_bitpos, rr_bitpos);
3910       end_bit = MAX (lr_bitpos + lr_bitsize, rr_bitpos + rr_bitsize);
3911       rnmode = get_best_mode (end_bit - first_bit, first_bit,
3912                               TYPE_ALIGN (TREE_TYPE (lr_inner)), word_mode,
3913                               volatilep);
3914       if (rnmode == VOIDmode)
3915         return 0;
3916
3917       rnbitsize = GET_MODE_BITSIZE (rnmode);
3918       rnbitpos = first_bit & ~ (rnbitsize - 1);
3919       xlr_bitpos = lr_bitpos - rnbitpos, xrr_bitpos = rr_bitpos - rnbitpos;
3920
3921       if (BYTES_BIG_ENDIAN)
3922         {
3923           xlr_bitpos = rnbitsize - xlr_bitpos - lr_bitsize;
3924           xrr_bitpos = rnbitsize - xrr_bitpos - rr_bitsize;
3925         }
3926
3927       lr_mask = const_binop (LSHIFT_EXPR, convert (type, lr_mask),
3928                              size_int (xlr_bitpos), 0);
3929       rr_mask = const_binop (LSHIFT_EXPR, convert (type, rr_mask),
3930                              size_int (xrr_bitpos), 0);
3931
3932       /* Make a mask that corresponds to both fields being compared.
3933          Do this for both items being compared.  If the masks agree,
3934          we can do this by masking both and comparing the masked
3935          results.  */
3936       ll_mask = const_binop (BIT_IOR_EXPR, ll_mask, rl_mask, 0);
3937       lr_mask = const_binop (BIT_IOR_EXPR, lr_mask, rr_mask, 0);
3938       if (operand_equal_p (ll_mask, lr_mask, 0) && lnbitsize == rnbitsize)
3939         {
3940           lhs = make_bit_field_ref (ll_inner, type, lnbitsize, lnbitpos,
3941                                     ll_unsignedp || rl_unsignedp);
3942           rhs = make_bit_field_ref (lr_inner, type, rnbitsize, rnbitpos,
3943                                     lr_unsignedp || rr_unsignedp);
3944           if (! all_ones_mask_p (ll_mask, lnbitsize))
3945             {
3946               lhs = build (BIT_AND_EXPR, type, lhs, ll_mask);
3947               rhs = build (BIT_AND_EXPR, type, rhs, ll_mask);
3948             }
3949           return build (wanted_code, truth_type, lhs, rhs);
3950         }
3951
3952       /* There is still another way we can do something:  If both pairs of
3953          fields being compared are adjacent, we may be able to make a wider
3954          field containing them both.  */
3955       if ((ll_bitsize + ll_bitpos == rl_bitpos
3956            && lr_bitsize + lr_bitpos == rr_bitpos)
3957           || (ll_bitpos == rl_bitpos + rl_bitsize
3958               && lr_bitpos == rr_bitpos + rr_bitsize))
3959         return build (wanted_code, truth_type,
3960                       make_bit_field_ref (ll_inner, type,
3961                                           ll_bitsize + rl_bitsize,
3962                                           MIN (ll_bitpos, rl_bitpos),
3963                                           ll_unsignedp),
3964                       make_bit_field_ref (lr_inner, type,
3965                                           lr_bitsize + rr_bitsize,
3966                                           MIN (lr_bitpos, rr_bitpos),
3967                                           lr_unsignedp));
3968
3969       return 0;
3970     }
3971
3972   /* Handle the case of comparisons with constants.  If there is something in
3973      common between the masks, those bits of the constants must be the same.
3974      If not, the condition is always false.  Test for this to avoid generating
3975      incorrect code below.  */
3976   result = const_binop (BIT_AND_EXPR, ll_mask, rl_mask, 0);
3977   if (! integer_zerop (result)
3978       && simple_cst_equal (const_binop (BIT_AND_EXPR, result, l_const, 0),
3979                            const_binop (BIT_AND_EXPR, result, r_const, 0)) != 1)
3980     {
3981       if (wanted_code == NE_EXPR)
3982         {
3983           warning ("`or' of unmatched not-equal tests is always 1");
3984           return convert (truth_type, integer_one_node);
3985         }
3986       else
3987         {
3988           warning ("`and' of mutually exclusive equal-tests is always 0");
3989           return convert (truth_type, integer_zero_node);
3990         }
3991     }
3992
3993   /* Construct the expression we will return.  First get the component
3994      reference we will make.  Unless the mask is all ones the width of
3995      that field, perform the mask operation.  Then compare with the
3996      merged constant.  */
3997   result = make_bit_field_ref (ll_inner, type, lnbitsize, lnbitpos,
3998                                ll_unsignedp || rl_unsignedp);
3999
4000   ll_mask = const_binop (BIT_IOR_EXPR, ll_mask, rl_mask, 0);
4001   if (! all_ones_mask_p (ll_mask, lnbitsize))
4002     result = build (BIT_AND_EXPR, type, result, ll_mask);
4003
4004   return build (wanted_code, truth_type, result,
4005                 const_binop (BIT_IOR_EXPR, l_const, r_const, 0));
4006 }
4007 \f
4008 /* If T contains a COMPOUND_EXPR which was inserted merely to evaluate
4009    S, a SAVE_EXPR, return the expression actually being evaluated.   Note
4010    that we may sometimes modify the tree.  */
4011
4012 static tree
4013 strip_compound_expr (t, s)
4014      tree t;
4015      tree s;
4016 {
4017   enum tree_code code = TREE_CODE (t);
4018
4019   /* See if this is the COMPOUND_EXPR we want to eliminate.  */
4020   if (code == COMPOUND_EXPR && TREE_CODE (TREE_OPERAND (t, 0)) == CONVERT_EXPR
4021       && TREE_OPERAND (TREE_OPERAND (t, 0), 0) == s)
4022     return TREE_OPERAND (t, 1);
4023
4024   /* See if this is a COND_EXPR or a simple arithmetic operator.   We
4025      don't bother handling any other types.  */
4026   else if (code == COND_EXPR)
4027     {
4028       TREE_OPERAND (t, 0) = strip_compound_expr (TREE_OPERAND (t, 0), s);
4029       TREE_OPERAND (t, 1) = strip_compound_expr (TREE_OPERAND (t, 1), s);
4030       TREE_OPERAND (t, 2) = strip_compound_expr (TREE_OPERAND (t, 2), s);
4031     }
4032   else if (TREE_CODE_CLASS (code) == '1')
4033     TREE_OPERAND (t, 0) = strip_compound_expr (TREE_OPERAND (t, 0), s);
4034   else if (TREE_CODE_CLASS (code) == '<'
4035            || TREE_CODE_CLASS (code) == '2')
4036     {
4037       TREE_OPERAND (t, 0) = strip_compound_expr (TREE_OPERAND (t, 0), s);
4038       TREE_OPERAND (t, 1) = strip_compound_expr (TREE_OPERAND (t, 1), s);
4039     }
4040
4041   return t;
4042 }
4043 \f
4044 /* Return a node which has the indicated constant VALUE (either 0 or
4045    1), and is of the indicated TYPE.  */
4046
4047 static tree
4048 constant_boolean_node (value, type)
4049      int value;
4050      tree type;
4051 {
4052   if (type == integer_type_node)
4053     return value ? integer_one_node : integer_zero_node;
4054   else if (TREE_CODE (type) == BOOLEAN_TYPE)
4055     return truthvalue_conversion (value ? integer_one_node :
4056                                   integer_zero_node);
4057   else
4058     {
4059       tree t = build_int_2 (value, 0);
4060       TREE_TYPE (t) = type;
4061       return t;
4062     }
4063 }
4064
4065 /* Utility function for the following routine, to see how complex a nesting of
4066    COND_EXPRs can be.  EXPR is the expression and LIMIT is a count beyond which
4067    we don't care (to avoid spending too much time on complex expressions.).  */
4068
4069 static int
4070 count_cond (expr, lim)
4071      tree expr;
4072      int lim;
4073 {
4074   int true, false;
4075
4076   if (TREE_CODE (expr) != COND_EXPR)
4077     return 0;
4078   else if (lim <= 0)
4079     return 0;
4080
4081   true = count_cond (TREE_OPERAND (expr, 1), lim - 1);
4082   false = count_cond (TREE_OPERAND (expr, 2), lim - 1 - true);
4083   return MIN (lim, 1 + true + false);
4084 }
4085 \f
4086 /* Perform constant folding and related simplification of EXPR.
4087    The related simplifications include x*1 => x, x*0 => 0, etc.,
4088    and application of the associative law.
4089    NOP_EXPR conversions may be removed freely (as long as we
4090    are careful not to change the C type of the overall expression)
4091    We cannot simplify through a CONVERT_EXPR, FIX_EXPR or FLOAT_EXPR,
4092    but we can constant-fold them if they have constant operands.  */
4093
4094 tree
4095 fold (expr)
4096      tree expr;
4097 {
4098   register tree t = expr;
4099   tree t1 = NULL_TREE;
4100   tree tem;
4101   tree type = TREE_TYPE (expr);
4102   register tree arg0 = NULL_TREE, arg1 = NULL_TREE;
4103   register enum tree_code code = TREE_CODE (t);
4104   register int kind;
4105   int invert;
4106
4107   /* WINS will be nonzero when the switch is done
4108      if all operands are constant.  */
4109
4110   int wins = 1;
4111
4112   /* Don't try to process an RTL_EXPR since its operands aren't trees.
4113      Likewise for a SAVE_EXPR that's already been evaluated.  */
4114   if (code == RTL_EXPR || (code == SAVE_EXPR && SAVE_EXPR_RTL (t)) != 0)
4115     return t;
4116
4117   /* Return right away if already constant.  */
4118   if (TREE_CONSTANT (t))
4119     {
4120       if (code == CONST_DECL)
4121         return DECL_INITIAL (t);
4122       return t;
4123     }
4124
4125 #ifdef MAX_INTEGER_COMPUTATION_MODE
4126   check_max_integer_computation_mode (expr);
4127 #endif
4128
4129   kind = TREE_CODE_CLASS (code);
4130   if (code == NOP_EXPR || code == FLOAT_EXPR || code == CONVERT_EXPR)
4131     {
4132       tree subop;
4133
4134       /* Special case for conversion ops that can have fixed point args.  */
4135       arg0 = TREE_OPERAND (t, 0);
4136
4137       /* Don't use STRIP_NOPS, because signedness of argument type matters.  */
4138       if (arg0 != 0)
4139         STRIP_TYPE_NOPS (arg0);
4140
4141       if (arg0 != 0 && TREE_CODE (arg0) == COMPLEX_CST)
4142         subop = TREE_REALPART (arg0);
4143       else
4144         subop = arg0;
4145
4146       if (subop != 0 && TREE_CODE (subop) != INTEGER_CST
4147 #if ! defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
4148           && TREE_CODE (subop) != REAL_CST
4149 #endif /* not REAL_IS_NOT_DOUBLE, or REAL_ARITHMETIC */
4150           )
4151         /* Note that TREE_CONSTANT isn't enough:
4152            static var addresses are constant but we can't
4153            do arithmetic on them.  */
4154         wins = 0;
4155     }
4156   else if (kind == 'e' || kind == '<'
4157            || kind == '1' || kind == '2' || kind == 'r')
4158     {
4159       register int len = tree_code_length[(int) code];
4160       register int i;
4161       for (i = 0; i < len; i++)
4162         {
4163           tree op = TREE_OPERAND (t, i);
4164           tree subop;
4165
4166           if (op == 0)
4167             continue;           /* Valid for CALL_EXPR, at least.  */
4168
4169           if (kind == '<' || code == RSHIFT_EXPR)
4170             {
4171               /* Signedness matters here.  Perhaps we can refine this
4172                  later.  */
4173               STRIP_TYPE_NOPS (op);
4174             }
4175           else
4176             {
4177               /* Strip any conversions that don't change the mode.  */
4178               STRIP_NOPS (op);
4179             }
4180
4181           if (TREE_CODE (op) == COMPLEX_CST)
4182             subop = TREE_REALPART (op);
4183           else
4184             subop = op;
4185
4186           if (TREE_CODE (subop) != INTEGER_CST
4187 #if ! defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
4188               && TREE_CODE (subop) != REAL_CST
4189 #endif /* not REAL_IS_NOT_DOUBLE, or REAL_ARITHMETIC */
4190               )
4191             /* Note that TREE_CONSTANT isn't enough:
4192                static var addresses are constant but we can't
4193                do arithmetic on them.  */
4194             wins = 0;
4195
4196           if (i == 0)
4197             arg0 = op;
4198           else if (i == 1)
4199             arg1 = op;
4200         }
4201     }
4202
4203   /* If this is a commutative operation, and ARG0 is a constant, move it
4204      to ARG1 to reduce the number of tests below.  */
4205   if ((code == PLUS_EXPR || code == MULT_EXPR || code == MIN_EXPR
4206        || code == MAX_EXPR || code == BIT_IOR_EXPR || code == BIT_XOR_EXPR
4207        || code == BIT_AND_EXPR)
4208       && (TREE_CODE (arg0) == INTEGER_CST || TREE_CODE (arg0) == REAL_CST))
4209     {
4210       tem = arg0; arg0 = arg1; arg1 = tem;
4211
4212       tem = TREE_OPERAND (t, 0); TREE_OPERAND (t, 0) = TREE_OPERAND (t, 1);
4213       TREE_OPERAND (t, 1) = tem;
4214     }
4215
4216   /* Now WINS is set as described above,
4217      ARG0 is the first operand of EXPR,
4218      and ARG1 is the second operand (if it has more than one operand).
4219
4220      First check for cases where an arithmetic operation is applied to a
4221      compound, conditional, or comparison operation.  Push the arithmetic
4222      operation inside the compound or conditional to see if any folding
4223      can then be done.  Convert comparison to conditional for this purpose.
4224      The also optimizes non-constant cases that used to be done in
4225      expand_expr.
4226
4227      Before we do that, see if this is a BIT_AND_EXPR or a BIT_OR_EXPR,
4228      one of the operands is a comparison and the other is a comparison, a
4229      BIT_AND_EXPR with the constant 1, or a truth value.  In that case, the
4230      code below would make the expression more complex.  Change it to a
4231      TRUTH_{AND,OR}_EXPR.  Likewise, convert a similar NE_EXPR to
4232      TRUTH_XOR_EXPR and an EQ_EXPR to the inversion of a TRUTH_XOR_EXPR.  */
4233
4234   if ((code == BIT_AND_EXPR || code == BIT_IOR_EXPR
4235        || code == EQ_EXPR || code == NE_EXPR)
4236       && ((truth_value_p (TREE_CODE (arg0))
4237            && (truth_value_p (TREE_CODE (arg1))
4238                || (TREE_CODE (arg1) == BIT_AND_EXPR
4239                    && integer_onep (TREE_OPERAND (arg1, 1)))))
4240           || (truth_value_p (TREE_CODE (arg1))
4241               && (truth_value_p (TREE_CODE (arg0))
4242                   || (TREE_CODE (arg0) == BIT_AND_EXPR
4243                       && integer_onep (TREE_OPERAND (arg0, 1)))))))
4244     {
4245       t = fold (build (code == BIT_AND_EXPR ? TRUTH_AND_EXPR
4246                        : code == BIT_IOR_EXPR ? TRUTH_OR_EXPR
4247                        : TRUTH_XOR_EXPR,
4248                        type, arg0, arg1));
4249
4250       if (code == EQ_EXPR)
4251         t = invert_truthvalue (t);
4252
4253       return t;
4254     }
4255
4256   if (TREE_CODE_CLASS (code) == '1')
4257     {
4258       if (TREE_CODE (arg0) == COMPOUND_EXPR)
4259         return build (COMPOUND_EXPR, type, TREE_OPERAND (arg0, 0),
4260                       fold (build1 (code, type, TREE_OPERAND (arg0, 1))));
4261       else if (TREE_CODE (arg0) == COND_EXPR)
4262         {
4263           t = fold (build (COND_EXPR, type, TREE_OPERAND (arg0, 0),
4264                            fold (build1 (code, type, TREE_OPERAND (arg0, 1))),
4265                            fold (build1 (code, type, TREE_OPERAND (arg0, 2)))));
4266
4267           /* If this was a conversion, and all we did was to move into
4268              inside the COND_EXPR, bring it back out.  But leave it if
4269              it is a conversion from integer to integer and the
4270              result precision is no wider than a word since such a
4271              conversion is cheap and may be optimized away by combine,
4272              while it couldn't if it were outside the COND_EXPR.  Then return
4273              so we don't get into an infinite recursion loop taking the
4274              conversion out and then back in.  */
4275
4276           if ((code == NOP_EXPR || code == CONVERT_EXPR
4277                || code == NON_LVALUE_EXPR)
4278               && TREE_CODE (t) == COND_EXPR
4279               && TREE_CODE (TREE_OPERAND (t, 1)) == code
4280               && TREE_CODE (TREE_OPERAND (t, 2)) == code
4281               && (TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 1), 0))
4282                   == TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 2), 0)))
4283               && ! (INTEGRAL_TYPE_P (TREE_TYPE (t))
4284                     && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 1), 0)))
4285                     && TYPE_PRECISION (TREE_TYPE (t)) <= BITS_PER_WORD))
4286             t = build1 (code, type,
4287                         build (COND_EXPR,
4288                                TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 1), 0)),
4289                                TREE_OPERAND (t, 0),
4290                                TREE_OPERAND (TREE_OPERAND (t, 1), 0),
4291                                TREE_OPERAND (TREE_OPERAND (t, 2), 0)));
4292           return t;
4293         }
4294       else if (TREE_CODE_CLASS (TREE_CODE (arg0)) == '<')
4295         return fold (build (COND_EXPR, type, arg0,
4296                             fold (build1 (code, type, integer_one_node)),
4297                             fold (build1 (code, type, integer_zero_node))));
4298    }
4299   else if (TREE_CODE_CLASS (code) == '2'
4300            || TREE_CODE_CLASS (code) == '<')
4301     {
4302       if (TREE_CODE (arg1) == COMPOUND_EXPR)
4303         return build (COMPOUND_EXPR, type, TREE_OPERAND (arg1, 0),
4304                       fold (build (code, type,
4305                                    arg0, TREE_OPERAND (arg1, 1))));
4306       else if ((TREE_CODE (arg1) == COND_EXPR
4307                 || (TREE_CODE_CLASS (TREE_CODE (arg1)) == '<'
4308                     && TREE_CODE_CLASS (code) != '<'))
4309                && (TREE_CODE (arg0) != COND_EXPR
4310                    || count_cond (arg0, 25) + count_cond (arg1, 25) <= 25)
4311                && (! TREE_SIDE_EFFECTS (arg0)
4312                    || (current_function_decl != 0
4313                        && ! contains_placeholder_p (arg0))))
4314         {
4315           tree test, true_value, false_value;
4316           tree lhs = 0, rhs = 0;
4317
4318           if (TREE_CODE (arg1) == COND_EXPR)
4319             {
4320               test = TREE_OPERAND (arg1, 0);
4321               true_value = TREE_OPERAND (arg1, 1);
4322               false_value = TREE_OPERAND (arg1, 2);
4323             }
4324           else
4325             {
4326               tree testtype = TREE_TYPE (arg1);
4327               test = arg1;
4328               true_value = convert (testtype, integer_one_node);
4329               false_value = convert (testtype, integer_zero_node);
4330             }
4331
4332           /* If ARG0 is complex we want to make sure we only evaluate
4333              it once.  Though this is only required if it is volatile, it
4334              might be more efficient even if it is not.  However, if we
4335              succeed in folding one part to a constant, we do not need
4336              to make this SAVE_EXPR.  Since we do this optimization
4337              primarily to see if we do end up with constant and this
4338              SAVE_EXPR interferes with later optimizations, suppressing
4339              it when we can is important.
4340
4341              If we are not in a function, we can't make a SAVE_EXPR, so don't
4342              try to do so.  Don't try to see if the result is a constant
4343              if an arm is a COND_EXPR since we get exponential behavior
4344              in that case.  */
4345
4346           if (TREE_CODE (arg0) != SAVE_EXPR && ! TREE_CONSTANT (arg0)
4347               && current_function_decl != 0
4348               && ((TREE_CODE (arg0) != VAR_DECL
4349                    && TREE_CODE (arg0) != PARM_DECL)
4350                   || TREE_SIDE_EFFECTS (arg0)))
4351             {
4352               if (TREE_CODE (true_value) != COND_EXPR)
4353                 lhs = fold (build (code, type, arg0, true_value));
4354
4355               if (TREE_CODE (false_value) != COND_EXPR)
4356                 rhs = fold (build (code, type, arg0, false_value));
4357
4358               if ((lhs == 0 || ! TREE_CONSTANT (lhs))
4359                   && (rhs == 0 || !TREE_CONSTANT (rhs)))
4360                 arg0 = save_expr (arg0), lhs = rhs = 0;
4361             }
4362
4363           if (lhs == 0)
4364             lhs = fold (build (code, type, arg0, true_value));
4365           if (rhs == 0)
4366             rhs = fold (build (code, type, arg0, false_value));
4367
4368           test = fold (build (COND_EXPR, type, test, lhs, rhs));
4369
4370           if (TREE_CODE (arg0) == SAVE_EXPR)
4371             return build (COMPOUND_EXPR, type,
4372                           convert (void_type_node, arg0),
4373                           strip_compound_expr (test, arg0));
4374           else
4375             return convert (type, test);
4376         }
4377
4378       else if (TREE_CODE (arg0) == COMPOUND_EXPR)
4379         return build (COMPOUND_EXPR, type, TREE_OPERAND (arg0, 0),
4380                       fold (build (code, type, TREE_OPERAND (arg0, 1), arg1)));
4381       else if ((TREE_CODE (arg0) == COND_EXPR
4382                 || (TREE_CODE_CLASS (TREE_CODE (arg0)) == '<'
4383                     && TREE_CODE_CLASS (code) != '<'))
4384                && (TREE_CODE (arg1) != COND_EXPR
4385                    || count_cond (arg0, 25) + count_cond (arg1, 25) <= 25)
4386                && (! TREE_SIDE_EFFECTS (arg1)
4387                    || (current_function_decl != 0
4388                        && ! contains_placeholder_p (arg1))))
4389         {
4390           tree test, true_value, false_value;
4391           tree lhs = 0, rhs = 0;
4392
4393           if (TREE_CODE (arg0) == COND_EXPR)
4394             {
4395               test = TREE_OPERAND (arg0, 0);
4396               true_value = TREE_OPERAND (arg0, 1);
4397               false_value = TREE_OPERAND (arg0, 2);
4398             }
4399           else
4400             {
4401               tree testtype = TREE_TYPE (arg0);
4402               test = arg0;
4403               true_value = convert (testtype, integer_one_node);
4404               false_value = convert (testtype, integer_zero_node);
4405             }
4406
4407           if (TREE_CODE (arg1) != SAVE_EXPR && ! TREE_CONSTANT (arg0)
4408               && current_function_decl != 0
4409               && ((TREE_CODE (arg1) != VAR_DECL
4410                    && TREE_CODE (arg1) != PARM_DECL)
4411                   || TREE_SIDE_EFFECTS (arg1)))
4412             {
4413               if (TREE_CODE (true_value) != COND_EXPR)
4414                 lhs = fold (build (code, type, true_value, arg1));
4415
4416               if (TREE_CODE (false_value) != COND_EXPR)
4417                 rhs = fold (build (code, type, false_value, arg1));
4418
4419               if ((lhs == 0 || ! TREE_CONSTANT (lhs))
4420                   && (rhs == 0 || !TREE_CONSTANT (rhs)))
4421                 arg1 = save_expr (arg1), lhs = rhs = 0;
4422             }
4423
4424           if (lhs == 0)
4425             lhs = fold (build (code, type, true_value, arg1));
4426
4427           if (rhs == 0)
4428             rhs = fold (build (code, type, false_value, arg1));
4429
4430           test = fold (build (COND_EXPR, type, test, lhs, rhs));
4431           if (TREE_CODE (arg1) == SAVE_EXPR)
4432             return build (COMPOUND_EXPR, type,
4433                           convert (void_type_node, arg1),
4434                           strip_compound_expr (test, arg1));
4435           else
4436             return convert (type, test);
4437         }
4438     }
4439   else if (TREE_CODE_CLASS (code) == '<'
4440            && TREE_CODE (arg0) == COMPOUND_EXPR)
4441     return build (COMPOUND_EXPR, type, TREE_OPERAND (arg0, 0),
4442                   fold (build (code, type, TREE_OPERAND (arg0, 1), arg1)));
4443   else if (TREE_CODE_CLASS (code) == '<'
4444            && TREE_CODE (arg1) == COMPOUND_EXPR)
4445     return build (COMPOUND_EXPR, type, TREE_OPERAND (arg1, 0),
4446                   fold (build (code, type, arg0, TREE_OPERAND (arg1, 1))));
4447
4448   switch (code)
4449     {
4450     case INTEGER_CST:
4451     case REAL_CST:
4452     case STRING_CST:
4453     case COMPLEX_CST:
4454     case CONSTRUCTOR:
4455       return t;
4456
4457     case CONST_DECL:
4458       return fold (DECL_INITIAL (t));
4459
4460     case NOP_EXPR:
4461     case FLOAT_EXPR:
4462     case CONVERT_EXPR:
4463     case FIX_TRUNC_EXPR:
4464       /* Other kinds of FIX are not handled properly by fold_convert.  */
4465
4466       if (TREE_TYPE (TREE_OPERAND (t, 0)) == TREE_TYPE (t))
4467         return TREE_OPERAND (t, 0);
4468
4469       /* Handle cases of two conversions in a row.  */
4470       if (TREE_CODE (TREE_OPERAND (t, 0)) == NOP_EXPR
4471           || TREE_CODE (TREE_OPERAND (t, 0)) == CONVERT_EXPR)
4472         {
4473           tree inside_type = TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 0), 0));
4474           tree inter_type = TREE_TYPE (TREE_OPERAND (t, 0));
4475           tree final_type = TREE_TYPE (t);
4476           int inside_int = INTEGRAL_TYPE_P (inside_type);
4477           int inside_ptr = POINTER_TYPE_P (inside_type);
4478           int inside_float = FLOAT_TYPE_P (inside_type);
4479           int inside_prec = TYPE_PRECISION (inside_type);
4480           int inside_unsignedp = TREE_UNSIGNED (inside_type);
4481           int inter_int = INTEGRAL_TYPE_P (inter_type);
4482           int inter_ptr = POINTER_TYPE_P (inter_type);
4483           int inter_float = FLOAT_TYPE_P (inter_type);
4484           int inter_prec = TYPE_PRECISION (inter_type);
4485           int inter_unsignedp = TREE_UNSIGNED (inter_type);
4486           int final_int = INTEGRAL_TYPE_P (final_type);
4487           int final_ptr = POINTER_TYPE_P (final_type);
4488           int final_float = FLOAT_TYPE_P (final_type);
4489           int final_prec = TYPE_PRECISION (final_type);
4490           int final_unsignedp = TREE_UNSIGNED (final_type);
4491
4492           /* In addition to the cases of two conversions in a row
4493              handled below, if we are converting something to its own
4494              type via an object of identical or wider precision, neither
4495              conversion is needed.  */
4496           if (inside_type == final_type
4497               && ((inter_int && final_int) || (inter_float && final_float))
4498               && inter_prec >= final_prec)
4499             return TREE_OPERAND (TREE_OPERAND (t, 0), 0);
4500
4501           /* Likewise, if the intermediate and final types are either both
4502              float or both integer, we don't need the middle conversion if
4503              it is wider than the final type and doesn't change the signedness
4504              (for integers).  Avoid this if the final type is a pointer
4505              since then we sometimes need the inner conversion.  Likewise if
4506              the outer has a precision not equal to the size of its mode.  */
4507           if ((((inter_int || inter_ptr) && (inside_int || inside_ptr))
4508                || (inter_float && inside_float))
4509               && inter_prec >= inside_prec
4510               && (inter_float || inter_unsignedp == inside_unsignedp)
4511               && ! (final_prec != GET_MODE_BITSIZE (TYPE_MODE (final_type))
4512                     && TYPE_MODE (final_type) == TYPE_MODE (inter_type))
4513               && ! final_ptr)
4514             return convert (final_type, TREE_OPERAND (TREE_OPERAND (t, 0), 0));
4515
4516           /* If we have a sign-extension of a zero-extended value, we can
4517              replace that by a single zero-extension.  */
4518           if (inside_int && inter_int && final_int
4519               && inside_prec < inter_prec && inter_prec < final_prec
4520               && inside_unsignedp && !inter_unsignedp)
4521             return convert (final_type, TREE_OPERAND (TREE_OPERAND (t, 0), 0));
4522
4523           /* Two conversions in a row are not needed unless:
4524              - some conversion is floating-point (overstrict for now), or
4525              - the intermediate type is narrower than both initial and
4526                final, or
4527              - the intermediate type and innermost type differ in signedness,
4528                and the outermost type is wider than the intermediate, or
4529              - the initial type is a pointer type and the precisions of the
4530                intermediate and final types differ, or
4531              - the final type is a pointer type and the precisions of the
4532                initial and intermediate types differ.  */
4533           if (! inside_float && ! inter_float && ! final_float
4534               && (inter_prec > inside_prec || inter_prec > final_prec)
4535               && ! (inside_int && inter_int
4536                     && inter_unsignedp != inside_unsignedp
4537                     && inter_prec < final_prec)
4538               && ((inter_unsignedp && inter_prec > inside_prec)
4539                   == (final_unsignedp && final_prec > inter_prec))
4540               && ! (inside_ptr && inter_prec != final_prec)
4541               && ! (final_ptr && inside_prec != inter_prec)
4542               && ! (final_prec != GET_MODE_BITSIZE (TYPE_MODE (final_type))
4543                     && TYPE_MODE (final_type) == TYPE_MODE (inter_type))
4544               && ! final_ptr)
4545             return convert (final_type, TREE_OPERAND (TREE_OPERAND (t, 0), 0));
4546         }
4547
4548       if (TREE_CODE (TREE_OPERAND (t, 0)) == MODIFY_EXPR
4549           && TREE_CONSTANT (TREE_OPERAND (TREE_OPERAND (t, 0), 1))
4550           /* Detect assigning a bitfield.  */
4551           && !(TREE_CODE (TREE_OPERAND (TREE_OPERAND (t, 0), 0)) == COMPONENT_REF
4552                && DECL_BIT_FIELD (TREE_OPERAND (TREE_OPERAND (TREE_OPERAND (t, 0), 0), 1))))
4553         {
4554           /* Don't leave an assignment inside a conversion
4555              unless assigning a bitfield.  */
4556           tree prev = TREE_OPERAND (t, 0);
4557           TREE_OPERAND (t, 0) = TREE_OPERAND (prev, 1);
4558           /* First do the assignment, then return converted constant.  */
4559           t = build (COMPOUND_EXPR, TREE_TYPE (t), prev, fold (t));
4560           TREE_USED (t) = 1;
4561           return t;
4562         }
4563       if (!wins)
4564         {
4565           TREE_CONSTANT (t) = TREE_CONSTANT (arg0);
4566           return t;
4567         }
4568       return fold_convert (t, arg0);
4569
4570 #if 0  /* This loses on &"foo"[0].  */
4571     case ARRAY_REF:
4572         {
4573           int i;
4574
4575           /* Fold an expression like: "foo"[2] */
4576           if (TREE_CODE (arg0) == STRING_CST
4577               && TREE_CODE (arg1) == INTEGER_CST
4578               && !TREE_INT_CST_HIGH (arg1)
4579               && (i = TREE_INT_CST_LOW (arg1)) < TREE_STRING_LENGTH (arg0))
4580             {
4581               t = build_int_2 (TREE_STRING_POINTER (arg0)[i], 0);
4582               TREE_TYPE (t) = TREE_TYPE (TREE_TYPE (arg0));
4583               force_fit_type (t, 0);
4584             }
4585         }
4586       return t;
4587 #endif /* 0 */
4588
4589     case COMPONENT_REF:
4590       if (TREE_CODE (arg0) == CONSTRUCTOR)
4591         {
4592           tree m = purpose_member (arg1, CONSTRUCTOR_ELTS (arg0));
4593           if (m)
4594             t = TREE_VALUE (m);
4595         }
4596       return t;
4597
4598     case RANGE_EXPR:
4599       TREE_CONSTANT (t) = wins;
4600       return t;
4601
4602     case NEGATE_EXPR:
4603       if (wins)
4604         {
4605           if (TREE_CODE (arg0) == INTEGER_CST)
4606             {
4607               HOST_WIDE_INT low, high;
4608               int overflow = neg_double (TREE_INT_CST_LOW (arg0),
4609                                          TREE_INT_CST_HIGH (arg0),
4610                                          &low, &high);
4611               t = build_int_2 (low, high);
4612               TREE_TYPE (t) = type;
4613               TREE_OVERFLOW (t)
4614                 = (TREE_OVERFLOW (arg0)
4615                    | force_fit_type (t, overflow && !TREE_UNSIGNED (type)));
4616               TREE_CONSTANT_OVERFLOW (t)
4617                 = TREE_OVERFLOW (t) | TREE_CONSTANT_OVERFLOW (arg0);
4618             }
4619           else if (TREE_CODE (arg0) == REAL_CST)
4620             t = build_real (type, REAL_VALUE_NEGATE (TREE_REAL_CST (arg0)));
4621         }
4622       else if (TREE_CODE (arg0) == NEGATE_EXPR)
4623         return TREE_OPERAND (arg0, 0);
4624
4625       /* Convert - (a - b) to (b - a) for non-floating-point.  */
4626       else if (TREE_CODE (arg0) == MINUS_EXPR && ! FLOAT_TYPE_P (type))
4627         return build (MINUS_EXPR, type, TREE_OPERAND (arg0, 1),
4628                       TREE_OPERAND (arg0, 0));
4629
4630       return t;
4631
4632     case ABS_EXPR:
4633       if (wins)
4634         {
4635           if (TREE_CODE (arg0) == INTEGER_CST)
4636             {
4637               if (! TREE_UNSIGNED (type)
4638                   && TREE_INT_CST_HIGH (arg0) < 0)
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));
4649                   TREE_CONSTANT_OVERFLOW (t)
4650                     = TREE_OVERFLOW (t) | TREE_CONSTANT_OVERFLOW (arg0);
4651                 }
4652             }
4653           else if (TREE_CODE (arg0) == REAL_CST)
4654             {
4655               if (REAL_VALUE_NEGATIVE (TREE_REAL_CST (arg0)))
4656                 t = build_real (type,
4657                                 REAL_VALUE_NEGATE (TREE_REAL_CST (arg0)));
4658             }
4659         }
4660       else if (TREE_CODE (arg0) == ABS_EXPR || TREE_CODE (arg0) == NEGATE_EXPR)
4661         return build1 (ABS_EXPR, type, TREE_OPERAND (arg0, 0));
4662       return t;
4663
4664     case CONJ_EXPR:
4665       if (TREE_CODE (TREE_TYPE (arg0)) != COMPLEX_TYPE)
4666         return arg0;
4667       else if (TREE_CODE (arg0) == COMPLEX_EXPR)
4668         return build (COMPLEX_EXPR, TREE_TYPE (arg0),
4669                       TREE_OPERAND (arg0, 0),
4670                       fold (build1 (NEGATE_EXPR,
4671                                     TREE_TYPE (TREE_TYPE (arg0)),
4672                                     TREE_OPERAND (arg0, 1))));
4673       else if (TREE_CODE (arg0) == COMPLEX_CST)
4674         return build_complex (type, TREE_OPERAND (arg0, 0),
4675                               fold (build1 (NEGATE_EXPR,
4676                                             TREE_TYPE (TREE_TYPE (arg0)),
4677                                             TREE_OPERAND (arg0, 1))));
4678       else if (TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MINUS_EXPR)
4679         return fold (build (TREE_CODE (arg0), type,
4680                             fold (build1 (CONJ_EXPR, type,
4681                                           TREE_OPERAND (arg0, 0))),
4682                             fold (build1 (CONJ_EXPR,
4683                                           type, TREE_OPERAND (arg0, 1)))));
4684       else if (TREE_CODE (arg0) == CONJ_EXPR)
4685         return TREE_OPERAND (arg0, 0);
4686       return t;
4687
4688     case BIT_NOT_EXPR:
4689       if (wins)
4690         {
4691           t = build_int_2 (~ TREE_INT_CST_LOW (arg0),
4692                            ~ TREE_INT_CST_HIGH (arg0));
4693           TREE_TYPE (t) = type;
4694           force_fit_type (t, 0);
4695           TREE_OVERFLOW (t) = TREE_OVERFLOW (arg0);
4696           TREE_CONSTANT_OVERFLOW (t) = TREE_CONSTANT_OVERFLOW (arg0);
4697         }
4698       else if (TREE_CODE (arg0) == BIT_NOT_EXPR)
4699         return TREE_OPERAND (arg0, 0);
4700       return t;
4701
4702     case PLUS_EXPR:
4703       /* A + (-B) -> A - B */
4704       if (TREE_CODE (arg1) == NEGATE_EXPR)
4705         return fold (build (MINUS_EXPR, type, arg0, TREE_OPERAND (arg1, 0)));
4706       else if (! FLOAT_TYPE_P (type))
4707         {
4708           if (integer_zerop (arg1))
4709             return non_lvalue (convert (type, arg0));
4710
4711           /* If we are adding two BIT_AND_EXPR's, both of which are and'ing
4712              with a constant, and the two constants have no bits in common,
4713              we should treat this as a BIT_IOR_EXPR since this may produce more
4714              simplifications.  */
4715           if (TREE_CODE (arg0) == BIT_AND_EXPR
4716               && TREE_CODE (arg1) == BIT_AND_EXPR
4717               && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
4718               && TREE_CODE (TREE_OPERAND (arg1, 1)) == INTEGER_CST
4719               && integer_zerop (const_binop (BIT_AND_EXPR,
4720                                              TREE_OPERAND (arg0, 1),
4721                                              TREE_OPERAND (arg1, 1), 0)))
4722             {
4723               code = BIT_IOR_EXPR;
4724               goto bit_ior;
4725             }
4726
4727           if (TREE_CODE (arg0) == MULT_EXPR && TREE_CODE (arg1) == MULT_EXPR)
4728             {
4729               tree arg00, arg01, arg10, arg11;
4730               tree alt0, alt1, same;
4731
4732               /* (A * C) + (B * C) -> (A+B) * C.
4733                  We are most concerned about the case where C is a constant,
4734                  but other combinations show up during loop reduction.  Since
4735                  it is not difficult, try all four possibilities.  */
4736
4737               arg00 = TREE_OPERAND (arg0, 0);
4738               arg01 = TREE_OPERAND (arg0, 1);
4739               arg10 = TREE_OPERAND (arg1, 0);
4740               arg11 = TREE_OPERAND (arg1, 1);
4741               same = NULL_TREE;
4742
4743               if (operand_equal_p (arg01, arg11, 0))
4744                 same = arg01, alt0 = arg00, alt1 = arg10;
4745               else if (operand_equal_p (arg00, arg10, 0))
4746                 same = arg00, alt0 = arg01, alt1 = arg11;
4747               else if (operand_equal_p (arg00, arg11, 0))
4748                 same = arg00, alt0 = arg01, alt1 = arg10;
4749               else if (operand_equal_p (arg01, arg10, 0))
4750                 same = arg01, alt0 = arg00, alt1 = arg11;
4751
4752               if (same)
4753                 return fold (build (MULT_EXPR, type,
4754                                     fold (build (PLUS_EXPR, type, alt0, alt1)),
4755                                     same));
4756             }
4757         }
4758       /* In IEEE floating point, x+0 may not equal x.  */
4759       else if ((TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
4760                 || flag_fast_math)
4761                && real_zerop (arg1))
4762         return non_lvalue (convert (type, arg0));
4763     associate:
4764       /* In most languages, can't associate operations on floats
4765          through parentheses.  Rather than remember where the parentheses
4766          were, we don't associate floats at all.  It shouldn't matter much.
4767          However, associating multiplications is only very slightly
4768          inaccurate, so do that if -ffast-math is specified.  */
4769       if (FLOAT_TYPE_P (type)
4770           && ! (flag_fast_math && code == MULT_EXPR))
4771         goto binary;
4772
4773       /* The varsign == -1 cases happen only for addition and subtraction.
4774          It says that the arg that was split was really CON minus VAR.
4775          The rest of the code applies to all associative operations.  */
4776       if (!wins)
4777         {
4778           tree var, con;
4779           int varsign;
4780
4781           if (split_tree (arg0, code, &var, &con, &varsign))
4782             {
4783               if (varsign == -1)
4784                 {
4785                   /* EXPR is (CON-VAR) +- ARG1.  */
4786                   /* If it is + and VAR==ARG1, return just CONST.  */
4787                   if (code == PLUS_EXPR && operand_equal_p (var, arg1, 0))
4788                     return convert (TREE_TYPE (t), con);
4789
4790                   /* If ARG0 is a constant, don't change things around;
4791                      instead keep all the constant computations together.  */
4792
4793                   if (TREE_CONSTANT (arg0))
4794                     return t;
4795
4796                   /* Otherwise return (CON +- ARG1) - VAR.  */
4797                   t = build (MINUS_EXPR, type,
4798                              fold (build (code, type, con, arg1)), var);
4799                 }
4800               else
4801                 {
4802                   /* EXPR is (VAR+CON) +- ARG1.  */
4803                   /* If it is - and VAR==ARG1, return just CONST.  */
4804                   if (code == MINUS_EXPR && operand_equal_p (var, arg1, 0))
4805                     return convert (TREE_TYPE (t), con);
4806
4807                   /* If ARG0 is a constant, don't change things around;
4808                      instead keep all the constant computations together.  */
4809
4810                   if (TREE_CONSTANT (arg0))
4811                     return t;
4812
4813                   /* Otherwise return VAR +- (ARG1 +- CON).  */
4814                   tem = fold (build (code, type, arg1, con));
4815                   t = build (code, type, var, tem);
4816
4817                   if (integer_zerop (tem)
4818                       && (code == PLUS_EXPR || code == MINUS_EXPR))
4819                     return convert (type, var);
4820                   /* If we have x +/- (c - d) [c an explicit integer]
4821                      change it to x -/+ (d - c) since if d is relocatable
4822                      then the latter can be a single immediate insn
4823                      and the former cannot.  */
4824                   if (TREE_CODE (tem) == MINUS_EXPR
4825                       && TREE_CODE (TREE_OPERAND (tem, 0)) == INTEGER_CST)
4826                     {
4827                       tree tem1 = TREE_OPERAND (tem, 1);
4828                       TREE_OPERAND (tem, 1) = TREE_OPERAND (tem, 0);
4829                       TREE_OPERAND (tem, 0) = tem1;
4830                       TREE_SET_CODE (t,
4831                                      (code == PLUS_EXPR ? MINUS_EXPR : PLUS_EXPR));
4832                     }
4833                 }
4834               return t;
4835             }
4836
4837           if (split_tree (arg1, code, &var, &con, &varsign))
4838             {
4839               if (TREE_CONSTANT (arg1))
4840                 return t;
4841
4842               if (varsign == -1)
4843                 TREE_SET_CODE (t,
4844                                (code == PLUS_EXPR ? MINUS_EXPR : PLUS_EXPR));
4845
4846               /* EXPR is ARG0 +- (CON +- VAR).  */
4847               if (TREE_CODE (t) == MINUS_EXPR
4848                   && operand_equal_p (var, arg0, 0))
4849                 {
4850                   /* If VAR and ARG0 cancel, return just CON or -CON.  */
4851                   if (code == PLUS_EXPR)
4852                     return convert (TREE_TYPE (t), con);
4853                   return fold (build1 (NEGATE_EXPR, TREE_TYPE (t),
4854                                        convert (TREE_TYPE (t), con)));
4855                 }
4856
4857               t = build (TREE_CODE (t), type,
4858                          fold (build (code, TREE_TYPE (t), arg0, con)), var);
4859
4860               if (integer_zerop (TREE_OPERAND (t, 0))
4861                   && TREE_CODE (t) == PLUS_EXPR)
4862                 return convert (TREE_TYPE (t), var);
4863               return t;
4864             }
4865         }
4866     binary:
4867 #if defined (REAL_IS_NOT_DOUBLE) && ! defined (REAL_ARITHMETIC)
4868       if (TREE_CODE (arg1) == REAL_CST)
4869         return t;
4870 #endif /* REAL_IS_NOT_DOUBLE, and no REAL_ARITHMETIC */
4871       if (wins)
4872         t1 = const_binop (code, arg0, arg1, 0);
4873       if (t1 != NULL_TREE)
4874         {
4875           /* The return value should always have
4876              the same type as the original expression.  */
4877           if (TREE_TYPE (t1) != TREE_TYPE (t))
4878             t1 = convert (TREE_TYPE (t), t1);
4879
4880           return t1;
4881         }
4882       return t;
4883
4884     case MINUS_EXPR:
4885       if (! FLOAT_TYPE_P (type))
4886         {
4887           if (! wins && integer_zerop (arg0))
4888             return build1 (NEGATE_EXPR, type, arg1);
4889           if (integer_zerop (arg1))
4890             return non_lvalue (convert (type, arg0));
4891
4892           /* (A * C) - (B * C) -> (A-B) * C.  Since we are most concerned
4893              about the case where C is a constant, just try one of the
4894              four possibilities.  */
4895
4896           if (TREE_CODE (arg0) == MULT_EXPR && TREE_CODE (arg1) == MULT_EXPR
4897               && operand_equal_p (TREE_OPERAND (arg0, 1),
4898                                   TREE_OPERAND (arg1, 1), 0))
4899             return fold (build (MULT_EXPR, type,
4900                                 fold (build (MINUS_EXPR, type,
4901                                              TREE_OPERAND (arg0, 0),
4902                                              TREE_OPERAND (arg1, 0))),
4903                                 TREE_OPERAND (arg0, 1)));
4904         }
4905       /* Convert A - (-B) to A + B.  */
4906       else if (TREE_CODE (arg1) == NEGATE_EXPR)
4907         return fold (build (PLUS_EXPR, type, arg0, TREE_OPERAND (arg1, 0)));
4908
4909       else if (TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
4910                || flag_fast_math)
4911         {
4912           /* Except with IEEE floating point, 0-x equals -x.  */
4913           if (! wins && real_zerop (arg0))
4914             return build1 (NEGATE_EXPR, type, arg1);
4915           /* Except with IEEE floating point, x-0 equals x.  */
4916           if (real_zerop (arg1))
4917             return non_lvalue (convert (type, arg0));
4918         }
4919
4920       /* Fold &x - &x.  This can happen from &x.foo - &x.
4921          This is unsafe for certain floats even in non-IEEE formats.
4922          In IEEE, it is unsafe because it does wrong for NaNs.
4923          Also note that operand_equal_p is always false if an operand
4924          is volatile.  */
4925
4926       if ((! FLOAT_TYPE_P (type) || flag_fast_math)
4927           && operand_equal_p (arg0, arg1, 0))
4928         return convert (type, integer_zero_node);
4929
4930       goto associate;
4931
4932     case MULT_EXPR:
4933       if (! FLOAT_TYPE_P (type))
4934         {
4935           if (integer_zerop (arg1))
4936             return omit_one_operand (type, arg1, arg0);
4937           if (integer_onep (arg1))
4938             return non_lvalue (convert (type, arg0));
4939
4940           /* ((A / C) * C) is A if the division is an
4941              EXACT_DIV_EXPR.   Since C is normally a constant,
4942              just check for one of the four possibilities.  */
4943
4944           if (TREE_CODE (arg0) == EXACT_DIV_EXPR
4945               && operand_equal_p (TREE_OPERAND (arg0, 1), arg1, 0))
4946             return TREE_OPERAND (arg0, 0);
4947
4948           /* (a * (1 << b)) is (a << b)  */
4949           if (TREE_CODE (arg1) == LSHIFT_EXPR
4950               && integer_onep (TREE_OPERAND (arg1, 0)))
4951             return fold (build (LSHIFT_EXPR, type, arg0,
4952                                 TREE_OPERAND (arg1, 1)));
4953           if (TREE_CODE (arg0) == LSHIFT_EXPR
4954               && integer_onep (TREE_OPERAND (arg0, 0)))
4955             return fold (build (LSHIFT_EXPR, type, arg1,
4956                                 TREE_OPERAND (arg0, 1)));
4957         }
4958       else
4959         {
4960           /* x*0 is 0, except for IEEE floating point.  */
4961           if ((TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
4962                || flag_fast_math)
4963               && real_zerop (arg1))
4964             return omit_one_operand (type, arg1, arg0);
4965           /* In IEEE floating point, x*1 is not equivalent to x for snans.
4966              However, ANSI says we can drop signals,
4967              so we can do this anyway.  */
4968           if (real_onep (arg1))
4969             return non_lvalue (convert (type, arg0));
4970           /* x*2 is x+x */
4971           if (! wins && real_twop (arg1) && current_function_decl != 0
4972               && ! contains_placeholder_p (arg0))
4973             {
4974               tree arg = save_expr (arg0);
4975               return build (PLUS_EXPR, type, arg, arg);
4976             }
4977         }
4978       goto associate;
4979
4980     case BIT_IOR_EXPR:
4981     bit_ior:
4982       {
4983       register enum tree_code code0, code1;
4984
4985       if (integer_all_onesp (arg1))
4986         return omit_one_operand (type, arg1, arg0);
4987       if (integer_zerop (arg1))
4988         return non_lvalue (convert (type, arg0));
4989       t1 = distribute_bit_expr (code, type, arg0, arg1);
4990       if (t1 != NULL_TREE)
4991         return t1;
4992
4993       /* (A << C1) | (A >> C2) if A is unsigned and C1+C2 is the size of A
4994          is a rotate of A by C1 bits.  */
4995       /* (A << B) | (A >> (Z - B)) if A is unsigned and Z is the size of A
4996          is a rotate of A by B bits.  */
4997
4998       code0 = TREE_CODE (arg0);
4999       code1 = TREE_CODE (arg1);
5000       if (((code0 == RSHIFT_EXPR && code1 == LSHIFT_EXPR)
5001           || (code1 == RSHIFT_EXPR && code0 == LSHIFT_EXPR))
5002           && operand_equal_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg1,0), 0)
5003           && TREE_UNSIGNED (TREE_TYPE (TREE_OPERAND (arg0, 0))))
5004         {
5005           register tree tree01, tree11;
5006           register enum tree_code code01, code11;
5007
5008           tree01 = TREE_OPERAND (arg0, 1);
5009           tree11 = TREE_OPERAND (arg1, 1);
5010           STRIP_NOPS (tree01);
5011           STRIP_NOPS (tree11);
5012           code01 = TREE_CODE (tree01);
5013           code11 = TREE_CODE (tree11);
5014           if (code01 == INTEGER_CST
5015             && code11 == INTEGER_CST
5016             && TREE_INT_CST_HIGH (tree01) == 0
5017             && TREE_INT_CST_HIGH (tree11) == 0
5018             && ((TREE_INT_CST_LOW (tree01) + TREE_INT_CST_LOW (tree11))
5019               == TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (arg0, 0)))))
5020             return build (LROTATE_EXPR, type, TREE_OPERAND (arg0, 0),
5021                       code0 == LSHIFT_EXPR ? tree01 : tree11);
5022           else if (code11 == MINUS_EXPR)
5023             {
5024               tree tree110, tree111;
5025               tree110 = TREE_OPERAND (tree11, 0);
5026               tree111 = TREE_OPERAND (tree11, 1);
5027               STRIP_NOPS (tree110);
5028               STRIP_NOPS (tree111);
5029               if (TREE_CODE (tree110) == INTEGER_CST
5030                   && TREE_INT_CST_HIGH (tree110) == 0
5031                   && (TREE_INT_CST_LOW (tree110)
5032                       == TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (arg0, 0))))
5033                   && operand_equal_p (tree01, tree111, 0))
5034                 return build ((code0 == LSHIFT_EXPR
5035                                ? LROTATE_EXPR
5036                                : RROTATE_EXPR),
5037                               type, TREE_OPERAND (arg0, 0), tree01);
5038             }
5039           else if (code01 == MINUS_EXPR)
5040             {
5041               tree tree010, tree011;
5042               tree010 = TREE_OPERAND (tree01, 0);
5043               tree011 = TREE_OPERAND (tree01, 1);
5044               STRIP_NOPS (tree010);
5045               STRIP_NOPS (tree011);
5046               if (TREE_CODE (tree010) == INTEGER_CST
5047                   && TREE_INT_CST_HIGH (tree010) == 0
5048                   && (TREE_INT_CST_LOW (tree010)
5049                       == TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (arg0, 0))))
5050                   && operand_equal_p (tree11, tree011, 0))
5051                 return build ((code0 != LSHIFT_EXPR
5052                                ? LROTATE_EXPR
5053                                : RROTATE_EXPR),
5054                                type, TREE_OPERAND (arg0, 0), tree11);
5055             }
5056         }
5057
5058       goto associate;
5059       }
5060
5061     case BIT_XOR_EXPR:
5062       if (integer_zerop (arg1))
5063         return non_lvalue (convert (type, arg0));
5064       if (integer_all_onesp (arg1))
5065         return fold (build1 (BIT_NOT_EXPR, type, arg0));
5066       goto associate;
5067
5068     case BIT_AND_EXPR:
5069     bit_and:
5070       if (integer_all_onesp (arg1))
5071         return non_lvalue (convert (type, arg0));
5072       if (integer_zerop (arg1))
5073         return omit_one_operand (type, arg1, arg0);
5074       t1 = distribute_bit_expr (code, type, arg0, arg1);
5075       if (t1 != NULL_TREE)
5076         return t1;
5077       /* Simplify ((int)c & 0x377) into (int)c, if c is unsigned char.  */
5078       if (TREE_CODE (arg0) == INTEGER_CST && TREE_CODE (arg1) == NOP_EXPR
5079           && TREE_UNSIGNED (TREE_TYPE (TREE_OPERAND (arg1, 0))))
5080         {
5081           int prec = TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (arg1, 0)));
5082           if (prec < BITS_PER_WORD && prec < HOST_BITS_PER_WIDE_INT
5083               && (~TREE_INT_CST_LOW (arg0)
5084                   & (((HOST_WIDE_INT) 1 << prec) - 1)) == 0)
5085             return build1 (NOP_EXPR, type, TREE_OPERAND (arg1, 0));
5086         }
5087       if (TREE_CODE (arg1) == INTEGER_CST && TREE_CODE (arg0) == NOP_EXPR
5088           && TREE_UNSIGNED (TREE_TYPE (TREE_OPERAND (arg0, 0))))
5089         {
5090           int prec = TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (arg0, 0)));
5091           if (prec < BITS_PER_WORD && prec < HOST_BITS_PER_WIDE_INT
5092               && (~TREE_INT_CST_LOW (arg1)
5093                   & (((HOST_WIDE_INT) 1 << prec) - 1)) == 0)
5094             return build1 (NOP_EXPR, type, TREE_OPERAND (arg0, 0));
5095         }
5096       goto associate;
5097
5098     case BIT_ANDTC_EXPR:
5099       if (integer_all_onesp (arg0))
5100         return non_lvalue (convert (type, arg1));
5101       if (integer_zerop (arg0))
5102         return omit_one_operand (type, arg0, arg1);
5103       if (TREE_CODE (arg1) == INTEGER_CST)
5104         {
5105           arg1 = fold (build1 (BIT_NOT_EXPR, type, arg1));
5106           code = BIT_AND_EXPR;
5107           goto bit_and;
5108         }
5109       goto binary;
5110
5111     case RDIV_EXPR:
5112       /* In most cases, do nothing with a divide by zero.  */
5113 #if !defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
5114 #ifndef REAL_INFINITY
5115       if (TREE_CODE (arg1) == REAL_CST && real_zerop (arg1))
5116         return t;
5117 #endif
5118 #endif /* not REAL_IS_NOT_DOUBLE, or REAL_ARITHMETIC */
5119
5120       /* In IEEE floating point, x/1 is not equivalent to x for snans.
5121          However, ANSI says we can drop signals, so we can do this anyway.  */
5122       if (real_onep (arg1))
5123         return non_lvalue (convert (type, arg0));
5124
5125       /* If ARG1 is a constant, we can convert this to a multiply by the
5126          reciprocal.  This does not have the same rounding properties,
5127          so only do this if -ffast-math.  We can actually always safely
5128          do it if ARG1 is a power of two, but it's hard to tell if it is
5129          or not in a portable manner.  */
5130       if (TREE_CODE (arg1) == REAL_CST)
5131         {
5132           if (flag_fast_math
5133               && 0 != (tem = const_binop (code, build_real (type, dconst1),
5134                                           arg1, 0)))
5135             return fold (build (MULT_EXPR, type, arg0, tem));
5136           /* Find the reciprocal if optimizing and the result is exact. */
5137           else if (optimize)
5138             {
5139               REAL_VALUE_TYPE r;
5140               r = TREE_REAL_CST (arg1);
5141               if (exact_real_inverse (TYPE_MODE(TREE_TYPE(arg0)), &r))
5142                   {
5143                     tem = build_real (type, r);
5144                     return fold (build (MULT_EXPR, type, arg0, tem));
5145                   }
5146             }
5147         }
5148       goto binary;
5149
5150     case TRUNC_DIV_EXPR:
5151     case ROUND_DIV_EXPR:
5152     case FLOOR_DIV_EXPR:
5153     case CEIL_DIV_EXPR:
5154     case EXACT_DIV_EXPR:
5155       if (integer_onep (arg1))
5156         return non_lvalue (convert (type, arg0));
5157       if (integer_zerop (arg1))
5158         return t;
5159
5160       /* If arg0 is a multiple of arg1, then rewrite to the fastest div
5161          operation, EXACT_DIV_EXPR.
5162
5163          Note that only CEIL_DIV_EXPR and FLOOR_DIV_EXPR are rewritten now.
5164          At one time others generated faster code, it's not clear if they do
5165          after the last round to changes to the DIV code in expmed.c.  */
5166       if ((code == CEIL_DIV_EXPR || code == FLOOR_DIV_EXPR)
5167           && multiple_of_p (type, arg0, arg1))
5168         return fold (build (EXACT_DIV_EXPR, type, arg0, arg1));
5169
5170       /* If we have ((a / C1) / C2) where both division are the same type, try
5171          to simplify.  First see if C1 * C2 overflows or not.  */
5172       if (TREE_CODE (arg0) == code && TREE_CODE (arg1) == INTEGER_CST
5173           && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST)
5174         {
5175           tree new_divisor;
5176
5177           new_divisor = const_binop (MULT_EXPR, TREE_OPERAND (arg0, 1), arg1, 0);
5178           tem = const_binop (FLOOR_DIV_EXPR, new_divisor, arg1, 0);
5179
5180           if (TREE_INT_CST_LOW (TREE_OPERAND (arg0, 1)) == TREE_INT_CST_LOW (tem)
5181               && TREE_INT_CST_HIGH (TREE_OPERAND (arg0, 1)) == TREE_INT_CST_HIGH (tem))
5182             {
5183               /* If no overflow, divide by C1*C2.  */
5184               return fold (build (code, type, TREE_OPERAND (arg0, 0), new_divisor));
5185             }
5186         }
5187
5188       /* Look for ((a * C1) / C3) or (((a * C1) + C2) / C3),
5189          where C1 % C3 == 0 or C3 % C1 == 0.  We can simplify these
5190          expressions, which often appear in the offsets or sizes of
5191          objects with a varying size.  Only deal with positive divisors
5192          and multiplicands.   If C2 is negative, we must have C2 % C3 == 0.
5193
5194          Look for NOPs and SAVE_EXPRs inside.  */
5195
5196       if (TREE_CODE (arg1) == INTEGER_CST
5197           && tree_int_cst_sgn (arg1) >= 0)
5198         {
5199           int have_save_expr = 0;
5200           tree c2 = integer_zero_node;
5201           tree xarg0 = arg0;
5202
5203           if (TREE_CODE (xarg0) == SAVE_EXPR && SAVE_EXPR_RTL (xarg0) == 0)
5204             have_save_expr = 1, xarg0 = TREE_OPERAND (xarg0, 0);
5205
5206           STRIP_NOPS (xarg0);
5207
5208           /* Look inside the dividend and simplify using EXACT_DIV_EXPR
5209              if possible.  */
5210           if (TREE_CODE (xarg0) == MULT_EXPR
5211               && multiple_of_p (type, TREE_OPERAND (xarg0, 0), arg1))
5212             {
5213               tree t;
5214
5215               t = fold (build (MULT_EXPR, type,
5216                                fold (build (EXACT_DIV_EXPR, type,
5217                                             TREE_OPERAND (xarg0, 0), arg1)),
5218                                TREE_OPERAND (xarg0, 1)));
5219               if (have_save_expr)
5220                 t = save_expr (t);
5221               return t;
5222
5223             }
5224
5225           if (TREE_CODE (xarg0) == MULT_EXPR
5226               && multiple_of_p (type, TREE_OPERAND (xarg0, 1), arg1))
5227             {
5228               tree t;
5229
5230               t = fold (build (MULT_EXPR, type,
5231                                fold (build (EXACT_DIV_EXPR, type,
5232                                             TREE_OPERAND (xarg0, 1), arg1)),
5233                                TREE_OPERAND (xarg0, 0)));
5234               if (have_save_expr)
5235                 t = save_expr (t);
5236               return t;
5237             }
5238
5239           if (TREE_CODE (xarg0) == PLUS_EXPR
5240               && TREE_CODE (TREE_OPERAND (xarg0, 1)) == INTEGER_CST)
5241             c2 = TREE_OPERAND (xarg0, 1), xarg0 = TREE_OPERAND (xarg0, 0);
5242           else if (TREE_CODE (xarg0) == MINUS_EXPR
5243                    && TREE_CODE (TREE_OPERAND (xarg0, 1)) == INTEGER_CST
5244                    /* If we are doing this computation unsigned, the negate
5245                       is incorrect.  */
5246                    && ! TREE_UNSIGNED (type))
5247             {
5248               c2 = fold (build1 (NEGATE_EXPR, type, TREE_OPERAND (xarg0, 1)));
5249               xarg0 = TREE_OPERAND (xarg0, 0);
5250             }
5251
5252           if (TREE_CODE (xarg0) == SAVE_EXPR && SAVE_EXPR_RTL (xarg0) == 0)
5253             have_save_expr = 1, xarg0 = TREE_OPERAND (xarg0, 0);
5254
5255           STRIP_NOPS (xarg0);
5256
5257           if (TREE_CODE (xarg0) == MULT_EXPR
5258               && TREE_CODE (TREE_OPERAND (xarg0, 1)) == INTEGER_CST
5259               && tree_int_cst_sgn (TREE_OPERAND (xarg0, 1)) >= 0
5260               && (integer_zerop (const_binop (TRUNC_MOD_EXPR,
5261                                               TREE_OPERAND (xarg0, 1), arg1, 1))
5262                   || integer_zerop (const_binop (TRUNC_MOD_EXPR, arg1,
5263                                                  TREE_OPERAND (xarg0, 1), 1)))
5264               && (tree_int_cst_sgn (c2) >= 0
5265                   || integer_zerop (const_binop (TRUNC_MOD_EXPR, c2,
5266                                                  arg1, 1))))
5267             {
5268               tree outer_div = integer_one_node;
5269               tree c1 = TREE_OPERAND (xarg0, 1);
5270               tree c3 = arg1;
5271
5272               /* If C3 > C1, set them equal and do a divide by
5273                  C3/C1 at the end of the operation.  */
5274               if (tree_int_cst_lt (c1, c3))
5275                 outer_div = const_binop (code, c3, c1, 0), c3 = c1;
5276
5277               /* The result is A * (C1/C3) + (C2/C3).  */
5278               t = fold (build (PLUS_EXPR, type,
5279                                fold (build (MULT_EXPR, type,
5280                                             TREE_OPERAND (xarg0, 0),
5281                                             const_binop (code, c1, c3, 1))),
5282                                const_binop (code, c2, c3, 1)));
5283
5284               if (! integer_onep (outer_div))
5285                 t = fold (build (code, type, t, convert (type, outer_div)));
5286
5287               if (have_save_expr)
5288                 t = save_expr (t);
5289
5290               return t;
5291             }
5292         }
5293
5294       goto binary;
5295
5296     case CEIL_MOD_EXPR:
5297     case FLOOR_MOD_EXPR:
5298     case ROUND_MOD_EXPR:
5299     case TRUNC_MOD_EXPR:
5300       if (integer_onep (arg1))
5301         return omit_one_operand (type, integer_zero_node, arg0);
5302       if (integer_zerop (arg1))
5303         return t;
5304
5305       /* Look for ((a * C1) % C3) or (((a * C1) + C2) % C3),
5306          where C1 % C3 == 0.  Handle similarly to the division case,
5307          but don't bother with SAVE_EXPRs.  */
5308
5309       if (TREE_CODE (arg1) == INTEGER_CST
5310           && ! integer_zerop (arg1))
5311         {
5312           tree c2 = integer_zero_node;
5313           tree xarg0 = arg0;
5314
5315           if (TREE_CODE (xarg0) == PLUS_EXPR
5316               && TREE_CODE (TREE_OPERAND (xarg0, 1)) == INTEGER_CST)
5317             c2 = TREE_OPERAND (xarg0, 1), xarg0 = TREE_OPERAND (xarg0, 0);
5318           else if (TREE_CODE (xarg0) == MINUS_EXPR
5319                    && TREE_CODE (TREE_OPERAND (xarg0, 1)) == INTEGER_CST
5320                    && ! TREE_UNSIGNED (type))
5321             {
5322               c2 = fold (build1 (NEGATE_EXPR, type, TREE_OPERAND (xarg0, 1)));
5323               xarg0 = TREE_OPERAND (xarg0, 0);
5324             }
5325
5326           STRIP_NOPS (xarg0);
5327
5328           if (TREE_CODE (xarg0) == MULT_EXPR
5329               && TREE_CODE (TREE_OPERAND (xarg0, 1)) == INTEGER_CST
5330               && integer_zerop (const_binop (TRUNC_MOD_EXPR,
5331                                              TREE_OPERAND (xarg0, 1),
5332                                              arg1, 1))
5333               && tree_int_cst_sgn (c2) >= 0)
5334             /* The result is (C2%C3).  */
5335             return omit_one_operand (type, const_binop (code, c2, arg1, 1),
5336                                      TREE_OPERAND (xarg0, 0));
5337         }
5338
5339       goto binary;
5340
5341     case LSHIFT_EXPR:
5342     case RSHIFT_EXPR:
5343     case LROTATE_EXPR:
5344     case RROTATE_EXPR:
5345       if (integer_zerop (arg1))
5346         return non_lvalue (convert (type, arg0));
5347       /* Since negative shift count is not well-defined,
5348          don't try to compute it in the compiler.  */
5349       if (TREE_CODE (arg1) == INTEGER_CST && tree_int_cst_sgn (arg1) < 0)
5350         return t;
5351       /* Rewrite an LROTATE_EXPR by a constant into an
5352          RROTATE_EXPR by a new constant.  */
5353       if (code == LROTATE_EXPR && TREE_CODE (arg1) == INTEGER_CST)
5354         {
5355           TREE_SET_CODE (t, RROTATE_EXPR);
5356           code = RROTATE_EXPR;
5357           TREE_OPERAND (t, 1) = arg1
5358             = const_binop
5359               (MINUS_EXPR,
5360                convert (TREE_TYPE (arg1),
5361                         build_int_2 (GET_MODE_BITSIZE (TYPE_MODE (type)), 0)),
5362                arg1, 0);
5363           if (tree_int_cst_sgn (arg1) < 0)
5364             return t;
5365         }
5366
5367       /* If we have a rotate of a bit operation with the rotate count and
5368          the second operand of the bit operation both constant,
5369          permute the two operations.  */
5370       if (code == RROTATE_EXPR && TREE_CODE (arg1) == INTEGER_CST
5371           && (TREE_CODE (arg0) == BIT_AND_EXPR
5372               || TREE_CODE (arg0) == BIT_ANDTC_EXPR
5373               || TREE_CODE (arg0) == BIT_IOR_EXPR
5374               || TREE_CODE (arg0) == BIT_XOR_EXPR)
5375           && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST)
5376         return fold (build (TREE_CODE (arg0), type,
5377                             fold (build (code, type,
5378                                          TREE_OPERAND (arg0, 0), arg1)),
5379                             fold (build (code, type,
5380                                          TREE_OPERAND (arg0, 1), arg1))));
5381
5382       /* Two consecutive rotates adding up to the width of the mode can
5383          be ignored.  */
5384       if (code == RROTATE_EXPR && TREE_CODE (arg1) == INTEGER_CST
5385           && TREE_CODE (arg0) == RROTATE_EXPR
5386           && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
5387           && TREE_INT_CST_HIGH (arg1) == 0
5388           && TREE_INT_CST_HIGH (TREE_OPERAND (arg0, 1)) == 0
5389           && ((TREE_INT_CST_LOW (arg1)
5390                + TREE_INT_CST_LOW (TREE_OPERAND (arg0, 1)))
5391               == GET_MODE_BITSIZE (TYPE_MODE (type))))
5392         return TREE_OPERAND (arg0, 0);
5393
5394       goto binary;
5395
5396     case MIN_EXPR:
5397       if (operand_equal_p (arg0, arg1, 0))
5398         return arg0;
5399       if (INTEGRAL_TYPE_P (type)
5400           && operand_equal_p (arg1, TYPE_MIN_VALUE (type), 1))
5401         return omit_one_operand (type, arg1, arg0);
5402       goto associate;
5403
5404     case MAX_EXPR:
5405       if (operand_equal_p (arg0, arg1, 0))
5406         return arg0;
5407       if (INTEGRAL_TYPE_P (type)
5408           && TYPE_MAX_VALUE (type)
5409           && operand_equal_p (arg1, TYPE_MAX_VALUE (type), 1))
5410         return omit_one_operand (type, arg1, arg0);
5411       goto associate;
5412
5413     case TRUTH_NOT_EXPR:
5414       /* Note that the operand of this must be an int
5415          and its values must be 0 or 1.
5416          ("true" is a fixed value perhaps depending on the language,
5417          but we don't handle values other than 1 correctly yet.)  */
5418       tem = invert_truthvalue (arg0);
5419       /* Avoid infinite recursion.  */
5420       if (TREE_CODE (tem) == TRUTH_NOT_EXPR)
5421         return t;
5422       return convert (type, tem);
5423
5424     case TRUTH_ANDIF_EXPR:
5425       /* Note that the operands of this must be ints
5426          and their values must be 0 or 1.
5427          ("true" is a fixed value perhaps depending on the language.)  */
5428       /* If first arg is constant zero, return it.  */
5429       if (integer_zerop (arg0))
5430         return arg0;
5431     case TRUTH_AND_EXPR:
5432       /* If either arg is constant true, drop it.  */
5433       if (TREE_CODE (arg0) == INTEGER_CST && ! integer_zerop (arg0))
5434         return non_lvalue (arg1);
5435       if (TREE_CODE (arg1) == INTEGER_CST && ! integer_zerop (arg1))
5436         return non_lvalue (arg0);
5437       /* If second arg is constant zero, result is zero, but first arg
5438          must be evaluated.  */
5439       if (integer_zerop (arg1))
5440         return omit_one_operand (type, arg1, arg0);
5441       /* Likewise for first arg, but note that only the TRUTH_AND_EXPR
5442          case will be handled here.  */
5443       if (integer_zerop (arg0))
5444         return omit_one_operand (type, arg0, arg1);
5445
5446     truth_andor:
5447       /* We only do these simplifications if we are optimizing.  */
5448       if (!optimize)
5449         return t;
5450
5451       /* Check for things like (A || B) && (A || C).  We can convert this
5452          to A || (B && C).  Note that either operator can be any of the four
5453          truth and/or operations and the transformation will still be
5454          valid.   Also note that we only care about order for the
5455          ANDIF and ORIF operators.  If B contains side effects, this
5456          might change the truth-value of A. */
5457       if (TREE_CODE (arg0) == TREE_CODE (arg1)
5458           && (TREE_CODE (arg0) == TRUTH_ANDIF_EXPR
5459               || TREE_CODE (arg0) == TRUTH_ORIF_EXPR
5460               || TREE_CODE (arg0) == TRUTH_AND_EXPR
5461               || TREE_CODE (arg0) == TRUTH_OR_EXPR)
5462           && ! TREE_SIDE_EFFECTS (TREE_OPERAND (arg0, 1)))
5463         {
5464           tree a00 = TREE_OPERAND (arg0, 0);
5465           tree a01 = TREE_OPERAND (arg0, 1);
5466           tree a10 = TREE_OPERAND (arg1, 0);
5467           tree a11 = TREE_OPERAND (arg1, 1);
5468           int commutative = ((TREE_CODE (arg0) == TRUTH_OR_EXPR
5469                               || TREE_CODE (arg0) == TRUTH_AND_EXPR)
5470                              && (code == TRUTH_AND_EXPR
5471                                  || code == TRUTH_OR_EXPR));
5472
5473           if (operand_equal_p (a00, a10, 0))
5474             return fold (build (TREE_CODE (arg0), type, a00,
5475                                 fold (build (code, type, a01, a11))));
5476           else if (commutative && operand_equal_p (a00, a11, 0))
5477             return fold (build (TREE_CODE (arg0), type, a00,
5478                                 fold (build (code, type, a01, a10))));
5479           else if (commutative && operand_equal_p (a01, a10, 0))
5480             return fold (build (TREE_CODE (arg0), type, a01,
5481                                 fold (build (code, type, a00, a11))));
5482
5483           /* This case if tricky because we must either have commutative
5484              operators or else A10 must not have side-effects.  */
5485
5486           else if ((commutative || ! TREE_SIDE_EFFECTS (a10))
5487                    && operand_equal_p (a01, a11, 0))
5488             return fold (build (TREE_CODE (arg0), type,
5489                                 fold (build (code, type, a00, a10)),
5490                                 a01));
5491         }
5492
5493       /* See if we can build a range comparison.  */
5494       if (0 != (tem = fold_range_test (t)))
5495         return tem;
5496
5497       /* Check for the possibility of merging component references.  If our
5498          lhs is another similar operation, try to merge its rhs with our
5499          rhs.  Then try to merge our lhs and rhs.  */
5500       if (TREE_CODE (arg0) == code
5501           && 0 != (tem = fold_truthop (code, type,
5502                                        TREE_OPERAND (arg0, 1), arg1)))
5503         return fold (build (code, type, TREE_OPERAND (arg0, 0), tem));
5504
5505       if ((tem = fold_truthop (code, type, arg0, arg1)) != 0)
5506         return tem;
5507
5508       return t;
5509
5510     case TRUTH_ORIF_EXPR:
5511       /* Note that the operands of this must be ints
5512          and their values must be 0 or true.
5513          ("true" is a fixed value perhaps depending on the language.)  */
5514       /* If first arg is constant true, return it.  */
5515       if (TREE_CODE (arg0) == INTEGER_CST && ! integer_zerop (arg0))
5516         return arg0;
5517     case TRUTH_OR_EXPR:
5518       /* If either arg is constant zero, drop it.  */
5519       if (TREE_CODE (arg0) == INTEGER_CST && integer_zerop (arg0))
5520         return non_lvalue (arg1);
5521       if (TREE_CODE (arg1) == INTEGER_CST && integer_zerop (arg1))
5522         return non_lvalue (arg0);
5523       /* If second arg is constant true, result is true, but we must
5524          evaluate first arg.  */
5525       if (TREE_CODE (arg1) == INTEGER_CST && ! integer_zerop (arg1))
5526         return omit_one_operand (type, arg1, arg0);
5527       /* Likewise for first arg, but note this only occurs here for
5528          TRUTH_OR_EXPR.  */
5529       if (TREE_CODE (arg0) == INTEGER_CST && ! integer_zerop (arg0))
5530         return omit_one_operand (type, arg0, arg1);
5531       goto truth_andor;
5532
5533     case TRUTH_XOR_EXPR:
5534       /* If either arg is constant zero, drop it.  */
5535       if (integer_zerop (arg0))
5536         return non_lvalue (arg1);
5537       if (integer_zerop (arg1))
5538         return non_lvalue (arg0);
5539       /* If either arg is constant true, this is a logical inversion.  */
5540       if (integer_onep (arg0))
5541         return non_lvalue (invert_truthvalue (arg1));
5542       if (integer_onep (arg1))
5543         return non_lvalue (invert_truthvalue (arg0));
5544       return t;
5545
5546     case EQ_EXPR:
5547     case NE_EXPR:
5548     case LT_EXPR:
5549     case GT_EXPR:
5550     case LE_EXPR:
5551     case GE_EXPR:
5552       /* If one arg is a constant integer, put it last.  */
5553       if (TREE_CODE (arg0) == INTEGER_CST
5554           && TREE_CODE (arg1) != INTEGER_CST)
5555         {
5556           TREE_OPERAND (t, 0) = arg1;
5557           TREE_OPERAND (t, 1) = arg0;
5558           arg0 = TREE_OPERAND (t, 0);
5559           arg1 = TREE_OPERAND (t, 1);
5560           code = swap_tree_comparison (code);
5561           TREE_SET_CODE (t, code);
5562         }
5563
5564       /* Convert foo++ == CONST into ++foo == CONST + INCR.
5565          First, see if one arg is constant; find the constant arg
5566          and the other one.  */
5567       {
5568         tree constop = 0, varop = NULL_TREE;
5569         int constopnum = -1;
5570
5571         if (TREE_CONSTANT (arg1))
5572           constopnum = 1, constop = arg1, varop = arg0;
5573         if (TREE_CONSTANT (arg0))
5574           constopnum = 0, constop = arg0, varop = arg1;
5575
5576         if (constop && TREE_CODE (varop) == POSTINCREMENT_EXPR)
5577           {
5578             /* This optimization is invalid for ordered comparisons
5579                if CONST+INCR overflows or if foo+incr might overflow.
5580                This optimization is invalid for floating point due to rounding.
5581                For pointer types we assume overflow doesn't happen.  */
5582             if (POINTER_TYPE_P (TREE_TYPE (varop))
5583                 || (! FLOAT_TYPE_P (TREE_TYPE (varop))
5584                     && (code == EQ_EXPR || code == NE_EXPR)))
5585               {
5586                 tree newconst
5587                   = fold (build (PLUS_EXPR, TREE_TYPE (varop),
5588                                  constop, TREE_OPERAND (varop, 1)));
5589                 TREE_SET_CODE (varop, PREINCREMENT_EXPR);
5590
5591                 /* If VAROP is a reference to a bitfield, we must mask
5592                    the constant by the width of the field.  */
5593                 if (TREE_CODE (TREE_OPERAND (varop, 0)) == COMPONENT_REF
5594                     && DECL_BIT_FIELD(TREE_OPERAND
5595                                       (TREE_OPERAND (varop, 0), 1)))
5596                   {
5597                     int size
5598                       = TREE_INT_CST_LOW (DECL_SIZE
5599                                           (TREE_OPERAND
5600                                            (TREE_OPERAND (varop, 0), 1)));
5601                     tree mask, unsigned_type;
5602                     int precision;
5603                     tree folded_compare;
5604
5605                     /* First check whether the comparison would come out
5606                        always the same.  If we don't do that we would
5607                        change the meaning with the masking.  */
5608                     if (constopnum == 0)
5609                       folded_compare = fold (build (code, type, constop,
5610                                                     TREE_OPERAND (varop, 0)));
5611                     else
5612                       folded_compare = fold (build (code, type,
5613                                                     TREE_OPERAND (varop, 0),
5614                                                     constop));
5615                     if (integer_zerop (folded_compare)
5616                         || integer_onep (folded_compare))
5617                       return omit_one_operand (type, folded_compare, varop);
5618
5619                     unsigned_type = type_for_size (size, 1);
5620                     precision = TYPE_PRECISION (unsigned_type);
5621                     mask = build_int_2 (~0, ~0);
5622                     TREE_TYPE (mask) = unsigned_type;
5623                     force_fit_type (mask, 0);
5624                     mask = const_binop (RSHIFT_EXPR, mask,
5625                                         size_int (precision - size), 0);
5626                     newconst = fold (build (BIT_AND_EXPR,
5627                                             TREE_TYPE (varop), newconst,
5628                                             convert (TREE_TYPE (varop),
5629                                                      mask)));
5630                   }
5631
5632
5633                 t = build (code, type, TREE_OPERAND (t, 0),
5634                            TREE_OPERAND (t, 1));
5635                 TREE_OPERAND (t, constopnum) = newconst;
5636                 return t;
5637               }
5638           }
5639         else if (constop && TREE_CODE (varop) == POSTDECREMENT_EXPR)
5640           {
5641             if (POINTER_TYPE_P (TREE_TYPE (varop))
5642                 || (! FLOAT_TYPE_P (TREE_TYPE (varop))
5643                     && (code == EQ_EXPR || code == NE_EXPR)))
5644               {
5645                 tree newconst
5646                   = fold (build (MINUS_EXPR, TREE_TYPE (varop),
5647                                  constop, TREE_OPERAND (varop, 1)));
5648                 TREE_SET_CODE (varop, PREDECREMENT_EXPR);
5649
5650                 if (TREE_CODE (TREE_OPERAND (varop, 0)) == COMPONENT_REF
5651                     && DECL_BIT_FIELD(TREE_OPERAND
5652                                       (TREE_OPERAND (varop, 0), 1)))
5653                   {
5654                     int size
5655                       = TREE_INT_CST_LOW (DECL_SIZE
5656                                           (TREE_OPERAND
5657                                            (TREE_OPERAND (varop, 0), 1)));
5658                     tree mask, unsigned_type;
5659                     int precision;
5660                     tree folded_compare;
5661
5662                     if (constopnum == 0)
5663                       folded_compare = fold (build (code, type, constop,
5664                                                     TREE_OPERAND (varop, 0)));
5665                     else
5666                       folded_compare = fold (build (code, type,
5667                                                     TREE_OPERAND (varop, 0),
5668                                                     constop));
5669                     if (integer_zerop (folded_compare)
5670                         || integer_onep (folded_compare))
5671                       return omit_one_operand (type, folded_compare, varop);
5672
5673                     unsigned_type = type_for_size (size, 1);
5674                     precision = TYPE_PRECISION (unsigned_type);
5675                     mask = build_int_2 (~0, ~0);
5676                     TREE_TYPE (mask) = TREE_TYPE (varop);
5677                     force_fit_type (mask, 0);
5678                     mask = const_binop (RSHIFT_EXPR, mask,
5679                                         size_int (precision - size), 0);
5680                     newconst = fold (build (BIT_AND_EXPR,
5681                                             TREE_TYPE (varop), newconst,
5682                                             convert (TREE_TYPE (varop),
5683                                                      mask)));
5684                   }
5685
5686
5687                 t = build (code, type, TREE_OPERAND (t, 0),
5688                            TREE_OPERAND (t, 1));
5689                 TREE_OPERAND (t, constopnum) = newconst;
5690                 return t;
5691               }
5692           }
5693       }
5694
5695       /* Change X >= CST to X > (CST - 1) if CST is positive.  */
5696       if (TREE_CODE (arg1) == INTEGER_CST
5697           && TREE_CODE (arg0) != INTEGER_CST
5698           && tree_int_cst_sgn (arg1) > 0)
5699         {
5700           switch (TREE_CODE (t))
5701             {
5702             case GE_EXPR:
5703               code = GT_EXPR;
5704               arg1 = const_binop (MINUS_EXPR, arg1, integer_one_node, 0);
5705               t = build (code, type, TREE_OPERAND (t, 0), arg1);
5706               break;
5707
5708             case LT_EXPR:
5709               code = LE_EXPR;
5710               arg1 = const_binop (MINUS_EXPR, arg1, integer_one_node, 0);
5711               t = build (code, type, TREE_OPERAND (t, 0), arg1);
5712               break;
5713
5714             default:
5715               break;
5716             }
5717         }
5718
5719       /* If this is an EQ or NE comparison with zero and ARG0 is
5720          (1 << foo) & bar, convert it to (bar >> foo) & 1.  Both require
5721          two operations, but the latter can be done in one less insn
5722          on machines that have only two-operand insns or on which a
5723          constant cannot be the first operand.  */
5724       if (integer_zerop (arg1) && (code == EQ_EXPR || code == NE_EXPR)
5725           && TREE_CODE (arg0) == BIT_AND_EXPR)
5726         {
5727           if (TREE_CODE (TREE_OPERAND (arg0, 0)) == LSHIFT_EXPR
5728               && integer_onep (TREE_OPERAND (TREE_OPERAND (arg0, 0), 0)))
5729             return
5730               fold (build (code, type,
5731                            build (BIT_AND_EXPR, TREE_TYPE (arg0),
5732                                   build (RSHIFT_EXPR,
5733                                          TREE_TYPE (TREE_OPERAND (arg0, 0)),
5734                                          TREE_OPERAND (arg0, 1),
5735                                          TREE_OPERAND (TREE_OPERAND (arg0, 0), 1)),
5736                                   convert (TREE_TYPE (arg0),
5737                                            integer_one_node)),
5738                            arg1));
5739           else if (TREE_CODE (TREE_OPERAND (arg0, 1)) == LSHIFT_EXPR
5740                    && integer_onep (TREE_OPERAND (TREE_OPERAND (arg0, 1), 0)))
5741             return
5742               fold (build (code, type,
5743                            build (BIT_AND_EXPR, TREE_TYPE (arg0),
5744                                   build (RSHIFT_EXPR,
5745                                          TREE_TYPE (TREE_OPERAND (arg0, 1)),
5746                                          TREE_OPERAND (arg0, 0),
5747                                          TREE_OPERAND (TREE_OPERAND (arg0, 1), 1)),
5748                                   convert (TREE_TYPE (arg0),
5749                                            integer_one_node)),
5750                            arg1));
5751         }
5752
5753       /* If this is an NE or EQ comparison of zero against the result of a
5754          signed MOD operation whose second operand is a power of 2, make
5755          the MOD operation unsigned since it is simpler and equivalent.  */
5756       if ((code == NE_EXPR || code == EQ_EXPR)
5757           && integer_zerop (arg1)
5758           && ! TREE_UNSIGNED (TREE_TYPE (arg0))
5759           && (TREE_CODE (arg0) == TRUNC_MOD_EXPR
5760               || TREE_CODE (arg0) == CEIL_MOD_EXPR
5761               || TREE_CODE (arg0) == FLOOR_MOD_EXPR
5762               || TREE_CODE (arg0) == ROUND_MOD_EXPR)
5763           && integer_pow2p (TREE_OPERAND (arg0, 1)))
5764         {
5765           tree newtype = unsigned_type (TREE_TYPE (arg0));
5766           tree newmod = build (TREE_CODE (arg0), newtype,
5767                                convert (newtype, TREE_OPERAND (arg0, 0)),
5768                                convert (newtype, TREE_OPERAND (arg0, 1)));
5769
5770           return build (code, type, newmod, convert (newtype, arg1));
5771         }
5772
5773       /* If this is an NE comparison of zero with an AND of one, remove the
5774          comparison since the AND will give the correct value.  */
5775       if (code == NE_EXPR && integer_zerop (arg1)
5776           && TREE_CODE (arg0) == BIT_AND_EXPR
5777           && integer_onep (TREE_OPERAND (arg0, 1)))
5778         return convert (type, arg0);
5779
5780       /* If we have (A & C) == C where C is a power of 2, convert this into
5781          (A & C) != 0.  Similarly for NE_EXPR.  */
5782       if ((code == EQ_EXPR || code == NE_EXPR)
5783           && TREE_CODE (arg0) == BIT_AND_EXPR
5784           && integer_pow2p (TREE_OPERAND (arg0, 1))
5785           && operand_equal_p (TREE_OPERAND (arg0, 1), arg1, 0))
5786         return build (code == EQ_EXPR ? NE_EXPR : EQ_EXPR, type,
5787                       arg0, integer_zero_node);
5788
5789       /* If X is unsigned, convert X < (1 << Y) into X >> Y == 0
5790          and similarly for >= into !=.  */
5791       if ((code == LT_EXPR || code == GE_EXPR)
5792           && TREE_UNSIGNED (TREE_TYPE (arg0))
5793           && TREE_CODE (arg1) == LSHIFT_EXPR
5794           && integer_onep (TREE_OPERAND (arg1, 0)))
5795         return build (code == LT_EXPR ? EQ_EXPR : NE_EXPR, type,
5796                       build (RSHIFT_EXPR, TREE_TYPE (arg0), arg0,
5797                              TREE_OPERAND (arg1, 1)),
5798                       convert (TREE_TYPE (arg0), integer_zero_node));
5799
5800       else if ((code == LT_EXPR || code == GE_EXPR)
5801                && TREE_UNSIGNED (TREE_TYPE (arg0))
5802                && (TREE_CODE (arg1) == NOP_EXPR
5803                    || TREE_CODE (arg1) == CONVERT_EXPR)
5804                && TREE_CODE (TREE_OPERAND (arg1, 0)) == LSHIFT_EXPR
5805                && integer_onep (TREE_OPERAND (TREE_OPERAND (arg1, 0), 0)))
5806         return
5807           build (code == LT_EXPR ? EQ_EXPR : NE_EXPR, type,
5808                  convert (TREE_TYPE (arg0),
5809                           build (RSHIFT_EXPR, TREE_TYPE (arg0), arg0,
5810                                  TREE_OPERAND (TREE_OPERAND (arg1, 0), 1))),
5811                  convert (TREE_TYPE (arg0), integer_zero_node));
5812
5813       /* Simplify comparison of something with itself.  (For IEEE
5814          floating-point, we can only do some of these simplifications.)  */
5815       if (operand_equal_p (arg0, arg1, 0))
5816         {
5817           switch (code)
5818             {
5819             case EQ_EXPR:
5820             case GE_EXPR:
5821             case LE_EXPR:
5822               if (INTEGRAL_TYPE_P (TREE_TYPE (arg0)))
5823                 return constant_boolean_node (1, type);
5824               code = EQ_EXPR;
5825               TREE_SET_CODE (t, code);
5826               break;
5827
5828             case NE_EXPR:
5829               /* For NE, we can only do this simplification if integer.  */
5830               if (! INTEGRAL_TYPE_P (TREE_TYPE (arg0)))
5831                 break;
5832               /* ... fall through ...  */
5833             case GT_EXPR:
5834             case LT_EXPR:
5835               return constant_boolean_node (0, type);
5836             default:
5837               abort ();
5838             }
5839         }
5840
5841       /* An unsigned comparison against 0 can be simplified.  */
5842       if (integer_zerop (arg1)
5843           && (INTEGRAL_TYPE_P (TREE_TYPE (arg1))
5844               || POINTER_TYPE_P (TREE_TYPE (arg1)))
5845           && TREE_UNSIGNED (TREE_TYPE (arg1)))
5846         {
5847           switch (TREE_CODE (t))
5848             {
5849             case GT_EXPR:
5850               code = NE_EXPR;
5851               TREE_SET_CODE (t, NE_EXPR);
5852               break;
5853             case LE_EXPR:
5854               code = EQ_EXPR;
5855               TREE_SET_CODE (t, EQ_EXPR);
5856               break;
5857             case GE_EXPR:
5858               return omit_one_operand (type,
5859                                        convert (type, integer_one_node),
5860                                        arg0);
5861             case LT_EXPR:
5862               return omit_one_operand (type,
5863                                        convert (type, integer_zero_node),
5864                                        arg0);
5865             default:
5866               break;
5867             }
5868         }
5869
5870       /* An unsigned <= 0x7fffffff can be simplified.  */
5871       {
5872         int width = TYPE_PRECISION (TREE_TYPE (arg1));
5873         if (TREE_CODE (arg1) == INTEGER_CST
5874             && ! TREE_CONSTANT_OVERFLOW (arg1)
5875             && width <= HOST_BITS_PER_WIDE_INT
5876             && TREE_INT_CST_LOW (arg1) == ((HOST_WIDE_INT) 1 << (width - 1)) - 1
5877             && TREE_INT_CST_HIGH (arg1) == 0
5878             && (INTEGRAL_TYPE_P (TREE_TYPE (arg1))
5879                 || POINTER_TYPE_P (TREE_TYPE (arg1)))
5880             && TREE_UNSIGNED (TREE_TYPE (arg1)))
5881           {
5882             switch (TREE_CODE (t))
5883               {
5884               case LE_EXPR:
5885                 return fold (build (GE_EXPR, type,
5886                                     convert (signed_type (TREE_TYPE (arg0)),
5887                                              arg0),
5888                                     convert (signed_type (TREE_TYPE (arg1)),
5889                                              integer_zero_node)));
5890               case GT_EXPR:
5891                 return fold (build (LT_EXPR, type,
5892                                     convert (signed_type (TREE_TYPE (arg0)),
5893                                              arg0),
5894                                     convert (signed_type (TREE_TYPE (arg1)),
5895                                              integer_zero_node)));
5896               default:
5897                 break;
5898               }
5899           }
5900       }
5901
5902       /* If we are comparing an expression that just has comparisons
5903          of two integer values, arithmetic expressions of those comparisons,
5904          and constants, we can simplify it.  There are only three cases
5905          to check: the two values can either be equal, the first can be
5906          greater, or the second can be greater.  Fold the expression for
5907          those three values.  Since each value must be 0 or 1, we have
5908          eight possibilities, each of which corresponds to the constant 0
5909          or 1 or one of the six possible comparisons.
5910
5911          This handles common cases like (a > b) == 0 but also handles
5912          expressions like  ((x > y) - (y > x)) > 0, which supposedly
5913          occur in macroized code.  */
5914
5915       if (TREE_CODE (arg1) == INTEGER_CST && TREE_CODE (arg0) != INTEGER_CST)
5916         {
5917           tree cval1 = 0, cval2 = 0;
5918           int save_p = 0;
5919
5920           if (twoval_comparison_p (arg0, &cval1, &cval2, &save_p)
5921               /* Don't handle degenerate cases here; they should already
5922                  have been handled anyway.  */
5923               && cval1 != 0 && cval2 != 0
5924               && ! (TREE_CONSTANT (cval1) && TREE_CONSTANT (cval2))
5925               && TREE_TYPE (cval1) == TREE_TYPE (cval2)
5926               && INTEGRAL_TYPE_P (TREE_TYPE (cval1))
5927               && TYPE_MAX_VALUE (TREE_TYPE (cval1))
5928               && TYPE_MAX_VALUE (TREE_TYPE (cval2))
5929               && ! operand_equal_p (TYPE_MIN_VALUE (TREE_TYPE (cval1)),
5930                                     TYPE_MAX_VALUE (TREE_TYPE (cval2)), 0))
5931             {
5932               tree maxval = TYPE_MAX_VALUE (TREE_TYPE (cval1));
5933               tree minval = TYPE_MIN_VALUE (TREE_TYPE (cval1));
5934
5935               /* We can't just pass T to eval_subst in case cval1 or cval2
5936                  was the same as ARG1.  */
5937
5938               tree high_result
5939                 = fold (build (code, type,
5940                                eval_subst (arg0, cval1, maxval, cval2, minval),
5941                                arg1));
5942               tree equal_result
5943                 = fold (build (code, type,
5944                                eval_subst (arg0, cval1, maxval, cval2, maxval),
5945                                arg1));
5946               tree low_result
5947                 = fold (build (code, type,
5948                                eval_subst (arg0, cval1, minval, cval2, maxval),
5949                                arg1));
5950
5951               /* All three of these results should be 0 or 1.  Confirm they
5952                  are.  Then use those values to select the proper code
5953                  to use.  */
5954
5955               if ((integer_zerop (high_result)
5956                    || integer_onep (high_result))
5957                   && (integer_zerop (equal_result)
5958                       || integer_onep (equal_result))
5959                   && (integer_zerop (low_result)
5960                       || integer_onep (low_result)))
5961                 {
5962                   /* Make a 3-bit mask with the high-order bit being the
5963                      value for `>', the next for '=', and the low for '<'.  */
5964                   switch ((integer_onep (high_result) * 4)
5965                           + (integer_onep (equal_result) * 2)
5966                           + integer_onep (low_result))
5967                     {
5968                     case 0:
5969                       /* Always false.  */
5970                       return omit_one_operand (type, integer_zero_node, arg0);
5971                     case 1:
5972                       code = LT_EXPR;
5973                       break;
5974                     case 2:
5975                       code = EQ_EXPR;
5976                       break;
5977                     case 3:
5978                       code = LE_EXPR;
5979                       break;
5980                     case 4:
5981                       code = GT_EXPR;
5982                       break;
5983                     case 5:
5984                       code = NE_EXPR;
5985                       break;
5986                     case 6:
5987                       code = GE_EXPR;
5988                       break;
5989                     case 7:
5990                       /* Always true.  */
5991                       return omit_one_operand (type, integer_one_node, arg0);
5992                     }
5993
5994                   t = build (code, type, cval1, cval2);
5995                   if (save_p)
5996                     return save_expr (t);
5997                   else
5998                     return fold (t);
5999                 }
6000             }
6001         }
6002
6003       /* If this is a comparison of a field, we may be able to simplify it.  */
6004       if ((TREE_CODE (arg0) == COMPONENT_REF
6005            || TREE_CODE (arg0) == BIT_FIELD_REF)
6006           && (code == EQ_EXPR || code == NE_EXPR)
6007           /* Handle the constant case even without -O
6008              to make sure the warnings are given.  */
6009           && (optimize || TREE_CODE (arg1) == INTEGER_CST))
6010         {
6011           t1 = optimize_bit_field_compare (code, type, arg0, arg1);
6012           return t1 ? t1 : t;
6013         }
6014
6015       /* If this is a comparison of complex values and either or both sides
6016          are a COMPLEX_EXPR or COMPLEX_CST, it is best to split up the
6017          comparisons and join them with a TRUTH_ANDIF_EXPR or TRUTH_ORIF_EXPR.
6018          This may prevent needless evaluations.  */
6019       if ((code == EQ_EXPR || code == NE_EXPR)
6020           && TREE_CODE (TREE_TYPE (arg0)) == COMPLEX_TYPE
6021           && (TREE_CODE (arg0) == COMPLEX_EXPR
6022               || TREE_CODE (arg1) == COMPLEX_EXPR
6023               || TREE_CODE (arg0) == COMPLEX_CST
6024               || TREE_CODE (arg1) == COMPLEX_CST))
6025         {
6026           tree subtype = TREE_TYPE (TREE_TYPE (arg0));
6027           tree real0, imag0, real1, imag1;
6028
6029           arg0 = save_expr (arg0);
6030           arg1 = save_expr (arg1);
6031           real0 = fold (build1 (REALPART_EXPR, subtype, arg0));
6032           imag0 = fold (build1 (IMAGPART_EXPR, subtype, arg0));
6033           real1 = fold (build1 (REALPART_EXPR, subtype, arg1));
6034           imag1 = fold (build1 (IMAGPART_EXPR, subtype, arg1));
6035
6036           return fold (build ((code == EQ_EXPR ? TRUTH_ANDIF_EXPR
6037                                : TRUTH_ORIF_EXPR),
6038                               type,
6039                               fold (build (code, type, real0, real1)),
6040                               fold (build (code, type, imag0, imag1))));
6041         }
6042
6043       /* From here on, the only cases we handle are when the result is
6044          known to be a constant.
6045
6046          To compute GT, swap the arguments and do LT.
6047          To compute GE, do LT and invert the result.
6048          To compute LE, swap the arguments, do LT and invert the result.
6049          To compute NE, do EQ and invert the result.
6050
6051          Therefore, the code below must handle only EQ and LT.  */
6052
6053       if (code == LE_EXPR || code == GT_EXPR)
6054         {
6055           tem = arg0, arg0 = arg1, arg1 = tem;
6056           code = swap_tree_comparison (code);
6057         }
6058
6059       /* Note that it is safe to invert for real values here because we
6060          will check below in the one case that it matters.  */
6061
6062       invert = 0;
6063       if (code == NE_EXPR || code == GE_EXPR)
6064         {
6065           invert = 1;
6066           code = invert_tree_comparison (code);
6067         }
6068
6069       /* Compute a result for LT or EQ if args permit;
6070          otherwise return T.  */
6071       if (TREE_CODE (arg0) == INTEGER_CST && TREE_CODE (arg1) == INTEGER_CST)
6072         {
6073           if (code == EQ_EXPR)
6074             t1 = build_int_2 ((TREE_INT_CST_LOW (arg0)
6075                                == TREE_INT_CST_LOW (arg1))
6076                               && (TREE_INT_CST_HIGH (arg0)
6077                                   == TREE_INT_CST_HIGH (arg1)),
6078                               0);
6079           else
6080             t1 = build_int_2 ((TREE_UNSIGNED (TREE_TYPE (arg0))
6081                                ? INT_CST_LT_UNSIGNED (arg0, arg1)
6082                                : INT_CST_LT (arg0, arg1)),
6083                               0);
6084         }
6085
6086 #if 0 /* This is no longer useful, but breaks some real code.  */
6087       /* Assume a nonexplicit constant cannot equal an explicit one,
6088          since such code would be undefined anyway.
6089          Exception: on sysvr4, using #pragma weak,
6090          a label can come out as 0.  */
6091       else if (TREE_CODE (arg1) == INTEGER_CST
6092                && !integer_zerop (arg1)
6093                && TREE_CONSTANT (arg0)
6094                && TREE_CODE (arg0) == ADDR_EXPR
6095                && code == EQ_EXPR)
6096         t1 = build_int_2 (0, 0);
6097 #endif
6098       /* Two real constants can be compared explicitly.  */
6099       else if (TREE_CODE (arg0) == REAL_CST && TREE_CODE (arg1) == REAL_CST)
6100         {
6101           /* If either operand is a NaN, the result is false with two
6102              exceptions: First, an NE_EXPR is true on NaNs, but that case
6103              is already handled correctly since we will be inverting the
6104              result for NE_EXPR.  Second, if we had inverted a LE_EXPR
6105              or a GE_EXPR into a LT_EXPR, we must return true so that it
6106              will be inverted into false.  */
6107
6108           if (REAL_VALUE_ISNAN (TREE_REAL_CST (arg0))
6109               || REAL_VALUE_ISNAN (TREE_REAL_CST (arg1)))
6110             t1 = build_int_2 (invert && code == LT_EXPR, 0);
6111
6112           else if (code == EQ_EXPR)
6113             t1 = build_int_2 (REAL_VALUES_EQUAL (TREE_REAL_CST (arg0),
6114                                                  TREE_REAL_CST (arg1)),
6115                               0);
6116           else
6117             t1 = build_int_2 (REAL_VALUES_LESS (TREE_REAL_CST (arg0),
6118                                                 TREE_REAL_CST (arg1)),
6119                               0);
6120         }
6121
6122       if (t1 == NULL_TREE)
6123         return t;
6124
6125       if (invert)
6126         TREE_INT_CST_LOW (t1) ^= 1;
6127
6128       TREE_TYPE (t1) = type;
6129       if (TREE_CODE (type) == BOOLEAN_TYPE)
6130         return truthvalue_conversion (t1);
6131       return t1;
6132
6133     case COND_EXPR:
6134       /* Pedantic ANSI C says that a conditional expression is never an lvalue,
6135          so all simple results must be passed through pedantic_non_lvalue.  */
6136       if (TREE_CODE (arg0) == INTEGER_CST)
6137         return pedantic_non_lvalue
6138           (TREE_OPERAND (t, (integer_zerop (arg0) ? 2 : 1)));
6139       else if (operand_equal_p (arg1, TREE_OPERAND (expr, 2), 0))
6140         return pedantic_omit_one_operand (type, arg1, arg0);
6141
6142       /* If the second operand is zero, invert the comparison and swap
6143          the second and third operands.  Likewise if the second operand
6144          is constant and the third is not or if the third operand is
6145          equivalent to the first operand of the comparison.  */
6146
6147       if (integer_zerop (arg1)
6148           || (TREE_CONSTANT (arg1) && ! TREE_CONSTANT (TREE_OPERAND (t, 2)))
6149           || (TREE_CODE_CLASS (TREE_CODE (arg0)) == '<'
6150               && operand_equal_for_comparison_p (TREE_OPERAND (arg0, 0),
6151                                                  TREE_OPERAND (t, 2),
6152                                                  TREE_OPERAND (arg0, 1))))
6153         {
6154           /* See if this can be inverted.  If it can't, possibly because
6155              it was a floating-point inequality comparison, don't do
6156              anything.  */
6157           tem = invert_truthvalue (arg0);
6158
6159           if (TREE_CODE (tem) != TRUTH_NOT_EXPR)
6160             {
6161               t = build (code, type, tem,
6162                          TREE_OPERAND (t, 2), TREE_OPERAND (t, 1));
6163               arg0 = tem;
6164               /* arg1 should be the first argument of the new T.  */
6165               arg1 = TREE_OPERAND (t, 1);
6166               STRIP_NOPS (arg1);
6167             }
6168         }
6169
6170       /* If we have A op B ? A : C, we may be able to convert this to a
6171          simpler expression, depending on the operation and the values
6172          of B and C.  IEEE floating point prevents this though,
6173          because A or B might be -0.0 or a NaN.  */
6174
6175       if (TREE_CODE_CLASS (TREE_CODE (arg0)) == '<'
6176           && (TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
6177               || ! FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (arg0, 0)))
6178               || flag_fast_math)
6179           && operand_equal_for_comparison_p (TREE_OPERAND (arg0, 0),
6180                                              arg1, TREE_OPERAND (arg0, 1)))
6181         {
6182           tree arg2 = TREE_OPERAND (t, 2);
6183           enum tree_code comp_code = TREE_CODE (arg0);
6184
6185           STRIP_NOPS (arg2);
6186
6187           /* If we have A op 0 ? A : -A, this is A, -A, abs (A), or abs (-A),
6188              depending on the comparison operation.  */
6189           if ((FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (arg0, 1)))
6190                ? real_zerop (TREE_OPERAND (arg0, 1))
6191                : integer_zerop (TREE_OPERAND (arg0, 1)))
6192               && TREE_CODE (arg2) == NEGATE_EXPR
6193               && operand_equal_p (TREE_OPERAND (arg2, 0), arg1, 0))
6194             switch (comp_code)
6195               {
6196               case EQ_EXPR:
6197                 return pedantic_non_lvalue
6198                   (fold (build1 (NEGATE_EXPR, type, arg1)));
6199               case NE_EXPR:
6200                 return pedantic_non_lvalue (convert (type, arg1));
6201               case GE_EXPR:
6202               case GT_EXPR:
6203                 if (TREE_UNSIGNED (TREE_TYPE (arg1)))
6204                   arg1 = convert (signed_type (TREE_TYPE (arg1)), arg1);
6205                 return pedantic_non_lvalue
6206                   (convert (type, fold (build1 (ABS_EXPR,
6207                                                 TREE_TYPE (arg1), arg1))));
6208               case LE_EXPR:
6209               case LT_EXPR:
6210                 if (TREE_UNSIGNED (TREE_TYPE (arg1)))
6211                   arg1 = convert (signed_type (TREE_TYPE (arg1)), arg1);
6212                 return pedantic_non_lvalue
6213                   (fold (build1 (NEGATE_EXPR, type,
6214                                  convert (type,
6215                                           fold (build1 (ABS_EXPR,
6216                                                         TREE_TYPE (arg1),
6217                                                         arg1))))));
6218               default:
6219                 abort ();
6220               }
6221
6222           /* If this is A != 0 ? A : 0, this is simply A.  For ==, it is
6223              always zero.  */
6224
6225           if (integer_zerop (TREE_OPERAND (arg0, 1)) && integer_zerop (arg2))
6226             {
6227               if (comp_code == NE_EXPR)
6228                 return pedantic_non_lvalue (convert (type, arg1));
6229               else if (comp_code == EQ_EXPR)
6230                 return pedantic_non_lvalue (convert (type, integer_zero_node));
6231             }
6232
6233           /* If this is A op B ? A : B, this is either A, B, min (A, B),
6234              or max (A, B), depending on the operation.  */
6235
6236           if (operand_equal_for_comparison_p (TREE_OPERAND (arg0, 1),
6237                                               arg2, TREE_OPERAND (arg0, 0)))
6238             {
6239               tree comp_op0 = TREE_OPERAND (arg0, 0);
6240               tree comp_op1 = TREE_OPERAND (arg0, 1);
6241               tree comp_type = TREE_TYPE (comp_op0);
6242
6243               switch (comp_code)
6244                 {
6245                 case EQ_EXPR:
6246                   return pedantic_non_lvalue (convert (type, arg2));
6247                 case NE_EXPR:
6248                   return pedantic_non_lvalue (convert (type, arg1));
6249                 case LE_EXPR:
6250                 case LT_EXPR:
6251                   /* In C++ a ?: expression can be an lvalue, so put the
6252                      operand which will be used if they are equal first
6253                      so that we can convert this back to the
6254                      corresponding COND_EXPR.  */
6255                   return pedantic_non_lvalue
6256                     (convert (type, (fold (build (MIN_EXPR, comp_type,
6257                                                   (comp_code == LE_EXPR
6258                                                    ? comp_op0 : comp_op1),
6259                                                   (comp_code == LE_EXPR
6260                                                    ? comp_op1 : comp_op0))))));
6261                   break;
6262                 case GE_EXPR:
6263                 case GT_EXPR:
6264                   return pedantic_non_lvalue
6265                     (convert (type, fold (build (MAX_EXPR, comp_type,
6266                                                  (comp_code == GE_EXPR
6267                                                   ? comp_op0 : comp_op1),
6268                                                  (comp_code == GE_EXPR
6269                                                   ? comp_op1 : comp_op0)))));
6270                   break;
6271                 default:
6272                   abort ();
6273                 }
6274             }
6275
6276           /* If this is A op C1 ? A : C2 with C1 and C2 constant integers,
6277              we might still be able to simplify this.  For example,
6278              if C1 is one less or one more than C2, this might have started
6279              out as a MIN or MAX and been transformed by this function.
6280              Only good for INTEGER_TYPEs, because we need TYPE_MAX_VALUE.  */
6281
6282           if (INTEGRAL_TYPE_P (type)
6283               && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
6284               && TREE_CODE (arg2) == INTEGER_CST)
6285             switch (comp_code)
6286               {
6287               case EQ_EXPR:
6288                 /* We can replace A with C1 in this case.  */
6289                 arg1 = convert (type, TREE_OPERAND (arg0, 1));
6290                 t = build (code, type, TREE_OPERAND (t, 0), arg1,
6291                            TREE_OPERAND (t, 2));
6292                 break;
6293
6294               case LT_EXPR:
6295                 /* If C1 is C2 + 1, this is min(A, C2).  */
6296                 if (! operand_equal_p (arg2, TYPE_MAX_VALUE (type), 1)
6297                     && operand_equal_p (TREE_OPERAND (arg0, 1),
6298                                         const_binop (PLUS_EXPR, arg2,
6299                                                      integer_one_node, 0), 1))
6300                   return pedantic_non_lvalue
6301                     (fold (build (MIN_EXPR, type, arg1, arg2)));
6302                 break;
6303
6304               case LE_EXPR:
6305                 /* If C1 is C2 - 1, this is min(A, C2).  */
6306                 if (! operand_equal_p (arg2, TYPE_MIN_VALUE (type), 1)
6307                     && operand_equal_p (TREE_OPERAND (arg0, 1),
6308                                         const_binop (MINUS_EXPR, arg2,
6309                                                      integer_one_node, 0), 1))
6310                   return pedantic_non_lvalue
6311                     (fold (build (MIN_EXPR, type, arg1, arg2)));
6312                 break;
6313
6314               case GT_EXPR:
6315                 /* If C1 is C2 - 1, this is max(A, C2).  */
6316                 if (! operand_equal_p (arg2, TYPE_MIN_VALUE (type), 1)
6317                     && operand_equal_p (TREE_OPERAND (arg0, 1),
6318                                         const_binop (MINUS_EXPR, arg2,
6319                                                      integer_one_node, 0), 1))
6320                   return pedantic_non_lvalue
6321                     (fold (build (MAX_EXPR, type, arg1, arg2)));
6322                 break;
6323
6324               case GE_EXPR:
6325                 /* If C1 is C2 + 1, this is max(A, C2).  */
6326                 if (! operand_equal_p (arg2, TYPE_MAX_VALUE (type), 1)
6327                     && operand_equal_p (TREE_OPERAND (arg0, 1),
6328                                         const_binop (PLUS_EXPR, arg2,
6329                                                      integer_one_node, 0), 1))
6330                   return pedantic_non_lvalue
6331                     (fold (build (MAX_EXPR, type, arg1, arg2)));
6332                 break;
6333               case NE_EXPR:
6334                 break;
6335               default:
6336                 abort ();
6337               }
6338         }
6339
6340       /* If the second operand is simpler than the third, swap them
6341          since that produces better jump optimization results.  */
6342       if ((TREE_CONSTANT (arg1) || TREE_CODE_CLASS (TREE_CODE (arg1)) == 'd'
6343            || TREE_CODE (arg1) == SAVE_EXPR)
6344           && ! (TREE_CONSTANT (TREE_OPERAND (t, 2))
6345                 || TREE_CODE_CLASS (TREE_CODE (TREE_OPERAND (t, 2))) == 'd'
6346                 || TREE_CODE (TREE_OPERAND (t, 2)) == SAVE_EXPR))
6347         {
6348           /* See if this can be inverted.  If it can't, possibly because
6349              it was a floating-point inequality comparison, don't do
6350              anything.  */
6351           tem = invert_truthvalue (arg0);
6352
6353           if (TREE_CODE (tem) != TRUTH_NOT_EXPR)
6354             {
6355               t = build (code, type, tem,
6356                          TREE_OPERAND (t, 2), TREE_OPERAND (t, 1));
6357               arg0 = tem;
6358               /* arg1 should be the first argument of the new T.  */
6359               arg1 = TREE_OPERAND (t, 1);
6360               STRIP_NOPS (arg1);
6361             }
6362         }
6363
6364       /* Convert A ? 1 : 0 to simply A.  */
6365       if (integer_onep (TREE_OPERAND (t, 1))
6366           && integer_zerop (TREE_OPERAND (t, 2))
6367           /* If we try to convert TREE_OPERAND (t, 0) to our type, the
6368              call to fold will try to move the conversion inside
6369              a COND, which will recurse.  In that case, the COND_EXPR
6370              is probably the best choice, so leave it alone.  */
6371           && type == TREE_TYPE (arg0))
6372         return pedantic_non_lvalue (arg0);
6373
6374       /* Look for expressions of the form A & 2 ? 2 : 0.  The result of this
6375          operation is simply A & 2.  */
6376
6377       if (integer_zerop (TREE_OPERAND (t, 2))
6378           && TREE_CODE (arg0) == NE_EXPR
6379           && integer_zerop (TREE_OPERAND (arg0, 1))
6380           && integer_pow2p (arg1)
6381           && TREE_CODE (TREE_OPERAND (arg0, 0)) == BIT_AND_EXPR
6382           && operand_equal_p (TREE_OPERAND (TREE_OPERAND (arg0, 0), 1),
6383                               arg1, 1))
6384         return pedantic_non_lvalue (convert (type, TREE_OPERAND (arg0, 0)));
6385
6386       return t;
6387
6388     case COMPOUND_EXPR:
6389       /* When pedantic, a compound expression can be neither an lvalue
6390          nor an integer constant expression.  */
6391       if (TREE_SIDE_EFFECTS (arg0) || pedantic)
6392         return t;
6393       /* Don't let (0, 0) be null pointer constant.  */
6394       if (integer_zerop (arg1))
6395         return build1 (NOP_EXPR, TREE_TYPE (arg1), arg1);
6396       return arg1;
6397
6398     case COMPLEX_EXPR:
6399       if (wins)
6400         return build_complex (type, arg0, arg1);
6401       return t;
6402
6403     case REALPART_EXPR:
6404       if (TREE_CODE (TREE_TYPE (arg0)) != COMPLEX_TYPE)
6405         return t;
6406       else if (TREE_CODE (arg0) == COMPLEX_EXPR)
6407         return omit_one_operand (type, TREE_OPERAND (arg0, 0),
6408                                  TREE_OPERAND (arg0, 1));
6409       else if (TREE_CODE (arg0) == COMPLEX_CST)
6410         return TREE_REALPART (arg0);
6411       else if (TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MINUS_EXPR)
6412         return fold (build (TREE_CODE (arg0), type,
6413                             fold (build1 (REALPART_EXPR, type,
6414                                           TREE_OPERAND (arg0, 0))),
6415                             fold (build1 (REALPART_EXPR,
6416                                           type, TREE_OPERAND (arg0, 1)))));
6417       return t;
6418
6419     case IMAGPART_EXPR:
6420       if (TREE_CODE (TREE_TYPE (arg0)) != COMPLEX_TYPE)
6421         return convert (type, integer_zero_node);
6422       else if (TREE_CODE (arg0) == COMPLEX_EXPR)
6423         return omit_one_operand (type, TREE_OPERAND (arg0, 1),
6424                                  TREE_OPERAND (arg0, 0));
6425       else if (TREE_CODE (arg0) == COMPLEX_CST)
6426         return TREE_IMAGPART (arg0);
6427       else if (TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MINUS_EXPR)
6428         return fold (build (TREE_CODE (arg0), type,
6429                             fold (build1 (IMAGPART_EXPR, type,
6430                                           TREE_OPERAND (arg0, 0))),
6431                             fold (build1 (IMAGPART_EXPR, type,
6432                                           TREE_OPERAND (arg0, 1)))));
6433       return t;
6434
6435       /* Pull arithmetic ops out of the CLEANUP_POINT_EXPR where
6436          appropriate.  */
6437     case CLEANUP_POINT_EXPR:
6438       if (! has_cleanups (arg0))
6439         return TREE_OPERAND (t, 0);
6440
6441       {
6442         enum tree_code code0 = TREE_CODE (arg0);
6443         int kind0 = TREE_CODE_CLASS (code0);
6444         tree arg00 = TREE_OPERAND (arg0, 0);
6445         tree arg01;
6446
6447         if (kind0 == '1' || code0 == TRUTH_NOT_EXPR)
6448           return fold (build1 (code0, type,
6449                                fold (build1 (CLEANUP_POINT_EXPR,
6450                                              TREE_TYPE (arg00), arg00))));
6451
6452         if (kind0 == '<' || kind0 == '2'
6453             || code0 == TRUTH_ANDIF_EXPR || code0 == TRUTH_ORIF_EXPR
6454             || code0 == TRUTH_AND_EXPR   || code0 == TRUTH_OR_EXPR
6455             || code0 == TRUTH_XOR_EXPR)
6456           {
6457             arg01 = TREE_OPERAND (arg0, 1);
6458
6459             if (TREE_CONSTANT (arg00)
6460                 || ((code0 == TRUTH_ANDIF_EXPR || code0 == TRUTH_ORIF_EXPR)
6461                     && ! has_cleanups (arg00)))
6462               return fold (build (code0, type, arg00,
6463                                   fold (build1 (CLEANUP_POINT_EXPR,
6464                                                 TREE_TYPE (arg01), arg01))));
6465
6466             if (TREE_CONSTANT (arg01))
6467               return fold (build (code0, type,
6468                                   fold (build1 (CLEANUP_POINT_EXPR,
6469                                                 TREE_TYPE (arg00), arg00)),
6470                                   arg01));
6471           }
6472
6473         return t;
6474       }
6475
6476     default:
6477       return t;
6478     } /* switch (code) */
6479 }
6480
6481 /* Determine if first argument is a multiple of second argument.
6482    Return 0 if it is not, or is not easily determined to so be.
6483
6484    An example of the sort of thing we care about (at this point --
6485    this routine could surely be made more general, and expanded
6486    to do what the *_DIV_EXPR's fold() cases do now) is discovering
6487    that
6488
6489      SAVE_EXPR (I) * SAVE_EXPR (J * 8)
6490
6491    is a multiple of
6492
6493      SAVE_EXPR (J * 8)
6494
6495    when we know that the two `SAVE_EXPR (J * 8)' nodes are the
6496    same node (which means they will have the same value at run
6497    time, even though we don't know when they'll be assigned).
6498
6499    This code also handles discovering that
6500
6501      SAVE_EXPR (I) * SAVE_EXPR (J * 8)
6502
6503    is a multiple of
6504
6505      8
6506
6507    (of course) so we don't have to worry about dealing with a
6508    possible remainder.
6509
6510    Note that we _look_ inside a SAVE_EXPR only to determine
6511    how it was calculated; it is not safe for fold() to do much
6512    of anything else with the internals of a SAVE_EXPR, since
6513    fold() cannot know when it will be evaluated at run time.
6514    For example, the latter example above _cannot_ be implemented
6515    as
6516
6517      SAVE_EXPR (I) * J
6518
6519    or any variant thereof, since the value of J at evaluation time
6520    of the original SAVE_EXPR is not necessarily the same at the time
6521    the new expression is evaluated.  The only optimization of this
6522    sort that would be valid is changing
6523
6524      SAVE_EXPR (I) * SAVE_EXPR (SAVE_EXPR (J) * 8)
6525    divided by
6526      8
6527
6528    to
6529
6530      SAVE_EXPR (I) * SAVE_EXPR (J)
6531
6532    (where the same SAVE_EXPR (J) is used in the original and the
6533    transformed version).  */
6534
6535 static int
6536 multiple_of_p (type, top, bottom)
6537      tree type;
6538      tree top;
6539      tree bottom;
6540 {
6541   if (operand_equal_p (top, bottom, 0))
6542     return 1;
6543
6544   if (TREE_CODE (type) != INTEGER_TYPE)
6545     return 0;
6546
6547   switch (TREE_CODE (top))
6548     {
6549     case MULT_EXPR:
6550       return (multiple_of_p (type, TREE_OPERAND (top, 0), bottom)
6551               || multiple_of_p (type, TREE_OPERAND (top, 1), bottom));
6552
6553     case PLUS_EXPR:
6554     case MINUS_EXPR:
6555       return (multiple_of_p (type, TREE_OPERAND (top, 0), bottom)
6556               && multiple_of_p (type, TREE_OPERAND (top, 1), bottom));
6557
6558     case NOP_EXPR:
6559       /* Punt if conversion from non-integral or wider integral type.  */
6560       if ((TREE_CODE (TREE_TYPE (TREE_OPERAND (top, 0))) != INTEGER_TYPE)
6561           || (TYPE_PRECISION (type)
6562               < TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (top, 0)))))
6563         return 0;
6564       /* Fall through. */
6565     case SAVE_EXPR:
6566       return multiple_of_p (type, TREE_OPERAND (top, 0), bottom);
6567
6568     case INTEGER_CST:
6569       if ((TREE_CODE (bottom) != INTEGER_CST)
6570           || (tree_int_cst_sgn (top) < 0)
6571           || (tree_int_cst_sgn (bottom) < 0))
6572         return 0;
6573       return integer_zerop (const_binop (TRUNC_MOD_EXPR,
6574                                          top, bottom, 0));
6575
6576     default:
6577       return 0;
6578     }
6579 }
6580 \f