gcc/fold-const.c

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