gcc/fold-const.c

   1 /* Fold a constant sub-tree into a single node for C-compiler
   2    Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999,
   3    2000, 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 2, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING.  If not, write to the Free
  19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
  20 02110-1301, USA.  */
  21
  22 /*@@ This file should be rewritten to use an arbitrary precision
  23   @@ representation for "struct tree_int_cst" and "struct tree_real_cst".
  24   @@ Perhaps the routines could also be used for bc/dc, and made a lib.
  25   @@ The routines that translate from the ap rep should
  26   @@ warn if precision et. al. is lost.
  27   @@ This would also make life easier when this technology is used
  28   @@ for cross-compilers.  */
  29
  30 /* The entry points in this file are fold, size_int_wide, size_binop
  31    and force_fit_type.
  32
  33    fold takes a tree as argument and returns a simplified tree.
  34
  35    size_binop takes a tree code for an arithmetic operation
  36    and two operands that are trees, and produces a tree for the
  37    result, assuming the type comes from `sizetype'.
  38
  39    size_int takes an integer value, and creates a tree constant
  40    with type from `sizetype'.
  41
  42    force_fit_type takes a constant, an overflowable flag and prior
  43    overflow indicators.  It forces the value to fit the type and sets
  44    TREE_OVERFLOW and TREE_CONSTANT_OVERFLOW as appropriate.  */
  45
  46 #include "config.h"
  47 #include "system.h"
  48 #include "coretypes.h"
  49 #include "tm.h"
  50 #include "flags.h"
  51 #include "tree.h"
  52 #include "real.h"
  53 #include "rtl.h"
  54 #include "expr.h"
  55 #include "tm_p.h"
  56 #include "toplev.h"
  57 #include "ggc.h"
  58 #include "hashtab.h"
  59 #include "langhooks.h"
  60 #include "md5.h"
  61
  62 /* The following constants represent a bit based encoding of GCC's
  63    comparison operators.  This encoding simplifies transformations
  64    on relational comparison operators, such as AND and OR.  */
  65 enum comparison_code {
  66   COMPCODE_FALSE = 0,
  67   COMPCODE_LT = 1,
  68   COMPCODE_EQ = 2,
  69   COMPCODE_LE = 3,
  70   COMPCODE_GT = 4,
  71   COMPCODE_LTGT = 5,
  72   COMPCODE_GE = 6,
  73   COMPCODE_ORD = 7,
  74   COMPCODE_UNORD = 8,
  75   COMPCODE_UNLT = 9,
  76   COMPCODE_UNEQ = 10,
  77   COMPCODE_UNLE = 11,
  78   COMPCODE_UNGT = 12,
  79   COMPCODE_NE = 13,
  80   COMPCODE_UNGE = 14,
  81   COMPCODE_TRUE = 15
  82 };
  83
  84 static void encode (HOST_WIDE_INT *, unsigned HOST_WIDE_INT, HOST_WIDE_INT);
  85 static void decode (HOST_WIDE_INT *, unsigned HOST_WIDE_INT *, HOST_WIDE_INT *);
  86 static bool negate_mathfn_p (enum built_in_function);
  87 static bool negate_expr_p (tree);
  88 static tree negate_expr (tree);
  89 static tree split_tree (tree, enum tree_code, tree *, tree *, tree *, int);
  90 static tree associate_trees (tree, tree, enum tree_code, tree);
  91 static tree const_binop (enum tree_code, tree, tree, int);
  92 static enum comparison_code comparison_to_compcode (enum tree_code);
  93 static enum tree_code compcode_to_comparison (enum comparison_code);
  94 static tree combine_comparisons (enum tree_code, enum tree_code,
  95                                  enum tree_code, tree, tree, tree);
  96 static int truth_value_p (enum tree_code);
  97 static int operand_equal_for_comparison_p (tree, tree, tree);
  98 static int twoval_comparison_p (tree, tree *, tree *, int *);
  99 static tree eval_subst (tree, tree, tree, tree, tree);
 100 static tree pedantic_omit_one_operand (tree, tree, tree);
 101 static tree distribute_bit_expr (enum tree_code, tree, tree, tree);
 102 static tree make_bit_field_ref (tree, tree, int, int, int);
 103 static tree optimize_bit_field_compare (enum tree_code, tree, tree, tree);
 104 static tree decode_field_reference (tree, HOST_WIDE_INT *, HOST_WIDE_INT *,
 105                                     enum machine_mode *, int *, int *,
 106                                     tree *, tree *);
 107 static int all_ones_mask_p (tree, int);
 108 static tree sign_bit_p (tree, tree);
 109 static int simple_operand_p (tree);
 110 static tree range_binop (enum tree_code, tree, tree, int, tree, int);
 111 static tree make_range (tree, int *, tree *, tree *);
 112 static tree build_range_check (tree, tree, int, tree, tree);
 113 static int merge_ranges (int *, tree *, tree *, int, tree, tree, int, tree,
 114                          tree);
 115 static tree fold_range_test (enum tree_code, tree, tree, tree);
 116 static tree fold_cond_expr_with_comparison (tree, tree, tree, tree);
 117 static tree unextend (tree, int, int, tree);
 118 static tree fold_truthop (enum tree_code, tree, tree, tree);
 119 static tree optimize_minmax_comparison (enum tree_code, tree, tree, tree);
 120 static tree extract_muldiv (tree, tree, enum tree_code, tree);
 121 static tree extract_muldiv_1 (tree, tree, enum tree_code, tree);
 122 static int multiple_of_p (tree, tree, tree);
 123 static tree fold_binary_op_with_conditional_arg (enum tree_code, tree,
 124                                                  tree, tree,
 125                                                  tree, tree, int);
 126 static bool fold_real_zero_addition_p (tree, tree, int);
 127 static tree fold_mathfn_compare (enum built_in_function, enum tree_code,
 128                                  tree, tree, tree);
 129 static tree fold_inf_compare (enum tree_code, tree, tree, tree);
 130 static tree fold_div_compare (enum tree_code, tree, tree, tree);
 131 static bool reorder_operands_p (tree, tree);
 132 static tree fold_negate_const (tree, tree);
 133 static tree fold_not_const (tree, tree);
 134 static tree fold_relational_const (enum tree_code, tree, tree, tree);
 135
 136 /* We know that A1 + B1 = SUM1, using 2's complement arithmetic and ignoring
 137    overflow.  Suppose A, B and SUM have the same respective signs as A1, B1,
 138    and SUM1.  Then this yields nonzero if overflow occurred during the
 139    addition.
 140
 141    Overflow occurs if A and B have the same sign, but A and SUM differ in
 142    sign.  Use `^' to test whether signs differ, and `< 0' to isolate the
 143    sign.  */
 144 #define OVERFLOW_SUM_SIGN(a, b, sum) ((~((a) ^ (b)) & ((a) ^ (sum))) < 0)
 145 \f
 146 /* To do constant folding on INTEGER_CST nodes requires two-word arithmetic.
 147    We do that by representing the two-word integer in 4 words, with only
 148    HOST_BITS_PER_WIDE_INT / 2 bits stored in each word, as a positive
 149    number.  The value of the word is LOWPART + HIGHPART * BASE.  */
 150
 151 #define LOWPART(x) \
 152   ((x) & (((unsigned HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT / 2)) - 1))
 153 #define HIGHPART(x) \
 154   ((unsigned HOST_WIDE_INT) (x) >> HOST_BITS_PER_WIDE_INT / 2)
 155 #define BASE ((unsigned HOST_WIDE_INT) 1 << HOST_BITS_PER_WIDE_INT / 2)
 156
 157 /* Unpack a two-word integer into 4 words.
 158    LOW and HI are the integer, as two `HOST_WIDE_INT' pieces.
 159    WORDS points to the array of HOST_WIDE_INTs.  */
 160
 161 static void
 162 encode (HOST_WIDE_INT *words, unsigned HOST_WIDE_INT low, HOST_WIDE_INT hi)
 163 {
 164   words[0] = LOWPART (low);
 165   words[1] = HIGHPART (low);
 166   words[2] = LOWPART (hi);
 167   words[3] = HIGHPART (hi);
 168 }
 169
 170 /* Pack an array of 4 words into a two-word integer.
 171    WORDS points to the array of words.
 172    The integer is stored into *LOW and *HI as two `HOST_WIDE_INT' pieces.  */
 173
 174 static void
 175 decode (HOST_WIDE_INT *words, unsigned HOST_WIDE_INT *low,
 176         HOST_WIDE_INT *hi)
 177 {
 178   *low = words[0] + words[1] * BASE;
 179   *hi = words[2] + words[3] * BASE;
 180 }
 181 \f
 182 /* T is an INT_CST node.  OVERFLOWABLE indicates if we are interested
 183    in overflow of the value, when >0 we are only interested in signed
 184    overflow, for <0 we are interested in any overflow.  OVERFLOWED
 185    indicates whether overflow has already occurred.  CONST_OVERFLOWED
 186    indicates whether constant overflow has already occurred.  We force
 187    T's value to be within range of T's type (by setting to 0 or 1 all
 188    the bits outside the type's range).  We set TREE_OVERFLOWED if,
 189         OVERFLOWED is nonzero,
 190         or OVERFLOWABLE is >0 and signed overflow occurs
 191         or OVERFLOWABLE is <0 and any overflow occurs
 192    We set TREE_CONSTANT_OVERFLOWED if,
 193         CONST_OVERFLOWED is nonzero
 194         or we set TREE_OVERFLOWED.
 195   We return either the original T, or a copy.  */
 196
 197 tree
 198 force_fit_type (tree t, int overflowable,
 199                 bool overflowed, bool overflowed_const)
 200 {
 201   unsigned HOST_WIDE_INT low;
 202   HOST_WIDE_INT high;
 203   unsigned int prec;
 204   int sign_extended_type;
 205
 206   gcc_assert (TREE_CODE (t) == INTEGER_CST);
 207
 208   low = TREE_INT_CST_LOW (t);
 209   high = TREE_INT_CST_HIGH (t);
 210
 211   if (POINTER_TYPE_P (TREE_TYPE (t))
 212       || TREE_CODE (TREE_TYPE (t)) == OFFSET_TYPE)
 213     prec = POINTER_SIZE;
 214   else
 215     prec = TYPE_PRECISION (TREE_TYPE (t));
 216   /* Size types *are* sign extended.  */
 217   sign_extended_type = (!TYPE_UNSIGNED (TREE_TYPE (t))
 218                         || (TREE_CODE (TREE_TYPE (t)) == INTEGER_TYPE
 219                             && TYPE_IS_SIZETYPE (TREE_TYPE (t))));
 220
 221   /* First clear all bits that are beyond the type's precision.  */
 222
 223   if (prec >= 2 * HOST_BITS_PER_WIDE_INT)
 224     ;
 225   else if (prec > HOST_BITS_PER_WIDE_INT)
 226     high &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
 227   else
 228     {
 229       high = 0;
 230       if (prec < HOST_BITS_PER_WIDE_INT)
 231         low &= ~((HOST_WIDE_INT) (-1) << prec);
 232     }
 233
 234   if (!sign_extended_type)
 235     /* No sign extension */;
 236   else if (prec >= 2 * HOST_BITS_PER_WIDE_INT)
 237     /* Correct width already.  */;
 238   else if (prec > HOST_BITS_PER_WIDE_INT)
 239     {
 240       /* Sign extend top half? */
 241       if (high & ((unsigned HOST_WIDE_INT)1
 242                   << (prec - HOST_BITS_PER_WIDE_INT - 1)))
 243         high |= (HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT);
 244     }
 245   else if (prec == HOST_BITS_PER_WIDE_INT)
 246     {
 247       if ((HOST_WIDE_INT)low < 0)
 248         high = -1;
 249     }
 250   else
 251     {
 252       /* Sign extend bottom half? */
 253       if (low & ((unsigned HOST_WIDE_INT)1 << (prec - 1)))
 254         {
 255           high = -1;
 256           low |= (HOST_WIDE_INT)(-1) << prec;
 257         }
 258     }
 259
 260   /* If the value changed, return a new node.  */
 261   if (overflowed || overflowed_const
 262       || low != TREE_INT_CST_LOW (t) || high != TREE_INT_CST_HIGH (t))
 263     {
 264       t = build_int_cst_wide (TREE_TYPE (t), low, high);
 265
 266       if (overflowed
 267           || overflowable < 0
 268           || (overflowable > 0 && sign_extended_type))
 269         {
 270           t = copy_node (t);
 271           TREE_OVERFLOW (t) = 1;
 272           TREE_CONSTANT_OVERFLOW (t) = 1;
 273         }
 274       else if (overflowed_const)
 275         {
 276           t = copy_node (t);
 277           TREE_CONSTANT_OVERFLOW (t) = 1;
 278         }
 279     }
 280
 281   return t;
 282 }
 283 \f
 284 /* Add two doubleword integers with doubleword result.
 285    Each argument is given as two `HOST_WIDE_INT' pieces.
 286    One argument is L1 and H1; the other, L2 and H2.
 287    The value is stored as two `HOST_WIDE_INT' pieces in *LV and *HV.  */
 288
 289 int
 290 add_double (unsigned HOST_WIDE_INT l1, HOST_WIDE_INT h1,
 291             unsigned HOST_WIDE_INT l2, HOST_WIDE_INT h2,
 292             unsigned HOST_WIDE_INT *lv, HOST_WIDE_INT *hv)
 293 {
 294   unsigned HOST_WIDE_INT l;
 295   HOST_WIDE_INT h;
 296
 297   l = l1 + l2;
 298   h = h1 + h2 + (l < l1);
 299
 300   *lv = l;
 301   *hv = h;
 302   return OVERFLOW_SUM_SIGN (h1, h2, h);
 303 }
 304
 305 /* Negate a doubleword integer with doubleword result.
 306    Return nonzero if the operation overflows, assuming it's signed.
 307    The argument is given as two `HOST_WIDE_INT' pieces in L1 and H1.
 308    The value is stored as two `HOST_WIDE_INT' pieces in *LV and *HV.  */
 309
 310 int
 311 neg_double (unsigned HOST_WIDE_INT l1, HOST_WIDE_INT h1,
 312             unsigned HOST_WIDE_INT *lv, HOST_WIDE_INT *hv)
 313 {
 314   if (l1 == 0)
 315     {
 316       *lv = 0;
 317       *hv = - h1;
 318       return (*hv & h1) < 0;
 319     }
 320   else
 321     {
 322       *lv = -l1;
 323       *hv = ~h1;
 324       return 0;
 325     }
 326 }
 327 \f
 328 /* Multiply two doubleword integers with doubleword result.
 329    Return nonzero if the operation overflows, assuming it's signed.
 330    Each argument is given as two `HOST_WIDE_INT' pieces.
 331    One argument is L1 and H1; the other, L2 and H2.
 332    The value is stored as two `HOST_WIDE_INT' pieces in *LV and *HV.  */
 333
 334 int
 335 mul_double (unsigned HOST_WIDE_INT l1, HOST_WIDE_INT h1,
 336             unsigned HOST_WIDE_INT l2, HOST_WIDE_INT h2,
 337             unsigned HOST_WIDE_INT *lv, HOST_WIDE_INT *hv)
 338 {
 339   HOST_WIDE_INT arg1[4];
 340   HOST_WIDE_INT arg2[4];
 341   HOST_WIDE_INT prod[4 * 2];
 342   unsigned HOST_WIDE_INT carry;
 343   int i, j, k;
 344   unsigned HOST_WIDE_INT toplow, neglow;
 345   HOST_WIDE_INT tophigh, neghigh;
 346
 347   encode (arg1, l1, h1);
 348   encode (arg2, l2, h2);
 349
 350   memset (prod, 0, sizeof prod);
 351
 352   for (i = 0; i < 4; i++)
 353     {
 354       carry = 0;
 355       for (j = 0; j < 4; j++)
 356         {
 357           k = i + j;
 358           /* This product is <= 0xFFFE0001, the sum <= 0xFFFF0000.  */
 359           carry += arg1[i] * arg2[j];
 360           /* Since prod[p] < 0xFFFF, this sum <= 0xFFFFFFFF.  */
 361           carry += prod[k];
 362           prod[k] = LOWPART (carry);
 363           carry = HIGHPART (carry);
 364         }
 365       prod[i + 4] = carry;
 366     }
 367
 368   decode (prod, lv, hv);        /* This ignores prod[4] through prod[4*2-1] */
 369
 370   /* Check for overflow by calculating the top half of the answer in full;
 371      it should agree with the low half's sign bit.  */
 372   decode (prod + 4, &toplow, &tophigh);
 373   if (h1 < 0)
 374     {
 375       neg_double (l2, h2, &neglow, &neghigh);
 376       add_double (neglow, neghigh, toplow, tophigh, &toplow, &tophigh);
 377     }
 378   if (h2 < 0)
 379     {
 380       neg_double (l1, h1, &neglow, &neghigh);
 381       add_double (neglow, neghigh, toplow, tophigh, &toplow, &tophigh);
 382     }
 383   return (*hv < 0 ? ~(toplow & tophigh) : toplow | tophigh) != 0;
 384 }
 385 \f
 386 /* Shift the doubleword integer in L1, H1 left by COUNT places
 387    keeping only PREC bits of result.
 388    Shift right if COUNT is negative.
 389    ARITH nonzero specifies arithmetic shifting; otherwise use logical shift.
 390    Store the value as two `HOST_WIDE_INT' pieces in *LV and *HV.  */
 391
 392 void
 393 lshift_double (unsigned HOST_WIDE_INT l1, HOST_WIDE_INT h1,
 394                HOST_WIDE_INT count, unsigned int prec,
 395                unsigned HOST_WIDE_INT *lv, HOST_WIDE_INT *hv, int arith)
 396 {
 397   unsigned HOST_WIDE_INT signmask;
 398
 399   if (count < 0)
 400     {
 401       rshift_double (l1, h1, -count, prec, lv, hv, arith);
 402       return;
 403     }
 404
 405   if (SHIFT_COUNT_TRUNCATED)
 406     count %= prec;
 407
 408   if (count >= 2 * HOST_BITS_PER_WIDE_INT)
 409     {
 410       /* Shifting by the host word size is undefined according to the
 411          ANSI standard, so we must handle this as a special case.  */
 412       *hv = 0;
 413       *lv = 0;
 414     }
 415   else if (count >= HOST_BITS_PER_WIDE_INT)
 416     {
 417       *hv = l1 << (count - HOST_BITS_PER_WIDE_INT);
 418       *lv = 0;
 419     }
 420   else
 421     {
 422       *hv = (((unsigned HOST_WIDE_INT) h1 << count)
 423              | (l1 >> (HOST_BITS_PER_WIDE_INT - count - 1) >> 1));
 424       *lv = l1 << count;
 425     }
 426
 427   /* Sign extend all bits that are beyond the precision.  */
 428
 429   signmask = -((prec > HOST_BITS_PER_WIDE_INT
 430                 ? ((unsigned HOST_WIDE_INT) *hv
 431                    >> (prec - HOST_BITS_PER_WIDE_INT - 1))
 432                 : (*lv >> (prec - 1))) & 1);
 433
 434   if (prec >= 2 * HOST_BITS_PER_WIDE_INT)
 435     ;
 436   else if (prec >= HOST_BITS_PER_WIDE_INT)
 437     {
 438       *hv &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
 439       *hv |= signmask << (prec - HOST_BITS_PER_WIDE_INT);
 440     }
 441   else
 442     {
 443       *hv = signmask;
 444       *lv &= ~((unsigned HOST_WIDE_INT) (-1) << prec);
 445       *lv |= signmask << prec;
 446     }
 447 }
 448
 449 /* Shift the doubleword integer in L1, H1 right by COUNT places
 450    keeping only PREC bits of result.  COUNT must be positive.
 451    ARITH nonzero specifies arithmetic shifting; otherwise use logical shift.
 452    Store the value as two `HOST_WIDE_INT' pieces in *LV and *HV.  */
 453
 454 void
 455 rshift_double (unsigned HOST_WIDE_INT l1, HOST_WIDE_INT h1,
 456                HOST_WIDE_INT count, unsigned int prec,
 457                unsigned HOST_WIDE_INT *lv, HOST_WIDE_INT *hv,
 458                int arith)
 459 {
 460   unsigned HOST_WIDE_INT signmask;
 461
 462   signmask = (arith
 463               ? -((unsigned HOST_WIDE_INT) h1 >> (HOST_BITS_PER_WIDE_INT - 1))
 464               : 0);
 465
 466   if (SHIFT_COUNT_TRUNCATED)
 467     count %= prec;
 468
 469   if (count >= 2 * HOST_BITS_PER_WIDE_INT)
 470     {
 471       /* Shifting by the host word size is undefined according to the
 472          ANSI standard, so we must handle this as a special case.  */
 473       *hv = 0;
 474       *lv = 0;
 475     }
 476   else if (count >= HOST_BITS_PER_WIDE_INT)
 477     {
 478       *hv = 0;
 479       *lv = (unsigned HOST_WIDE_INT) h1 >> (count - HOST_BITS_PER_WIDE_INT);
 480     }
 481   else
 482     {
 483       *hv = (unsigned HOST_WIDE_INT) h1 >> count;
 484       *lv = ((l1 >> count)
 485              | ((unsigned HOST_WIDE_INT) h1 << (HOST_BITS_PER_WIDE_INT - count - 1) << 1));
 486     }
 487
 488   /* Zero / sign extend all bits that are beyond the precision.  */
 489
 490   if (count >= (HOST_WIDE_INT)prec)
 491     {
 492       *hv = signmask;
 493       *lv = signmask;
 494     }
 495   else if ((prec - count) >= 2 * HOST_BITS_PER_WIDE_INT)
 496     ;
 497   else if ((prec - count) >= HOST_BITS_PER_WIDE_INT)
 498     {
 499       *hv &= ~((HOST_WIDE_INT) (-1) << (prec - count - HOST_BITS_PER_WIDE_INT));
 500       *hv |= signmask << (prec - count - HOST_BITS_PER_WIDE_INT);
 501     }
 502   else
 503     {
 504       *hv = signmask;
 505       *lv &= ~((unsigned HOST_WIDE_INT) (-1) << (prec - count));
 506       *lv |= signmask << (prec - count);
 507     }
 508 }
 509 \f
 510 /* Rotate the doubleword integer in L1, H1 left by COUNT places
 511    keeping only PREC bits of result.
 512    Rotate right if COUNT is negative.
 513    Store the value as two `HOST_WIDE_INT' pieces in *LV and *HV.  */
 514
 515 void
 516 lrotate_double (unsigned HOST_WIDE_INT l1, HOST_WIDE_INT h1,
 517                 HOST_WIDE_INT count, unsigned int prec,
 518                 unsigned HOST_WIDE_INT *lv, HOST_WIDE_INT *hv)
 519 {
 520   unsigned HOST_WIDE_INT s1l, s2l;
 521   HOST_WIDE_INT s1h, s2h;
 522
 523   count %= prec;
 524   if (count < 0)
 525     count += prec;
 526
 527   lshift_double (l1, h1, count, prec, &s1l, &s1h, 0);
 528   rshift_double (l1, h1, prec - count, prec, &s2l, &s2h, 0);
 529   *lv = s1l | s2l;
 530   *hv = s1h | s2h;
 531 }
 532
 533 /* Rotate the doubleword integer in L1, H1 left by COUNT places
 534    keeping only PREC bits of result.  COUNT must be positive.
 535    Store the value as two `HOST_WIDE_INT' pieces in *LV and *HV.  */
 536
 537 void
 538 rrotate_double (unsigned HOST_WIDE_INT l1, HOST_WIDE_INT h1,
 539                 HOST_WIDE_INT count, unsigned int prec,
 540                 unsigned HOST_WIDE_INT *lv, HOST_WIDE_INT *hv)
 541 {
 542   unsigned HOST_WIDE_INT s1l, s2l;
 543   HOST_WIDE_INT s1h, s2h;
 544
 545   count %= prec;
 546   if (count < 0)
 547     count += prec;
 548
 549   rshift_double (l1, h1, count, prec, &s1l, &s1h, 0);
 550   lshift_double (l1, h1, prec - count, prec, &s2l, &s2h, 0);
 551   *lv = s1l | s2l;
 552   *hv = s1h | s2h;
 553 }
 554 \f
 555 /* Divide doubleword integer LNUM, HNUM by doubleword integer LDEN, HDEN
 556    for a quotient (stored in *LQUO, *HQUO) and remainder (in *LREM, *HREM).
 557    CODE is a tree code for a kind of division, one of
 558    TRUNC_DIV_EXPR, FLOOR_DIV_EXPR, CEIL_DIV_EXPR, ROUND_DIV_EXPR
 559    or EXACT_DIV_EXPR
 560    It controls how the quotient is rounded to an integer.
 561    Return nonzero if the operation overflows.
 562    UNS nonzero says do unsigned division.  */
 563
 564 int
 565 div_and_round_double (enum tree_code code, int uns,
 566                       unsigned HOST_WIDE_INT lnum_orig, /* num == numerator == dividend */
 567                       HOST_WIDE_INT hnum_orig,
 568                       unsigned HOST_WIDE_INT lden_orig, /* den == denominator == divisor */
 569                       HOST_WIDE_INT hden_orig,
 570                       unsigned HOST_WIDE_INT *lquo,
 571                       HOST_WIDE_INT *hquo, unsigned HOST_WIDE_INT *lrem,
 572                       HOST_WIDE_INT *hrem)
 573 {
 574   int quo_neg = 0;
 575   HOST_WIDE_INT num[4 + 1];     /* extra element for scaling.  */
 576   HOST_WIDE_INT den[4], quo[4];
 577   int i, j;
 578   unsigned HOST_WIDE_INT work;
 579   unsigned HOST_WIDE_INT carry = 0;
 580   unsigned HOST_WIDE_INT lnum = lnum_orig;
 581   HOST_WIDE_INT hnum = hnum_orig;
 582   unsigned HOST_WIDE_INT lden = lden_orig;
 583   HOST_WIDE_INT hden = hden_orig;
 584   int overflow = 0;
 585
 586   if (hden == 0 && lden == 0)
 587     overflow = 1, lden = 1;
 588
 589   /* Calculate quotient sign and convert operands to unsigned.  */
 590   if (!uns)
 591     {
 592       if (hnum < 0)
 593         {
 594           quo_neg = ~ quo_neg;
 595           /* (minimum integer) / (-1) is the only overflow case.  */
 596           if (neg_double (lnum, hnum, &lnum, &hnum)
 597               && ((HOST_WIDE_INT) lden & hden) == -1)
 598             overflow = 1;
 599         }
 600       if (hden < 0)
 601         {
 602           quo_neg = ~ quo_neg;
 603           neg_double (lden, hden, &lden, &hden);
 604         }
 605     }
 606
 607   if (hnum == 0 && hden == 0)
 608     {                           /* single precision */
 609       *hquo = *hrem = 0;
 610       /* This unsigned division rounds toward zero.  */
 611       *lquo = lnum / lden;
 612       goto finish_up;
 613     }
 614
 615   if (hnum == 0)
 616     {                           /* trivial case: dividend < divisor */
 617       /* hden != 0 already checked.  */
 618       *hquo = *lquo = 0;
 619       *hrem = hnum;
 620       *lrem = lnum;
 621       goto finish_up;
 622     }
 623
 624   memset (quo, 0, sizeof quo);
 625
 626   memset (num, 0, sizeof num);  /* to zero 9th element */
 627   memset (den, 0, sizeof den);
 628
 629   encode (num, lnum, hnum);
 630   encode (den, lden, hden);
 631
 632   /* Special code for when the divisor < BASE.  */
 633   if (hden == 0 && lden < (unsigned HOST_WIDE_INT) BASE)
 634     {
 635       /* hnum != 0 already checked.  */
 636       for (i = 4 - 1; i >= 0; i--)
 637         {
 638           work = num[i] + carry * BASE;
 639           quo[i] = work / lden;
 640           carry = work % lden;
 641         }
 642     }
 643   else
 644     {
 645       /* Full double precision division,
 646          with thanks to Don Knuth's "Seminumerical Algorithms".  */
 647       int num_hi_sig, den_hi_sig;
 648       unsigned HOST_WIDE_INT quo_est, scale;
 649
 650       /* Find the highest nonzero divisor digit.  */
 651       for (i = 4 - 1;; i--)
 652         if (den[i] != 0)
 653           {
 654             den_hi_sig = i;
 655             break;
 656           }
 657
 658       /* Insure that the first digit of the divisor is at least BASE/2.
 659          This is required by the quotient digit estimation algorithm.  */
 660
 661       scale = BASE / (den[den_hi_sig] + 1);
 662       if (scale > 1)
 663         {               /* scale divisor and dividend */
 664           carry = 0;
 665           for (i = 0; i <= 4 - 1; i++)
 666             {
 667               work = (num[i] * scale) + carry;
 668               num[i] = LOWPART (work);
 669               carry = HIGHPART (work);
 670             }
 671
 672           num[4] = carry;
 673           carry = 0;
 674           for (i = 0; i <= 4 - 1; i++)
 675             {
 676               work = (den[i] * scale) + carry;
 677               den[i] = LOWPART (work);
 678               carry = HIGHPART (work);
 679               if (den[i] != 0) den_hi_sig = i;
 680             }
 681         }
 682
 683       num_hi_sig = 4;
 684
 685       /* Main loop */
 686       for (i = num_hi_sig - den_hi_sig - 1; i >= 0; i--)
 687         {
 688           /* Guess the next quotient digit, quo_est, by dividing the first
 689              two remaining dividend digits by the high order quotient digit.
 690              quo_est is never low and is at most 2 high.  */
 691           unsigned HOST_WIDE_INT tmp;
 692
 693           num_hi_sig = i + den_hi_sig + 1;
 694           work = num[num_hi_sig] * BASE + num[num_hi_sig - 1];
 695           if (num[num_hi_sig] != den[den_hi_sig])
 696             quo_est = work / den[den_hi_sig];
 697           else
 698             quo_est = BASE - 1;
 699
 700           /* Refine quo_est so it's usually correct, and at most one high.  */
 701           tmp = work - quo_est * den[den_hi_sig];
 702           if (tmp < BASE
 703               && (den[den_hi_sig - 1] * quo_est
 704                   > (tmp * BASE + num[num_hi_sig - 2])))
 705             quo_est--;
 706
 707           /* Try QUO_EST as the quotient digit, by multiplying the
 708              divisor by QUO_EST and subtracting from the remaining dividend.
 709              Keep in mind that QUO_EST is the I - 1st digit.  */
 710
 711           carry = 0;
 712           for (j = 0; j <= den_hi_sig; j++)
 713             {
 714               work = quo_est * den[j] + carry;
 715               carry = HIGHPART (work);
 716               work = num[i + j] - LOWPART (work);
 717               num[i + j] = LOWPART (work);
 718               carry += HIGHPART (work) != 0;
 719             }
 720
 721           /* If quo_est was high by one, then num[i] went negative and
 722              we need to correct things.  */
 723           if (num[num_hi_sig] < (HOST_WIDE_INT) carry)
 724             {
 725               quo_est--;
 726               carry = 0;                /* add divisor back in */
 727               for (j = 0; j <= den_hi_sig; j++)
 728                 {
 729                   work = num[i + j] + den[j] + carry;
 730                   carry = HIGHPART (work);
 731                   num[i + j] = LOWPART (work);
 732                 }
 733
 734               num [num_hi_sig] += carry;
 735             }
 736
 737           /* Store the quotient digit.  */
 738           quo[i] = quo_est;
 739         }
 740     }
 741
 742   decode (quo, lquo, hquo);
 743
 744  finish_up:
 745   /* If result is negative, make it so.  */
 746   if (quo_neg)
 747     neg_double (*lquo, *hquo, lquo, hquo);
 748
 749   /* Compute trial remainder:  rem = num - (quo * den)  */
 750   mul_double (*lquo, *hquo, lden_orig, hden_orig, lrem, hrem);
 751   neg_double (*lrem, *hrem, lrem, hrem);
 752   add_double (lnum_orig, hnum_orig, *lrem, *hrem, lrem, hrem);
 753
 754   switch (code)
 755     {
 756     case TRUNC_DIV_EXPR:
 757     case TRUNC_MOD_EXPR:        /* round toward zero */
 758     case EXACT_DIV_EXPR:        /* for this one, it shouldn't matter */
 759       return overflow;
 760
 761     case FLOOR_DIV_EXPR:
 762     case FLOOR_MOD_EXPR:        /* round toward negative infinity */
 763       if (quo_neg && (*lrem != 0 || *hrem != 0))   /* ratio < 0 && rem != 0 */
 764         {
 765           /* quo = quo - 1;  */
 766           add_double (*lquo, *hquo, (HOST_WIDE_INT) -1, (HOST_WIDE_INT)  -1,
 767                       lquo, hquo);
 768         }
 769       else
 770         return overflow;
 771       break;
 772
 773     case CEIL_DIV_EXPR:
 774     case CEIL_MOD_EXPR:         /* round toward positive infinity */
 775       if (!quo_neg && (*lrem != 0 || *hrem != 0))  /* ratio > 0 && rem != 0 */
 776         {
 777           add_double (*lquo, *hquo, (HOST_WIDE_INT) 1, (HOST_WIDE_INT) 0,
 778                       lquo, hquo);
 779         }
 780       else
 781         return overflow;
 782       break;
 783
 784     case ROUND_DIV_EXPR:
 785     case ROUND_MOD_EXPR:        /* round to closest integer */
 786       {
 787         unsigned HOST_WIDE_INT labs_rem = *lrem;
 788         HOST_WIDE_INT habs_rem = *hrem;
 789         unsigned HOST_WIDE_INT labs_den = lden, ltwice;
 790         HOST_WIDE_INT habs_den = hden, htwice;
 791
 792         /* Get absolute values.  */
 793         if (*hrem < 0)
 794           neg_double (*lrem, *hrem, &labs_rem, &habs_rem);
 795         if (hden < 0)
 796           neg_double (lden, hden, &labs_den, &habs_den);
 797
 798         /* If (2 * abs (lrem) >= abs (lden)) */
 799         mul_double ((HOST_WIDE_INT) 2, (HOST_WIDE_INT) 0,
 800                     labs_rem, habs_rem, &ltwice, &htwice);
 801
 802         if (((unsigned HOST_WIDE_INT) habs_den
 803              < (unsigned HOST_WIDE_INT) htwice)
 804             || (((unsigned HOST_WIDE_INT) habs_den
 805                  == (unsigned HOST_WIDE_INT) htwice)
 806                 && (labs_den < ltwice)))
 807           {
 808             if (*hquo < 0)
 809               /* quo = quo - 1;  */
 810               add_double (*lquo, *hquo,
 811                           (HOST_WIDE_INT) -1, (HOST_WIDE_INT) -1, lquo, hquo);
 812             else
 813               /* quo = quo + 1; */
 814               add_double (*lquo, *hquo, (HOST_WIDE_INT) 1, (HOST_WIDE_INT) 0,
 815                           lquo, hquo);
 816           }
 817         else
 818           return overflow;
 819       }
 820       break;
 821
 822     default:
 823       gcc_unreachable ();
 824     }
 825
 826   /* Compute true remainder:  rem = num - (quo * den)  */
 827   mul_double (*lquo, *hquo, lden_orig, hden_orig, lrem, hrem);
 828   neg_double (*lrem, *hrem, lrem, hrem);
 829   add_double (lnum_orig, hnum_orig, *lrem, *hrem, lrem, hrem);
 830   return overflow;
 831 }
 832
 833 /* If ARG2 divides ARG1 with zero remainder, carries out the division
 834    of type CODE and returns the quotient.
 835    Otherwise returns NULL_TREE.  */
 836
 837 static tree
 838 div_if_zero_remainder (enum tree_code code, tree arg1, tree arg2)
 839 {
 840   unsigned HOST_WIDE_INT int1l, int2l;
 841   HOST_WIDE_INT int1h, int2h;
 842   unsigned HOST_WIDE_INT quol, reml;
 843   HOST_WIDE_INT quoh, remh;
 844   tree type = TREE_TYPE (arg1);
 845   int uns = TYPE_UNSIGNED (type);
 846
 847   int1l = TREE_INT_CST_LOW (arg1);
 848   int1h = TREE_INT_CST_HIGH (arg1);
 849   int2l = TREE_INT_CST_LOW (arg2);
 850   int2h = TREE_INT_CST_HIGH (arg2);
 851
 852   div_and_round_double (code, uns, int1l, int1h, int2l, int2h,
 853                         &quol, &quoh, &reml, &remh);
 854   if (remh != 0 || reml != 0)
 855     return NULL_TREE;
 856
 857   return build_int_cst_wide (type, quol, quoh);
 858 }
 859 \f
 860 /* Return true if built-in mathematical function specified by CODE
 861    preserves the sign of it argument, i.e. -f(x) == f(-x).  */
 862
 863 static bool
 864 negate_mathfn_p (enum built_in_function code)
 865 {
 866   switch (code)
 867     {
 868     case BUILT_IN_ASIN:
 869     case BUILT_IN_ASINF:
 870     case BUILT_IN_ASINL:
 871     case BUILT_IN_ATAN:
 872     case BUILT_IN_ATANF:
 873     case BUILT_IN_ATANL:
 874     case BUILT_IN_SIN:
 875     case BUILT_IN_SINF:
 876     case BUILT_IN_SINL:
 877     case BUILT_IN_TAN:
 878     case BUILT_IN_TANF:
 879     case BUILT_IN_TANL:
 880       return true;
 881
 882     default:
 883       break;
 884     }
 885   return false;
 886 }
 887
 888 /* Check whether we may negate an integer constant T without causing
 889    overflow.  */
 890
 891 bool
 892 may_negate_without_overflow_p (tree t)
 893 {
 894   unsigned HOST_WIDE_INT val;
 895   unsigned int prec;
 896   tree type;
 897
 898   gcc_assert (TREE_CODE (t) == INTEGER_CST);
 899
 900   type = TREE_TYPE (t);
 901   if (TYPE_UNSIGNED (type))
 902     return false;
 903
 904   prec = TYPE_PRECISION (type);
 905   if (prec > HOST_BITS_PER_WIDE_INT)
 906     {
 907       if (TREE_INT_CST_LOW (t) != 0)
 908         return true;
 909       prec -= HOST_BITS_PER_WIDE_INT;
 910       val = TREE_INT_CST_HIGH (t);
 911     }
 912   else
 913     val = TREE_INT_CST_LOW (t);
 914   if (prec < HOST_BITS_PER_WIDE_INT)
 915     val &= ((unsigned HOST_WIDE_INT) 1 << prec) - 1;
 916   return val != ((unsigned HOST_WIDE_INT) 1 << (prec - 1));
 917 }
 918
 919 /* Determine whether an expression T can be cheaply negated using
 920    the function negate_expr.  */
 921
 922 static bool
 923 negate_expr_p (tree t)
 924 {
 925   tree type;
 926
 927   if (t == 0)
 928     return false;
 929
 930   type = TREE_TYPE (t);
 931
 932   STRIP_SIGN_NOPS (t);
 933   switch (TREE_CODE (t))
 934     {
 935     case INTEGER_CST:
 936       if (TYPE_UNSIGNED (type) || ! flag_trapv)
 937         return true;
 938
 939       /* Check that -CST will not overflow type.  */
 940       return may_negate_without_overflow_p (t);
 941
 942     case REAL_CST:
 943     case NEGATE_EXPR:
 944       return true;
 945
 946     case COMPLEX_CST:
 947       return negate_expr_p (TREE_REALPART (t))
 948              && negate_expr_p (TREE_IMAGPART (t));
 949
 950     case PLUS_EXPR:
 951       if (FLOAT_TYPE_P (type) && !flag_unsafe_math_optimizations)
 952         return false;
 953       /* -(A + B) -> (-B) - A.  */
 954       if (negate_expr_p (TREE_OPERAND (t, 1))
 955           && reorder_operands_p (TREE_OPERAND (t, 0),
 956                                  TREE_OPERAND (t, 1)))
 957         return true;
 958       /* -(A + B) -> (-A) - B.  */
 959       return negate_expr_p (TREE_OPERAND (t, 0));
 960
 961     case MINUS_EXPR:
 962       /* We can't turn -(A-B) into B-A when we honor signed zeros.  */
 963       return (! FLOAT_TYPE_P (type) || flag_unsafe_math_optimizations)
 964              && reorder_operands_p (TREE_OPERAND (t, 0),
 965                                     TREE_OPERAND (t, 1));
 966
 967     case MULT_EXPR:
 968       if (TYPE_UNSIGNED (TREE_TYPE (t)))
 969         break;
 970
 971       /* Fall through.  */
 972
 973     case RDIV_EXPR:
 974       if (! HONOR_SIGN_DEPENDENT_ROUNDING (TYPE_MODE (TREE_TYPE (t))))
 975         return negate_expr_p (TREE_OPERAND (t, 1))
 976                || negate_expr_p (TREE_OPERAND (t, 0));
 977       break;
 978
 979     case NOP_EXPR:
 980       /* Negate -((double)float) as (double)(-float).  */
 981       if (TREE_CODE (type) == REAL_TYPE)
 982         {
 983           tree tem = strip_float_extensions (t);
 984           if (tem != t)
 985             return negate_expr_p (tem);
 986         }
 987       break;
 988
 989     case CALL_EXPR:
 990       /* Negate -f(x) as f(-x).  */
 991       if (negate_mathfn_p (builtin_mathfn_code (t)))
 992         return negate_expr_p (TREE_VALUE (TREE_OPERAND (t, 1)));
 993       break;
 994
 995     case RSHIFT_EXPR:
 996       /* Optimize -((int)x >> 31) into (unsigned)x >> 31.  */
 997       if (TREE_CODE (TREE_OPERAND (t, 1)) == INTEGER_CST)
 998         {
 999           tree op1 = TREE_OPERAND (t, 1);
1000           if (TREE_INT_CST_HIGH (op1) == 0
1001               && (unsigned HOST_WIDE_INT) (TYPE_PRECISION (type) - 1)
1002                  == TREE_INT_CST_LOW (op1))
1003             return true;
1004         }
1005       break;
1006
1007     default:
1008       break;
1009     }
1010   return false;
1011 }
1012
1013 /* Given T, an expression, return the negation of T.  Allow for T to be
1014    null, in which case return null.  */
1015
1016 static tree
1017 negate_expr (tree t)
1018 {
1019   tree type;
1020   tree tem;
1021
1022   if (t == 0)
1023     return 0;
1024
1025   type = TREE_TYPE (t);
1026   STRIP_SIGN_NOPS (t);
1027
1028   switch (TREE_CODE (t))
1029     {
1030     case INTEGER_CST:
1031       tem = fold_negate_const (t, type);
1032       if (! TREE_OVERFLOW (tem)
1033           || TYPE_UNSIGNED (type)
1034           || ! flag_trapv)
1035         return tem;
1036       break;
1037
1038     case REAL_CST:
1039       tem = fold_negate_const (t, type);
1040       /* Two's complement FP formats, such as c4x, may overflow.  */
1041       if (! TREE_OVERFLOW (tem) || ! flag_trapping_math)
1042         return fold_convert (type, tem);
1043       break;
1044
1045     case COMPLEX_CST:
1046       {
1047         tree rpart = negate_expr (TREE_REALPART (t));
1048         tree ipart = negate_expr (TREE_IMAGPART (t));
1049
1050         if ((TREE_CODE (rpart) == REAL_CST
1051              && TREE_CODE (ipart) == REAL_CST)
1052             || (TREE_CODE (rpart) == INTEGER_CST
1053                 && TREE_CODE (ipart) == INTEGER_CST))
1054           return build_complex (type, rpart, ipart);
1055       }
1056       break;
1057
1058     case NEGATE_EXPR:
1059       return fold_convert (type, TREE_OPERAND (t, 0));
1060
1061     case PLUS_EXPR:
1062       if (! FLOAT_TYPE_P (type) || flag_unsafe_math_optimizations)
1063         {
1064           /* -(A + B) -> (-B) - A.  */
1065           if (negate_expr_p (TREE_OPERAND (t, 1))
1066               && reorder_operands_p (TREE_OPERAND (t, 0),
1067                                      TREE_OPERAND (t, 1)))
1068             {
1069               tem = negate_expr (TREE_OPERAND (t, 1));
1070               tem = fold_build2 (MINUS_EXPR, TREE_TYPE (t),
1071                                  tem, TREE_OPERAND (t, 0));
1072               return fold_convert (type, tem);
1073             }
1074
1075           /* -(A + B) -> (-A) - B.  */
1076           if (negate_expr_p (TREE_OPERAND (t, 0)))
1077             {
1078               tem = negate_expr (TREE_OPERAND (t, 0));
1079               tem = fold_build2 (MINUS_EXPR, TREE_TYPE (t),
1080                                  tem, TREE_OPERAND (t, 1));
1081               return fold_convert (type, tem);
1082             }
1083         }
1084       break;
1085
1086     case MINUS_EXPR:
1087       /* - (A - B) -> B - A  */
1088       if ((! FLOAT_TYPE_P (type) || flag_unsafe_math_optimizations)
1089           && reorder_operands_p (TREE_OPERAND (t, 0), TREE_OPERAND (t, 1)))
1090         return fold_convert (type,
1091                              fold_build2 (MINUS_EXPR, TREE_TYPE (t),
1092                                           TREE_OPERAND (t, 1),
1093                                           TREE_OPERAND (t, 0)));
1094       break;
1095
1096     case MULT_EXPR:
1097       if (TYPE_UNSIGNED (TREE_TYPE (t)))
1098         break;
1099
1100       /* Fall through.  */
1101
1102     case RDIV_EXPR:
1103       if (! HONOR_SIGN_DEPENDENT_ROUNDING (TYPE_MODE (TREE_TYPE (t))))
1104         {
1105           tem = TREE_OPERAND (t, 1);
1106           if (negate_expr_p (tem))
1107             return fold_convert (type,
1108                                  fold_build2 (TREE_CODE (t), TREE_TYPE (t),
1109                                               TREE_OPERAND (t, 0),
1110                                               negate_expr (tem)));
1111           tem = TREE_OPERAND (t, 0);
1112           if (negate_expr_p (tem))
1113             return fold_convert (type,
1114                                  fold_build2 (TREE_CODE (t), TREE_TYPE (t),
1115                                               negate_expr (tem),
1116                                               TREE_OPERAND (t, 1)));
1117         }
1118       break;
1119
1120     case NOP_EXPR:
1121       /* Convert -((double)float) into (double)(-float).  */
1122       if (TREE_CODE (type) == REAL_TYPE)
1123         {
1124           tem = strip_float_extensions (t);
1125           if (tem != t && negate_expr_p (tem))
1126             return fold_convert (type, negate_expr (tem));
1127         }
1128       break;
1129
1130     case CALL_EXPR:
1131       /* Negate -f(x) as f(-x).  */
1132       if (negate_mathfn_p (builtin_mathfn_code (t))
1133           && negate_expr_p (TREE_VALUE (TREE_OPERAND (t, 1))))
1134         {
1135           tree fndecl, arg, arglist;
1136
1137           fndecl = get_callee_fndecl (t);
1138           arg = negate_expr (TREE_VALUE (TREE_OPERAND (t, 1)));
1139           arglist = build_tree_list (NULL_TREE, arg);
1140           return build_function_call_expr (fndecl, arglist);
1141         }
1142       break;
1143
1144     case RSHIFT_EXPR:
1145       /* Optimize -((int)x >> 31) into (unsigned)x >> 31.  */
1146       if (TREE_CODE (TREE_OPERAND (t, 1)) == INTEGER_CST)
1147         {
1148           tree op1 = TREE_OPERAND (t, 1);
1149           if (TREE_INT_CST_HIGH (op1) == 0
1150               && (unsigned HOST_WIDE_INT) (TYPE_PRECISION (type) - 1)
1151                  == TREE_INT_CST_LOW (op1))
1152             {
1153               tree ntype = TYPE_UNSIGNED (type)
1154                            ? lang_hooks.types.signed_type (type)
1155                            : lang_hooks.types.unsigned_type (type);
1156               tree temp = fold_convert (ntype, TREE_OPERAND (t, 0));
1157               temp = fold_build2 (RSHIFT_EXPR, ntype, temp, op1);
1158               return fold_convert (type, temp);
1159             }
1160         }
1161       break;
1162
1163     default:
1164       break;
1165     }
1166
1167   tem = fold_build1 (NEGATE_EXPR, TREE_TYPE (t), t);
1168   return fold_convert (type, tem);
1169 }
1170 \f
1171 /* Split a tree IN into a constant, literal and variable parts that could be
1172    combined with CODE to make IN.  "constant" means an expression with
1173    TREE_CONSTANT but that isn't an actual constant.  CODE must be a
1174    commutative arithmetic operation.  Store the constant part into *CONP,
1175    the literal in *LITP and return the variable part.  If a part isn't
1176    present, set it to null.  If the tree does not decompose in this way,
1177    return the entire tree as the variable part and the other parts as null.
1178
1179    If CODE is PLUS_EXPR we also split trees that use MINUS_EXPR.  In that
1180    case, we negate an operand that was subtracted.  Except if it is a
1181    literal for which we use *MINUS_LITP instead.
1182
1183    If NEGATE_P is true, we are negating all of IN, again except a literal
1184    for which we use *MINUS_LITP instead.
1185
1186    If IN is itself a literal or constant, return it as appropriate.
1187
1188    Note that we do not guarantee that any of the three values will be the
1189    same type as IN, but they will have the same signedness and mode.  */
1190
1191 static tree
1192 split_tree (tree in, enum tree_code code, tree *conp, tree *litp,
1193             tree *minus_litp, int negate_p)
1194 {
1195   tree var = 0;
1196
1197   *conp = 0;
1198   *litp = 0;
1199   *minus_litp = 0;
1200
1201   /* Strip any conversions that don't change the machine mode or signedness.  */
1202   STRIP_SIGN_NOPS (in);
1203
1204   if (TREE_CODE (in) == INTEGER_CST || TREE_CODE (in) == REAL_CST)
1205     *litp = in;
1206   else if (TREE_CODE (in) == code
1207            || (! FLOAT_TYPE_P (TREE_TYPE (in))
1208                /* We can associate addition and subtraction together (even
1209                   though the C standard doesn't say so) for integers because
1210                   the value is not affected.  For reals, the value might be
1211                   affected, so we can't.  */
1212                && ((code == PLUS_EXPR && TREE_CODE (in) == MINUS_EXPR)
1213                    || (code == MINUS_EXPR && TREE_CODE (in) == PLUS_EXPR))))
1214     {
1215       tree op0 = TREE_OPERAND (in, 0);
1216       tree op1 = TREE_OPERAND (in, 1);
1217       int neg1_p = TREE_CODE (in) == MINUS_EXPR;
1218       int neg_litp_p = 0, neg_conp_p = 0, neg_var_p = 0;
1219
1220       /* First see if either of the operands is a literal, then a constant.  */
1221       if (TREE_CODE (op0) == INTEGER_CST || TREE_CODE (op0) == REAL_CST)
1222         *litp = op0, op0 = 0;
1223       else if (TREE_CODE (op1) == INTEGER_CST || TREE_CODE (op1) == REAL_CST)
1224         *litp = op1, neg_litp_p = neg1_p, op1 = 0;
1225
1226       if (op0 != 0 && TREE_CONSTANT (op0))
1227         *conp = op0, op0 = 0;
1228       else if (op1 != 0 && TREE_CONSTANT (op1))
1229         *conp = op1, neg_conp_p = neg1_p, op1 = 0;
1230
1231       /* If we haven't dealt with either operand, this is not a case we can
1232          decompose.  Otherwise, VAR is either of the ones remaining, if any.  */
1233       if (op0 != 0 && op1 != 0)
1234         var = in;
1235       else if (op0 != 0)
1236         var = op0;
1237       else
1238         var = op1, neg_var_p = neg1_p;
1239
1240       /* Now do any needed negations.  */
1241       if (neg_litp_p)
1242         *minus_litp = *litp, *litp = 0;
1243       if (neg_conp_p)
1244         *conp = negate_expr (*conp);
1245       if (neg_var_p)
1246         var = negate_expr (var);
1247     }
1248   else if (TREE_CONSTANT (in))
1249     *conp = in;
1250   else
1251     var = in;
1252
1253   if (negate_p)
1254     {
1255       if (*litp)
1256         *minus_litp = *litp, *litp = 0;
1257       else if (*minus_litp)
1258         *litp = *minus_litp, *minus_litp = 0;
1259       *conp = negate_expr (*conp);
1260       var = negate_expr (var);
1261     }
1262
1263   return var;
1264 }
1265
1266 /* Re-associate trees split by the above function.  T1 and T2 are either
1267    expressions to associate or null.  Return the new expression, if any.  If
1268    we build an operation, do it in TYPE and with CODE.  */
1269
1270 static tree
1271 associate_trees (tree t1, tree t2, enum tree_code code, tree type)
1272 {
1273   if (t1 == 0)
1274     return t2;
1275   else if (t2 == 0)
1276     return t1;
1277
1278   /* If either input is CODE, a PLUS_EXPR, or a MINUS_EXPR, don't
1279      try to fold this since we will have infinite recursion.  But do
1280      deal with any NEGATE_EXPRs.  */
1281   if (TREE_CODE (t1) == code || TREE_CODE (t2) == code
1282       || TREE_CODE (t1) == MINUS_EXPR || TREE_CODE (t2) == MINUS_EXPR)
1283     {
1284       if (code == PLUS_EXPR)
1285         {
1286           if (TREE_CODE (t1) == NEGATE_EXPR)
1287             return build2 (MINUS_EXPR, type, fold_convert (type, t2),
1288                            fold_convert (type, TREE_OPERAND (t1, 0)));
1289           else if (TREE_CODE (t2) == NEGATE_EXPR)
1290             return build2 (MINUS_EXPR, type, fold_convert (type, t1),
1291                            fold_convert (type, TREE_OPERAND (t2, 0)));
1292           else if (integer_zerop (t2))
1293             return fold_convert (type, t1);
1294         }
1295       else if (code == MINUS_EXPR)
1296         {
1297           if (integer_zerop (t2))
1298             return fold_convert (type, t1);
1299         }
1300
1301       return build2 (code, type, fold_convert (type, t1),
1302                      fold_convert (type, t2));
1303     }
1304
1305   return fold_build2 (code, type, fold_convert (type, t1),
1306                       fold_convert (type, t2));
1307 }
1308 \f
1309 /* Combine two integer constants ARG1 and ARG2 under operation CODE
1310    to produce a new constant.
1311
1312    If NOTRUNC is nonzero, do not truncate the result to fit the data type.  */
1313
1314 tree
1315 int_const_binop (enum tree_code code, tree arg1, tree arg2, int notrunc)
1316 {
1317   unsigned HOST_WIDE_INT int1l, int2l;
1318   HOST_WIDE_INT int1h, int2h;
1319   unsigned HOST_WIDE_INT low;
1320   HOST_WIDE_INT hi;
1321   unsigned HOST_WIDE_INT garbagel;
1322   HOST_WIDE_INT garbageh;
1323   tree t;
1324   tree type = TREE_TYPE (arg1);
1325   int uns = TYPE_UNSIGNED (type);
1326   int is_sizetype
1327     = (TREE_CODE (type) == INTEGER_TYPE && TYPE_IS_SIZETYPE (type));
1328   int overflow = 0;
1329
1330   int1l = TREE_INT_CST_LOW (arg1);
1331   int1h = TREE_INT_CST_HIGH (arg1);
1332   int2l = TREE_INT_CST_LOW (arg2);
1333   int2h = TREE_INT_CST_HIGH (arg2);
1334
1335   switch (code)
1336     {
1337     case BIT_IOR_EXPR:
1338       low = int1l | int2l, hi = int1h | int2h;
1339       break;
1340
1341     case BIT_XOR_EXPR:
1342       low = int1l ^ int2l, hi = int1h ^ int2h;
1343       break;
1344
1345     case BIT_AND_EXPR:
1346       low = int1l & int2l, hi = int1h & int2h;
1347       break;
1348
1349     case RSHIFT_EXPR:
1350       int2l = -int2l;
1351     case LSHIFT_EXPR:
1352       /* It's unclear from the C standard whether shifts can overflow.
1353          The following code ignores overflow; perhaps a C standard
1354          interpretation ruling is needed.  */
1355       lshift_double (int1l, int1h, int2l, TYPE_PRECISION (type),
1356                      &low, &hi, !uns);
1357       break;
1358
1359     case RROTATE_EXPR:
1360       int2l = - int2l;
1361     case LROTATE_EXPR:
1362       lrotate_double (int1l, int1h, int2l, TYPE_PRECISION (type),
1363                       &low, &hi);
1364       break;
1365
1366     case PLUS_EXPR:
1367       overflow = add_double (int1l, int1h, int2l, int2h, &low, &hi);
1368       break;
1369
1370     case MINUS_EXPR:
1371       neg_double (int2l, int2h, &low, &hi);
1372       add_double (int1l, int1h, low, hi, &low, &hi);
1373       overflow = OVERFLOW_SUM_SIGN (hi, int2h, int1h);
1374       break;
1375
1376     case MULT_EXPR:
1377       overflow = mul_double (int1l, int1h, int2l, int2h, &low, &hi);
1378       break;
1379
1380     case TRUNC_DIV_EXPR:
1381     case FLOOR_DIV_EXPR: case CEIL_DIV_EXPR:
1382     case EXACT_DIV_EXPR:
1383       /* This is a shortcut for a common special case.  */
1384       if (int2h == 0 && (HOST_WIDE_INT) int2l > 0
1385           && ! TREE_CONSTANT_OVERFLOW (arg1)
1386           && ! TREE_CONSTANT_OVERFLOW (arg2)
1387           && int1h == 0 && (HOST_WIDE_INT) int1l >= 0)
1388         {
1389           if (code == CEIL_DIV_EXPR)
1390             int1l += int2l - 1;
1391
1392           low = int1l / int2l, hi = 0;
1393           break;
1394         }
1395
1396       /* ... fall through ...  */
1397
1398     case ROUND_DIV_EXPR:
1399       if (int2h == 0 && int2l == 1)
1400         {
1401           low = int1l, hi = int1h;
1402           break;
1403         }
1404       if (int1l == int2l && int1h == int2h
1405           && ! (int1l == 0 && int1h == 0))
1406         {
1407           low = 1, hi = 0;
1408           break;
1409         }
1410       overflow = div_and_round_double (code, uns, int1l, int1h, int2l, int2h,
1411                                        &low, &hi, &garbagel, &garbageh);
1412       break;
1413
1414     case TRUNC_MOD_EXPR:
1415     case FLOOR_MOD_EXPR: case CEIL_MOD_EXPR:
1416       /* This is a shortcut for a common special case.  */
1417       if (int2h == 0 && (HOST_WIDE_INT) int2l > 0
1418           && ! TREE_CONSTANT_OVERFLOW (arg1)
1419           && ! TREE_CONSTANT_OVERFLOW (arg2)
1420           && int1h == 0 && (HOST_WIDE_INT) int1l >= 0)
1421         {
1422           if (code == CEIL_MOD_EXPR)
1423             int1l += int2l - 1;
1424           low = int1l % int2l, hi = 0;
1425           break;
1426         }
1427
1428       /* ... fall through ...  */
1429
1430     case ROUND_MOD_EXPR:
1431       overflow = div_and_round_double (code, uns,
1432                                        int1l, int1h, int2l, int2h,
1433                                        &garbagel, &garbageh, &low, &hi);
1434       break;
1435
1436     case MIN_EXPR:
1437     case MAX_EXPR:
1438       if (uns)
1439         low = (((unsigned HOST_WIDE_INT) int1h
1440                 < (unsigned HOST_WIDE_INT) int2h)
1441                || (((unsigned HOST_WIDE_INT) int1h
1442                     == (unsigned HOST_WIDE_INT) int2h)
1443                    && int1l < int2l));
1444       else
1445         low = (int1h < int2h
1446                || (int1h == int2h && int1l < int2l));
1447
1448       if (low == (code == MIN_EXPR))
1449         low = int1l, hi = int1h;
1450       else
1451         low = int2l, hi = int2h;
1452       break;
1453
1454     default:
1455       gcc_unreachable ();
1456     }
1457
1458   t = build_int_cst_wide (TREE_TYPE (arg1), low, hi);
1459
1460   if (notrunc)
1461     {
1462       /* Propagate overflow flags ourselves.  */
1463       if (((!uns || is_sizetype) && overflow)
1464           | TREE_OVERFLOW (arg1) | TREE_OVERFLOW (arg2))
1465         {
1466           t = copy_node (t);
1467           TREE_OVERFLOW (t) = 1;
1468           TREE_CONSTANT_OVERFLOW (t) = 1;
1469         }
1470       else if (TREE_CONSTANT_OVERFLOW (arg1) | TREE_CONSTANT_OVERFLOW (arg2))
1471         {
1472           t = copy_node (t);
1473           TREE_CONSTANT_OVERFLOW (t) = 1;
1474         }
1475     }
1476   else
1477     t = force_fit_type (t, 1,
1478                         ((!uns || is_sizetype) && overflow)
1479                         | TREE_OVERFLOW (arg1) | TREE_OVERFLOW (arg2),
1480                         TREE_CONSTANT_OVERFLOW (arg1)
1481                         | TREE_CONSTANT_OVERFLOW (arg2));
1482
1483   return t;
1484 }
1485
1486 /* Combine two constants ARG1 and ARG2 under operation CODE to produce a new
1487    constant.  We assume ARG1 and ARG2 have the same data type, or at least
1488    are the same kind of constant and the same machine mode.
1489
1490    If NOTRUNC is nonzero, do not truncate the result to fit the data type.  */
1491
1492 static tree
1493 const_binop (enum tree_code code, tree arg1, tree arg2, int notrunc)
1494 {
1495   STRIP_NOPS (arg1);
1496   STRIP_NOPS (arg2);
1497
1498   if (TREE_CODE (arg1) == INTEGER_CST)
1499     return int_const_binop (code, arg1, arg2, notrunc);
1500
1501   if (TREE_CODE (arg1) == REAL_CST)
1502     {
1503       enum machine_mode mode;
1504       REAL_VALUE_TYPE d1;
1505       REAL_VALUE_TYPE d2;
1506       REAL_VALUE_TYPE value;
1507       REAL_VALUE_TYPE result;
1508       bool inexact;
1509       tree t, type;
1510
1511       d1 = TREE_REAL_CST (arg1);
1512       d2 = TREE_REAL_CST (arg2);
1513
1514       type = TREE_TYPE (arg1);
1515       mode = TYPE_MODE (type);
1516
1517       /* Don't perform operation if we honor signaling NaNs and
1518          either operand is a NaN.  */
1519       if (HONOR_SNANS (mode)
1520           && (REAL_VALUE_ISNAN (d1) || REAL_VALUE_ISNAN (d2)))
1521         return NULL_TREE;
1522
1523       /* Don't perform operation if it would raise a division
1524          by zero exception.  */
1525       if (code == RDIV_EXPR
1526           && REAL_VALUES_EQUAL (d2, dconst0)
1527           && (flag_trapping_math || ! MODE_HAS_INFINITIES (mode)))
1528         return NULL_TREE;
1529
1530       /* If either operand is a NaN, just return it.  Otherwise, set up
1531          for floating-point trap; we return an overflow.  */
1532       if (REAL_VALUE_ISNAN (d1))
1533         return arg1;
1534       else if (REAL_VALUE_ISNAN (d2))
1535         return arg2;
1536
1537       inexact = real_arithmetic (&value, code, &d1, &d2);
1538       real_convert (&result, mode, &value);
1539
1540       /* Don't constant fold this floating point operation if the
1541          result may dependent upon the run-time rounding mode and
1542          flag_rounding_math is set, or if GCC's software emulation
1543          is unable to accurately represent the result.  */
1544
1545       if ((flag_rounding_math
1546            || (REAL_MODE_FORMAT_COMPOSITE_P (mode)
1547                && !flag_unsafe_math_optimizations))
1548           && (inexact || !real_identical (&result, &value)))
1549         return NULL_TREE;
1550
1551       t = build_real (type, result);
1552
1553       TREE_OVERFLOW (t) = TREE_OVERFLOW (arg1) | TREE_OVERFLOW (arg2);
1554       TREE_CONSTANT_OVERFLOW (t)
1555         = TREE_OVERFLOW (t)
1556           | TREE_CONSTANT_OVERFLOW (arg1)
1557           | TREE_CONSTANT_OVERFLOW (arg2);
1558       return t;
1559     }
1560   if (TREE_CODE (arg1) == COMPLEX_CST)
1561     {
1562       tree type = TREE_TYPE (arg1);
1563       tree r1 = TREE_REALPART (arg1);
1564       tree i1 = TREE_IMAGPART (arg1);
1565       tree r2 = TREE_REALPART (arg2);
1566       tree i2 = TREE_IMAGPART (arg2);
1567       tree t;
1568
1569       switch (code)
1570         {
1571         case PLUS_EXPR:
1572           t = build_complex (type,
1573                              const_binop (PLUS_EXPR, r1, r2, notrunc),
1574                              const_binop (PLUS_EXPR, i1, i2, notrunc));
1575           break;
1576
1577         case MINUS_EXPR:
1578           t = build_complex (type,
1579                              const_binop (MINUS_EXPR, r1, r2, notrunc),
1580                              const_binop (MINUS_EXPR, i1, i2, notrunc));
1581           break;
1582
1583         case MULT_EXPR:
1584           t = build_complex (type,
1585                              const_binop (MINUS_EXPR,
1586                                           const_binop (MULT_EXPR,
1587                                                        r1, r2, notrunc),
1588                                           const_binop (MULT_EXPR,
1589                                                        i1, i2, notrunc),
1590                                           notrunc),
1591                              const_binop (PLUS_EXPR,
1592                                           const_binop (MULT_EXPR,
1593                                                        r1, i2, notrunc),
1594                                           const_binop (MULT_EXPR,
1595                                                        i1, r2, notrunc),
1596                                           notrunc));
1597           break;
1598
1599         case RDIV_EXPR:
1600           {
1601             tree t1, t2, real, imag;
1602             tree magsquared
1603               = const_binop (PLUS_EXPR,
1604                              const_binop (MULT_EXPR, r2, r2, notrunc),
1605                              const_binop (MULT_EXPR, i2, i2, notrunc),
1606                              notrunc);
1607
1608             t1 = const_binop (PLUS_EXPR,
1609                               const_binop (MULT_EXPR, r1, r2, notrunc),
1610                               const_binop (MULT_EXPR, i1, i2, notrunc),
1611                               notrunc);
1612             t2 = const_binop (MINUS_EXPR,
1613                               const_binop (MULT_EXPR, i1, r2, notrunc),
1614                               const_binop (MULT_EXPR, r1, i2, notrunc),
1615                               notrunc);
1616
1617             if (INTEGRAL_TYPE_P (TREE_TYPE (r1)))
1618               {
1619                 real = const_binop (TRUNC_DIV_EXPR, t1, magsquared, notrunc);
1620                 imag = const_binop (TRUNC_DIV_EXPR, t2, magsquared, notrunc);
1621               }
1622             else
1623               {
1624                 real = const_binop (RDIV_EXPR, t1, magsquared, notrunc);
1625                 imag = const_binop (RDIV_EXPR, t2, magsquared, notrunc);
1626                 if (!real || !imag)
1627                   return NULL_TREE;
1628               }
1629
1630             t = build_complex (type, real, imag);
1631           }
1632           break;
1633
1634         default:
1635           gcc_unreachable ();
1636         }
1637       return t;
1638     }
1639   return 0;
1640 }
1641
1642 /* Create a size type INT_CST node with NUMBER sign extended.  KIND
1643    indicates which particular sizetype to create.  */
1644
1645 tree
1646 size_int_kind (HOST_WIDE_INT number, enum size_type_kind kind)
1647 {
1648   return build_int_cst (sizetype_tab[(int) kind], number);
1649 }
1650 \f
1651 /* Combine operands OP1 and OP2 with arithmetic operation CODE.  CODE
1652    is a tree code.  The type of the result is taken from the operands.
1653    Both must be the same type integer type and it must be a size type.
1654    If the operands are constant, so is the result.  */
1655
1656 tree
1657 size_binop (enum tree_code code, tree arg0, tree arg1)
1658 {
1659   tree type = TREE_TYPE (arg0);
1660
1661   gcc_assert (TREE_CODE (type) == INTEGER_TYPE && TYPE_IS_SIZETYPE (type)
1662               && type == TREE_TYPE (arg1));
1663
1664   /* Handle the special case of two integer constants faster.  */
1665   if (TREE_CODE (arg0) == INTEGER_CST && TREE_CODE (arg1) == INTEGER_CST)
1666     {
1667       /* And some specific cases even faster than that.  */
1668       if (code == PLUS_EXPR && integer_zerop (arg0))
1669         return arg1;
1670       else if ((code == MINUS_EXPR || code == PLUS_EXPR)
1671                && integer_zerop (arg1))
1672         return arg0;
1673       else if (code == MULT_EXPR && integer_onep (arg0))
1674         return arg1;
1675
1676       /* Handle general case of two integer constants.  */
1677       return int_const_binop (code, arg0, arg1, 0);
1678     }
1679
1680   if (arg0 == error_mark_node || arg1 == error_mark_node)
1681     return error_mark_node;
1682
1683   return fold_build2 (code, type, arg0, arg1);
1684 }
1685
1686 /* Given two values, either both of sizetype or both of bitsizetype,
1687    compute the difference between the two values.  Return the value
1688    in signed type corresponding to the type of the operands.  */
1689
1690 tree
1691 size_diffop (tree arg0, tree arg1)
1692 {
1693   tree type = TREE_TYPE (arg0);
1694   tree ctype;
1695
1696   gcc_assert (TREE_CODE (type) == INTEGER_TYPE && TYPE_IS_SIZETYPE (type)
1697               && type == TREE_TYPE (arg1));
1698
1699   /* If the type is already signed, just do the simple thing.  */
1700   if (!TYPE_UNSIGNED (type))
1701     return size_binop (MINUS_EXPR, arg0, arg1);
1702
1703   ctype = type == bitsizetype ? sbitsizetype : ssizetype;
1704
1705   /* If either operand is not a constant, do the conversions to the signed
1706      type and subtract.  The hardware will do the right thing with any
1707      overflow in the subtraction.  */
1708   if (TREE_CODE (arg0) != INTEGER_CST || TREE_CODE (arg1) != INTEGER_CST)
1709     return size_binop (MINUS_EXPR, fold_convert (ctype, arg0),
1710                        fold_convert (ctype, arg1));
1711
1712   /* If ARG0 is larger than ARG1, subtract and return the result in CTYPE.
1713      Otherwise, subtract the other way, convert to CTYPE (we know that can't
1714      overflow) and negate (which can't either).  Special-case a result
1715      of zero while we're here.  */
1716   if (tree_int_cst_equal (arg0, arg1))
1717     return fold_convert (ctype, integer_zero_node);
1718   else if (tree_int_cst_lt (arg1, arg0))
1719     return fold_convert (ctype, size_binop (MINUS_EXPR, arg0, arg1));
1720   else
1721     return size_binop (MINUS_EXPR, fold_convert (ctype, integer_zero_node),
1722                        fold_convert (ctype, size_binop (MINUS_EXPR,
1723                                                         arg1, arg0)));
1724 }
1725 \f
1726 /* A subroutine of fold_convert_const handling conversions of an
1727    INTEGER_CST to another integer type.  */
1728
1729 static tree
1730 fold_convert_const_int_from_int (tree type, tree arg1)
1731 {
1732   tree t;
1733
1734   /* Given an integer constant, make new constant with new type,
1735      appropriately sign-extended or truncated.  */
1736   t = build_int_cst_wide (type, TREE_INT_CST_LOW (arg1),
1737                           TREE_INT_CST_HIGH (arg1));
1738
1739   t = force_fit_type (t,
1740                       /* Don't set the overflow when
1741                          converting a pointer  */
1742                       !POINTER_TYPE_P (TREE_TYPE (arg1)),
1743                       (TREE_INT_CST_HIGH (arg1) < 0
1744                        && (TYPE_UNSIGNED (type)
1745                            < TYPE_UNSIGNED (TREE_TYPE (arg1))))
1746                       | TREE_OVERFLOW (arg1),
1747                       TREE_CONSTANT_OVERFLOW (arg1));
1748
1749   return t;
1750 }
1751
1752 /* A subroutine of fold_convert_const handling conversions a REAL_CST
1753    to an integer type.  */
1754
1755 static tree
1756 fold_convert_const_int_from_real (enum tree_code code, tree type, tree arg1)
1757 {
1758   int overflow = 0;
1759   tree t;
1760
1761   /* The following code implements the floating point to integer
1762      conversion rules required by the Java Language Specification,
1763      that IEEE NaNs are mapped to zero and values that overflow
1764      the target precision saturate, i.e. values greater than
1765      INT_MAX are mapped to INT_MAX, and values less than INT_MIN
1766      are mapped to INT_MIN.  These semantics are allowed by the
1767      C and C++ standards that simply state that the behavior of
1768      FP-to-integer conversion is unspecified upon overflow.  */
1769
1770   HOST_WIDE_INT high, low;
1771   REAL_VALUE_TYPE r;
1772   REAL_VALUE_TYPE x = TREE_REAL_CST (arg1);
1773
1774   switch (code)
1775     {
1776     case FIX_TRUNC_EXPR:
1777       real_trunc (&r, VOIDmode, &x);
1778       break;
1779
1780     case FIX_CEIL_EXPR:
1781       real_ceil (&r, VOIDmode, &x);
1782       break;
1783
1784     case FIX_FLOOR_EXPR:
1785       real_floor (&r, VOIDmode, &x);
1786       break;
1787
1788     case FIX_ROUND_EXPR:
1789       real_round (&r, VOIDmode, &x);
1790       break;
1791
1792     default:
1793       gcc_unreachable ();
1794     }
1795
1796   /* If R is NaN, return zero and show we have an overflow.  */
1797   if (REAL_VALUE_ISNAN (r))
1798     {
1799       overflow = 1;
1800       high = 0;
1801       low = 0;
1802     }
1803
1804   /* See if R is less than the lower bound or greater than the
1805      upper bound.  */
1806
1807   if (! overflow)
1808     {
1809       tree lt = TYPE_MIN_VALUE (type);
1810       REAL_VALUE_TYPE l = real_value_from_int_cst (NULL_TREE, lt);
1811       if (REAL_VALUES_LESS (r, l))
1812         {
1813           overflow = 1;
1814           high = TREE_INT_CST_HIGH (lt);
1815           low = TREE_INT_CST_LOW (lt);
1816         }
1817     }
1818
1819   if (! overflow)
1820     {
1821       tree ut = TYPE_MAX_VALUE (type);
1822       if (ut)
1823         {
1824           REAL_VALUE_TYPE u = real_value_from_int_cst (NULL_TREE, ut);
1825           if (REAL_VALUES_LESS (u, r))
1826             {
1827               overflow = 1;
1828               high = TREE_INT_CST_HIGH (ut);
1829               low = TREE_INT_CST_LOW (ut);
1830             }
1831         }
1832     }
1833
1834   if (! overflow)
1835     REAL_VALUE_TO_INT (&low, &high, r);
1836
1837   t = build_int_cst_wide (type, low, high);
1838
1839   t = force_fit_type (t, -1, overflow | TREE_OVERFLOW (arg1),
1840                       TREE_CONSTANT_OVERFLOW (arg1));
1841   return t;
1842 }
1843
1844 /* A subroutine of fold_convert_const handling conversions a REAL_CST
1845    to another floating point type.  */
1846
1847 static tree
1848 fold_convert_const_real_from_real (tree type, tree arg1)
1849 {
1850   REAL_VALUE_TYPE value;
1851   tree t;
1852
1853   real_convert (&value, TYPE_MODE (type), &TREE_REAL_CST (arg1));
1854   t = build_real (type, value);
1855
1856   TREE_OVERFLOW (t) = TREE_OVERFLOW (arg1);
1857   TREE_CONSTANT_OVERFLOW (t)
1858     = TREE_OVERFLOW (t) | TREE_CONSTANT_OVERFLOW (arg1);
1859   return t;
1860 }
1861
1862 /* Attempt to fold type conversion operation CODE of expression ARG1 to
1863    type TYPE.  If no simplification can be done return NULL_TREE.  */
1864
1865 static tree
1866 fold_convert_const (enum tree_code code, tree type, tree arg1)
1867 {
1868   if (TREE_TYPE (arg1) == type)
1869     return arg1;
1870
1871   if (POINTER_TYPE_P (type) || INTEGRAL_TYPE_P (type))
1872     {
1873       if (TREE_CODE (arg1) == INTEGER_CST)
1874         return fold_convert_const_int_from_int (type, arg1);
1875       else if (TREE_CODE (arg1) == REAL_CST)
1876         return fold_convert_const_int_from_real (code, type, arg1);
1877     }
1878   else if (TREE_CODE (type) == REAL_TYPE)
1879     {
1880       if (TREE_CODE (arg1) == INTEGER_CST)
1881         return build_real_from_int_cst (type, arg1);
1882       if (TREE_CODE (arg1) == REAL_CST)
1883         return fold_convert_const_real_from_real (type, arg1);
1884     }
1885   return NULL_TREE;
1886 }
1887
1888 /* Construct a vector of zero elements of vector type TYPE.  */
1889
1890 static tree
1891 build_zero_vector (tree type)
1892 {
1893   tree elem, list;
1894   int i, units;
1895
1896   elem = fold_convert_const (NOP_EXPR, TREE_TYPE (type), integer_zero_node);
1897   units = TYPE_VECTOR_SUBPARTS (type);
1898
1899   list = NULL_TREE;
1900   for (i = 0; i < units; i++)
1901     list = tree_cons (NULL_TREE, elem, list);
1902   return build_vector (type, list);
1903 }
1904
1905 /* Convert expression ARG to type TYPE.  Used by the middle-end for
1906    simple conversions in preference to calling the front-end's convert.  */
1907
1908 tree
1909 fold_convert (tree type, tree arg)
1910 {
1911   tree orig = TREE_TYPE (arg);
1912   tree tem;
1913
1914   if (type == orig)
1915     return arg;
1916
1917   if (TREE_CODE (arg) == ERROR_MARK
1918       || TREE_CODE (type) == ERROR_MARK
1919       || TREE_CODE (orig) == ERROR_MARK)
1920     return error_mark_node;
1921
1922   if (TYPE_MAIN_VARIANT (type) == TYPE_MAIN_VARIANT (orig)
1923       || lang_hooks.types_compatible_p (TYPE_MAIN_VARIANT (type),
1924                                         TYPE_MAIN_VARIANT (orig)))
1925     return fold_build1 (NOP_EXPR, type, arg);
1926
1927   switch (TREE_CODE (type))
1928     {
1929     case INTEGER_TYPE: case CHAR_TYPE: case ENUMERAL_TYPE: case BOOLEAN_TYPE:
1930     case POINTER_TYPE: case REFERENCE_TYPE:
1931     case OFFSET_TYPE:
1932       if (TREE_CODE (arg) == INTEGER_CST)
1933         {
1934           tem = fold_convert_const (NOP_EXPR, type, arg);
1935           if (tem != NULL_TREE)
1936             return tem;
1937         }
1938       if (INTEGRAL_TYPE_P (orig) || POINTER_TYPE_P (orig)
1939           || TREE_CODE (orig) == OFFSET_TYPE)
1940         return fold_build1 (NOP_EXPR, type, arg);
1941       if (TREE_CODE (orig) == COMPLEX_TYPE)
1942         {
1943           tem = fold_build1 (REALPART_EXPR, TREE_TYPE (orig), arg);
1944           return fold_convert (type, tem);
1945         }
1946       gcc_assert (TREE_CODE (orig) == VECTOR_TYPE
1947                   && tree_int_cst_equal (TYPE_SIZE (type), TYPE_SIZE (orig)));
1948       return fold_build1 (NOP_EXPR, type, arg);
1949
1950     case REAL_TYPE:
1951       if (TREE_CODE (arg) == INTEGER_CST)
1952         {
1953           tem = fold_convert_const (FLOAT_EXPR, type, arg);
1954           if (tem != NULL_TREE)
1955             return tem;
1956         }
1957       else if (TREE_CODE (arg) == REAL_CST)
1958         {
1959           tem = fold_convert_const (NOP_EXPR, type, arg);
1960           if (tem != NULL_TREE)
1961             return tem;
1962         }
1963
1964       switch (TREE_CODE (orig))
1965         {
1966         case INTEGER_TYPE: case CHAR_TYPE:
1967         case BOOLEAN_TYPE: case ENUMERAL_TYPE:
1968         case POINTER_TYPE: case REFERENCE_TYPE:
1969           return fold_build1 (FLOAT_EXPR, type, arg);
1970
1971         case REAL_TYPE:
1972           return fold_build1 (flag_float_store ? CONVERT_EXPR : NOP_EXPR,
1973                               type, arg);
1974
1975         case COMPLEX_TYPE:
1976           tem = fold_build1 (REALPART_EXPR, TREE_TYPE (orig), arg);
1977           return fold_convert (type, tem);
1978
1979         default:
1980           gcc_unreachable ();
1981         }
1982
1983     case COMPLEX_TYPE:
1984       switch (TREE_CODE (orig))
1985         {
1986         case INTEGER_TYPE: case CHAR_TYPE:
1987         case BOOLEAN_TYPE: case ENUMERAL_TYPE:
1988         case POINTER_TYPE: case REFERENCE_TYPE:
1989         case REAL_TYPE:
1990           return build2 (COMPLEX_EXPR, type,
1991                          fold_convert (TREE_TYPE (type), arg),
1992                          fold_convert (TREE_TYPE (type), integer_zero_node));
1993         case COMPLEX_TYPE:
1994           {
1995             tree rpart, ipart;
1996
1997             if (TREE_CODE (arg) == COMPLEX_EXPR)
1998               {
1999                 rpart = fold_convert (TREE_TYPE (type), TREE_OPERAND (arg, 0));
2000                 ipart = fold_convert (TREE_TYPE (type), TREE_OPERAND (arg, 1));
2001                 return fold_build2 (COMPLEX_EXPR, type, rpart, ipart);
2002               }
2003
2004             arg = save_expr (arg);
2005             rpart = fold_build1 (REALPART_EXPR, TREE_TYPE (orig), arg);
2006             ipart = fold_build1 (IMAGPART_EXPR, TREE_TYPE (orig), arg);
2007             rpart = fold_convert (TREE_TYPE (type), rpart);
2008             ipart = fold_convert (TREE_TYPE (type), ipart);
2009             return fold_build2 (COMPLEX_EXPR, type, rpart, ipart);
2010           }
2011
2012         default:
2013           gcc_unreachable ();
2014         }
2015
2016     case VECTOR_TYPE:
2017       if (integer_zerop (arg))
2018         return build_zero_vector (type);
2019       gcc_assert (tree_int_cst_equal (TYPE_SIZE (type), TYPE_SIZE (orig)));
2020       gcc_assert (INTEGRAL_TYPE_P (orig) || POINTER_TYPE_P (orig)
2021                   || TREE_CODE (orig) == VECTOR_TYPE);
2022       return fold_build1 (NOP_EXPR, type, arg);
2023
2024     case VOID_TYPE:
2025       return fold_build1 (CONVERT_EXPR, type, fold_ignored_result (arg));
2026
2027     default:
2028       gcc_unreachable ();
2029     }
2030 }
2031 \f
2032 /* Return false if expr can be assumed not to be an lvalue, true
2033    otherwise.  */
2034
2035 static bool
2036 maybe_lvalue_p (tree x)
2037 {
2038   /* We only need to wrap lvalue tree codes.  */
2039   switch (TREE_CODE (x))
2040   {
2041   case VAR_DECL:
2042   case PARM_DECL:
2043   case RESULT_DECL:
2044   case LABEL_DECL:
2045   case FUNCTION_DECL:
2046   case SSA_NAME:
2047
2048   case COMPONENT_REF:
2049   case INDIRECT_REF:
2050   case ALIGN_INDIRECT_REF:
2051   case MISALIGNED_INDIRECT_REF:
2052   case ARRAY_REF:
2053   case ARRAY_RANGE_REF:
2054   case BIT_FIELD_REF:
2055   case OBJ_TYPE_REF:
2056
2057   case REALPART_EXPR:
2058   case IMAGPART_EXPR:
2059   case PREINCREMENT_EXPR:
2060   case PREDECREMENT_EXPR:
2061   case SAVE_EXPR:
2062   case TRY_CATCH_EXPR:
2063   case WITH_CLEANUP_EXPR:
2064   case COMPOUND_EXPR:
2065   case MODIFY_EXPR:
2066   case TARGET_EXPR:
2067   case COND_EXPR:
2068   case BIND_EXPR:
2069   case MIN_EXPR:
2070   case MAX_EXPR:
2071     break;
2072
2073   default:
2074     /* Assume the worst for front-end tree codes.  */
2075     if ((int)TREE_CODE (x) >= NUM_TREE_CODES)
2076       break;
2077     return false;
2078   }
2079
2080   return true;
2081 }
2082
2083 /* Return an expr equal to X but certainly not valid as an lvalue.  */
2084
2085 tree
2086 non_lvalue (tree x)
2087 {
2088   /* While we are in GIMPLE, NON_LVALUE_EXPR doesn't mean anything to
2089      us.  */
2090   if (in_gimple_form)
2091     return x;
2092
2093   if (! maybe_lvalue_p (x))
2094     return x;
2095   return build1 (NON_LVALUE_EXPR, TREE_TYPE (x), x);
2096 }
2097
2098 /* Nonzero means lvalues are limited to those valid in pedantic ANSI C.
2099    Zero means allow extended lvalues.  */
2100
2101 int pedantic_lvalues;
2102
2103 /* When pedantic, return an expr equal to X but certainly not valid as a
2104    pedantic lvalue.  Otherwise, return X.  */
2105
2106 static tree
2107 pedantic_non_lvalue (tree x)
2108 {
2109   if (pedantic_lvalues)
2110     return non_lvalue (x);
2111   else
2112     return x;
2113 }
2114 \f
2115 /* Given a tree comparison code, return the code that is the logical inverse
2116    of the given code.  It is not safe to do this for floating-point
2117    comparisons, except for NE_EXPR and EQ_EXPR, so we receive a machine mode
2118    as well: if reversing the comparison is unsafe, return ERROR_MARK.  */
2119
2120 enum tree_code
2121 invert_tree_comparison (enum tree_code code, bool honor_nans)
2122 {
2123   if (honor_nans && flag_trapping_math)
2124     return ERROR_MARK;
2125
2126   switch (code)
2127     {
2128     case EQ_EXPR:
2129       return NE_EXPR;
2130     case NE_EXPR:
2131       return EQ_EXPR;
2132     case GT_EXPR:
2133       return honor_nans ? UNLE_EXPR : LE_EXPR;
2134     case GE_EXPR:
2135       return honor_nans ? UNLT_EXPR : LT_EXPR;
2136     case LT_EXPR:
2137       return honor_nans ? UNGE_EXPR : GE_EXPR;
2138     case LE_EXPR:
2139       return honor_nans ? UNGT_EXPR : GT_EXPR;
2140     case LTGT_EXPR:
2141       return UNEQ_EXPR;
2142     case UNEQ_EXPR:
2143       return LTGT_EXPR;
2144     case UNGT_EXPR:
2145       return LE_EXPR;
2146     case UNGE_EXPR:
2147       return LT_EXPR;
2148     case UNLT_EXPR:
2149       return GE_EXPR;
2150     case UNLE_EXPR:
2151       return GT_EXPR;
2152     case ORDERED_EXPR:
2153       return UNORDERED_EXPR;
2154     case UNORDERED_EXPR:
2155       return ORDERED_EXPR;
2156     default:
2157       gcc_unreachable ();
2158     }
2159 }
2160
2161 /* Similar, but return the comparison that results if the operands are
2162    swapped.  This is safe for floating-point.  */
2163
2164 enum tree_code
2165 swap_tree_comparison (enum tree_code code)
2166 {
2167   switch (code)
2168     {
2169     case EQ_EXPR:
2170     case NE_EXPR:
2171     case ORDERED_EXPR:
2172     case UNORDERED_EXPR:
2173     case LTGT_EXPR:
2174     case UNEQ_EXPR:
2175       return code;
2176     case GT_EXPR:
2177       return LT_EXPR;
2178     case GE_EXPR:
2179       return LE_EXPR;
2180     case LT_EXPR:
2181       return GT_EXPR;
2182     case LE_EXPR:
2183       return GE_EXPR;
2184     case UNGT_EXPR:
2185       return UNLT_EXPR;
2186     case UNGE_EXPR:
2187       return UNLE_EXPR;
2188     case UNLT_EXPR:
2189       return UNGT_EXPR;
2190     case UNLE_EXPR:
2191       return UNGE_EXPR;
2192     default:
2193       gcc_unreachable ();
2194     }
2195 }
2196
2197
2198 /* Convert a comparison tree code from an enum tree_code representation
2199    into a compcode bit-based encoding.  This function is the inverse of
2200    compcode_to_comparison.  */
2201
2202 static enum comparison_code
2203 comparison_to_compcode (enum tree_code code)
2204 {
2205   switch (code)
2206     {
2207     case LT_EXPR:
2208       return COMPCODE_LT;
2209     case EQ_EXPR:
2210       return COMPCODE_EQ;
2211     case LE_EXPR:
2212       return COMPCODE_LE;
2213     case GT_EXPR:
2214       return COMPCODE_GT;
2215     case NE_EXPR:
2216       return COMPCODE_NE;
2217     case GE_EXPR:
2218       return COMPCODE_GE;
2219     case ORDERED_EXPR:
2220       return COMPCODE_ORD;
2221     case UNORDERED_EXPR:
2222       return COMPCODE_UNORD;
2223     case UNLT_EXPR:
2224       return COMPCODE_UNLT;
2225     case UNEQ_EXPR:
2226       return COMPCODE_UNEQ;
2227     case UNLE_EXPR:
2228       return COMPCODE_UNLE;
2229     case UNGT_EXPR:
2230       return COMPCODE_UNGT;
2231     case LTGT_EXPR:
2232       return COMPCODE_LTGT;
2233     case UNGE_EXPR:
2234       return COMPCODE_UNGE;
2235     default:
2236       gcc_unreachable ();
2237     }
2238 }
2239
2240 /* Convert a compcode bit-based encoding of a comparison operator back
2241    to GCC's enum tree_code representation.  This function is the
2242    inverse of comparison_to_compcode.  */
2243
2244 static enum tree_code
2245 compcode_to_comparison (enum comparison_code code)
2246 {
2247   switch (code)
2248     {
2249     case COMPCODE_LT:
2250       return LT_EXPR;
2251     case COMPCODE_EQ:
2252       return EQ_EXPR;
2253     case COMPCODE_LE:
2254       return LE_EXPR;
2255     case COMPCODE_GT:
2256       return GT_EXPR;
2257     case COMPCODE_NE:
2258       return NE_EXPR;
2259     case COMPCODE_GE:
2260       return GE_EXPR;
2261     case COMPCODE_ORD:
2262       return ORDERED_EXPR;
2263     case COMPCODE_UNORD:
2264       return UNORDERED_EXPR;
2265     case COMPCODE_UNLT:
2266       return UNLT_EXPR;
2267     case COMPCODE_UNEQ:
2268       return UNEQ_EXPR;
2269     case COMPCODE_UNLE:
2270       return UNLE_EXPR;
2271     case COMPCODE_UNGT:
2272       return UNGT_EXPR;
2273     case COMPCODE_LTGT:
2274       return LTGT_EXPR;
2275     case COMPCODE_UNGE:
2276       return UNGE_EXPR;
2277     default:
2278       gcc_unreachable ();
2279     }
2280 }
2281
2282 /* Return a tree for the comparison which is the combination of
2283    doing the AND or OR (depending on CODE) of the two operations LCODE
2284    and RCODE on the identical operands LL_ARG and LR_ARG.  Take into account
2285    the possibility of trapping if the mode has NaNs, and return NULL_TREE
2286    if this makes the transformation invalid.  */
2287
2288 tree
2289 combine_comparisons (enum tree_code code, enum tree_code lcode,
2290                      enum tree_code rcode, tree truth_type,
2291                      tree ll_arg, tree lr_arg)
2292 {
2293   bool honor_nans = HONOR_NANS (TYPE_MODE (TREE_TYPE (ll_arg)));
2294   enum comparison_code lcompcode = comparison_to_compcode (lcode);
2295   enum comparison_code rcompcode = comparison_to_compcode (rcode);
2296   enum comparison_code compcode;
2297
2298   switch (code)
2299     {
2300     case TRUTH_AND_EXPR: case TRUTH_ANDIF_EXPR:
2301       compcode = lcompcode & rcompcode;
2302       break;
2303
2304     case TRUTH_OR_EXPR: case TRUTH_ORIF_EXPR:
2305       compcode = lcompcode | rcompcode;
2306       break;
2307
2308     default:
2309       return NULL_TREE;
2310     }
2311
2312   if (!honor_nans)
2313     {
2314       /* Eliminate unordered comparisons, as well as LTGT and ORD
2315          which are not used unless the mode has NaNs.  */
2316       compcode &= ~COMPCODE_UNORD;
2317       if (compcode == COMPCODE_LTGT)
2318         compcode = COMPCODE_NE;
2319       else if (compcode == COMPCODE_ORD)
2320         compcode = COMPCODE_TRUE;
2321     }
2322    else if (flag_trapping_math)
2323      {
2324         /* Check that the original operation and the optimized ones will trap
2325            under the same condition.  */
2326         bool ltrap = (lcompcode & COMPCODE_UNORD) == 0
2327                      && (lcompcode != COMPCODE_EQ)
2328                      && (lcompcode != COMPCODE_ORD);
2329         bool rtrap = (rcompcode & COMPCODE_UNORD) == 0
2330                      && (rcompcode != COMPCODE_EQ)
2331                      && (rcompcode != COMPCODE_ORD);
2332         bool trap = (compcode & COMPCODE_UNORD) == 0
2333                     && (compcode != COMPCODE_EQ)
2334                     && (compcode != COMPCODE_ORD);
2335
2336         /* In a short-circuited boolean expression the LHS might be
2337            such that the RHS, if evaluated, will never trap.  For
2338            example, in ORD (x, y) && (x < y), we evaluate the RHS only
2339            if neither x nor y is NaN.  (This is a mixed blessing: for
2340            example, the expression above will never trap, hence
2341            optimizing it to x < y would be invalid).  */
2342         if ((code == TRUTH_ORIF_EXPR && (lcompcode & COMPCODE_UNORD))
2343             || (code == TRUTH_ANDIF_EXPR && !(lcompcode & COMPCODE_UNORD)))
2344           rtrap = false;
2345
2346         /* If the comparison was short-circuited, and only the RHS
2347            trapped, we may now generate a spurious trap.  */
2348         if (rtrap && !ltrap
2349             && (code == TRUTH_ANDIF_EXPR || code == TRUTH_ORIF_EXPR))
2350           return NULL_TREE;
2351
2352         /* If we changed the conditions that cause a trap, we lose.  */
2353         if ((ltrap || rtrap) != trap)
2354           return NULL_TREE;
2355       }
2356
2357   if (compcode == COMPCODE_TRUE)
2358     return constant_boolean_node (true, truth_type);
2359   else if (compcode == COMPCODE_FALSE)
2360     return constant_boolean_node (false, truth_type);
2361   else
2362     return fold_build2 (compcode_to_comparison (compcode),
2363                         truth_type, ll_arg, lr_arg);
2364 }
2365
2366 /* Return nonzero if CODE is a tree code that represents a truth value.  */
2367
2368 static int
2369 truth_value_p (enum tree_code code)
2370 {
2371   return (TREE_CODE_CLASS (code) == tcc_comparison
2372           || code == TRUTH_AND_EXPR || code == TRUTH_ANDIF_EXPR
2373           || code == TRUTH_OR_EXPR || code == TRUTH_ORIF_EXPR
2374           || code == TRUTH_XOR_EXPR || code == TRUTH_NOT_EXPR);
2375 }
2376 \f
2377 /* Return nonzero if two operands (typically of the same tree node)
2378    are necessarily equal.  If either argument has side-effects this
2379    function returns zero.  FLAGS modifies behavior as follows:
2380
2381    If OEP_ONLY_CONST is set, only return nonzero for constants.
2382    This function tests whether the operands are indistinguishable;
2383    it does not test whether they are equal using C's == operation.
2384    The distinction is important for IEEE floating point, because
2385    (1) -0.0 and 0.0 are distinguishable, but -0.0==0.0, and
2386    (2) two NaNs may be indistinguishable, but NaN!=NaN.
2387
2388    If OEP_ONLY_CONST is unset, a VAR_DECL is considered equal to itself
2389    even though it may hold multiple values during a function.
2390    This is because a GCC tree node guarantees that nothing else is
2391    executed between the evaluation of its "operands" (which may often
2392    be evaluated in arbitrary order).  Hence if the operands themselves
2393    don't side-effect, the VAR_DECLs, PARM_DECLs etc... must hold the
2394    same value in each operand/subexpression.  Hence leaving OEP_ONLY_CONST
2395    unset means assuming isochronic (or instantaneous) tree equivalence.
2396    Unless comparing arbitrary expression trees, such as from different
2397    statements, this flag can usually be left unset.
2398
2399    If OEP_PURE_SAME is set, then pure functions with identical arguments
2400    are considered the same.  It is used when the caller has other ways
2401    to ensure that global memory is unchanged in between.  */
2402
2403 int
2404 operand_equal_p (tree arg0, tree arg1, unsigned int flags)
2405 {
2406   /* If either is ERROR_MARK, they aren't equal.  */
2407   if (TREE_CODE (arg0) == ERROR_MARK || TREE_CODE (arg1) == ERROR_MARK)
2408     return 0;
2409
2410   /* If both types don't have the same signedness, then we can't consider
2411      them equal.  We must check this before the STRIP_NOPS calls
2412      because they may change the signedness of the arguments.  */
2413   if (TYPE_UNSIGNED (TREE_TYPE (arg0)) != TYPE_UNSIGNED (TREE_TYPE (arg1)))
2414     return 0;
2415
2416   STRIP_NOPS (arg0);
2417   STRIP_NOPS (arg1);
2418
2419   if (TREE_CODE (arg0) != TREE_CODE (arg1)
2420       /* This is needed for conversions and for COMPONENT_REF.
2421          Might as well play it safe and always test this.  */
2422       || TREE_CODE (TREE_TYPE (arg0)) == ERROR_MARK
2423       || TREE_CODE (TREE_TYPE (arg1)) == ERROR_MARK
2424       || TYPE_MODE (TREE_TYPE (arg0)) != TYPE_MODE (TREE_TYPE (arg1)))
2425     return 0;
2426
2427   /* If ARG0 and ARG1 are the same SAVE_EXPR, they are necessarily equal.
2428      We don't care about side effects in that case because the SAVE_EXPR
2429      takes care of that for us. In all other cases, two expressions are
2430      equal if they have no side effects.  If we have two identical
2431      expressions with side effects that should be treated the same due
2432      to the only side effects being identical SAVE_EXPR's, that will
2433      be detected in the recursive calls below.  */
2434   if (arg0 == arg1 && ! (flags & OEP_ONLY_CONST)
2435       && (TREE_CODE (arg0) == SAVE_EXPR
2436           || (! TREE_SIDE_EFFECTS (arg0) && ! TREE_SIDE_EFFECTS (arg1))))
2437     return 1;
2438
2439   /* Next handle constant cases, those for which we can return 1 even
2440      if ONLY_CONST is set.  */
2441   if (TREE_CONSTANT (arg0) && TREE_CONSTANT (arg1))
2442     switch (TREE_CODE (arg0))
2443       {
2444       case INTEGER_CST:
2445         return (! TREE_CONSTANT_OVERFLOW (arg0)
2446                 && ! TREE_CONSTANT_OVERFLOW (arg1)
2447                 && tree_int_cst_equal (arg0, arg1));
2448
2449       case REAL_CST:
2450         return (! TREE_CONSTANT_OVERFLOW (arg0)
2451                 && ! TREE_CONSTANT_OVERFLOW (arg1)
2452                 && REAL_VALUES_IDENTICAL (TREE_REAL_CST (arg0),
2453                                           TREE_REAL_CST (arg1)));
2454
2455       case VECTOR_CST:
2456         {
2457           tree v1, v2;
2458
2459           if (TREE_CONSTANT_OVERFLOW (arg0)
2460               || TREE_CONSTANT_OVERFLOW (arg1))
2461             return 0;
2462
2463           v1 = TREE_VECTOR_CST_ELTS (arg0);
2464           v2 = TREE_VECTOR_CST_ELTS (arg1);
2465           while (v1 && v2)
2466             {
2467               if (!operand_equal_p (TREE_VALUE (v1), TREE_VALUE (v2),
2468                                     flags))
2469                 return 0;
2470               v1 = TREE_CHAIN (v1);
2471               v2 = TREE_CHAIN (v2);
2472             }
2473
2474           return v1 == v2;
2475         }
2476
2477       case COMPLEX_CST:
2478         return (operand_equal_p (TREE_REALPART (arg0), TREE_REALPART (arg1),
2479                                  flags)
2480                 && operand_equal_p (TREE_IMAGPART (arg0), TREE_IMAGPART (arg1),
2481                                     flags));
2482
2483       case STRING_CST:
2484         return (TREE_STRING_LENGTH (arg0) == TREE_STRING_LENGTH (arg1)
2485                 && ! memcmp (TREE_STRING_POINTER (arg0),
2486                               TREE_STRING_POINTER (arg1),
2487                               TREE_STRING_LENGTH (arg0)));
2488
2489       case ADDR_EXPR:
2490         return operand_equal_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg1, 0),
2491                                 0);
2492       default:
2493         break;
2494       }
2495
2496   if (flags & OEP_ONLY_CONST)
2497     return 0;
2498
2499 /* Define macros to test an operand from arg0 and arg1 for equality and a
2500    variant that allows null and views null as being different from any
2501    non-null value.  In the latter case, if either is null, the both
2502    must be; otherwise, do the normal comparison.  */
2503 #define OP_SAME(N) operand_equal_p (TREE_OPERAND (arg0, N),     \
2504                                     TREE_OPERAND (arg1, N), flags)
2505
2506 #define OP_SAME_WITH_NULL(N)                            \
2507   ((!TREE_OPERAND (arg0, N) || !TREE_OPERAND (arg1, N)) \
2508    ? TREE_OPERAND (arg0, N) == TREE_OPERAND (arg1, N) : OP_SAME (N))
2509
2510   switch (TREE_CODE_CLASS (TREE_CODE (arg0)))
2511     {
2512     case tcc_unary:
2513       /* Two conversions are equal only if signedness and modes match.  */
2514       switch (TREE_CODE (arg0))
2515         {
2516         case NOP_EXPR:
2517         case CONVERT_EXPR:
2518         case FIX_CEIL_EXPR:
2519         case FIX_TRUNC_EXPR:
2520         case FIX_FLOOR_EXPR:
2521         case FIX_ROUND_EXPR:
2522           if (TYPE_UNSIGNED (TREE_TYPE (arg0))
2523               != TYPE_UNSIGNED (TREE_TYPE (arg1)))
2524             return 0;
2525           break;
2526         default:
2527           break;
2528         }
2529
2530       return OP_SAME (0);
2531
2532
2533     case tcc_comparison:
2534     case tcc_binary:
2535       if (OP_SAME (0) && OP_SAME (1))
2536         return 1;
2537
2538       /* For commutative ops, allow the other order.  */
2539       return (commutative_tree_code (TREE_CODE (arg0))
2540               && operand_equal_p (TREE_OPERAND (arg0, 0),
2541                                   TREE_OPERAND (arg1, 1), flags)
2542               && operand_equal_p (TREE_OPERAND (arg0, 1),
2543                                   TREE_OPERAND (arg1, 0), flags));
2544
2545     case tcc_reference:
2546       /* If either of the pointer (or reference) expressions we are
2547          dereferencing contain a side effect, these cannot be equal.  */
2548       if (TREE_SIDE_EFFECTS (arg0)
2549           || TREE_SIDE_EFFECTS (arg1))
2550         return 0;
2551
2552       switch (TREE_CODE (arg0))
2553         {
2554         case INDIRECT_REF:
2555         case ALIGN_INDIRECT_REF:
2556         case MISALIGNED_INDIRECT_REF:
2557         case REALPART_EXPR:
2558         case IMAGPART_EXPR:
2559           return OP_SAME (0);
2560
2561         case ARRAY_REF:
2562         case ARRAY_RANGE_REF:
2563           /* Operands 2 and 3 may be null.  */
2564           return (OP_SAME (0)
2565                   && OP_SAME (1)
2566                   && OP_SAME_WITH_NULL (2)
2567                   && OP_SAME_WITH_NULL (3));
2568
2569         case COMPONENT_REF:
2570           /* Handle operand 2 the same as for ARRAY_REF.  */
2571           return OP_SAME (0) && OP_SAME (1) && OP_SAME_WITH_NULL (2);
2572
2573         case BIT_FIELD_REF:
2574           return OP_SAME (0) && OP_SAME (1) && OP_SAME (2);
2575
2576         default:
2577           return 0;
2578         }
2579
2580     case tcc_expression:
2581       switch (TREE_CODE (arg0))
2582         {
2583         case ADDR_EXPR:
2584         case TRUTH_NOT_EXPR:
2585           return OP_SAME (0);
2586
2587         case TRUTH_ANDIF_EXPR:
2588         case TRUTH_ORIF_EXPR:
2589           return OP_SAME (0) && OP_SAME (1);
2590
2591         case TRUTH_AND_EXPR:
2592         case TRUTH_OR_EXPR:
2593         case TRUTH_XOR_EXPR:
2594           if (OP_SAME (0) && OP_SAME (1))
2595             return 1;
2596
2597           /* Otherwise take into account this is a commutative operation.  */
2598           return (operand_equal_p (TREE_OPERAND (arg0, 0),
2599                                    TREE_OPERAND (arg1, 1), flags)
2600                   && operand_equal_p (TREE_OPERAND (arg0, 1),
2601                                       TREE_OPERAND (arg1, 0), flags));
2602
2603         case CALL_EXPR:
2604           /* If the CALL_EXPRs call different functions, then they
2605              clearly can not be equal.  */
2606           if (!OP_SAME (0))
2607             return 0;
2608
2609           {
2610             unsigned int cef = call_expr_flags (arg0);
2611             if (flags & OEP_PURE_SAME)
2612               cef &= ECF_CONST | ECF_PURE;
2613             else
2614               cef &= ECF_CONST;
2615             if (!cef)
2616               return 0;
2617           }
2618
2619           /* Now see if all the arguments are the same.  operand_equal_p
2620              does not handle TREE_LIST, so we walk the operands here
2621              feeding them to operand_equal_p.  */
2622           arg0 = TREE_OPERAND (arg0, 1);
2623           arg1 = TREE_OPERAND (arg1, 1);
2624           while (arg0 && arg1)
2625             {
2626               if (! operand_equal_p (TREE_VALUE (arg0), TREE_VALUE (arg1),
2627                                      flags))
2628                 return 0;
2629
2630               arg0 = TREE_CHAIN (arg0);
2631               arg1 = TREE_CHAIN (arg1);
2632             }
2633
2634           /* If we get here and both argument lists are exhausted
2635              then the CALL_EXPRs are equal.  */
2636           return ! (arg0 || arg1);
2637
2638         default:
2639           return 0;
2640         }
2641
2642     case tcc_declaration:
2643       /* Consider __builtin_sqrt equal to sqrt.  */
2644       return (TREE_CODE (arg0) == FUNCTION_DECL
2645               && DECL_BUILT_IN (arg0) && DECL_BUILT_IN (arg1)
2646               && DECL_BUILT_IN_CLASS (arg0) == DECL_BUILT_IN_CLASS (arg1)
2647               && DECL_FUNCTION_CODE (arg0) == DECL_FUNCTION_CODE (arg1));
2648
2649     default:
2650       return 0;
2651     }
2652
2653 #undef OP_SAME
2654 #undef OP_SAME_WITH_NULL
2655 }
2656 \f
2657 /* Similar to operand_equal_p, but see if ARG0 might have been made by
2658    shorten_compare from ARG1 when ARG1 was being compared with OTHER.
2659
2660    When in doubt, return 0.  */
2661
2662 static int
2663 operand_equal_for_comparison_p (tree arg0, tree arg1, tree other)
2664 {
2665   int unsignedp1, unsignedpo;
2666   tree primarg0, primarg1, primother;
2667   unsigned int correct_width;
2668
2669   if (operand_equal_p (arg0, arg1, 0))
2670     return 1;
2671
2672   if (! INTEGRAL_TYPE_P (TREE_TYPE (arg0))
2673       || ! INTEGRAL_TYPE_P (TREE_TYPE (arg1)))
2674     return 0;
2675
2676   /* Discard any conversions that don't change the modes of ARG0 and ARG1
2677      and see if the inner values are the same.  This removes any
2678      signedness comparison, which doesn't matter here.  */
2679   primarg0 = arg0, primarg1 = arg1;
2680   STRIP_NOPS (primarg0);
2681   STRIP_NOPS (primarg1);
2682   if (operand_equal_p (primarg0, primarg1, 0))
2683     return 1;
2684
2685   /* Duplicate what shorten_compare does to ARG1 and see if that gives the
2686      actual comparison operand, ARG0.
2687
2688      First throw away any conversions to wider types
2689      already present in the operands.  */
2690
2691   primarg1 = get_narrower (arg1, &unsignedp1);
2692   primother = get_narrower (other, &unsignedpo);
2693
2694   correct_width = TYPE_PRECISION (TREE_TYPE (arg1));
2695   if (unsignedp1 == unsignedpo
2696       && TYPE_PRECISION (TREE_TYPE (primarg1)) < correct_width
2697       && TYPE_PRECISION (TREE_TYPE (primother)) < correct_width)
2698     {
2699       tree type = TREE_TYPE (arg0);
2700
2701       /* Make sure shorter operand is extended the right way
2702          to match the longer operand.  */
2703       primarg1 = fold_convert (lang_hooks.types.signed_or_unsigned_type
2704                                (unsignedp1, TREE_TYPE (primarg1)), primarg1);
2705
2706       if (operand_equal_p (arg0, fold_convert (type, primarg1), 0))
2707         return 1;
2708     }
2709
2710   return 0;
2711 }
2712 \f
2713 /* See if ARG is an expression that is either a comparison or is performing
2714    arithmetic on comparisons.  The comparisons must only be comparing
2715    two different values, which will be stored in *CVAL1 and *CVAL2; if
2716    they are nonzero it means that some operands have already been found.
2717    No variables may be used anywhere else in the expression except in the
2718    comparisons.  If SAVE_P is true it means we removed a SAVE_EXPR around
2719    the expression and save_expr needs to be called with CVAL1 and CVAL2.
2720
2721    If this is true, return 1.  Otherwise, return zero.  */
2722
2723 static int
2724 twoval_comparison_p (tree arg, tree *cval1, tree *cval2, int *save_p)
2725 {
2726   enum tree_code code = TREE_CODE (arg);
2727   enum tree_code_class class = TREE_CODE_CLASS (code);
2728
2729   /* We can handle some of the tcc_expression cases here.  */
2730   if (class == tcc_expression && code == TRUTH_NOT_EXPR)
2731     class = tcc_unary;
2732   else if (class == tcc_expression
2733            && (code == TRUTH_ANDIF_EXPR || code == TRUTH_ORIF_EXPR
2734                || code == COMPOUND_EXPR))
2735     class = tcc_binary;
2736
2737   else if (class == tcc_expression && code == SAVE_EXPR
2738            && ! TREE_SIDE_EFFECTS (TREE_OPERAND (arg, 0)))
2739     {
2740       /* If we've already found a CVAL1 or CVAL2, this expression is
2741          two complex to handle.  */
2742       if (*cval1 || *cval2)
2743         return 0;
2744
2745       class = tcc_unary;
2746       *save_p = 1;
2747     }
2748
2749   switch (class)
2750     {
2751     case tcc_unary:
2752       return twoval_comparison_p (TREE_OPERAND (arg, 0), cval1, cval2, save_p);
2753
2754     case tcc_binary:
2755       return (twoval_comparison_p (TREE_OPERAND (arg, 0), cval1, cval2, save_p)
2756               && twoval_comparison_p (TREE_OPERAND (arg, 1),
2757                                       cval1, cval2, save_p));
2758
2759     case tcc_constant:
2760       return 1;
2761
2762     case tcc_expression:
2763       if (code == COND_EXPR)
2764         return (twoval_comparison_p (TREE_OPERAND (arg, 0),
2765                                      cval1, cval2, save_p)
2766                 && twoval_comparison_p (TREE_OPERAND (arg, 1),
2767                                         cval1, cval2, save_p)
2768                 && twoval_comparison_p (TREE_OPERAND (arg, 2),
2769                                         cval1, cval2, save_p));
2770       return 0;
2771
2772     case tcc_comparison:
2773       /* First see if we can handle the first operand, then the second.  For
2774          the second operand, we know *CVAL1 can't be zero.  It must be that
2775          one side of the comparison is each of the values; test for the
2776          case where this isn't true by failing if the two operands
2777          are the same.  */
2778
2779       if (operand_equal_p (TREE_OPERAND (arg, 0),
2780                            TREE_OPERAND (arg, 1), 0))
2781         return 0;
2782
2783       if (*cval1 == 0)
2784         *cval1 = TREE_OPERAND (arg, 0);
2785       else if (operand_equal_p (*cval1, TREE_OPERAND (arg, 0), 0))
2786         ;
2787       else if (*cval2 == 0)
2788         *cval2 = TREE_OPERAND (arg, 0);
2789       else if (operand_equal_p (*cval2, TREE_OPERAND (arg, 0), 0))
2790         ;
2791       else
2792         return 0;
2793
2794       if (operand_equal_p (*cval1, TREE_OPERAND (arg, 1), 0))
2795         ;
2796       else if (*cval2 == 0)
2797         *cval2 = TREE_OPERAND (arg, 1);
2798       else if (operand_equal_p (*cval2, TREE_OPERAND (arg, 1), 0))
2799         ;
2800       else
2801         return 0;
2802
2803       return 1;
2804
2805     default:
2806       return 0;
2807     }
2808 }
2809 \f
2810 /* ARG is a tree that is known to contain just arithmetic operations and
2811    comparisons.  Evaluate the operations in the tree substituting NEW0 for
2812    any occurrence of OLD0 as an operand of a comparison and likewise for
2813    NEW1 and OLD1.  */
2814
2815 static tree
2816 eval_subst (tree arg, tree old0, tree new0, tree old1, tree new1)
2817 {
2818   tree type = TREE_TYPE (arg);
2819   enum tree_code code = TREE_CODE (arg);
2820   enum tree_code_class class = TREE_CODE_CLASS (code);
2821
2822   /* We can handle some of the tcc_expression cases here.  */
2823   if (class == tcc_expression && code == TRUTH_NOT_EXPR)
2824     class = tcc_unary;
2825   else if (class == tcc_expression
2826            && (code == TRUTH_ANDIF_EXPR || code == TRUTH_ORIF_EXPR))
2827     class = tcc_binary;
2828
2829   switch (class)
2830     {
2831     case tcc_unary:
2832       return fold_build1 (code, type,
2833                           eval_subst (TREE_OPERAND (arg, 0),
2834                                       old0, new0, old1, new1));
2835
2836     case tcc_binary:
2837       return fold_build2 (code, type,
2838                           eval_subst (TREE_OPERAND (arg, 0),
2839                                       old0, new0, old1, new1),
2840                           eval_subst (TREE_OPERAND (arg, 1),
2841                                       old0, new0, old1, new1));
2842
2843     case tcc_expression:
2844       switch (code)
2845         {
2846         case SAVE_EXPR:
2847           return eval_subst (TREE_OPERAND (arg, 0), old0, new0, old1, new1);
2848
2849         case COMPOUND_EXPR:
2850           return eval_subst (TREE_OPERAND (arg, 1), old0, new0, old1, new1);
2851
2852         case COND_EXPR:
2853           return fold_build3 (code, type,
2854                               eval_subst (TREE_OPERAND (arg, 0),
2855                                           old0, new0, old1, new1),
2856                               eval_subst (TREE_OPERAND (arg, 1),
2857                                           old0, new0, old1, new1),
2858                               eval_subst (TREE_OPERAND (arg, 2),
2859                                           old0, new0, old1, new1));
2860         default:
2861           break;
2862         }
2863       /* Fall through - ???  */
2864
2865     case tcc_comparison:
2866       {
2867         tree arg0 = TREE_OPERAND (arg, 0);
2868         tree arg1 = TREE_OPERAND (arg, 1);
2869
2870         /* We need to check both for exact equality and tree equality.  The
2871            former will be true if the operand has a side-effect.  In that
2872            case, we know the operand occurred exactly once.  */
2873
2874         if (arg0 == old0 || operand_equal_p (arg0, old0, 0))
2875           arg0 = new0;
2876         else if (arg0 == old1 || operand_equal_p (arg0, old1, 0))
2877           arg0 = new1;
2878
2879         if (arg1 == old0 || operand_equal_p (arg1, old0, 0))
2880           arg1 = new0;
2881         else if (arg1 == old1 || operand_equal_p (arg1, old1, 0))
2882           arg1 = new1;
2883
2884         return fold_build2 (code, type, arg0, arg1);
2885       }
2886
2887     default:
2888       return arg;
2889     }
2890 }
2891 \f
2892 /* Return a tree for the case when the result of an expression is RESULT
2893    converted to TYPE and OMITTED was previously an operand of the expression
2894    but is now not needed (e.g., we folded OMITTED * 0).
2895
2896    If OMITTED has side effects, we must evaluate it.  Otherwise, just do
2897    the conversion of RESULT to TYPE.  */
2898
2899 tree
2900 omit_one_operand (tree type, tree result, tree omitted)
2901 {
2902   tree t = fold_convert (type, result);
2903
2904   if (TREE_SIDE_EFFECTS (omitted))
2905     return build2 (COMPOUND_EXPR, type, fold_ignored_result (omitted), t);
2906
2907   return non_lvalue (t);
2908 }
2909
2910 /* Similar, but call pedantic_non_lvalue instead of non_lvalue.  */
2911
2912 static tree
2913 pedantic_omit_one_operand (tree type, tree result, tree omitted)
2914 {
2915   tree t = fold_convert (type, result);
2916
2917   if (TREE_SIDE_EFFECTS (omitted))
2918     return build2 (COMPOUND_EXPR, type, fold_ignored_result (omitted), t);
2919
2920   return pedantic_non_lvalue (t);
2921 }
2922
2923 /* Return a tree for the case when the result of an expression is RESULT
2924    converted to TYPE and OMITTED1 and OMITTED2 were previously operands
2925    of the expression but are now not needed.
2926
2927    If OMITTED1 or OMITTED2 has side effects, they must be evaluated.
2928    If both OMITTED1 and OMITTED2 have side effects, OMITTED1 is
2929    evaluated before OMITTED2.  Otherwise, if neither has side effects,
2930    just do the conversion of RESULT to TYPE.  */
2931
2932 tree
2933 omit_two_operands (tree type, tree result, tree omitted1, tree omitted2)
2934 {
2935   tree t = fold_convert (type, result);
2936
2937   if (TREE_SIDE_EFFECTS (omitted2))
2938     t = build2 (COMPOUND_EXPR, type, omitted2, t);
2939   if (TREE_SIDE_EFFECTS (omitted1))
2940     t = build2 (COMPOUND_EXPR, type, omitted1, t);
2941
2942   return TREE_CODE (t) != COMPOUND_EXPR ? non_lvalue (t) : t;
2943 }
2944
2945 \f
2946 /* Return a simplified tree node for the truth-negation of ARG.  This
2947    never alters ARG itself.  We assume that ARG is an operation that
2948    returns a truth value (0 or 1).
2949
2950    FIXME: one would think we would fold the result, but it causes
2951    problems with the dominator optimizer.  */
2952 tree
2953 invert_truthvalue (tree arg)
2954 {
2955   tree type = TREE_TYPE (arg);
2956   enum tree_code code = TREE_CODE (arg);
2957
2958   if (code == ERROR_MARK)
2959     return arg;
2960
2961   /* If this is a comparison, we can simply invert it, except for
2962      floating-point non-equality comparisons, in which case we just
2963      enclose a TRUTH_NOT_EXPR around what we have.  */
2964
2965   if (TREE_CODE_CLASS (code) == tcc_comparison)
2966     {
2967       tree op_type = TREE_TYPE (TREE_OPERAND (arg, 0));
2968       if (FLOAT_TYPE_P (op_type)
2969           && flag_trapping_math
2970           && code != ORDERED_EXPR && code != UNORDERED_EXPR
2971           && code != NE_EXPR && code != EQ_EXPR)
2972         return build1 (TRUTH_NOT_EXPR, type, arg);
2973       else
2974         {
2975           code = invert_tree_comparison (code,
2976                                          HONOR_NANS (TYPE_MODE (op_type)));
2977           if (code == ERROR_MARK)
2978             return build1 (TRUTH_NOT_EXPR, type, arg);
2979           else
2980             return build2 (code, type,
2981                            TREE_OPERAND (arg, 0), TREE_OPERAND (arg, 1));
2982         }
2983     }
2984
2985   switch (code)
2986     {
2987     case INTEGER_CST:
2988       return constant_boolean_node (integer_zerop (arg), type);
2989
2990     case TRUTH_AND_EXPR:
2991       return build2 (TRUTH_OR_EXPR, type,
2992                      invert_truthvalue (TREE_OPERAND (arg, 0)),
2993                      invert_truthvalue (TREE_OPERAND (arg, 1)));
2994
2995     case TRUTH_OR_EXPR:
2996       return build2 (TRUTH_AND_EXPR, type,
2997                      invert_truthvalue (TREE_OPERAND (arg, 0)),
2998                      invert_truthvalue (TREE_OPERAND (arg, 1)));
2999
3000     case TRUTH_XOR_EXPR:
3001       /* Here we can invert either operand.  We invert the first operand
3002          unless the second operand is a TRUTH_NOT_EXPR in which case our
3003          result is the XOR of the first operand with the inside of the
3004          negation of the second operand.  */
3005
3006       if (TREE_CODE (TREE_OPERAND (arg, 1)) == TRUTH_NOT_EXPR)
3007         return build2 (TRUTH_XOR_EXPR, type, TREE_OPERAND (arg, 0),
3008                        TREE_OPERAND (TREE_OPERAND (arg, 1), 0));
3009       else
3010         return build2 (TRUTH_XOR_EXPR, type,
3011                        invert_truthvalue (TREE_OPERAND (arg, 0)),
3012                        TREE_OPERAND (arg, 1));
3013
3014     case TRUTH_ANDIF_EXPR:
3015       return build2 (TRUTH_ORIF_EXPR, type,
3016                      invert_truthvalue (TREE_OPERAND (arg, 0)),
3017                      invert_truthvalue (TREE_OPERAND (arg, 1)));
3018
3019     case TRUTH_ORIF_EXPR:
3020       return build2 (TRUTH_ANDIF_EXPR, type,
3021                      invert_truthvalue (TREE_OPERAND (arg, 0)),
3022                      invert_truthvalue (TREE_OPERAND (arg, 1)));
3023
3024     case TRUTH_NOT_EXPR:
3025       return TREE_OPERAND (arg, 0);
3026
3027     case COND_EXPR:
3028       return build3 (COND_EXPR, type, TREE_OPERAND (arg, 0),
3029                      invert_truthvalue (TREE_OPERAND (arg, 1)),
3030                      invert_truthvalue (TREE_OPERAND (arg, 2)));
3031
3032     case COMPOUND_EXPR:
3033       return build2 (COMPOUND_EXPR, type, TREE_OPERAND (arg, 0),
3034                      invert_truthvalue (TREE_OPERAND (arg, 1)));
3035
3036     case NON_LVALUE_EXPR:
3037       return invert_truthvalue (TREE_OPERAND (arg, 0));
3038
3039     case NOP_EXPR:
3040       if (TREE_CODE (TREE_TYPE (arg)) == BOOLEAN_TYPE)
3041         break;
3042
3043     case CONVERT_EXPR:
3044     case FLOAT_EXPR:
3045       return build1 (TREE_CODE (arg), type,
3046                      invert_truthvalue (TREE_OPERAND (arg, 0)));
3047
3048     case BIT_AND_EXPR:
3049       if (!integer_onep (TREE_OPERAND (arg, 1)))
3050         break;
3051       return build2 (EQ_EXPR, type, arg,
3052                      fold_convert (type, integer_zero_node));
3053
3054     case SAVE_EXPR:
3055       return build1 (TRUTH_NOT_EXPR, type, arg);
3056
3057     case CLEANUP_POINT_EXPR:
3058       return build1 (CLEANUP_POINT_EXPR, type,
3059                      invert_truthvalue (TREE_OPERAND (arg, 0)));
3060
3061     default:
3062       break;
3063     }
3064   gcc_assert (TREE_CODE (TREE_TYPE (arg)) == BOOLEAN_TYPE);
3065   return build1 (TRUTH_NOT_EXPR, type, arg);
3066 }
3067
3068 /* Given a bit-wise operation CODE applied to ARG0 and ARG1, see if both
3069    operands are another bit-wise operation with a common input.  If so,
3070    distribute the bit operations to save an operation and possibly two if
3071    constants are involved.  For example, convert
3072         (A | B) & (A | C) into A | (B & C)
3073    Further simplification will occur if B and C are constants.
3074
3075    If this optimization cannot be done, 0 will be returned.  */
3076
3077 static tree
3078 distribute_bit_expr (enum tree_code code, tree type, tree arg0, tree arg1)
3079 {
3080   tree common;
3081   tree left, right;
3082
3083   if (TREE_CODE (arg0) != TREE_CODE (arg1)
3084       || TREE_CODE (arg0) == code
3085       || (TREE_CODE (arg0) != BIT_AND_EXPR
3086           && TREE_CODE (arg0) != BIT_IOR_EXPR))
3087     return 0;
3088
3089   if (operand_equal_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg1, 0), 0))
3090     {
3091       common = TREE_OPERAND (arg0, 0);
3092       left = TREE_OPERAND (arg0, 1);
3093       right = TREE_OPERAND (arg1, 1);
3094     }
3095   else if (operand_equal_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg1, 1), 0))
3096     {
3097       common = TREE_OPERAND (arg0, 0);
3098       left = TREE_OPERAND (arg0, 1);
3099       right = TREE_OPERAND (arg1, 0);
3100     }
3101   else if (operand_equal_p (TREE_OPERAND (arg0, 1), TREE_OPERAND (arg1, 0), 0))
3102     {
3103       common = TREE_OPERAND (arg0, 1);
3104       left = TREE_OPERAND (arg0, 0);
3105       right = TREE_OPERAND (arg1, 1);
3106     }
3107   else if (operand_equal_p (TREE_OPERAND (arg0, 1), TREE_OPERAND (arg1, 1), 0))
3108     {
3109       common = TREE_OPERAND (arg0, 1);
3110       left = TREE_OPERAND (arg0, 0);
3111       right = TREE_OPERAND (arg1, 0);
3112     }
3113   else
3114     return 0;
3115
3116   return fold_build2 (TREE_CODE (arg0), type, common,
3117                       fold_build2 (code, type, left, right));
3118 }
3119
3120 /* Knowing that ARG0 and ARG1 are both RDIV_EXPRs, simplify a binary operation
3121    with code CODE.  This optimization is unsafe.  */
3122 static tree
3123 distribute_real_division (enum tree_code code, tree type, tree arg0, tree arg1)
3124 {
3125   bool mul0 = TREE_CODE (arg0) == MULT_EXPR;
3126   bool mul1 = TREE_CODE (arg1) == MULT_EXPR;
3127
3128   /* (A / C) +- (B / C) -> (A +- B) / C.  */
3129   if (mul0 == mul1
3130       && operand_equal_p (TREE_OPERAND (arg0, 1),
3131                        TREE_OPERAND (arg1, 1), 0))
3132     return fold_build2 (mul0 ? MULT_EXPR : RDIV_EXPR, type,
3133                         fold_build2 (code, type,
3134                                      TREE_OPERAND (arg0, 0),
3135                                      TREE_OPERAND (arg1, 0)),
3136                         TREE_OPERAND (arg0, 1));
3137
3138   /* (A / C1) +- (A / C2) -> A * (1 / C1 +- 1 / C2).  */
3139   if (operand_equal_p (TREE_OPERAND (arg0, 0),
3140                        TREE_OPERAND (arg1, 0), 0)
3141       && TREE_CODE (TREE_OPERAND (arg0, 1)) == REAL_CST
3142       && TREE_CODE (TREE_OPERAND (arg1, 1)) == REAL_CST)
3143     {
3144       REAL_VALUE_TYPE r0, r1;
3145       r0 = TREE_REAL_CST (TREE_OPERAND (arg0, 1));
3146       r1 = TREE_REAL_CST (TREE_OPERAND (arg1, 1));
3147       if (!mul0)
3148         real_arithmetic (&r0, RDIV_EXPR, &dconst1, &r0);
3149       if (!mul1)
3150         real_arithmetic (&r1, RDIV_EXPR, &dconst1, &r1);
3151       real_arithmetic (&r0, code, &r0, &r1);
3152       return fold_build2 (MULT_EXPR, type,
3153                           TREE_OPERAND (arg0, 0),
3154                           build_real (type, r0));
3155     }
3156
3157   return NULL_TREE;
3158 }
3159 \f
3160 /* Return a BIT_FIELD_REF of type TYPE to refer to BITSIZE bits of INNER
3161    starting at BITPOS.  The field is unsigned if UNSIGNEDP is nonzero.  */
3162
3163 static tree
3164 make_bit_field_ref (tree inner, tree type, int bitsize, int bitpos,
3165                     int unsignedp)
3166 {
3167   tree result;
3168
3169   if (bitpos == 0)
3170     {
3171       tree size = TYPE_SIZE (TREE_TYPE (inner));
3172       if ((INTEGRAL_TYPE_P (TREE_TYPE (inner))
3173            || POINTER_TYPE_P (TREE_TYPE (inner)))
3174           && host_integerp (size, 0)
3175           && tree_low_cst (size, 0) == bitsize)
3176         return fold_convert (type, inner);
3177     }
3178
3179   result = build3 (BIT_FIELD_REF, type, inner,
3180                    size_int (bitsize), bitsize_int (bitpos));
3181
3182   BIT_FIELD_REF_UNSIGNED (result) = unsignedp;
3183
3184   return result;
3185 }
3186
3187 /* Optimize a bit-field compare.
3188
3189    There are two cases:  First is a compare against a constant and the
3190    second is a comparison of two items where the fields are at the same
3191    bit position relative to the start of a chunk (byte, halfword, word)
3192    large enough to contain it.  In these cases we can avoid the shift
3193    implicit in bitfield extractions.
3194
3195    For constants, we emit a compare of the shifted constant with the
3196    BIT_AND_EXPR of a mask and a byte, halfword, or word of the operand being
3197    compared.  For two fields at the same position, we do the ANDs with the
3198    similar mask and compare the result of the ANDs.
3199
3200    CODE is the comparison code, known to be either NE_EXPR or EQ_EXPR.
3201    COMPARE_TYPE is the type of the comparison, and LHS and RHS
3202    are the left and right operands of the comparison, respectively.
3203
3204    If the optimization described above can be done, we return the resulting
3205    tree.  Otherwise we return zero.  */
3206
3207 static tree
3208 optimize_bit_field_compare (enum tree_code code, tree compare_type,
3209                             tree lhs, tree rhs)
3210 {
3211   HOST_WIDE_INT lbitpos, lbitsize, rbitpos, rbitsize, nbitpos, nbitsize;
3212   tree type = TREE_TYPE (lhs);
3213   tree signed_type, unsigned_type;
3214   int const_p = TREE_CODE (rhs) == INTEGER_CST;
3215   enum machine_mode lmode, rmode, nmode;
3216   int lunsignedp, runsignedp;
3217   int lvolatilep = 0, rvolatilep = 0;
3218   tree linner, rinner = NULL_TREE;
3219   tree mask;
3220   tree offset;
3221
3222   /* Get all the information about the extractions being done.  If the bit size
3223      if the same as the size of the underlying object, we aren't doing an
3224      extraction at all and so can do nothing.  We also don't want to
3225      do anything if the inner expression is a PLACEHOLDER_EXPR since we
3226      then will no longer be able to replace it.  */
3227   linner = get_inner_reference (lhs, &lbitsize, &lbitpos, &offset, &lmode,
3228                                 &lunsignedp, &lvolatilep, false);
3229   if (linner == lhs || lbitsize == GET_MODE_BITSIZE (lmode) || lbitsize < 0
3230       || offset != 0 || TREE_CODE (linner) == PLACEHOLDER_EXPR)
3231     return 0;
3232
3233  if (!const_p)
3234    {
3235      /* If this is not a constant, we can only do something if bit positions,
3236         sizes, and signedness are the same.  */
3237      rinner = get_inner_reference (rhs, &rbitsize, &rbitpos, &offset, &rmode,
3238                                    &runsignedp, &rvolatilep, false);
3239
3240      if (rinner == rhs || lbitpos != rbitpos || lbitsize != rbitsize
3241          || lunsignedp != runsignedp || offset != 0
3242          || TREE_CODE (rinner) == PLACEHOLDER_EXPR)
3243        return 0;
3244    }
3245
3246   /* See if we can find a mode to refer to this field.  We should be able to,
3247      but fail if we can't.  */
3248   nmode = get_best_mode (lbitsize, lbitpos,
3249                          const_p ? TYPE_ALIGN (TREE_TYPE (linner))
3250                          : MIN (TYPE_ALIGN (TREE_TYPE (linner)),
3251                                 TYPE_ALIGN (TREE_TYPE (rinner))),
3252                          word_mode, lvolatilep || rvolatilep);
3253   if (nmode == VOIDmode)
3254     return 0;
3255
3256   /* Set signed and unsigned types of the precision of this mode for the
3257      shifts below.  */
3258   signed_type = lang_hooks.types.type_for_mode (nmode, 0);
3259   unsigned_type = lang_hooks.types.type_for_mode (nmode, 1);
3260
3261   /* Compute the bit position and size for the new reference and our offset
3262      within it. If the new reference is the same size as the original, we
3263      won't optimize anything, so return zero.  */
3264   nbitsize = GET_MODE_BITSIZE (nmode);
3265   nbitpos = lbitpos & ~ (nbitsize - 1);
3266   lbitpos -= nbitpos;
3267   if (nbitsize == lbitsize)
3268     return 0;
3269
3270   if (BYTES_BIG_ENDIAN)
3271     lbitpos = nbitsize - lbitsize - lbitpos;
3272
3273   /* Make the mask to be used against the extracted field.  */
3274   mask = build_int_cst (unsigned_type, -1);
3275   mask = force_fit_type (mask, 0, false, false);
3276   mask = fold_convert (unsigned_type, mask);
3277   mask = const_binop (LSHIFT_EXPR, mask, size_int (nbitsize - lbitsize), 0);
3278   mask = const_binop (RSHIFT_EXPR, mask,
3279                       size_int (nbitsize - lbitsize - lbitpos), 0);
3280
3281   if (! const_p)
3282     /* If not comparing with constant, just rework the comparison
3283        and return.  */
3284     return build2 (code, compare_type,
3285                    build2 (BIT_AND_EXPR, unsigned_type,
3286                            make_bit_field_ref (linner, unsigned_type,
3287                                                nbitsize, nbitpos, 1),
3288                            mask),
3289                    build2 (BIT_AND_EXPR, unsigned_type,
3290                            make_bit_field_ref (rinner, unsigned_type,
3291                                                nbitsize, nbitpos, 1),
3292                            mask));
3293
3294   /* Otherwise, we are handling the constant case. See if the constant is too
3295      big for the field.  Warn and return a tree of for 0 (false) if so.  We do
3296      this not only for its own sake, but to avoid having to test for this
3297      error case below.  If we didn't, we might generate wrong code.
3298
3299      For unsigned fields, the constant shifted right by the field length should
3300      be all zero.  For signed fields, the high-order bits should agree with
3301      the sign bit.  */
3302
3303   if (lunsignedp)
3304     {
3305       if (! integer_zerop (const_binop (RSHIFT_EXPR,
3306                                         fold_convert (unsigned_type, rhs),
3307                                         size_int (lbitsize), 0)))
3308         {
3309           warning (0, "comparison is always %d due to width of bit-field",
3310                    code == NE_EXPR);
3311           return constant_boolean_node (code == NE_EXPR, compare_type);
3312         }
3313     }
3314   else
3315     {
3316       tree tem = const_binop (RSHIFT_EXPR, fold_convert (signed_type, rhs),
3317                               size_int (lbitsize - 1), 0);
3318       if (! integer_zerop (tem) && ! integer_all_onesp (tem))
3319         {
3320           warning (0, "comparison is always %d due to width of bit-field",
3321                    code == NE_EXPR);
3322           return constant_boolean_node (code == NE_EXPR, compare_type);
3323         }
3324     }
3325
3326   /* Single-bit compares should always be against zero.  */
3327   if (lbitsize == 1 && ! integer_zerop (rhs))
3328     {
3329       code = code == EQ_EXPR ? NE_EXPR : EQ_EXPR;
3330       rhs = fold_convert (type, integer_zero_node);
3331     }
3332
3333   /* Make a new bitfield reference, shift the constant over the
3334      appropriate number of bits and mask it with the computed mask
3335      (in case this was a signed field).  If we changed it, make a new one.  */
3336   lhs = make_bit_field_ref (linner, unsigned_type, nbitsize, nbitpos, 1);
3337   if (lvolatilep)
3338     {
3339       TREE_SIDE_EFFECTS (lhs) = 1;
3340       TREE_THIS_VOLATILE (lhs) = 1;
3341     }
3342
3343   rhs = fold (const_binop (BIT_AND_EXPR,
3344                            const_binop (LSHIFT_EXPR,
3345                                         fold_convert (unsigned_type, rhs),
3346                                         size_int (lbitpos), 0),
3347                            mask, 0));
3348
3349   return build2 (code, compare_type,
3350                  build2 (BIT_AND_EXPR, unsigned_type, lhs, mask),
3351                  rhs);
3352 }
3353 \f
3354 /* Subroutine for fold_truthop: decode a field reference.
3355
3356    If EXP is a comparison reference, we return the innermost reference.
3357
3358    *PBITSIZE is set to the number of bits in the reference, *PBITPOS is
3359    set to the starting bit number.
3360
3361    If the innermost field can be completely contained in a mode-sized
3362    unit, *PMODE is set to that mode.  Otherwise, it is set to VOIDmode.
3363
3364    *PVOLATILEP is set to 1 if the any expression encountered is volatile;
3365    otherwise it is not changed.
3366
3367    *PUNSIGNEDP is set to the signedness of the field.
3368
3369    *PMASK is set to the mask used.  This is either contained in a
3370    BIT_AND_EXPR or derived from the width of the field.
3371
3372    *PAND_MASK is set to the mask found in a BIT_AND_EXPR, if any.
3373
3374    Return 0 if this is not a component reference or is one that we can't
3375    do anything with.  */
3376
3377 static tree
3378 decode_field_reference (tree exp, HOST_WIDE_INT *pbitsize,
3379                         HOST_WIDE_INT *pbitpos, enum machine_mode *pmode,
3380                         int *punsignedp, int *pvolatilep,
3381                         tree *pmask, tree *pand_mask)
3382 {
3383   tree outer_type = 0;
3384   tree and_mask = 0;
3385   tree mask, inner, offset;
3386   tree unsigned_type;
3387   unsigned int precision;
3388
3389   /* All the optimizations using this function assume integer fields.
3390      There are problems with FP fields since the type_for_size call
3391      below can fail for, e.g., XFmode.  */
3392   if (! INTEGRAL_TYPE_P (TREE_TYPE (exp)))
3393     return 0;
3394
3395   /* We are interested in the bare arrangement of bits, so strip everything
3396      that doesn't affect the machine mode.  However, record the type of the
3397      outermost expression if it may matter below.  */
3398   if (TREE_CODE (exp) == NOP_EXPR
3399       || TREE_CODE (exp) == CONVERT_EXPR
3400       || TREE_CODE (exp) == NON_LVALUE_EXPR)
3401     outer_type = TREE_TYPE (exp);
3402   STRIP_NOPS (exp);
3403
3404   if (TREE_CODE (exp) == BIT_AND_EXPR)
3405     {
3406       and_mask = TREE_OPERAND (exp, 1);
3407       exp = TREE_OPERAND (exp, 0);
3408       STRIP_NOPS (exp); STRIP_NOPS (and_mask);
3409       if (TREE_CODE (and_mask) != INTEGER_CST)
3410         return 0;
3411     }
3412
3413   inner = get_inner_reference (exp, pbitsize, pbitpos, &offset, pmode,
3414                                punsignedp, pvolatilep, false);
3415   if ((inner == exp && and_mask == 0)
3416       || *pbitsize < 0 || offset != 0
3417       || TREE_CODE (inner) == PLACEHOLDER_EXPR)
3418     return 0;
3419
3420   /* If the number of bits in the reference is the same as the bitsize of
3421      the outer type, then the outer type gives the signedness. Otherwise
3422      (in case of a small bitfield) the signedness is unchanged.  */
3423   if (outer_type && *pbitsize == TYPE_PRECISION (outer_type))
3424     *punsignedp = TYPE_UNSIGNED (outer_type);
3425
3426   /* Compute the mask to access the bitfield.  */
3427   unsigned_type = lang_hooks.types.type_for_size (*pbitsize, 1);
3428   precision = TYPE_PRECISION (unsigned_type);
3429
3430   mask = build_int_cst (unsigned_type, -1);
3431   mask = force_fit_type (mask, 0, false, false);
3432
3433   mask = const_binop (LSHIFT_EXPR, mask, size_int (precision - *pbitsize), 0);
3434   mask = const_binop (RSHIFT_EXPR, mask, size_int (precision - *pbitsize), 0);
3435
3436   /* Merge it with the mask we found in the BIT_AND_EXPR, if any.  */
3437   if (and_mask != 0)
3438     mask = fold_build2 (BIT_AND_EXPR, unsigned_type,
3439                         fold_convert (unsigned_type, and_mask), mask);
3440
3441   *pmask = mask;
3442   *pand_mask = and_mask;
3443   return inner;
3444 }
3445
3446 /* Return nonzero if MASK represents a mask of SIZE ones in the low-order
3447    bit positions.  */
3448
3449 static int
3450 all_ones_mask_p (tree mask, int size)
3451 {
3452   tree type = TREE_TYPE (mask);
3453   unsigned int precision = TYPE_PRECISION (type);
3454   tree tmask;
3455
3456   tmask = build_int_cst (lang_hooks.types.signed_type (type), -1);
3457   tmask = force_fit_type (tmask, 0, false, false);
3458
3459   return
3460     tree_int_cst_equal (mask,
3461                         const_binop (RSHIFT_EXPR,
3462                                      const_binop (LSHIFT_EXPR, tmask,
3463                                                   size_int (precision - size),
3464                                                   0),
3465                                      size_int (precision - size), 0));
3466 }
3467
3468 /* Subroutine for fold: determine if VAL is the INTEGER_CONST that
3469    represents the sign bit of EXP's type.  If EXP represents a sign
3470    or zero extension, also test VAL against the unextended type.
3471    The return value is the (sub)expression whose sign bit is VAL,
3472    or NULL_TREE otherwise.  */
3473
3474 static tree
3475 sign_bit_p (tree exp, tree val)
3476 {
3477   unsigned HOST_WIDE_INT mask_lo, lo;
3478   HOST_WIDE_INT mask_hi, hi;
3479   int width;
3480   tree t;
3481
3482   /* Tree EXP must have an integral type.  */
3483   t = TREE_TYPE (exp);
3484   if (! INTEGRAL_TYPE_P (t))
3485     return NULL_TREE;
3486
3487   /* Tree VAL must be an integer constant.  */
3488   if (TREE_CODE (val) != INTEGER_CST
3489       || TREE_CONSTANT_OVERFLOW (val))
3490     return NULL_TREE;
3491
3492   width = TYPE_PRECISION (t);
3493   if (width > HOST_BITS_PER_WIDE_INT)
3494     {
3495       hi = (unsigned HOST_WIDE_INT) 1 << (width - HOST_BITS_PER_WIDE_INT - 1);
3496       lo = 0;
3497
3498       mask_hi = ((unsigned HOST_WIDE_INT) -1
3499                  >> (2 * HOST_BITS_PER_WIDE_INT - width));
3500       mask_lo = -1;
3501     }
3502   else
3503     {
3504       hi = 0;
3505       lo = (unsigned HOST_WIDE_INT) 1 << (width - 1);
3506
3507       mask_hi = 0;
3508       mask_lo = ((unsigned HOST_WIDE_INT) -1
3509                  >> (HOST_BITS_PER_WIDE_INT - width));
3510     }
3511
3512   /* We mask off those bits beyond TREE_TYPE (exp) so that we can
3513      treat VAL as if it were unsigned.  */
3514   if ((TREE_INT_CST_HIGH (val) & mask_hi) == hi
3515       && (TREE_INT_CST_LOW (val) & mask_lo) == lo)
3516     return exp;
3517
3518   /* Handle extension from a narrower type.  */
3519   if (TREE_CODE (exp) == NOP_EXPR
3520       && TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (exp, 0))) < width)
3521     return sign_bit_p (TREE_OPERAND (exp, 0), val);
3522
3523   return NULL_TREE;
3524 }
3525
3526 /* Subroutine for fold_truthop: determine if an operand is simple enough
3527    to be evaluated unconditionally.  */
3528
3529 static int
3530 simple_operand_p (tree exp)
3531 {
3532   /* Strip any conversions that don't change the machine mode.  */
3533   STRIP_NOPS (exp);
3534
3535   return (CONSTANT_CLASS_P (exp)
3536           || TREE_CODE (exp) == SSA_NAME
3537           || (DECL_P (exp)
3538               && ! TREE_ADDRESSABLE (exp)
3539               && ! TREE_THIS_VOLATILE (exp)
3540               && ! DECL_NONLOCAL (exp)
3541               /* Don't regard global variables as simple.  They may be
3542                  allocated in ways unknown to the compiler (shared memory,
3543                  #pragma weak, etc).  */
3544               && ! TREE_PUBLIC (exp)
3545               && ! DECL_EXTERNAL (exp)
3546               /* Loading a static variable is unduly expensive, but global
3547                  registers aren't expensive.  */
3548               && (! TREE_STATIC (exp) || DECL_REGISTER (exp))));
3549 }
3550 \f
3551 /* The following functions are subroutines to fold_range_test and allow it to
3552    try to change a logical combination of comparisons into a range test.
3553
3554    For example, both
3555         X == 2 || X == 3 || X == 4 || X == 5
3556    and
3557         X >= 2 && X <= 5
3558    are converted to
3559         (unsigned) (X - 2) <= 3
3560
3561    We describe each set of comparisons as being either inside or outside
3562    a range, using a variable named like IN_P, and then describe the
3563    range with a lower and upper bound.  If one of the bounds is omitted,
3564    it represents either the highest or lowest value of the type.
3565
3566    In the comments below, we represent a range by two numbers in brackets
3567    preceded by a "+" to designate being inside that range, or a "-" to
3568    designate being outside that range, so the condition can be inverted by
3569    flipping the prefix.  An omitted bound is represented by a "-".  For
3570    example, "- [-, 10]" means being outside the range starting at the lowest
3571    possible value and ending at 10, in other words, being greater than 10.
3572    The range "+ [-, -]" is always true and hence the range "- [-, -]" is
3573    always false.
3574
3575    We set up things so that the missing bounds are handled in a consistent
3576    manner so neither a missing bound nor "true" and "false" need to be
3577    handled using a special case.  */
3578
3579 /* Return the result of applying CODE to ARG0 and ARG1, but handle the case
3580    of ARG0 and/or ARG1 being omitted, meaning an unlimited range. UPPER0_P
3581    and UPPER1_P are nonzero if the respective argument is an upper bound
3582    and zero for a lower.  TYPE, if nonzero, is the type of the result; it
3583    must be specified for a comparison.  ARG1 will be converted to ARG0's
3584    type if both are specified.  */
3585
3586 static tree
3587 range_binop (enum tree_code code, tree type, tree arg0, int upper0_p,
3588              tree arg1, int upper1_p)
3589 {
3590   tree tem;
3591   int result;
3592   int sgn0, sgn1;
3593
3594   /* If neither arg represents infinity, do the normal operation.
3595      Else, if not a comparison, return infinity.  Else handle the special
3596      comparison rules. Note that most of the cases below won't occur, but
3597      are handled for consistency.  */
3598
3599   if (arg0 != 0 && arg1 != 0)
3600     {
3601       tem = fold_build2 (code, type != 0 ? type : TREE_TYPE (arg0),
3602                          arg0, fold_convert (TREE_TYPE (arg0), arg1));
3603       STRIP_NOPS (tem);
3604       return TREE_CODE (tem) == INTEGER_CST ? tem : 0;
3605     }
3606
3607   if (TREE_CODE_CLASS (code) != tcc_comparison)
3608     return 0;
3609
3610   /* Set SGN[01] to -1 if ARG[01] is a lower bound, 1 for upper, and 0
3611      for neither.  In real maths, we cannot assume open ended ranges are
3612      the same. But, this is computer arithmetic, where numbers are finite.
3613      We can therefore make the transformation of any unbounded range with
3614      the value Z, Z being greater than any representable number. This permits
3615      us to treat unbounded ranges as equal.  */
3616   sgn0 = arg0 != 0 ? 0 : (upper0_p ? 1 : -1);
3617   sgn1 = arg1 != 0 ? 0 : (upper1_p ? 1 : -1);
3618   switch (code)
3619     {
3620     case EQ_EXPR:
3621       result = sgn0 == sgn1;
3622       break;
3623     case NE_EXPR:
3624       result = sgn0 != sgn1;
3625       break;
3626     case LT_EXPR:
3627       result = sgn0 < sgn1;
3628       break;
3629     case LE_EXPR:
3630       result = sgn0 <= sgn1;
3631       break;
3632     case GT_EXPR:
3633       result = sgn0 > sgn1;
3634       break;
3635     case GE_EXPR:
3636       result = sgn0 >= sgn1;
3637       break;
3638     default:
3639       gcc_unreachable ();
3640     }
3641
3642   return constant_boolean_node (result, type);
3643 }
3644 \f
3645 /* Given EXP, a logical expression, set the range it is testing into
3646    variables denoted by PIN_P, PLOW, and PHIGH.  Return the expression
3647    actually being tested.  *PLOW and *PHIGH will be made of the same type
3648    as the returned expression.  If EXP is not a comparison, we will most
3649    likely not be returning a useful value and range.  */
3650
3651 static tree
3652 make_range (tree exp, int *pin_p, tree *plow, tree *phigh)
3653 {
3654   enum tree_code code;
3655   tree arg0 = NULL_TREE, arg1 = NULL_TREE;
3656   tree exp_type = NULL_TREE, arg0_type = NULL_TREE;
3657   int in_p, n_in_p;
3658   tree low, high, n_low, n_high;
3659
3660   /* Start with simply saying "EXP != 0" and then look at the code of EXP
3661      and see if we can refine the range.  Some of the cases below may not
3662      happen, but it doesn't seem worth worrying about this.  We "continue"
3663      the outer loop when we've changed something; otherwise we "break"
3664      the switch, which will "break" the while.  */
3665
3666   in_p = 0;
3667   low = high = fold_convert (TREE_TYPE (exp), integer_zero_node);
3668
3669   while (1)
3670     {
3671       code = TREE_CODE (exp);
3672       exp_type = TREE_TYPE (exp);
3673
3674       if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)))
3675         {
3676           if (TREE_CODE_LENGTH (code) > 0)
3677             arg0 = TREE_OPERAND (exp, 0);
3678           if (TREE_CODE_CLASS (code) == tcc_comparison
3679               || TREE_CODE_CLASS (code) == tcc_unary
3680               || TREE_CODE_CLASS (code) == tcc_binary)
3681             arg0_type = TREE_TYPE (arg0);
3682           if (TREE_CODE_CLASS (code) == tcc_binary
3683               || TREE_CODE_CLASS (code) == tcc_comparison
3684               || (TREE_CODE_CLASS (code) == tcc_expression
3685                   && TREE_CODE_LENGTH (code) > 1))
3686             arg1 = TREE_OPERAND (exp, 1);
3687         }
3688
3689       switch (code)
3690         {
3691         case TRUTH_NOT_EXPR:
3692           in_p = ! in_p, exp = arg0;
3693           continue;
3694
3695         case EQ_EXPR: case NE_EXPR:
3696         case LT_EXPR: case LE_EXPR: case GE_EXPR: case GT_EXPR:
3697           /* We can only do something if the range is testing for zero
3698              and if the second operand is an integer constant.  Note that
3699              saying something is "in" the range we make is done by
3700              complementing IN_P since it will set in the initial case of
3701              being not equal to zero; "out" is leaving it alone.  */
3702           if (low == 0 || high == 0
3703               || ! integer_zerop (low) || ! integer_zerop (high)
3704               || TREE_CODE (arg1) != INTEGER_CST)
3705             break;
3706
3707           switch (code)
3708             {
3709             case NE_EXPR:  /* - [c, c]  */
3710               low = high = arg1;
3711               break;
3712             case EQ_EXPR:  /* + [c, c]  */
3713               in_p = ! in_p, low = high = arg1;
3714               break;
3715             case GT_EXPR:  /* - [-, c] */
3716               low = 0, high = arg1;
3717               break;
3718             case GE_EXPR:  /* + [c, -] */
3719               in_p = ! in_p, low = arg1, high = 0;
3720               break;
3721             case LT_EXPR:  /* - [c, -] */
3722               low = arg1, high = 0;
3723               break;
3724             case LE_EXPR:  /* + [-, c] */
3725               in_p = ! in_p, low = 0, high = arg1;
3726               break;
3727             default:
3728               gcc_unreachable ();
3729             }
3730
3731           /* If this is an unsigned comparison, we also know that EXP is
3732              greater than or equal to zero.  We base the range tests we make
3733              on that fact, so we record it here so we can parse existing
3734              range tests.  We test arg0_type since often the return type
3735              of, e.g. EQ_EXPR, is boolean.  */
3736           if (TYPE_UNSIGNED (arg0_type) && (low == 0 || high == 0))
3737             {
3738               if (! merge_ranges (&n_in_p, &n_low, &n_high,
3739                                   in_p, low, high, 1,
3740                                   fold_convert (arg0_type, integer_zero_node),
3741                                   NULL_TREE))
3742                 break;
3743
3744               in_p = n_in_p, low = n_low, high = n_high;
3745
3746               /* If the high bound is missing, but we have a nonzero low
3747                  bound, reverse the range so it goes from zero to the low bound
3748                  minus 1.  */
3749               if (high == 0 && low && ! integer_zerop (low))
3750                 {
3751                   in_p = ! in_p;
3752                   high = range_binop (MINUS_EXPR, NULL_TREE, low, 0,
3753                                       integer_one_node, 0);
3754                   low = fold_convert (arg0_type, integer_zero_node);
3755                 }
3756             }
3757
3758           exp = arg0;
3759           continue;
3760
3761         case NEGATE_EXPR:
3762           /* (-x) IN [a,b] -> x in [-b, -a]  */
3763           n_low = range_binop (MINUS_EXPR, exp_type,
3764                                fold_convert (exp_type, integer_zero_node),
3765                                0, high, 1);
3766           n_high = range_binop (MINUS_EXPR, exp_type,
3767                                 fold_convert (exp_type, integer_zero_node),
3768                                 0, low, 0);
3769           low = n_low, high = n_high;
3770           exp = arg0;
3771           continue;
3772
3773         case BIT_NOT_EXPR:
3774           /* ~ X -> -X - 1  */
3775           exp = build2 (MINUS_EXPR, exp_type, negate_expr (arg0),
3776                         fold_convert (exp_type, integer_one_node));
3777           continue;
3778
3779         case PLUS_EXPR:  case MINUS_EXPR:
3780           if (TREE_CODE (arg1) != INTEGER_CST)
3781             break;
3782
3783           /* If EXP is signed, any overflow in the computation is undefined,
3784              so we don't worry about it so long as our computations on
3785              the bounds don't overflow.  For unsigned, overflow is defined
3786              and this is exactly the right thing.  */
3787           n_low = range_binop (code == MINUS_EXPR ? PLUS_EXPR : MINUS_EXPR,
3788                                arg0_type, low, 0, arg1, 0);
3789           n_high = range_binop (code == MINUS_EXPR ? PLUS_EXPR : MINUS_EXPR,
3790                                 arg0_type, high, 1, arg1, 0);
3791           if ((n_low != 0 && TREE_OVERFLOW (n_low))
3792               || (n_high != 0 && TREE_OVERFLOW (n_high)))
3793             break;
3794
3795           /* Check for an unsigned range which has wrapped around the maximum
3796              value thus making n_high < n_low, and normalize it.  */
3797           if (n_low && n_high && tree_int_cst_lt (n_high, n_low))
3798             {
3799               low = range_binop (PLUS_EXPR, arg0_type, n_high, 0,
3800                                  integer_one_node, 0);
3801               high = range_binop (MINUS_EXPR, arg0_type, n_low, 0,
3802                                   integer_one_node, 0);
3803
3804               /* If the range is of the form +/- [ x+1, x ], we won't
3805                  be able to normalize it.  But then, it represents the
3806                  whole range or the empty set, so make it
3807                  +/- [ -, - ].  */
3808               if (tree_int_cst_equal (n_low, low)
3809                   && tree_int_cst_equal (n_high, high))
3810                 low = high = 0;
3811               else
3812                 in_p = ! in_p;
3813             }
3814           else
3815             low = n_low, high = n_high;
3816
3817           exp = arg0;
3818           continue;
3819
3820         case NOP_EXPR:  case NON_LVALUE_EXPR:  case CONVERT_EXPR:
3821           if (TYPE_PRECISION (arg0_type) > TYPE_PRECISION (exp_type))
3822             break;
3823
3824           if (! INTEGRAL_TYPE_P (arg0_type)
3825               || (low != 0 && ! int_fits_type_p (low, arg0_type))
3826               || (high != 0 && ! int_fits_type_p (high, arg0_type)))
3827             break;
3828
3829           n_low = low, n_high = high;
3830
3831           if (n_low != 0)
3832             n_low = fold_convert (arg0_type, n_low);
3833
3834           if (n_high != 0)
3835             n_high = fold_convert (arg0_type, n_high);
3836
3837
3838           /* If we're converting arg0 from an unsigned type, to exp,
3839              a signed type,  we will be doing the comparison as unsigned.
3840              The tests above have already verified that LOW and HIGH
3841              are both positive.
3842
3843              So we have to ensure that we will handle large unsigned
3844              values the same way that the current signed bounds treat
3845              negative values.  */
3846
3847           if (!TYPE_UNSIGNED (exp_type) && TYPE_UNSIGNED (arg0_type))
3848             {
3849               tree high_positive;
3850               tree equiv_type = lang_hooks.types.type_for_mode
3851                 (TYPE_MODE (arg0_type), 1);
3852
3853               /* A range without an upper bound is, naturally, unbounded.
3854                  Since convert would have cropped a very large value, use
3855                  the max value for the destination type.  */
3856               high_positive
3857                 = TYPE_MAX_VALUE (equiv_type) ? TYPE_MAX_VALUE (equiv_type)
3858                 : TYPE_MAX_VALUE (arg0_type);
3859
3860               if (TYPE_PRECISION (exp_type) == TYPE_PRECISION (arg0_type))
3861                 high_positive = fold_build2 (RSHIFT_EXPR, arg0_type,
3862                                              fold_convert (arg0_type,
3863                                                            high_positive),
3864                                              fold_convert (arg0_type,
3865                                                            integer_one_node));
3866
3867               /* If the low bound is specified, "and" the range with the
3868                  range for which the original unsigned value will be
3869                  positive.  */
3870               if (low != 0)
3871                 {
3872                   if (! merge_ranges (&n_in_p, &n_low, &n_high,
3873                                       1, n_low, n_high, 1,
3874                                       fold_convert (arg0_type,
3875                                                     integer_zero_node),
3876                                       high_positive))
3877                     break;
3878
3879                   in_p = (n_in_p == in_p);
3880                 }
3881               else
3882                 {
3883                   /* Otherwise, "or" the range with the range of the input
3884                      that will be interpreted as negative.  */
3885                   if (! merge_ranges (&n_in_p, &n_low, &n_high,
3886                                       0, n_low, n_high, 1,
3887                                       fold_convert (arg0_type,
3888                                                     integer_zero_node),
3889                                       high_positive))
3890                     break;
3891
3892                   in_p = (in_p != n_in_p);
3893                 }
3894             }
3895
3896           exp = arg0;
3897           low = n_low, high = n_high;
3898           continue;
3899
3900         default:
3901           break;
3902         }
3903
3904       break;
3905     }
3906
3907   /* If EXP is a constant, we can evaluate whether this is true or false.  */
3908   if (TREE_CODE (exp) == INTEGER_CST)
3909     {
3910       in_p = in_p == (integer_onep (range_binop (GE_EXPR, integer_type_node,
3911                                                  exp, 0, low, 0))
3912                       && integer_onep (range_binop (LE_EXPR, integer_type_node,
3913                                                     exp, 1, high, 1)));
3914       low = high = 0;
3915       exp = 0;
3916     }
3917
3918   *pin_p = in_p, *plow = low, *phigh = high;
3919   return exp;
3920 }
3921 \f
3922 /* Given a range, LOW, HIGH, and IN_P, an expression, EXP, and a result
3923    type, TYPE, return an expression to test if EXP is in (or out of, depending
3924    on IN_P) the range.  Return 0 if the test couldn't be created.  */
3925
3926 static tree
3927 build_range_check (tree type, tree exp, int in_p, tree low, tree high)
3928 {
3929   tree etype = TREE_TYPE (exp);
3930   tree value;
3931
3932   if (! in_p)
3933     {
3934       value = build_range_check (type, exp, 1, low, high);
3935       if (value != 0)
3936         return invert_truthvalue (value);
3937
3938       return 0;
3939     }
3940
3941   if (low == 0 && high == 0)
3942     return fold_convert (type, integer_one_node);
3943
3944   if (low == 0)
3945     return fold_build2 (LE_EXPR, type, exp,
3946                         fold_convert (etype, high));
3947
3948   if (high == 0)
3949     return fold_build2 (GE_EXPR, type, exp,
3950                         fold_convert (etype, low));
3951
3952   if (operand_equal_p (low, high, 0))
3953     return fold_build2 (EQ_EXPR, type, exp,
3954                         fold_convert (etype, low));
3955
3956   if (integer_zerop (low))
3957     {
3958       if (! TYPE_UNSIGNED (etype))
3959         {
3960           etype = lang_hooks.types.unsigned_type (etype);
3961           high = fold_convert (etype, high);
3962           exp = fold_convert (etype, exp);
3963         }
3964       return build_range_check (type, exp, 1, 0, high);
3965     }
3966
3967   /* Optimize (c>=1) && (c<=127) into (signed char)c > 0.  */
3968   if (integer_onep (low) && TREE_CODE (high) == INTEGER_CST)
3969     {
3970       unsigned HOST_WIDE_INT lo;
3971       HOST_WIDE_INT hi;
3972       int prec;
3973
3974       prec = TYPE_PRECISION (etype);
3975       if (prec <= HOST_BITS_PER_WIDE_INT)
3976         {
3977           hi = 0;
3978           lo = ((unsigned HOST_WIDE_INT) 1 << (prec - 1)) - 1;
3979         }
3980       else
3981         {
3982           hi = ((HOST_WIDE_INT) 1 << (prec - HOST_BITS_PER_WIDE_INT - 1)) - 1;
3983           lo = (unsigned HOST_WIDE_INT) -1;
3984         }
3985
3986       if (TREE_INT_CST_HIGH (high) == hi && TREE_INT_CST_LOW (high) == lo)
3987         {
3988           if (TYPE_UNSIGNED (etype))
3989             {
3990               etype = lang_hooks.types.signed_type (etype);
3991               exp = fold_convert (etype, exp);
3992             }
3993           return fold_build2 (GT_EXPR, type, exp,
3994                               fold_convert (etype, integer_zero_node));
3995         }
3996     }
3997
3998   value = const_binop (MINUS_EXPR, high, low, 0);
3999   if (value != 0 && TREE_OVERFLOW (value) && ! TYPE_UNSIGNED (etype))
4000     {
4001       tree utype, minv, maxv;
4002
4003       /* Check if (unsigned) INT_MAX + 1 == (unsigned) INT_MIN
4004          for the type in question, as we rely on this here.  */
4005       switch (TREE_CODE (etype))
4006         {
4007         case INTEGER_TYPE:
4008         case ENUMERAL_TYPE:
4009         case CHAR_TYPE:
4010           utype = lang_hooks.types.unsigned_type (etype);
4011           maxv = fold_convert (utype, TYPE_MAX_VALUE (etype));
4012           maxv = range_binop (PLUS_EXPR, NULL_TREE, maxv, 1,
4013                               integer_one_node, 1);
4014           minv = fold_convert (utype, TYPE_MIN_VALUE (etype));
4015           if (integer_zerop (range_binop (NE_EXPR, integer_type_node,
4016                                           minv, 1, maxv, 1)))
4017             {
4018               etype = utype;
4019               high = fold_convert (etype, high);
4020               low = fold_convert (etype, low);
4021               exp = fold_convert (etype, exp);
4022               value = const_binop (MINUS_EXPR, high, low, 0);
4023             }
4024           break;
4025         default:
4026           break;
4027         }
4028     }
4029
4030   if (value != 0 && ! TREE_OVERFLOW (value))
4031     return build_range_check (type,
4032                               fold_build2 (MINUS_EXPR, etype, exp, low),
4033                               1, fold_convert (etype, integer_zero_node),
4034                               value);
4035
4036   return 0;
4037 }
4038 \f
4039 /* Given two ranges, see if we can merge them into one.  Return 1 if we
4040    can, 0 if we can't.  Set the output range into the specified parameters.  */
4041
4042 static int
4043 merge_ranges (int *pin_p, tree *plow, tree *phigh, int in0_p, tree low0,