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, 2006 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 the built-in mathematical function specified by CODE
 861    is odd, 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_FLT_FN (BUILT_IN_ASIN):
 869     CASE_FLT_FN (BUILT_IN_ASINH):
 870     CASE_FLT_FN (BUILT_IN_ATAN):
 871     CASE_FLT_FN (BUILT_IN_ATANH):
 872     CASE_FLT_FN (BUILT_IN_CBRT):
 873     CASE_FLT_FN (BUILT_IN_SIN):
 874     CASE_FLT_FN (BUILT_IN_SINH):
 875     CASE_FLT_FN (BUILT_IN_TAN):
 876     CASE_FLT_FN (BUILT_IN_TANH):
 877       return true;
 878
 879     default:
 880       break;
 881     }
 882   return false;
 883 }
 884
 885 /* Check whether we may negate an integer constant T without causing
 886    overflow.  */
 887
 888 bool
 889 may_negate_without_overflow_p (tree t)
 890 {
 891   unsigned HOST_WIDE_INT val;
 892   unsigned int prec;
 893   tree type;
 894
 895   gcc_assert (TREE_CODE (t) == INTEGER_CST);
 896
 897   type = TREE_TYPE (t);
 898   if (TYPE_UNSIGNED (type))
 899     return false;
 900
 901   prec = TYPE_PRECISION (type);
 902   if (prec > HOST_BITS_PER_WIDE_INT)
 903     {
 904       if (TREE_INT_CST_LOW (t) != 0)
 905         return true;
 906       prec -= HOST_BITS_PER_WIDE_INT;
 907       val = TREE_INT_CST_HIGH (t);
 908     }
 909   else
 910     val = TREE_INT_CST_LOW (t);
 911   if (prec < HOST_BITS_PER_WIDE_INT)
 912     val &= ((unsigned HOST_WIDE_INT) 1 << prec) - 1;
 913   return val != ((unsigned HOST_WIDE_INT) 1 << (prec - 1));
 914 }
 915
 916 /* Determine whether an expression T can be cheaply negated using
 917    the function negate_expr.  */
 918
 919 static bool
 920 negate_expr_p (tree t)
 921 {
 922   tree type;
 923
 924   if (t == 0)
 925     return false;
 926
 927   type = TREE_TYPE (t);
 928
 929   STRIP_SIGN_NOPS (t);
 930   switch (TREE_CODE (t))
 931     {
 932     case INTEGER_CST:
 933       if (TYPE_UNSIGNED (type) || ! flag_trapv)
 934         return true;
 935
 936       /* Check that -CST will not overflow type.  */
 937       return may_negate_without_overflow_p (t);
 938     case BIT_NOT_EXPR:
 939        return INTEGRAL_TYPE_P (type);
 940
 941     case REAL_CST:
 942     case NEGATE_EXPR:
 943       return true;
 944
 945     case COMPLEX_CST:
 946       return negate_expr_p (TREE_REALPART (t))
 947              && negate_expr_p (TREE_IMAGPART (t));
 948
 949     case PLUS_EXPR:
 950       if (FLOAT_TYPE_P (type) && !flag_unsafe_math_optimizations)
 951         return false;
 952       /* -(A + B) -> (-B) - A.  */
 953       if (negate_expr_p (TREE_OPERAND (t, 1))
 954           && reorder_operands_p (TREE_OPERAND (t, 0),
 955                                  TREE_OPERAND (t, 1)))
 956         return true;
 957       /* -(A + B) -> (-A) - B.  */
 958       return negate_expr_p (TREE_OPERAND (t, 0));
 959
 960     case MINUS_EXPR:
 961       /* We can't turn -(A-B) into B-A when we honor signed zeros.  */
 962       return (! FLOAT_TYPE_P (type) || flag_unsafe_math_optimizations)
 963              && reorder_operands_p (TREE_OPERAND (t, 0),
 964                                     TREE_OPERAND (t, 1));
 965
 966     case MULT_EXPR:
 967       if (TYPE_UNSIGNED (TREE_TYPE (t)))
 968         break;
 969
 970       /* Fall through.  */
 971
 972     case RDIV_EXPR:
 973       if (! HONOR_SIGN_DEPENDENT_ROUNDING (TYPE_MODE (TREE_TYPE (t))))
 974         return negate_expr_p (TREE_OPERAND (t, 1))
 975                || negate_expr_p (TREE_OPERAND (t, 0));
 976       break;
 977
 978     case TRUNC_DIV_EXPR:
 979     case ROUND_DIV_EXPR:
 980     case FLOOR_DIV_EXPR:
 981     case CEIL_DIV_EXPR:
 982     case EXACT_DIV_EXPR:
 983       if (TYPE_UNSIGNED (TREE_TYPE (t)) || flag_wrapv)
 984         break;
 985       return negate_expr_p (TREE_OPERAND (t, 1))
 986              || negate_expr_p (TREE_OPERAND (t, 0));
 987
 988     case NOP_EXPR:
 989       /* Negate -((double)float) as (double)(-float).  */
 990       if (TREE_CODE (type) == REAL_TYPE)
 991         {
 992           tree tem = strip_float_extensions (t);
 993           if (tem != t)
 994             return negate_expr_p (tem);
 995         }
 996       break;
 997
 998     case CALL_EXPR:
 999       /* Negate -f(x) as f(-x).  */
1000       if (negate_mathfn_p (builtin_mathfn_code (t)))
1001         return negate_expr_p (TREE_VALUE (TREE_OPERAND (t, 1)));
1002       break;
1003
1004     case RSHIFT_EXPR:
1005       /* Optimize -((int)x >> 31) into (unsigned)x >> 31.  */
1006       if (TREE_CODE (TREE_OPERAND (t, 1)) == INTEGER_CST)
1007         {
1008           tree op1 = TREE_OPERAND (t, 1);
1009           if (TREE_INT_CST_HIGH (op1) == 0
1010               && (unsigned HOST_WIDE_INT) (TYPE_PRECISION (type) - 1)
1011                  == TREE_INT_CST_LOW (op1))
1012             return true;
1013         }
1014       break;
1015
1016     default:
1017       break;
1018     }
1019   return false;
1020 }
1021
1022 /* Given T, an expression, return the negation of T.  Allow for T to be
1023    null, in which case return null.  */
1024
1025 static tree
1026 negate_expr (tree t)
1027 {
1028   tree type;
1029   tree tem;
1030
1031   if (t == 0)
1032     return 0;
1033
1034   type = TREE_TYPE (t);
1035   STRIP_SIGN_NOPS (t);
1036
1037   switch (TREE_CODE (t))
1038     {
1039     /* Convert - (~A) to A + 1.  */
1040     case BIT_NOT_EXPR:
1041       if (INTEGRAL_TYPE_P (type))
1042         return fold_build2 (PLUS_EXPR, type, TREE_OPERAND (t, 0),
1043                             build_int_cst (type, 1));
1044       break;
1045
1046     case INTEGER_CST:
1047       tem = fold_negate_const (t, type);
1048       if (! TREE_OVERFLOW (tem)
1049           || TYPE_UNSIGNED (type)
1050           || ! flag_trapv)
1051         return tem;
1052       break;
1053
1054     case REAL_CST:
1055       tem = fold_negate_const (t, type);
1056       /* Two's complement FP formats, such as c4x, may overflow.  */
1057       if (! TREE_OVERFLOW (tem) || ! flag_trapping_math)
1058         return fold_convert (type, tem);
1059       break;
1060
1061     case COMPLEX_CST:
1062       {
1063         tree rpart = negate_expr (TREE_REALPART (t));
1064         tree ipart = negate_expr (TREE_IMAGPART (t));
1065
1066         if ((TREE_CODE (rpart) == REAL_CST
1067              && TREE_CODE (ipart) == REAL_CST)
1068             || (TREE_CODE (rpart) == INTEGER_CST
1069                 && TREE_CODE (ipart) == INTEGER_CST))
1070           return build_complex (type, rpart, ipart);
1071       }
1072       break;
1073
1074     case NEGATE_EXPR:
1075       return fold_convert (type, TREE_OPERAND (t, 0));
1076
1077     case PLUS_EXPR:
1078       if (! FLOAT_TYPE_P (type) || flag_unsafe_math_optimizations)
1079         {
1080           /* -(A + B) -> (-B) - A.  */
1081           if (negate_expr_p (TREE_OPERAND (t, 1))
1082               && reorder_operands_p (TREE_OPERAND (t, 0),
1083                                      TREE_OPERAND (t, 1)))
1084             {
1085               tem = negate_expr (TREE_OPERAND (t, 1));
1086               tem = fold_build2 (MINUS_EXPR, TREE_TYPE (t),
1087                                  tem, TREE_OPERAND (t, 0));
1088               return fold_convert (type, tem);
1089             }
1090
1091           /* -(A + B) -> (-A) - B.  */
1092           if (negate_expr_p (TREE_OPERAND (t, 0)))
1093             {
1094               tem = negate_expr (TREE_OPERAND (t, 0));
1095               tem = fold_build2 (MINUS_EXPR, TREE_TYPE (t),
1096                                  tem, TREE_OPERAND (t, 1));
1097               return fold_convert (type, tem);
1098             }
1099         }
1100       break;
1101
1102     case MINUS_EXPR:
1103       /* - (A - B) -> B - A  */
1104       if ((! FLOAT_TYPE_P (type) || flag_unsafe_math_optimizations)
1105           && reorder_operands_p (TREE_OPERAND (t, 0), TREE_OPERAND (t, 1)))
1106         return fold_convert (type,
1107                              fold_build2 (MINUS_EXPR, TREE_TYPE (t),
1108                                           TREE_OPERAND (t, 1),
1109                                           TREE_OPERAND (t, 0)));
1110       break;
1111
1112     case MULT_EXPR:
1113       if (TYPE_UNSIGNED (TREE_TYPE (t)))
1114         break;
1115
1116       /* Fall through.  */
1117
1118     case RDIV_EXPR:
1119       if (! HONOR_SIGN_DEPENDENT_ROUNDING (TYPE_MODE (TREE_TYPE (t))))
1120         {
1121           tem = TREE_OPERAND (t, 1);
1122           if (negate_expr_p (tem))
1123             return fold_convert (type,
1124                                  fold_build2 (TREE_CODE (t), TREE_TYPE (t),
1125                                               TREE_OPERAND (t, 0),
1126                                               negate_expr (tem)));
1127           tem = TREE_OPERAND (t, 0);
1128           if (negate_expr_p (tem))
1129             return fold_convert (type,
1130                                  fold_build2 (TREE_CODE (t), TREE_TYPE (t),
1131                                               negate_expr (tem),
1132                                               TREE_OPERAND (t, 1)));
1133         }
1134       break;
1135
1136     case TRUNC_DIV_EXPR:
1137     case ROUND_DIV_EXPR:
1138     case FLOOR_DIV_EXPR:
1139     case CEIL_DIV_EXPR:
1140     case EXACT_DIV_EXPR:
1141       if (!TYPE_UNSIGNED (TREE_TYPE (t)) && !flag_wrapv)
1142         {
1143           tem = TREE_OPERAND (t, 1);
1144           if (negate_expr_p (tem))
1145             return fold_convert (type,
1146                                  fold_build2 (TREE_CODE (t), TREE_TYPE (t),
1147                                               TREE_OPERAND (t, 0),
1148                                               negate_expr (tem)));
1149           tem = TREE_OPERAND (t, 0);
1150           if (negate_expr_p (tem))
1151             return fold_convert (type,
1152                                  fold_build2 (TREE_CODE (t), TREE_TYPE (t),
1153                                               negate_expr (tem),
1154                                               TREE_OPERAND (t, 1)));
1155         }
1156       break;
1157
1158     case NOP_EXPR:
1159       /* Convert -((double)float) into (double)(-float).  */
1160       if (TREE_CODE (type) == REAL_TYPE)
1161         {
1162           tem = strip_float_extensions (t);
1163           if (tem != t && negate_expr_p (tem))
1164             return fold_convert (type, negate_expr (tem));
1165         }
1166       break;
1167
1168     case CALL_EXPR:
1169       /* Negate -f(x) as f(-x).  */
1170       if (negate_mathfn_p (builtin_mathfn_code (t))
1171           && negate_expr_p (TREE_VALUE (TREE_OPERAND (t, 1))))
1172         {
1173           tree fndecl, arg, arglist;
1174
1175           fndecl = get_callee_fndecl (t);
1176           arg = negate_expr (TREE_VALUE (TREE_OPERAND (t, 1)));
1177           arglist = build_tree_list (NULL_TREE, arg);
1178           return build_function_call_expr (fndecl, arglist);
1179         }
1180       break;
1181
1182     case RSHIFT_EXPR:
1183       /* Optimize -((int)x >> 31) into (unsigned)x >> 31.  */
1184       if (TREE_CODE (TREE_OPERAND (t, 1)) == INTEGER_CST)
1185         {
1186           tree op1 = TREE_OPERAND (t, 1);
1187           if (TREE_INT_CST_HIGH (op1) == 0
1188               && (unsigned HOST_WIDE_INT) (TYPE_PRECISION (type) - 1)
1189                  == TREE_INT_CST_LOW (op1))
1190             {
1191               tree ntype = TYPE_UNSIGNED (type)
1192                            ? lang_hooks.types.signed_type (type)
1193                            : lang_hooks.types.unsigned_type (type);
1194               tree temp = fold_convert (ntype, TREE_OPERAND (t, 0));
1195               temp = fold_build2 (RSHIFT_EXPR, ntype, temp, op1);
1196               return fold_convert (type, temp);
1197             }
1198         }
1199       break;
1200
1201     default:
1202       break;
1203     }
1204
1205   tem = fold_build1 (NEGATE_EXPR, TREE_TYPE (t), t);
1206   return fold_convert (type, tem);
1207 }
1208 \f
1209 /* Split a tree IN into a constant, literal and variable parts that could be
1210    combined with CODE to make IN.  "constant" means an expression with
1211    TREE_CONSTANT but that isn't an actual constant.  CODE must be a
1212    commutative arithmetic operation.  Store the constant part into *CONP,
1213    the literal in *LITP and return the variable part.  If a part isn't
1214    present, set it to null.  If the tree does not decompose in this way,
1215    return the entire tree as the variable part and the other parts as null.
1216
1217    If CODE is PLUS_EXPR we also split trees that use MINUS_EXPR.  In that
1218    case, we negate an operand that was subtracted.  Except if it is a
1219    literal for which we use *MINUS_LITP instead.
1220
1221    If NEGATE_P is true, we are negating all of IN, again except a literal
1222    for which we use *MINUS_LITP instead.
1223
1224    If IN is itself a literal or constant, return it as appropriate.
1225
1226    Note that we do not guarantee that any of the three values will be the
1227    same type as IN, but they will have the same signedness and mode.  */
1228
1229 static tree
1230 split_tree (tree in, enum tree_code code, tree *conp, tree *litp,
1231             tree *minus_litp, int negate_p)
1232 {
1233   tree var = 0;
1234
1235   *conp = 0;
1236   *litp = 0;
1237   *minus_litp = 0;
1238
1239   /* Strip any conversions that don't change the machine mode or signedness.  */
1240   STRIP_SIGN_NOPS (in);
1241
1242   if (TREE_CODE (in) == INTEGER_CST || TREE_CODE (in) == REAL_CST)
1243     *litp = in;
1244   else if (TREE_CODE (in) == code
1245            || (! FLOAT_TYPE_P (TREE_TYPE (in))
1246                /* We can associate addition and subtraction together (even
1247                   though the C standard doesn't say so) for integers because
1248                   the value is not affected.  For reals, the value might be
1249                   affected, so we can't.  */
1250                && ((code == PLUS_EXPR && TREE_CODE (in) == MINUS_EXPR)
1251                    || (code == MINUS_EXPR && TREE_CODE (in) == PLUS_EXPR))))
1252     {
1253       tree op0 = TREE_OPERAND (in, 0);
1254       tree op1 = TREE_OPERAND (in, 1);
1255       int neg1_p = TREE_CODE (in) == MINUS_EXPR;
1256       int neg_litp_p = 0, neg_conp_p = 0, neg_var_p = 0;
1257
1258       /* First see if either of the operands is a literal, then a constant.  */
1259       if (TREE_CODE (op0) == INTEGER_CST || TREE_CODE (op0) == REAL_CST)
1260         *litp = op0, op0 = 0;
1261       else if (TREE_CODE (op1) == INTEGER_CST || TREE_CODE (op1) == REAL_CST)
1262         *litp = op1, neg_litp_p = neg1_p, op1 = 0;
1263
1264       if (op0 != 0 && TREE_CONSTANT (op0))
1265         *conp = op0, op0 = 0;
1266       else if (op1 != 0 && TREE_CONSTANT (op1))
1267         *conp = op1, neg_conp_p = neg1_p, op1 = 0;
1268
1269       /* If we haven't dealt with either operand, this is not a case we can
1270          decompose.  Otherwise, VAR is either of the ones remaining, if any.  */
1271       if (op0 != 0 && op1 != 0)
1272         var = in;
1273       else if (op0 != 0)
1274         var = op0;
1275       else
1276         var = op1, neg_var_p = neg1_p;
1277
1278       /* Now do any needed negations.  */
1279       if (neg_litp_p)
1280         *minus_litp = *litp, *litp = 0;
1281       if (neg_conp_p)
1282         *conp = negate_expr (*conp);
1283       if (neg_var_p)
1284         var = negate_expr (var);
1285     }
1286   else if (TREE_CONSTANT (in))
1287     *conp = in;
1288   else
1289     var = in;
1290
1291   if (negate_p)
1292     {
1293       if (*litp)
1294         *minus_litp = *litp, *litp = 0;
1295       else if (*minus_litp)
1296         *litp = *minus_litp, *minus_litp = 0;
1297       *conp = negate_expr (*conp);
1298       var = negate_expr (var);
1299     }
1300
1301   return var;
1302 }
1303
1304 /* Re-associate trees split by the above function.  T1 and T2 are either
1305    expressions to associate or null.  Return the new expression, if any.  If
1306    we build an operation, do it in TYPE and with CODE.  */
1307
1308 static tree
1309 associate_trees (tree t1, tree t2, enum tree_code code, tree type)
1310 {
1311   if (t1 == 0)
1312     return t2;
1313   else if (t2 == 0)
1314     return t1;
1315
1316   /* If either input is CODE, a PLUS_EXPR, or a MINUS_EXPR, don't
1317      try to fold this since we will have infinite recursion.  But do
1318      deal with any NEGATE_EXPRs.  */
1319   if (TREE_CODE (t1) == code || TREE_CODE (t2) == code
1320       || TREE_CODE (t1) == MINUS_EXPR || TREE_CODE (t2) == MINUS_EXPR)
1321     {
1322       if (code == PLUS_EXPR)
1323         {
1324           if (TREE_CODE (t1) == NEGATE_EXPR)
1325             return build2 (MINUS_EXPR, type, fold_convert (type, t2),
1326                            fold_convert (type, TREE_OPERAND (t1, 0)));
1327           else if (TREE_CODE (t2) == NEGATE_EXPR)
1328             return build2 (MINUS_EXPR, type, fold_convert (type, t1),
1329                            fold_convert (type, TREE_OPERAND (t2, 0)));
1330           else if (integer_zerop (t2))
1331             return fold_convert (type, t1);
1332         }
1333       else if (code == MINUS_EXPR)
1334         {
1335           if (integer_zerop (t2))
1336             return fold_convert (type, t1);
1337         }
1338
1339       return build2 (code, type, fold_convert (type, t1),
1340                      fold_convert (type, t2));
1341     }
1342
1343   return fold_build2 (code, type, fold_convert (type, t1),
1344                       fold_convert (type, t2));
1345 }
1346 \f
1347 /* Combine two integer constants ARG1 and ARG2 under operation CODE
1348    to produce a new constant.  Return NULL_TREE if we don't know how
1349    to evaluate CODE at compile-time.
1350
1351    If NOTRUNC is nonzero, do not truncate the result to fit the data type.  */
1352
1353 tree
1354 int_const_binop (enum tree_code code, tree arg1, tree arg2, int notrunc)
1355 {
1356   unsigned HOST_WIDE_INT int1l, int2l;
1357   HOST_WIDE_INT int1h, int2h;
1358   unsigned HOST_WIDE_INT low;
1359   HOST_WIDE_INT hi;
1360   unsigned HOST_WIDE_INT garbagel;
1361   HOST_WIDE_INT garbageh;
1362   tree t;
1363   tree type = TREE_TYPE (arg1);
1364   int uns = TYPE_UNSIGNED (type);
1365   int is_sizetype
1366     = (TREE_CODE (type) == INTEGER_TYPE && TYPE_IS_SIZETYPE (type));
1367   int overflow = 0;
1368
1369   int1l = TREE_INT_CST_LOW (arg1);
1370   int1h = TREE_INT_CST_HIGH (arg1);
1371   int2l = TREE_INT_CST_LOW (arg2);
1372   int2h = TREE_INT_CST_HIGH (arg2);
1373
1374   switch (code)
1375     {
1376     case BIT_IOR_EXPR:
1377       low = int1l | int2l, hi = int1h | int2h;
1378       break;
1379
1380     case BIT_XOR_EXPR:
1381       low = int1l ^ int2l, hi = int1h ^ int2h;
1382       break;
1383
1384     case BIT_AND_EXPR:
1385       low = int1l & int2l, hi = int1h & int2h;
1386       break;
1387
1388     case RSHIFT_EXPR:
1389       int2l = -int2l;
1390     case LSHIFT_EXPR:
1391       /* It's unclear from the C standard whether shifts can overflow.
1392          The following code ignores overflow; perhaps a C standard
1393          interpretation ruling is needed.  */
1394       lshift_double (int1l, int1h, int2l, TYPE_PRECISION (type),
1395                      &low, &hi, !uns);
1396       break;
1397
1398     case RROTATE_EXPR:
1399       int2l = - int2l;
1400     case LROTATE_EXPR:
1401       lrotate_double (int1l, int1h, int2l, TYPE_PRECISION (type),
1402                       &low, &hi);
1403       break;
1404
1405     case PLUS_EXPR:
1406       overflow = add_double (int1l, int1h, int2l, int2h, &low, &hi);
1407       break;
1408
1409     case MINUS_EXPR:
1410       neg_double (int2l, int2h, &low, &hi);
1411       add_double (int1l, int1h, low, hi, &low, &hi);
1412       overflow = OVERFLOW_SUM_SIGN (hi, int2h, int1h);
1413       break;
1414
1415     case MULT_EXPR:
1416       overflow = mul_double (int1l, int1h, int2l, int2h, &low, &hi);
1417       break;
1418
1419     case TRUNC_DIV_EXPR:
1420     case FLOOR_DIV_EXPR: case CEIL_DIV_EXPR:
1421     case EXACT_DIV_EXPR:
1422       /* This is a shortcut for a common special case.  */
1423       if (int2h == 0 && (HOST_WIDE_INT) int2l > 0
1424           && ! TREE_CONSTANT_OVERFLOW (arg1)
1425           && ! TREE_CONSTANT_OVERFLOW (arg2)
1426           && int1h == 0 && (HOST_WIDE_INT) int1l >= 0)
1427         {
1428           if (code == CEIL_DIV_EXPR)
1429             int1l += int2l - 1;
1430
1431           low = int1l / int2l, hi = 0;
1432           break;
1433         }
1434
1435       /* ... fall through ...  */
1436
1437     case ROUND_DIV_EXPR:
1438       if (int2h == 0 && int2l == 0)
1439         return NULL_TREE;
1440       if (int2h == 0 && int2l == 1)
1441         {
1442           low = int1l, hi = int1h;
1443           break;
1444         }
1445       if (int1l == int2l && int1h == int2h
1446           && ! (int1l == 0 && int1h == 0))
1447         {
1448           low = 1, hi = 0;
1449           break;
1450         }
1451       overflow = div_and_round_double (code, uns, int1l, int1h, int2l, int2h,
1452                                        &low, &hi, &garbagel, &garbageh);
1453       break;
1454
1455     case TRUNC_MOD_EXPR:
1456     case FLOOR_MOD_EXPR: case CEIL_MOD_EXPR:
1457       /* This is a shortcut for a common special case.  */
1458       if (int2h == 0 && (HOST_WIDE_INT) int2l > 0
1459           && ! TREE_CONSTANT_OVERFLOW (arg1)
1460           && ! TREE_CONSTANT_OVERFLOW (arg2)
1461           && int1h == 0 && (HOST_WIDE_INT) int1l >= 0)
1462         {
1463           if (code == CEIL_MOD_EXPR)
1464             int1l += int2l - 1;
1465           low = int1l % int2l, hi = 0;
1466           break;
1467         }
1468
1469       /* ... fall through ...  */
1470
1471     case ROUND_MOD_EXPR:
1472       if (int2h == 0 && int2l == 0)
1473         return NULL_TREE;
1474       overflow = div_and_round_double (code, uns,
1475                                        int1l, int1h, int2l, int2h,
1476                                        &garbagel, &garbageh, &low, &hi);
1477       break;
1478
1479     case MIN_EXPR:
1480     case MAX_EXPR:
1481       if (uns)
1482         low = (((unsigned HOST_WIDE_INT) int1h
1483                 < (unsigned HOST_WIDE_INT) int2h)
1484                || (((unsigned HOST_WIDE_INT) int1h
1485                     == (unsigned HOST_WIDE_INT) int2h)
1486                    && int1l < int2l));
1487       else
1488         low = (int1h < int2h
1489                || (int1h == int2h && int1l < int2l));
1490
1491       if (low == (code == MIN_EXPR))
1492         low = int1l, hi = int1h;
1493       else
1494         low = int2l, hi = int2h;
1495       break;
1496
1497     default:
1498       return NULL_TREE;
1499     }
1500
1501   t = build_int_cst_wide (TREE_TYPE (arg1), low, hi);
1502
1503   if (notrunc)
1504     {
1505       /* Propagate overflow flags ourselves.  */
1506       if (((!uns || is_sizetype) && overflow)
1507           | TREE_OVERFLOW (arg1) | TREE_OVERFLOW (arg2))
1508         {
1509           t = copy_node (t);
1510           TREE_OVERFLOW (t) = 1;
1511           TREE_CONSTANT_OVERFLOW (t) = 1;
1512         }
1513       else if (TREE_CONSTANT_OVERFLOW (arg1) | TREE_CONSTANT_OVERFLOW (arg2))
1514         {
1515           t = copy_node (t);
1516           TREE_CONSTANT_OVERFLOW (t) = 1;
1517         }
1518     }
1519   else
1520     t = force_fit_type (t, 1,
1521                         ((!uns || is_sizetype) && overflow)
1522                         | TREE_OVERFLOW (arg1) | TREE_OVERFLOW (arg2),
1523                         TREE_CONSTANT_OVERFLOW (arg1)
1524                         | TREE_CONSTANT_OVERFLOW (arg2));
1525
1526   return t;
1527 }
1528
1529 /* Combine two constants ARG1 and ARG2 under operation CODE to produce a new
1530    constant.  We assume ARG1 and ARG2 have the same data type, or at least
1531    are the same kind of constant and the same machine mode.
1532
1533    If NOTRUNC is nonzero, do not truncate the result to fit the data type.  */
1534
1535 static tree
1536 const_binop (enum tree_code code, tree arg1, tree arg2, int notrunc)
1537 {
1538   STRIP_NOPS (arg1);
1539   STRIP_NOPS (arg2);
1540
1541   if (TREE_CODE (arg1) == INTEGER_CST)
1542     return int_const_binop (code, arg1, arg2, notrunc);
1543
1544   if (TREE_CODE (arg1) == REAL_CST)
1545     {
1546       enum machine_mode mode;
1547       REAL_VALUE_TYPE d1;
1548       REAL_VALUE_TYPE d2;
1549       REAL_VALUE_TYPE value;
1550       REAL_VALUE_TYPE result;
1551       bool inexact;
1552       tree t, type;
1553
1554       /* The following codes are handled by real_arithmetic.  */
1555       switch (code)
1556         {
1557         case PLUS_EXPR:
1558         case MINUS_EXPR:
1559         case MULT_EXPR:
1560         case RDIV_EXPR:
1561         case MIN_EXPR:
1562         case MAX_EXPR:
1563           break;
1564
1565         default:
1566           return NULL_TREE;
1567         }
1568
1569       d1 = TREE_REAL_CST (arg1);
1570       d2 = TREE_REAL_CST (arg2);
1571
1572       type = TREE_TYPE (arg1);
1573       mode = TYPE_MODE (type);
1574
1575       /* Don't perform operation if we honor signaling NaNs and
1576          either operand is a NaN.  */
1577       if (HONOR_SNANS (mode)
1578           && (REAL_VALUE_ISNAN (d1) || REAL_VALUE_ISNAN (d2)))
1579         return NULL_TREE;
1580
1581       /* Don't perform operation if it would raise a division
1582          by zero exception.  */
1583       if (code == RDIV_EXPR
1584           && REAL_VALUES_EQUAL (d2, dconst0)
1585           && (flag_trapping_math || ! MODE_HAS_INFINITIES (mode)))
1586         return NULL_TREE;
1587
1588       /* If either operand is a NaN, just return it.  Otherwise, set up
1589          for floating-point trap; we return an overflow.  */
1590       if (REAL_VALUE_ISNAN (d1))
1591         return arg1;
1592       else if (REAL_VALUE_ISNAN (d2))
1593         return arg2;
1594
1595       inexact = real_arithmetic (&value, code, &d1, &d2);
1596       real_convert (&result, mode, &value);
1597
1598       /* Don't constant fold this floating point operation if
1599          the result has overflowed and flag_trapping_math.  */
1600
1601       if (flag_trapping_math
1602           && MODE_HAS_INFINITIES (mode)
1603           && REAL_VALUE_ISINF (result)
1604           && !REAL_VALUE_ISINF (d1)
1605           && !REAL_VALUE_ISINF (d2))
1606         return NULL_TREE;
1607
1608       /* Don't constant fold this floating point operation if the
1609          result may dependent upon the run-time rounding mode and
1610          flag_rounding_math is set, or if GCC's software emulation
1611          is unable to accurately represent the result.  */
1612
1613       if ((flag_rounding_math
1614            || (REAL_MODE_FORMAT_COMPOSITE_P (mode)
1615                && !flag_unsafe_math_optimizations))
1616           && (inexact || !real_identical (&result, &value)))
1617         return NULL_TREE;
1618
1619       t = build_real (type, result);
1620
1621       TREE_OVERFLOW (t) = TREE_OVERFLOW (arg1) | TREE_OVERFLOW (arg2);
1622       TREE_CONSTANT_OVERFLOW (t)
1623         = TREE_OVERFLOW (t)
1624           | TREE_CONSTANT_OVERFLOW (arg1)
1625           | TREE_CONSTANT_OVERFLOW (arg2);
1626       return t;
1627     }
1628
1629   if (TREE_CODE (arg1) == COMPLEX_CST)
1630     {
1631       tree type = TREE_TYPE (arg1);
1632       tree r1 = TREE_REALPART (arg1);
1633       tree i1 = TREE_IMAGPART (arg1);
1634       tree r2 = TREE_REALPART (arg2);
1635       tree i2 = TREE_IMAGPART (arg2);
1636       tree t;
1637
1638       switch (code)
1639         {
1640         case PLUS_EXPR:
1641           t = build_complex (type,
1642                              const_binop (PLUS_EXPR, r1, r2, notrunc),
1643                              const_binop (PLUS_EXPR, i1, i2, notrunc));
1644           break;
1645
1646         case MINUS_EXPR:
1647           t = build_complex (type,
1648                              const_binop (MINUS_EXPR, r1, r2, notrunc),
1649                              const_binop (MINUS_EXPR, i1, i2, notrunc));
1650           break;
1651
1652         case MULT_EXPR:
1653           t = build_complex (type,
1654                              const_binop (MINUS_EXPR,
1655                                           const_binop (MULT_EXPR,
1656                                                        r1, r2, notrunc),
1657                                           const_binop (MULT_EXPR,
1658                                                        i1, i2, notrunc),
1659                                           notrunc),
1660                              const_binop (PLUS_EXPR,
1661                                           const_binop (MULT_EXPR,
1662                                                        r1, i2, notrunc),
1663                                           const_binop (MULT_EXPR,
1664                                                        i1, r2, notrunc),
1665                                           notrunc));
1666           break;
1667
1668         case RDIV_EXPR:
1669           {
1670             tree t1, t2, real, imag;
1671             tree magsquared
1672               = const_binop (PLUS_EXPR,
1673                              const_binop (MULT_EXPR, r2, r2, notrunc),
1674                              const_binop (MULT_EXPR, i2, i2, notrunc),
1675                              notrunc);
1676
1677             t1 = const_binop (PLUS_EXPR,
1678                               const_binop (MULT_EXPR, r1, r2, notrunc),
1679                               const_binop (MULT_EXPR, i1, i2, notrunc),
1680                               notrunc);
1681             t2 = const_binop (MINUS_EXPR,
1682                               const_binop (MULT_EXPR, i1, r2, notrunc),
1683                               const_binop (MULT_EXPR, r1, i2, notrunc),
1684                               notrunc);
1685
1686             if (INTEGRAL_TYPE_P (TREE_TYPE (r1)))
1687               {
1688                 real = const_binop (TRUNC_DIV_EXPR, t1, magsquared, notrunc);
1689                 imag = const_binop (TRUNC_DIV_EXPR, t2, magsquared, notrunc);
1690               }
1691             else
1692               {
1693                 real = const_binop (RDIV_EXPR, t1, magsquared, notrunc);
1694                 imag = const_binop (RDIV_EXPR, t2, magsquared, notrunc);
1695                 if (!real || !imag)
1696                   return NULL_TREE;
1697               }
1698
1699             t = build_complex (type, real, imag);
1700           }
1701           break;
1702
1703         default:
1704           return NULL_TREE;
1705         }
1706       return t;
1707     }
1708   return NULL_TREE;
1709 }
1710
1711 /* Create a size type INT_CST node with NUMBER sign extended.  KIND
1712    indicates which particular sizetype to create.  */
1713
1714 tree
1715 size_int_kind (HOST_WIDE_INT number, enum size_type_kind kind)
1716 {
1717   return build_int_cst (sizetype_tab[(int) kind], number);
1718 }
1719 \f
1720 /* Combine operands OP1 and OP2 with arithmetic operation CODE.  CODE
1721    is a tree code.  The type of the result is taken from the operands.
1722    Both must be the same type integer type and it must be a size type.
1723    If the operands are constant, so is the result.  */
1724
1725 tree
1726 size_binop (enum tree_code code, tree arg0, tree arg1)
1727 {
1728   tree type = TREE_TYPE (arg0);
1729
1730   gcc_assert (TREE_CODE (type) == INTEGER_TYPE && TYPE_IS_SIZETYPE (type)
1731               && type == TREE_TYPE (arg1));
1732
1733   /* Handle the special case of two integer constants faster.  */
1734   if (TREE_CODE (arg0) == INTEGER_CST && TREE_CODE (arg1) == INTEGER_CST)
1735     {
1736       /* And some specific cases even faster than that.  */
1737       if (code == PLUS_EXPR && integer_zerop (arg0))
1738         return arg1;
1739       else if ((code == MINUS_EXPR || code == PLUS_EXPR)
1740                && integer_zerop (arg1))
1741         return arg0;
1742       else if (code == MULT_EXPR && integer_onep (arg0))
1743         return arg1;
1744
1745       /* Handle general case of two integer constants.  */
1746       return int_const_binop (code, arg0, arg1, 0);
1747     }
1748
1749   if (arg0 == error_mark_node || arg1 == error_mark_node)
1750     return error_mark_node;
1751
1752   return fold_build2 (code, type, arg0, arg1);
1753 }
1754
1755 /* Given two values, either both of sizetype or both of bitsizetype,
1756    compute the difference between the two values.  Return the value
1757    in signed type corresponding to the type of the operands.  */
1758
1759 tree
1760 size_diffop (tree arg0, tree arg1)
1761 {
1762   tree type = TREE_TYPE (arg0);
1763   tree ctype;
1764
1765   gcc_assert (TREE_CODE (type) == INTEGER_TYPE && TYPE_IS_SIZETYPE (type)
1766               && type == TREE_TYPE (arg1));
1767
1768   /* If the type is already signed, just do the simple thing.  */
1769   if (!TYPE_UNSIGNED (type))
1770     return size_binop (MINUS_EXPR, arg0, arg1);
1771
1772   ctype = type == bitsizetype ? sbitsizetype : ssizetype;
1773
1774   /* If either operand is not a constant, do the conversions to the signed
1775      type and subtract.  The hardware will do the right thing with any
1776      overflow in the subtraction.  */
1777   if (TREE_CODE (arg0) != INTEGER_CST || TREE_CODE (arg1) != INTEGER_CST)
1778     return size_binop (MINUS_EXPR, fold_convert (ctype, arg0),
1779                        fold_convert (ctype, arg1));
1780
1781   /* If ARG0 is larger than ARG1, subtract and return the result in CTYPE.
1782      Otherwise, subtract the other way, convert to CTYPE (we know that can't
1783      overflow) and negate (which can't either).  Special-case a result
1784      of zero while we're here.  */
1785   if (tree_int_cst_equal (arg0, arg1))
1786     return build_int_cst (ctype, 0);
1787   else if (tree_int_cst_lt (arg1, arg0))
1788     return fold_convert (ctype, size_binop (MINUS_EXPR, arg0, arg1));
1789   else
1790     return size_binop (MINUS_EXPR, build_int_cst (ctype, 0),
1791                        fold_convert (ctype, size_binop (MINUS_EXPR,
1792                                                         arg1, arg0)));
1793 }
1794 \f
1795 /* A subroutine of fold_convert_const handling conversions of an
1796    INTEGER_CST to another integer type.  */
1797
1798 static tree
1799 fold_convert_const_int_from_int (tree type, tree arg1)
1800 {
1801   tree t;
1802
1803   /* Given an integer constant, make new constant with new type,
1804      appropriately sign-extended or truncated.  */
1805   t = build_int_cst_wide (type, TREE_INT_CST_LOW (arg1),
1806                           TREE_INT_CST_HIGH (arg1));
1807
1808   t = force_fit_type (t,
1809                       /* Don't set the overflow when
1810                          converting a pointer  */
1811                       !POINTER_TYPE_P (TREE_TYPE (arg1)),
1812                       (TREE_INT_CST_HIGH (arg1) < 0
1813                        && (TYPE_UNSIGNED (type)
1814                            < TYPE_UNSIGNED (TREE_TYPE (arg1))))
1815                       | TREE_OVERFLOW (arg1),
1816                       TREE_CONSTANT_OVERFLOW (arg1));
1817
1818   return t;
1819 }
1820
1821 /* A subroutine of fold_convert_const handling conversions a REAL_CST
1822    to an integer type.  */
1823
1824 static tree
1825 fold_convert_const_int_from_real (enum tree_code code, tree type, tree arg1)
1826 {
1827   int overflow = 0;
1828   tree t;
1829
1830   /* The following code implements the floating point to integer
1831      conversion rules required by the Java Language Specification,
1832      that IEEE NaNs are mapped to zero and values that overflow
1833      the target precision saturate, i.e. values greater than
1834      INT_MAX are mapped to INT_MAX, and values less than INT_MIN
1835      are mapped to INT_MIN.  These semantics are allowed by the
1836      C and C++ standards that simply state that the behavior of
1837      FP-to-integer conversion is unspecified upon overflow.  */
1838
1839   HOST_WIDE_INT high, low;
1840   REAL_VALUE_TYPE r;
1841   REAL_VALUE_TYPE x = TREE_REAL_CST (arg1);
1842
1843   switch (code)
1844     {
1845     case FIX_TRUNC_EXPR:
1846       real_trunc (&r, VOIDmode, &x);
1847       break;
1848
1849     case FIX_CEIL_EXPR:
1850       real_ceil (&r, VOIDmode, &x);
1851       break;
1852
1853     case FIX_FLOOR_EXPR:
1854       real_floor (&r, VOIDmode, &x);
1855       break;
1856
1857     case FIX_ROUND_EXPR:
1858       real_round (&r, VOIDmode, &x);
1859       break;
1860
1861     default:
1862       gcc_unreachable ();
1863     }
1864
1865   /* If R is NaN, return zero and show we have an overflow.  */
1866   if (REAL_VALUE_ISNAN (r))
1867     {
1868       overflow = 1;
1869       high = 0;
1870       low = 0;
1871     }
1872
1873   /* See if R is less than the lower bound or greater than the
1874      upper bound.  */
1875
1876   if (! overflow)
1877     {
1878       tree lt = TYPE_MIN_VALUE (type);
1879       REAL_VALUE_TYPE l = real_value_from_int_cst (NULL_TREE, lt);
1880       if (REAL_VALUES_LESS (r, l))
1881         {
1882           overflow = 1;
1883           high = TREE_INT_CST_HIGH (lt);
1884           low = TREE_INT_CST_LOW (lt);
1885         }
1886     }
1887
1888   if (! overflow)
1889     {
1890       tree ut = TYPE_MAX_VALUE (type);
1891       if (ut)
1892         {
1893           REAL_VALUE_TYPE u = real_value_from_int_cst (NULL_TREE, ut);
1894           if (REAL_VALUES_LESS (u, r))
1895             {
1896               overflow = 1;
1897               high = TREE_INT_CST_HIGH (ut);
1898               low = TREE_INT_CST_LOW (ut);
1899             }
1900         }
1901     }
1902
1903   if (! overflow)
1904     REAL_VALUE_TO_INT (&low, &high, r);
1905
1906   t = build_int_cst_wide (type, low, high);
1907
1908   t = force_fit_type (t, -1, overflow | TREE_OVERFLOW (arg1),
1909                       TREE_CONSTANT_OVERFLOW (arg1));
1910   return t;
1911 }
1912
1913 /* A subroutine of fold_convert_const handling conversions a REAL_CST
1914    to another floating point type.  */
1915
1916 static tree
1917 fold_convert_const_real_from_real (tree type, tree arg1)
1918 {
1919   REAL_VALUE_TYPE value;
1920   tree t;
1921
1922   real_convert (&value, TYPE_MODE (type), &TREE_REAL_CST (arg1));
1923   t = build_real (type, value);
1924
1925   TREE_OVERFLOW (t) = TREE_OVERFLOW (arg1);
1926   TREE_CONSTANT_OVERFLOW (t)
1927     = TREE_OVERFLOW (t) | TREE_CONSTANT_OVERFLOW (arg1);
1928   return t;
1929 }
1930
1931 /* Attempt to fold type conversion operation CODE of expression ARG1 to
1932    type TYPE.  If no simplification can be done return NULL_TREE.  */
1933
1934 static tree
1935 fold_convert_const (enum tree_code code, tree type, tree arg1)
1936 {
1937   if (TREE_TYPE (arg1) == type)
1938     return arg1;
1939
1940   if (POINTER_TYPE_P (type) || INTEGRAL_TYPE_P (type))
1941     {
1942       if (TREE_CODE (arg1) == INTEGER_CST)
1943         return fold_convert_const_int_from_int (type, arg1);
1944       else if (TREE_CODE (arg1) == REAL_CST)
1945         return fold_convert_const_int_from_real (code, type, arg1);
1946     }
1947   else if (TREE_CODE (type) == REAL_TYPE)
1948     {
1949       if (TREE_CODE (arg1) == INTEGER_CST)
1950         return build_real_from_int_cst (type, arg1);
1951       if (TREE_CODE (arg1) == REAL_CST)
1952         return fold_convert_const_real_from_real (type, arg1);
1953     }
1954   return NULL_TREE;
1955 }
1956
1957 /* Construct a vector of zero elements of vector type TYPE.  */
1958
1959 static tree
1960 build_zero_vector (tree type)
1961 {
1962   tree elem, list;
1963   int i, units;
1964
1965   elem = fold_convert_const (NOP_EXPR, TREE_TYPE (type), integer_zero_node);
1966   units = TYPE_VECTOR_SUBPARTS (type);
1967
1968   list = NULL_TREE;
1969   for (i = 0; i < units; i++)
1970     list = tree_cons (NULL_TREE, elem, list);
1971   return build_vector (type, list);
1972 }
1973
1974 /* Convert expression ARG to type TYPE.  Used by the middle-end for
1975    simple conversions in preference to calling the front-end's convert.  */
1976
1977 tree
1978 fold_convert (tree type, tree arg)
1979 {
1980   tree orig = TREE_TYPE (arg);
1981   tree tem;
1982
1983   if (type == orig)
1984     return arg;
1985
1986   if (TREE_CODE (arg) == ERROR_MARK
1987       || TREE_CODE (type) == ERROR_MARK
1988       || TREE_CODE (orig) == ERROR_MARK)
1989     return error_mark_node;
1990
1991   if (TYPE_MAIN_VARIANT (type) == TYPE_MAIN_VARIANT (orig)
1992       || lang_hooks.types_compatible_p (TYPE_MAIN_VARIANT (type),
1993                                         TYPE_MAIN_VARIANT (orig)))
1994     return fold_build1 (NOP_EXPR, type, arg);
1995
1996   switch (TREE_CODE (type))
1997     {
1998     case INTEGER_TYPE: case ENUMERAL_TYPE: case BOOLEAN_TYPE:
1999     case POINTER_TYPE: case REFERENCE_TYPE:
2000     case OFFSET_TYPE:
2001       if (TREE_CODE (arg) == INTEGER_CST)
2002         {
2003           tem = fold_convert_const (NOP_EXPR, type, arg);
2004           if (tem != NULL_TREE)
2005             return tem;
2006         }
2007       if (INTEGRAL_TYPE_P (orig) || POINTER_TYPE_P (orig)
2008           || TREE_CODE (orig) == OFFSET_TYPE)
2009         return fold_build1 (NOP_EXPR, type, arg);
2010       if (TREE_CODE (orig) == COMPLEX_TYPE)
2011         {
2012           tem = fold_build1 (REALPART_EXPR, TREE_TYPE (orig), arg);
2013           return fold_convert (type, tem);
2014         }
2015       gcc_assert (TREE_CODE (orig) == VECTOR_TYPE
2016                   && tree_int_cst_equal (TYPE_SIZE (type), TYPE_SIZE (orig)));
2017       return fold_build1 (NOP_EXPR, type, arg);
2018
2019     case REAL_TYPE:
2020       if (TREE_CODE (arg) == INTEGER_CST)
2021         {
2022           tem = fold_convert_const (FLOAT_EXPR, type, arg);
2023           if (tem != NULL_TREE)
2024             return tem;
2025         }
2026       else if (TREE_CODE (arg) == REAL_CST)
2027         {
2028           tem = fold_convert_const (NOP_EXPR, type, arg);
2029           if (tem != NULL_TREE)
2030             return tem;
2031         }
2032
2033       switch (TREE_CODE (orig))
2034         {
2035         case INTEGER_TYPE:
2036         case BOOLEAN_TYPE: case ENUMERAL_TYPE:
2037         case POINTER_TYPE: case REFERENCE_TYPE:
2038           return fold_build1 (FLOAT_EXPR, type, arg);
2039
2040         case REAL_TYPE:
2041           return fold_build1 (NOP_EXPR, type, arg);
2042
2043         case COMPLEX_TYPE:
2044           tem = fold_build1 (REALPART_EXPR, TREE_TYPE (orig), arg);
2045           return fold_convert (type, tem);
2046
2047         default:
2048           gcc_unreachable ();
2049         }
2050
2051     case COMPLEX_TYPE:
2052       switch (TREE_CODE (orig))
2053         {
2054         case INTEGER_TYPE:
2055         case BOOLEAN_TYPE: case ENUMERAL_TYPE:
2056         case POINTER_TYPE: case REFERENCE_TYPE:
2057         case REAL_TYPE:
2058           return build2 (COMPLEX_EXPR, type,
2059                          fold_convert (TREE_TYPE (type), arg),
2060                          fold_convert (TREE_TYPE (type), integer_zero_node));
2061         case COMPLEX_TYPE:
2062           {
2063             tree rpart, ipart;
2064
2065             if (TREE_CODE (arg) == COMPLEX_EXPR)
2066               {
2067                 rpart = fold_convert (TREE_TYPE (type), TREE_OPERAND (arg, 0));
2068                 ipart = fold_convert (TREE_TYPE (type), TREE_OPERAND (arg, 1));
2069                 return fold_build2 (COMPLEX_EXPR, type, rpart, ipart);
2070               }
2071
2072             arg = save_expr (arg);
2073             rpart = fold_build1 (REALPART_EXPR, TREE_TYPE (orig), arg);
2074             ipart = fold_build1 (IMAGPART_EXPR, TREE_TYPE (orig), arg);
2075             rpart = fold_convert (TREE_TYPE (type), rpart);
2076             ipart = fold_convert (TREE_TYPE (type), ipart);
2077             return fold_build2 (COMPLEX_EXPR, type, rpart, ipart);
2078           }
2079
2080         default:
2081           gcc_unreachable ();
2082         }
2083
2084     case VECTOR_TYPE:
2085       if (integer_zerop (arg))
2086         return build_zero_vector (type);
2087       gcc_assert (tree_int_cst_equal (TYPE_SIZE (type), TYPE_SIZE (orig)));
2088       gcc_assert (INTEGRAL_TYPE_P (orig) || POINTER_TYPE_P (orig)
2089                   || TREE_CODE (orig) == VECTOR_TYPE);
2090       return fold_build1 (VIEW_CONVERT_EXPR, type, arg);
2091
2092     case VOID_TYPE:
2093       return fold_build1 (NOP_EXPR, type, fold_ignored_result (arg));
2094
2095     default:
2096       gcc_unreachable ();
2097     }
2098 }
2099 \f
2100 /* Return false if expr can be assumed not to be an lvalue, true
2101    otherwise.  */
2102
2103 static bool
2104 maybe_lvalue_p (tree x)
2105 {
2106   /* We only need to wrap lvalue tree codes.  */
2107   switch (TREE_CODE (x))
2108   {
2109   case VAR_DECL:
2110   case PARM_DECL:
2111   case RESULT_DECL:
2112   case LABEL_DECL:
2113   case FUNCTION_DECL:
2114   case SSA_NAME:
2115
2116   case COMPONENT_REF:
2117   case INDIRECT_REF:
2118   case ALIGN_INDIRECT_REF:
2119   case MISALIGNED_INDIRECT_REF:
2120   case ARRAY_REF:
2121   case ARRAY_RANGE_REF:
2122   case BIT_FIELD_REF:
2123   case OBJ_TYPE_REF:
2124
2125   case REALPART_EXPR:
2126   case IMAGPART_EXPR:
2127   case PREINCREMENT_EXPR:
2128   case PREDECREMENT_EXPR:
2129   case SAVE_EXPR:
2130   case TRY_CATCH_EXPR:
2131   case WITH_CLEANUP_EXPR:
2132   case COMPOUND_EXPR:
2133   case MODIFY_EXPR:
2134   case TARGET_EXPR:
2135   case COND_EXPR:
2136   case BIND_EXPR:
2137   case MIN_EXPR:
2138   case MAX_EXPR:
2139     break;
2140
2141   default:
2142     /* Assume the worst for front-end tree codes.  */
2143     if ((int)TREE_CODE (x) >= NUM_TREE_CODES)
2144       break;
2145     return false;
2146   }
2147
2148   return true;
2149 }
2150
2151 /* Return an expr equal to X but certainly not valid as an lvalue.  */
2152
2153 tree
2154 non_lvalue (tree x)
2155 {
2156   /* While we are in GIMPLE, NON_LVALUE_EXPR doesn't mean anything to
2157      us.  */
2158   if (in_gimple_form)
2159     return x;
2160
2161   if (! maybe_lvalue_p (x))
2162     return x;
2163   return build1 (NON_LVALUE_EXPR, TREE_TYPE (x), x);
2164 }
2165
2166 /* Nonzero means lvalues are limited to those valid in pedantic ANSI C.
2167    Zero means allow extended lvalues.  */
2168
2169 int pedantic_lvalues;
2170
2171 /* When pedantic, return an expr equal to X but certainly not valid as a
2172    pedantic lvalue.  Otherwise, return X.  */
2173
2174 static tree
2175 pedantic_non_lvalue (tree x)
2176 {
2177   if (pedantic_lvalues)
2178     return non_lvalue (x);
2179   else
2180     return x;
2181 }
2182 \f
2183 /* Given a tree comparison code, return the code that is the logical inverse
2184    of the given code.  It is not safe to do this for floating-point
2185    comparisons, except for NE_EXPR and EQ_EXPR, so we receive a machine mode
2186    as well: if reversing the comparison is unsafe, return ERROR_MARK.  */
2187
2188 enum tree_code
2189 invert_tree_comparison (enum tree_code code, bool honor_nans)
2190 {
2191   if (honor_nans && flag_trapping_math)
2192     return ERROR_MARK;
2193
2194   switch (code)
2195     {
2196     case EQ_EXPR:
2197       return NE_EXPR;
2198     case NE_EXPR:
2199       return EQ_EXPR;
2200     case GT_EXPR:
2201       return honor_nans ? UNLE_EXPR : LE_EXPR;
2202     case GE_EXPR:
2203       return honor_nans ? UNLT_EXPR : LT_EXPR;
2204     case LT_EXPR:
2205       return honor_nans ? UNGE_EXPR : GE_EXPR;
2206     case LE_EXPR:
2207       return honor_nans ? UNGT_EXPR : GT_EXPR;
2208     case LTGT_EXPR:
2209       return UNEQ_EXPR;
2210     case UNEQ_EXPR:
2211       return LTGT_EXPR;
2212     case UNGT_EXPR:
2213       return LE_EXPR;
2214     case UNGE_EXPR:
2215       return LT_EXPR;
2216     case UNLT_EXPR:
2217       return GE_EXPR;
2218     case UNLE_EXPR:
2219       return GT_EXPR;
2220     case ORDERED_EXPR:
2221       return UNORDERED_EXPR;
2222     case UNORDERED_EXPR:
2223       return ORDERED_EXPR;
2224     default:
2225       gcc_unreachable ();
2226     }
2227 }
2228
2229 /* Similar, but return the comparison that results if the operands are
2230    swapped.  This is safe for floating-point.  */
2231
2232 enum tree_code
2233 swap_tree_comparison (enum tree_code code)
2234 {
2235   switch (code)
2236     {
2237     case EQ_EXPR:
2238     case NE_EXPR:
2239     case ORDERED_EXPR:
2240     case UNORDERED_EXPR:
2241     case LTGT_EXPR:
2242     case UNEQ_EXPR:
2243       return code;
2244     case GT_EXPR:
2245       return LT_EXPR;
2246     case GE_EXPR:
2247       return LE_EXPR;
2248     case LT_EXPR:
2249       return GT_EXPR;
2250     case LE_EXPR:
2251       return GE_EXPR;
2252     case UNGT_EXPR:
2253       return UNLT_EXPR;
2254     case UNGE_EXPR:
2255       return UNLE_EXPR;
2256     case UNLT_EXPR:
2257       return UNGT_EXPR;
2258     case UNLE_EXPR:
2259       return UNGE_EXPR;
2260     default:
2261       gcc_unreachable ();
2262     }
2263 }
2264
2265
2266 /* Convert a comparison tree code from an enum tree_code representation
2267    into a compcode bit-based encoding.  This function is the inverse of
2268    compcode_to_comparison.  */
2269
2270 static enum comparison_code
2271 comparison_to_compcode (enum tree_code code)
2272 {
2273   switch (code)
2274     {
2275     case LT_EXPR:
2276       return COMPCODE_LT;
2277     case EQ_EXPR:
2278       return COMPCODE_EQ;
2279     case LE_EXPR:
2280       return COMPCODE_LE;
2281     case GT_EXPR:
2282       return COMPCODE_GT;
2283     case NE_EXPR:
2284       return COMPCODE_NE;
2285     case GE_EXPR:
2286       return COMPCODE_GE;
2287     case ORDERED_EXPR:
2288       return COMPCODE_ORD;
2289     case UNORDERED_EXPR:
2290       return COMPCODE_UNORD;
2291     case UNLT_EXPR:
2292       return COMPCODE_UNLT;
2293     case UNEQ_EXPR:
2294       return COMPCODE_UNEQ;
2295     case UNLE_EXPR:
2296       return COMPCODE_UNLE;
2297     case UNGT_EXPR:
2298       return COMPCODE_UNGT;
2299     case LTGT_EXPR:
2300       return COMPCODE_LTGT;
2301     case UNGE_EXPR:
2302       return COMPCODE_UNGE;
2303     default:
2304       gcc_unreachable ();
2305     }
2306 }
2307
2308 /* Convert a compcode bit-based encoding of a comparison operator back
2309    to GCC's enum tree_code representation.  This function is the
2310    inverse of comparison_to_compcode.  */
2311
2312 static enum tree_code
2313 compcode_to_comparison (enum comparison_code code)
2314 {
2315   switch (code)
2316     {
2317     case COMPCODE_LT:
2318       return LT_EXPR;
2319     case COMPCODE_EQ:
2320       return EQ_EXPR;
2321     case COMPCODE_LE:
2322       return LE_EXPR;
2323     case COMPCODE_GT:
2324       return GT_EXPR;
2325     case COMPCODE_NE:
2326       return NE_EXPR;
2327     case COMPCODE_GE:
2328       return GE_EXPR;
2329     case COMPCODE_ORD:
2330       return ORDERED_EXPR;
2331     case COMPCODE_UNORD:
2332       return UNORDERED_EXPR;
2333     case COMPCODE_UNLT:
2334       return UNLT_EXPR;
2335     case COMPCODE_UNEQ:
2336       return UNEQ_EXPR;
2337     case COMPCODE_UNLE:
2338       return UNLE_EXPR;
2339     case COMPCODE_UNGT:
2340       return UNGT_EXPR;
2341     case COMPCODE_LTGT:
2342       return LTGT_EXPR;
2343     case COMPCODE_UNGE:
2344       return UNGE_EXPR;
2345     default:
2346       gcc_unreachable ();
2347     }
2348 }
2349
2350 /* Return a tree for the comparison which is the combination of
2351    doing the AND or OR (depending on CODE) of the two operations LCODE
2352    and RCODE on the identical operands LL_ARG and LR_ARG.  Take into account
2353    the possibility of trapping if the mode has NaNs, and return NULL_TREE
2354    if this makes the transformation invalid.  */
2355
2356 tree
2357 combine_comparisons (enum tree_code code, enum tree_code lcode,
2358                      enum tree_code rcode, tree truth_type,
2359                      tree ll_arg, tree lr_arg)
2360 {
2361   bool honor_nans = HONOR_NANS (TYPE_MODE (TREE_TYPE (ll_arg)));
2362   enum comparison_code lcompcode = comparison_to_compcode (lcode);
2363   enum comparison_code rcompcode = comparison_to_compcode (rcode);
2364   enum comparison_code compcode;
2365
2366   switch (code)
2367     {
2368     case TRUTH_AND_EXPR: case TRUTH_ANDIF_EXPR:
2369       compcode = lcompcode & rcompcode;
2370       break;
2371
2372     case TRUTH_OR_EXPR: case TRUTH_ORIF_EXPR:
2373       compcode = lcompcode | rcompcode;
2374       break;
2375
2376     default:
2377       return NULL_TREE;
2378     }
2379
2380   if (!honor_nans)
2381     {
2382       /* Eliminate unordered comparisons, as well as LTGT and ORD
2383          which are not used unless the mode has NaNs.  */
2384       compcode &= ~COMPCODE_UNORD;
2385       if (compcode == COMPCODE_LTGT)
2386         compcode = COMPCODE_NE;
2387       else if (compcode == COMPCODE_ORD)
2388         compcode = COMPCODE_TRUE;
2389     }
2390    else if (flag_trapping_math)
2391      {
2392         /* Check that the original operation and the optimized ones will trap
2393            under the same condition.  */
2394         bool ltrap = (lcompcode & COMPCODE_UNORD) == 0
2395                      && (lcompcode != COMPCODE_EQ)
2396                      && (lcompcode != COMPCODE_ORD);
2397         bool rtrap = (rcompcode & COMPCODE_UNORD) == 0
2398                      && (rcompcode != COMPCODE_EQ)
2399                      && (rcompcode != COMPCODE_ORD);
2400         bool trap = (compcode & COMPCODE_UNORD) == 0
2401                     && (compcode != COMPCODE_EQ)
2402                     && (compcode != COMPCODE_ORD);
2403
2404         /* In a short-circuited boolean expression the LHS might be
2405            such that the RHS, if evaluated, will never trap.  For
2406            example, in ORD (x, y) && (x < y), we evaluate the RHS only
2407            if neither x nor y is NaN.  (This is a mixed blessing: for
2408            example, the expression above will never trap, hence
2409            optimizing it to x < y would be invalid).  */
2410         if ((code == TRUTH_ORIF_EXPR && (lcompcode & COMPCODE_UNORD))
2411             || (code == TRUTH_ANDIF_EXPR && !(lcompcode & COMPCODE_UNORD)))
2412           rtrap = false;
2413
2414         /* If the comparison was short-circuited, and only the RHS
2415            trapped, we may now generate a spurious trap.  */
2416         if (rtrap && !ltrap
2417             && (code == TRUTH_ANDIF_EXPR || code == TRUTH_ORIF_EXPR))
2418           return NULL_TREE;
2419
2420         /* If we changed the conditions that cause a trap, we lose.  */
2421         if ((ltrap || rtrap) != trap)
2422           return NULL_TREE;
2423       }
2424
2425   if (compcode == COMPCODE_TRUE)
2426     return constant_boolean_node (true, truth_type);
2427   else if (compcode == COMPCODE_FALSE)
2428     return constant_boolean_node (false, truth_type);
2429   else
2430     return fold_build2 (compcode_to_comparison (compcode),
2431                         truth_type, ll_arg, lr_arg);
2432 }
2433
2434 /* Return nonzero if CODE is a tree code that represents a truth value.  */
2435
2436 static int
2437 truth_value_p (enum tree_code code)
2438 {
2439   return (TREE_CODE_CLASS (code) == tcc_comparison
2440           || code == TRUTH_AND_EXPR || code == TRUTH_ANDIF_EXPR
2441           || code == TRUTH_OR_EXPR || code == TRUTH_ORIF_EXPR
2442           || code == TRUTH_XOR_EXPR || code == TRUTH_NOT_EXPR);
2443 }
2444 \f
2445 /* Return nonzero if two operands (typically of the same tree node)
2446    are necessarily equal.  If either argument has side-effects this
2447    function returns zero.  FLAGS modifies behavior as follows:
2448
2449    If OEP_ONLY_CONST is set, only return nonzero for constants.
2450    This function tests whether the operands are indistinguishable;
2451    it does not test whether they are equal using C's == operation.
2452    The distinction is important for IEEE floating point, because
2453    (1) -0.0 and 0.0 are distinguishable, but -0.0==0.0, and
2454    (2) two NaNs may be indistinguishable, but NaN!=NaN.
2455
2456    If OEP_ONLY_CONST is unset, a VAR_DECL is considered equal to itself
2457    even though it may hold multiple values during a function.
2458    This is because a GCC tree node guarantees that nothing else is
2459    executed between the evaluation of its "operands" (which may often
2460    be evaluated in arbitrary order).  Hence if the operands themselves
2461    don't side-effect, the VAR_DECLs, PARM_DECLs etc... must hold the
2462    same value in each operand/subexpression.  Hence leaving OEP_ONLY_CONST
2463    unset means assuming isochronic (or instantaneous) tree equivalence.
2464    Unless comparing arbitrary expression trees, such as from different
2465    statements, this flag can usually be left unset.
2466
2467    If OEP_PURE_SAME is set, then pure functions with identical arguments
2468    are considered the same.  It is used when the caller has other ways
2469    to ensure that global memory is unchanged in between.  */
2470
2471 int
2472 operand_equal_p (tree arg0, tree arg1, unsigned int flags)
2473 {
2474   /* If either is ERROR_MARK, they aren't equal.  */
2475   if (TREE_CODE (arg0) == ERROR_MARK || TREE_CODE (arg1) == ERROR_MARK)
2476     return 0;
2477
2478   /* If both types don't have the same signedness, then we can't consider
2479      them equal.  We must check this before the STRIP_NOPS calls
2480      because they may change the signedness of the arguments.  */
2481   if (TYPE_UNSIGNED (TREE_TYPE (arg0)) != TYPE_UNSIGNED (TREE_TYPE (arg1)))
2482     return 0;
2483
2484   STRIP_NOPS (arg0);
2485   STRIP_NOPS (arg1);
2486
2487   if (TREE_CODE (arg0) != TREE_CODE (arg1)
2488       /* This is needed for conversions and for COMPONENT_REF.
2489          Might as well play it safe and always test this.  */
2490       || TREE_CODE (TREE_TYPE (arg0)) == ERROR_MARK
2491       || TREE_CODE (TREE_TYPE (arg1)) == ERROR_MARK
2492       || TYPE_MODE (TREE_TYPE (arg0)) != TYPE_MODE (TREE_TYPE (arg1)))
2493     return 0;
2494
2495   /* If ARG0 and ARG1 are the same SAVE_EXPR, they are necessarily equal.
2496      We don't care about side effects in that case because the SAVE_EXPR
2497      takes care of that for us. In all other cases, two expressions are
2498      equal if they have no side effects.  If we have two identical
2499      expressions with side effects that should be treated the same due
2500      to the only side effects being identical SAVE_EXPR's, that will
2501      be detected in the recursive calls below.  */
2502   if (arg0 == arg1 && ! (flags & OEP_ONLY_CONST)
2503       && (TREE_CODE (arg0) == SAVE_EXPR
2504           || (! TREE_SIDE_EFFECTS (arg0) && ! TREE_SIDE_EFFECTS (arg1))))
2505     return 1;
2506
2507   /* Next handle constant cases, those for which we can return 1 even
2508      if ONLY_CONST is set.  */
2509   if (TREE_CONSTANT (arg0) && TREE_CONSTANT (arg1))
2510     switch (TREE_CODE (arg0))
2511       {
2512       case INTEGER_CST:
2513         return (! TREE_CONSTANT_OVERFLOW (arg0)
2514                 && ! TREE_CONSTANT_OVERFLOW (arg1)
2515                 && tree_int_cst_equal (arg0, arg1));
2516
2517       case REAL_CST:
2518         return (! TREE_CONSTANT_OVERFLOW (arg0)
2519                 && ! TREE_CONSTANT_OVERFLOW (arg1)
2520                 && REAL_VALUES_IDENTICAL (TREE_REAL_CST (arg0),
2521                                           TREE_REAL_CST (arg1)));
2522
2523       case VECTOR_CST:
2524         {
2525           tree v1, v2;
2526
2527           if (TREE_CONSTANT_OVERFLOW (arg0)
2528               || TREE_CONSTANT_OVERFLOW (arg1))
2529             return 0;
2530
2531           v1 = TREE_VECTOR_CST_ELTS (arg0);
2532           v2 = TREE_VECTOR_CST_ELTS (arg1);
2533           while (v1 && v2)
2534             {
2535               if (!operand_equal_p (TREE_VALUE (v1), TREE_VALUE (v2),
2536                                     flags))
2537                 return 0;
2538               v1 = TREE_CHAIN (v1);
2539               v2 = TREE_CHAIN (v2);
2540             }
2541
2542           return v1 == v2;
2543         }
2544
2545       case COMPLEX_CST:
2546         return (operand_equal_p (TREE_REALPART (arg0), TREE_REALPART (arg1),
2547                                  flags)
2548                 && operand_equal_p (TREE_IMAGPART (arg0), TREE_IMAGPART (arg1),
2549                                     flags));
2550
2551       case STRING_CST:
2552         return (TREE_STRING_LENGTH (arg0) == TREE_STRING_LENGTH (arg1)
2553                 && ! memcmp (TREE_STRING_POINTER (arg0),
2554                               TREE_STRING_POINTER (arg1),
2555                               TREE_STRING_LENGTH (arg0)));
2556
2557       case ADDR_EXPR:
2558         return operand_equal_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg1, 0),
2559                                 0);
2560       default:
2561         break;
2562       }
2563
2564   if (flags & OEP_ONLY_CONST)
2565     return 0;
2566
2567 /* Define macros to test an operand from arg0 and arg1 for equality and a
2568    variant that allows null and views null as being different from any
2569    non-null value.  In the latter case, if either is null, the both
2570    must be; otherwise, do the normal comparison.  */
2571 #define OP_SAME(N) operand_equal_p (TREE_OPERAND (arg0, N),     \
2572                                     TREE_OPERAND (arg1, N), flags)
2573
2574 #define OP_SAME_WITH_NULL(N)                            \
2575   ((!TREE_OPERAND (arg0, N) || !TREE_OPERAND (arg1, N)) \
2576    ? TREE_OPERAND (arg0, N) == TREE_OPERAND (arg1, N) : OP_SAME (N))
2577
2578   switch (TREE_CODE_CLASS (TREE_CODE (arg0)))
2579     {
2580     case tcc_unary:
2581       /* Two conversions are equal only if signedness and modes match.  */
2582       switch (TREE_CODE (arg0))
2583         {
2584         case NOP_EXPR:
2585         case CONVERT_EXPR:
2586         case FIX_CEIL_EXPR:
2587         case FIX_TRUNC_EXPR:
2588         case FIX_FLOOR_EXPR:
2589         case FIX_ROUND_EXPR:
2590           if (TYPE_UNSIGNED (TREE_TYPE (arg0))
2591               != TYPE_UNSIGNED (TREE_TYPE (arg1)))
2592             return 0;
2593           break;
2594         default:
2595           break;
2596         }
2597
2598       return OP_SAME (0);
2599
2600
2601     case tcc_comparison:
2602     case tcc_binary:
2603       if (OP_SAME (0) && OP_SAME (1))
2604         return 1;
2605
2606       /* For commutative ops, allow the other order.  */
2607       return (commutative_tree_code (TREE_CODE (arg0))
2608               && operand_equal_p (TREE_OPERAND (arg0, 0),
2609                                   TREE_OPERAND (arg1, 1), flags)
2610               && operand_equal_p (TREE_OPERAND (arg0, 1),
2611                                   TREE_OPERAND (arg1, 0), flags));
2612
2613     case tcc_reference:
2614       /* If either of the pointer (or reference) expressions we are
2615          dereferencing contain a side effect, these cannot be equal.  */
2616       if (TREE_SIDE_EFFECTS (arg0)
2617           || TREE_SIDE_EFFECTS (arg1))
2618         return 0;
2619
2620       switch (TREE_CODE (arg0))
2621         {
2622         case INDIRECT_REF:
2623         case ALIGN_INDIRECT_REF:
2624         case MISALIGNED_INDIRECT_REF:
2625         case REALPART_EXPR:
2626         case IMAGPART_EXPR:
2627           return OP_SAME (0);
2628
2629         case ARRAY_REF:
2630         case ARRAY_RANGE_REF:
2631           /* Operands 2 and 3 may be null.  */
2632           return (OP_SAME (0)
2633                   && OP_SAME (1)
2634                   && OP_SAME_WITH_NULL (2)
2635                   && OP_SAME_WITH_NULL (3));
2636
2637         case COMPONENT_REF:
2638           /* Handle operand 2 the same as for ARRAY_REF.  Operand 0
2639              may be NULL when we're called to compare MEM_EXPRs.  */
2640           return OP_SAME_WITH_NULL (0)
2641                  && OP_SAME (1)
2642                  && OP_SAME_WITH_NULL (2);
2643
2644         case BIT_FIELD_REF:
2645           return OP_SAME (0) && OP_SAME (1) && OP_SAME (2);
2646
2647         default:
2648           return 0;
2649         }
2650
2651     case tcc_expression:
2652       switch (TREE_CODE (arg0))
2653         {
2654         case ADDR_EXPR:
2655         case TRUTH_NOT_EXPR:
2656           return OP_SAME (0);
2657
2658         case TRUTH_ANDIF_EXPR:
2659         case TRUTH_ORIF_EXPR:
2660           return OP_SAME (0) && OP_SAME (1);
2661
2662         case TRUTH_AND_EXPR:
2663         case TRUTH_OR_EXPR:
2664         case TRUTH_XOR_EXPR:
2665           if (OP_SAME (0) && OP_SAME (1))
2666             return 1;
2667
2668           /* Otherwise take into account this is a commutative operation.  */
2669           return (operand_equal_p (TREE_OPERAND (arg0, 0),
2670                                    TREE_OPERAND (arg1, 1), flags)
2671                   && operand_equal_p (TREE_OPERAND (arg0, 1),
2672                                       TREE_OPERAND (arg1, 0), flags));
2673
2674         case CALL_EXPR:
2675           /* If the CALL_EXPRs call different functions, then they
2676              clearly can not be equal.  */
2677           if (!OP_SAME (0))
2678             return 0;
2679
2680           {
2681             unsigned int cef = call_expr_flags (arg0);
2682             if (flags & OEP_PURE_SAME)
2683               cef &= ECF_CONST | ECF_PURE;
2684             else
2685               cef &= ECF_CONST;
2686             if (!cef)
2687               return 0;
2688           }
2689
2690           /* Now see if all the arguments are the same.  operand_equal_p
2691              does not handle TREE_LIST, so we walk the operands here
2692              feeding them to operand_equal_p.  */
2693           arg0 = TREE_OPERAND (arg0, 1);
2694           arg1 = TREE_OPERAND (arg1, 1);
2695           while (arg0 && arg1)
2696             {
2697               if (! operand_equal_p (TREE_VALUE (arg0), TREE_VALUE (arg1),
2698                                      flags))
2699                 return 0;
2700
2701               arg0 = TREE_CHAIN (arg0);
2702               arg1 = TREE_CHAIN (arg1);
2703             }
2704
2705           /* If we get here and both argument lists are exhausted
2706              then the CALL_EXPRs are equal.  */
2707           return ! (arg0 || arg1);
2708
2709         default:
2710           return 0;
2711         }
2712
2713     case tcc_declaration:
2714       /* Consider __builtin_sqrt equal to sqrt.  */
2715       return (TREE_CODE (arg0) == FUNCTION_DECL
2716               && DECL_BUILT_IN (arg0) && DECL_BUILT_IN (arg1)
2717               && DECL_BUILT_IN_CLASS (arg0) == DECL_BUILT_IN_CLASS (arg1)
2718               && DECL_FUNCTION_CODE (arg0) == DECL_FUNCTION_CODE (arg1));
2719
2720     default:
2721       return 0;
2722     }
2723
2724 #undef OP_SAME
2725 #undef OP_SAME_WITH_NULL
2726 }
2727 \f
2728 /* Similar to operand_equal_p, but see if ARG0 might have been made by
2729    shorten_compare from ARG1 when ARG1 was being compared with OTHER.
2730
2731    When in doubt, return 0.  */
2732
2733 static int
2734 operand_equal_for_comparison_p (tree arg0, tree arg1, tree other)
2735 {
2736   int unsignedp1, unsignedpo;
2737   tree primarg0, primarg1, primother;
2738   unsigned int correct_width;
2739
2740   if (operand_equal_p (arg0, arg1, 0))
2741     return 1;
2742
2743   if (! INTEGRAL_TYPE_P (TREE_TYPE (arg0))
2744       || ! INTEGRAL_TYPE_P (TREE_TYPE (arg1)))
2745     return 0;
2746
2747   /* Discard any conversions that don't change the modes of ARG0 and ARG1
2748      and see if the inner values are the same.  This removes any
2749      signedness comparison, which doesn't matter here.  */
2750   primarg0 = arg0, primarg1 = arg1;
2751   STRIP_NOPS (primarg0);
2752   STRIP_NOPS (primarg1);
2753   if (operand_equal_p (primarg0, primarg1, 0))
2754     return 1;
2755
2756   /* Duplicate what shorten_compare does to ARG1 and see if that gives the
2757      actual comparison operand, ARG0.
2758
2759      First throw away any conversions to wider types
2760      already present in the operands.  */
2761
2762   primarg1 = get_narrower (arg1, &unsignedp1);
2763   primother = get_narrower (other, &unsignedpo);
2764
2765   correct_width = TYPE_PRECISION (TREE_TYPE (arg1));
2766   if (unsignedp1 == unsignedpo
2767       && TYPE_PRECISION (TREE_TYPE (primarg1)) < correct_width
2768       && TYPE_PRECISION (TREE_TYPE (primother)) < correct_width)
2769     {
2770       tree type = TREE_TYPE (arg0);
2771
2772       /* Make sure shorter operand is extended the right way
2773          to match the longer operand.  */
2774       primarg1 = fold_convert (lang_hooks.types.signed_or_unsigned_type
2775                                (unsignedp1, TREE_TYPE (primarg1)), primarg1);
2776
2777       if (operand_equal_p (arg0, fold_convert (type, primarg1), 0))
2778         return 1;
2779     }
2780
2781   return 0;
2782 }
2783 \f
2784 /* See if ARG is an expression that is either a comparison or is performing
2785    arithmetic on comparisons.  The comparisons must only be comparing
2786    two different values, which will be stored in *CVAL1 and *CVAL2; if
2787    they are nonzero it means that some operands have already been found.
2788    No variables may be used anywhere else in the expression except in the
2789    comparisons.  If SAVE_P is true it means we removed a SAVE_EXPR around
2790    the expression and save_expr needs to be called with CVAL1 and CVAL2.
2791
2792    If this is true, return 1.  Otherwise, return zero.  */
2793
2794 static int
2795 twoval_comparison_p (tree arg, tree *cval1, tree *cval2, int *save_p)
2796 {
2797   enum tree_code code = TREE_CODE (arg);
2798   enum tree_code_class class = TREE_CODE_CLASS (code);
2799
2800   /* We can handle some of the tcc_expression cases here.  */
2801   if (class == tcc_expression && code == TRUTH_NOT_EXPR)
2802     class = tcc_unary;
2803   else if (class == tcc_expression
2804            && (code == TRUTH_ANDIF_EXPR || code == TRUTH_ORIF_EXPR
2805                || code == COMPOUND_EXPR))
2806     class = tcc_binary;
2807
2808   else if (class == tcc_expression && code == SAVE_EXPR
2809            && ! TREE_SIDE_EFFECTS (TREE_OPERAND (arg, 0)))
2810     {
2811       /* If we've already found a CVAL1 or CVAL2, this expression is
2812          two complex to handle.  */
2813       if (*cval1 || *cval2)
2814         return 0;
2815
2816       class = tcc_unary;
2817       *save_p = 1;
2818     }
2819
2820   switch (class)
2821     {
2822     case tcc_unary:
2823       return twoval_comparison_p (TREE_OPERAND (arg, 0), cval1, cval2, save_p);
2824
2825     case tcc_binary:
2826       return (twoval_comparison_p (TREE_OPERAND (arg, 0), cval1, cval2, save_p)
2827               && twoval_comparison_p (TREE_OPERAND (arg, 1),
2828                                       cval1, cval2, save_p));
2829
2830     case tcc_constant:
2831       return 1;
2832
2833     case tcc_expression:
2834       if (code == COND_EXPR)
2835         return (twoval_comparison_p (TREE_OPERAND (arg, 0),
2836                                      cval1, cval2, save_p)
2837                 && twoval_comparison_p (TREE_OPERAND (arg, 1),
2838                                         cval1, cval2, save_p)
2839                 && twoval_comparison_p (TREE_OPERAND (arg, 2),
2840                                         cval1, cval2, save_p));
2841       return 0;
2842
2843     case tcc_comparison:
2844       /* First see if we can handle the first operand, then the second.  For
2845          the second operand, we know *CVAL1 can't be zero.  It must be that
2846          one side of the comparison is each of the values; test for the
2847          case where this isn't true by failing if the two operands
2848          are the same.  */
2849
2850       if (operand_equal_p (TREE_OPERAND (arg, 0),
2851                            TREE_OPERAND (arg, 1), 0))
2852         return 0;
2853
2854       if (*cval1 == 0)
2855         *cval1 = TREE_OPERAND (arg, 0);
2856       else if (operand_equal_p (*cval1, TREE_OPERAND (arg, 0), 0))
2857         ;
2858       else if (*cval2 == 0)
2859         *cval2 = TREE_OPERAND (arg, 0);
2860       else if (operand_equal_p (*cval2, TREE_OPERAND (arg, 0), 0))
2861         ;
2862       else
2863         return 0;
2864
2865       if (operand_equal_p (*cval1, TREE_OPERAND (arg, 1), 0))
2866         ;
2867       else if (*cval2 == 0)
2868         *cval2 = TREE_OPERAND (arg, 1);
2869       else if (operand_equal_p (*cval2, TREE_OPERAND (arg, 1), 0))
2870         ;
2871       else
2872         return 0;
2873
2874       return 1;
2875
2876     default:
2877       return 0;
2878     }
2879 }
2880 \f
2881 /* ARG is a tree that is known to contain just arithmetic operations and
2882    comparisons.  Evaluate the operations in the tree substituting NEW0 for
2883    any occurrence of OLD0 as an operand of a comparison and likewise for
2884    NEW1 and OLD1.  */
2885
2886 static tree
2887 eval_subst (tree arg, tree old0, tree new0, tree old1, tree new1)
2888 {
2889   tree type = TREE_TYPE (arg);
2890   enum tree_code code = TREE_CODE (arg);
2891   enum tree_code_class class = TREE_CODE_CLASS (code);
2892
2893   /* We can handle some of the tcc_expression cases here.  */
2894   if (class == tcc_expression && code == TRUTH_NOT_EXPR)
2895     class = tcc_unary;
2896   else if (class == tcc_expression
2897            && (code == TRUTH_ANDIF_EXPR || code == TRUTH_ORIF_EXPR))
2898     class = tcc_binary;
2899
2900   switch (class)
2901     {
2902     case tcc_unary:
2903       return fold_build1 (code, type,
2904                           eval_subst (TREE_OPERAND (arg, 0),
2905                                       old0, new0, old1, new1));
2906
2907     case tcc_binary:
2908       return fold_build2 (code, type,
2909                           eval_subst (TREE_OPERAND (arg, 0),
2910                                       old0, new0, old1, new1),
2911                           eval_subst (TREE_OPERAND (arg, 1),
2912                                       old0, new0, old1, new1));
2913
2914     case tcc_expression:
2915       switch (code)
2916         {
2917         case SAVE_EXPR:
2918           return eval_subst (TREE_OPERAND (arg, 0), old0, new0, old1, new1);
2919
2920         case COMPOUND_EXPR:
2921           return eval_subst (TREE_OPERAND (arg, 1), old0, new0, old1, new1);
2922
2923         case COND_EXPR:
2924           return fold_build3 (code, type,
2925                               eval_subst (TREE_OPERAND (arg, 0),
2926                                           old0, new0, old1, new1),
2927                               eval_subst (TREE_OPERAND (arg, 1),
2928                                           old0, new0, old1, new1),
2929                               eval_subst (TREE_OPERAND (arg, 2),
2930                                           old0, new0, old1, new1));
2931         default:
2932           break;
2933         }
2934       /* Fall through - ???  */
2935
2936     case tcc_comparison:
2937       {
2938         tree arg0 = TREE_OPERAND (arg, 0);
2939         tree arg1 = TREE_OPERAND (arg, 1);
2940
2941         /* We need to check both for exact equality and tree equality.  The
2942            former will be true if the operand has a side-effect.  In that
2943            case, we know the operand occurred exactly once.  */
2944
2945         if (arg0 == old0 || operand_equal_p (arg0, old0, 0))
2946           arg0 = new0;
2947         else if (arg0 == old1 || operand_equal_p (arg0, old1, 0))
2948           arg0 = new1;
2949
2950         if (arg1 == old0 || operand_equal_p (arg1, old0, 0))
2951           arg1 = new0;
2952         else if (arg1 == old1 || operand_equal_p (arg1, old1, 0))
2953           arg1 = new1;
2954
2955         return fold_build2 (code, type, arg0, arg1);
2956       }
2957
2958     default:
2959       return arg;
2960     }
2961 }
2962 \f
2963 /* Return a tree for the case when the result of an expression is RESULT
2964    converted to TYPE and OMITTED was previously an operand of the expression
2965    but is now not needed (e.g., we folded OMITTED * 0).
2966
2967    If OMITTED has side effects, we must evaluate it.  Otherwise, just do
2968    the conversion of RESULT to TYPE.  */
2969
2970 tree
2971 omit_one_operand (tree type, tree result, tree omitted)
2972 {
2973   tree t = fold_convert (type, result);
2974
2975   if (TREE_SIDE_EFFECTS (omitted))
2976     return build2 (COMPOUND_EXPR, type, fold_ignored_result (omitted), t);
2977
2978   return non_lvalue (t);
2979 }
2980
2981 /* Similar, but call pedantic_non_lvalue instead of non_lvalue.  */
2982
2983 static tree
2984 pedantic_omit_one_operand (tree type, tree result, tree omitted)
2985 {
2986   tree t = fold_convert (type, result);
2987
2988   if (TREE_SIDE_EFFECTS (omitted))
2989     return build2 (COMPOUND_EXPR, type, fold_ignored_result (omitted), t);
2990
2991   return pedantic_non_lvalue (t);
2992 }
2993
2994 /* Return a tree for the case when the result of an expression is RESULT
2995    converted to TYPE and OMITTED1 and OMITTED2 were previously operands
2996    of the expression but are now not needed.
2997
2998    If OMITTED1 or OMITTED2 has side effects, they must be evaluated.
2999    If both OMITTED1 and OMITTED2 have side effects, OMITTED1 is
3000    evaluated before OMITTED2.  Otherwise, if neither has side effects,
3001    just do the conversion of RESULT to TYPE.  */
3002
3003 tree
3004 omit_two_operands (tree type, tree result, tree omitted1, tree omitted2)
3005 {
3006   tree t = fold_convert (type, result);
3007
3008   if (TREE_SIDE_EFFECTS (omitted2))
3009     t = build2 (COMPOUND_EXPR, type, omitted2, t);
3010   if (TREE_SIDE_EFFECTS (omitted1))
3011     t = build2 (COMPOUND_EXPR, type, omitted1, t);
3012
3013   return TREE_CODE (t) != COMPOUND_EXPR ? non_lvalue (t) : t;
3014 }
3015
3016 \f
3017 /* Return a simplified tree node for the truth-negation of ARG.  This
3018    never alters ARG itself.  We assume that ARG is an operation that
3019    returns a truth value (0 or 1).
3020
3021    FIXME: one would think we would fold the result, but it causes
3022    problems with the dominator optimizer.  */
3023 tree
3024 invert_truthvalue (tree arg)
3025 {
3026   tree type = TREE_TYPE (arg);
3027   enum tree_code code = TREE_CODE (arg);
3028
3029   if (code == ERROR_MARK)
3030     return arg;
3031
3032   /* If this is a comparison, we can simply invert it, except for
3033      floating-point non-equality comparisons, in which case we just
3034      enclose a TRUTH_NOT_EXPR around what we have.  */
3035
3036   if (TREE_CODE_CLASS (code) == tcc_comparison)
3037     {
3038       tree op_type = TREE_TYPE (TREE_OPERAND (arg, 0));
3039       if (FLOAT_TYPE_P (op_type)
3040           && flag_trapping_math
3041           && code != ORDERED_EXPR && code != UNORDERED_EXPR
3042           && code != NE_EXPR && code != EQ_EXPR)
3043         return build1 (TRUTH_NOT_EXPR, type, arg);
3044       else
3045         {
3046           code = invert_tree_comparison (code,
3047                                          HONOR_NANS (TYPE_MODE (op_type)));
3048           if (code == ERROR_MARK)
3049             return build1 (TRUTH_NOT_EXPR, type, arg);
3050           else
3051             return build2 (code, type,
3052                            TREE_OPERAND (arg, 0), TREE_OPERAND (arg, 1));
3053         }
3054     }
3055
3056   switch (code)
3057     {
3058     case INTEGER_CST:
3059       return constant_boolean_node (integer_zerop (arg), type);
3060
3061     case TRUTH_AND_EXPR:
3062       return build2 (TRUTH_OR_EXPR, type,
3063                      invert_truthvalue (TREE_OPERAND (arg, 0)),
3064                      invert_truthvalue (TREE_OPERAND (arg, 1)));
3065
3066     case TRUTH_OR_EXPR:
3067       return build2 (TRUTH_AND_EXPR, type,
3068                      invert_truthvalue (TREE_OPERAND (arg, 0)),
3069                      invert_truthvalue (TREE_OPERAND (arg, 1)));
3070
3071     case TRUTH_XOR_EXPR:
3072       /* Here we can invert either operand.  We invert the first operand
3073          unless the second operand is a TRUTH_NOT_EXPR in which case our
3074          result is the XOR of the first operand with the inside of the
3075          negation of the second operand.  */
3076
3077       if (TREE_CODE (TREE_OPERAND (arg, 1)) == TRUTH_NOT_EXPR)
3078         return build2 (TRUTH_XOR_EXPR, type, TREE_OPERAND (arg, 0),
3079                        TREE_OPERAND (TREE_OPERAND (arg, 1), 0));
3080       else
3081         return build2 (TRUTH_XOR_EXPR, type,
3082                        invert_truthvalue (TREE_OPERAND (arg, 0)),
3083                        TREE_OPERAND (arg, 1));
3084
3085     case TRUTH_ANDIF_EXPR:
3086       return build2 (TRUTH_ORIF_EXPR, type,
3087                      invert_truthvalue (TREE_OPERAND (arg, 0)),
3088                      invert_truthvalue (TREE_OPERAND (arg, 1)));
3089
3090     case TRUTH_ORIF_EXPR:
3091       return build2 (TRUTH_ANDIF_EXPR, type,
3092                      invert_truthvalue (TREE_OPERAND (arg, 0)),
3093                      invert_truthvalue (TREE_OPERAND (arg, 1)));
3094
3095     case TRUTH_NOT_EXPR:
3096       return TREE_OPERAND (arg, 0);
3097
3098     case COND_EXPR:
3099       {
3100         tree arg1 = TREE_OPERAND (arg, 1);
3101         tree arg2 = TREE_OPERAND (arg, 2);
3102         /* A COND_EXPR may have a throw as one operand, which
3103            then has void type.  Just leave void operands
3104            as they are.  */
3105         return build3 (COND_EXPR, type, TREE_OPERAND (arg, 0),
3106                        VOID_TYPE_P (TREE_TYPE (arg1))
3107                        ? arg1 : invert_truthvalue (arg1),
3108                        VOID_TYPE_P (TREE_TYPE (arg2))
3109                        ? arg2 : invert_truthvalue (arg2));
3110       }
3111
3112     case COMPOUND_EXPR:
3113       return build2 (COMPOUND_EXPR, type, TREE_OPERAND (arg, 0),
3114                      invert_truthvalue (TREE_OPERAND (arg, 1)));
3115
3116     case NON_LVALUE_EXPR:
3117       return invert_truthvalue (TREE_OPERAND (arg, 0));
3118
3119     case NOP_EXPR:
3120       if (TREE_CODE (TREE_TYPE (arg)) == BOOLEAN_TYPE)
3121         break;
3122
3123     case CONVERT_EXPR:
3124     case FLOAT_EXPR:
3125       return build1 (TREE_CODE (arg), type,
3126                      invert_truthvalue (TREE_OPERAND (arg, 0)));
3127
3128     case BIT_AND_EXPR:
3129       if (!integer_onep (TREE_OPERAND (arg, 1)))
3130         break;
3131       return build2 (EQ_EXPR, type, arg,
3132                      build_int_cst (type, 0));
3133
3134     case SAVE_EXPR:
3135       return build1 (TRUTH_NOT_EXPR, type, arg);
3136
3137     case CLEANUP_POINT_EXPR:
3138       return build1 (CLEANUP_POINT_EXPR, type,
3139                      invert_truthvalue (TREE_OPERAND (arg, 0)));
3140
3141     default:
3142       break;
3143     }
3144   gcc_assert (TREE_CODE (TREE_TYPE (arg)) == BOOLEAN_TYPE);
3145   return build1 (TRUTH_NOT_EXPR, type, arg);
3146 }
3147
3148 /* Given a bit-wise operation CODE applied to ARG0 and ARG1, see if both
3149    operands are another bit-wise operation with a common input.  If so,
3150    distribute the bit operations to save an operation and possibly two if
3151    constants are involved.  For example, convert
3152         (A | B) & (A | C) into A | (B & C)
3153    Further simplification will occur if B and C are constants.
3154
3155    If this optimization cannot be done, 0 will be returned.  */
3156
3157 static tree
3158 distribute_bit_expr (enum tree_code code, tree type, tree arg0, tree arg1)
3159 {
3160   tree common;
3161   tree left, right;
3162
3163   if (TREE_CODE (arg0) != TREE_CODE (arg1)
3164       || TREE_CODE (arg0) == code
3165       || (TREE_CODE (arg0) != BIT_AND_EXPR
3166           && TREE_CODE (arg0) != BIT_IOR_EXPR))
3167     return 0;
3168
3169   if (operand_equal_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg1, 0), 0))
3170     {
3171       common = TREE_OPERAND (arg0, 0);
3172       left = TREE_OPERAND (arg0, 1);
3173       right = TREE_OPERAND (arg1, 1);
3174     }
3175   else if (operand_equal_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg1, 1), 0))
3176     {
3177       common = TREE_OPERAND (arg0, 0);
3178       left = TREE_OPERAND (arg0, 1);
3179       right = TREE_OPERAND (arg1, 0);
3180     }
3181   else if (operand_equal_p (TREE_OPERAND (arg0, 1), TREE_OPERAND (arg1, 0), 0))
3182     {
3183       common = TREE_OPERAND (arg0, 1);
3184       left = TREE_OPERAND (arg0, 0);
3185       right = TREE_OPERAND (arg1, 1);
3186     }
3187   else if (operand_equal_p (TREE_OPERAND (arg0, 1), TREE_OPERAND (arg1, 1), 0))
3188     {
3189       common = TREE_OPERAND (arg0, 1);
3190       left = TREE_OPERAND (arg0, 0);
3191       right = TREE_OPERAND (arg1, 0);
3192     }
3193   else
3194     return 0;
3195
3196   return fold_build2 (TREE_CODE (arg0), type, common,
3197                       fold_build2 (code, type, left, right));
3198 }
3199
3200 /* Knowing that ARG0 and ARG1 are both RDIV_EXPRs, simplify a binary operation
3201    with code CODE.  This optimization is unsafe.  */
3202 static tree
3203 distribute_real_division (enum tree_code code, tree type, tree arg0, tree arg1)
3204 {
3205   bool mul0 = TREE_CODE (arg0) == MULT_EXPR;
3206   bool mul1 = TREE_CODE (arg1) == MULT_EXPR;
3207
3208   /* (A / C) +- (B / C) -> (A +- B) / C.  */
3209   if (mul0 == mul1
3210       && operand_equal_p (TREE_OPERAND (arg0, 1),
3211                        TREE_OPERAND (arg1, 1), 0))
3212     return fold_build2 (mul0 ? MULT_EXPR : RDIV_EXPR, type,
3213                         fold_build2 (code, type,
3214                                      TREE_OPERAND (arg0, 0),
3215                                      TREE_OPERAND (arg1, 0)),
3216                         TREE_OPERAND (arg0, 1));
3217
3218   /* (A / C1) +- (A / C2) -> A * (1 / C1 +- 1 / C2).  */
3219   if (operand_equal_p (TREE_OPERAND (arg0, 0),
3220                        TREE_OPERAND (arg1, 0), 0)
3221       && TREE_CODE (TREE_OPERAND (arg0, 1)) == REAL_CST
3222       && TREE_CODE (TREE_OPERAND (arg1, 1)) == REAL_CST)
3223     {
3224       REAL_VALUE_TYPE r0, r1;
3225       r0 = TREE_REAL_CST (TREE_OPERAND (arg0, 1));
3226       r1 = TREE_REAL_CST (TREE_OPERAND (arg1, 1));
3227       if (!mul0)
3228         real_arithmetic (&r0, RDIV_EXPR, &dconst1, &r0);
3229       if (!mul1)
3230         real_arithmetic (&r1, RDIV_EXPR, &dconst1, &r1);
3231       real_arithmetic (&r0, code, &r0, &r1);
3232       return fold_build2 (MULT_EXPR, type,
3233                           TREE_OPERAND (arg0, 0),
3234                           build_real (type, r0));
3235     }
3236
3237   return NULL_TREE;
3238 }
3239 \f
3240 /* Return a BIT_FIELD_REF of type TYPE to refer to BITSIZE bits of INNER
3241    starting at BITPOS.  The field is unsigned if UNSIGNEDP is nonzero.  */
3242
3243 static tree
3244 make_bit_field_ref (tree inner, tree type, int bitsize, int bitpos,
3245                     int unsignedp)
3246 {
3247   tree result;
3248
3249   if (bitpos == 0)
3250     {
3251       tree size = TYPE_SIZE (TREE_TYPE (inner));
3252       if ((INTEGRAL_TYPE_P (TREE_TYPE (inner))
3253            || POINTER_TYPE_P (TREE_TYPE (inner)))
3254           && host_integerp (size, 0)
3255           && tree_low_cst (size, 0) == bitsize)
3256         return fold_convert (type, inner);
3257     }
3258
3259   result = build3 (BIT_FIELD_REF, type, inner,
3260                    size_int (bitsize), bitsize_int (bitpos));
3261
3262   BIT_FIELD_REF_UNSIGNED (result) = unsignedp;
3263
3264   return result;
3265 }
3266
3267 /* Optimize a bit-field compare.
3268
3269    There are two cases:  First is a compare against a constant and the
3270    second is a comparison of two items where the fields are at the same
3271    bit position relative to the start of a chunk (byte, halfword, word)
3272    large enough to contain it.  In these cases we can avoid the shift
3273    implicit in bitfield extractions.
3274
3275    For constants, we emit a compare of the shifted constant with the
3276    BIT_AND_EXPR of a mask and a byte, halfword, or word of the operand being
3277    compared.  For two fields at the same position, we do the ANDs with the
3278    similar mask and compare the result of the ANDs.
3279
3280    CODE is the comparison code, known to be either NE_EXPR or EQ_EXPR.
3281    COMPARE_TYPE is the type of the comparison, and LHS and RHS
3282    are the left and right operands of the comparison, respectively.
3283
3284    If the optimization described above can be done, we return the resulting
3285    tree.  Otherwise we return zero.  */
3286
3287 static tree
3288 optimize_bit_field_compare (enum tree_code code, tree compare_type,
3289                             tree lhs, tree rhs)
3290 {
3291   HOST_WIDE_INT lbitpos, lbitsize, rbitpos, rbitsize, nbitpos, nbitsize;
3292   tree type = TREE_TYPE (lhs);
3293   tree signed_type, unsigned_type;
3294   int const_p = TREE_CODE (rhs) == INTEGER_CST;
3295   enum machine_mode lmode, rmode, nmode;
3296   int lunsignedp, runsignedp;
3297   int lvolatilep = 0, rvolatilep = 0;
3298   tree linner, rinner = NULL_TREE;
3299   tree mask;
3300   tree offset;
3301
3302   /* Get all the information about the extractions being done.  If the bit size
3303      if the same as the size of the underlying object, we aren't doing an
3304      extraction at all and so can do nothing.  We also don't want to
3305      do anything if the inner expression is a PLACEHOLDER_EXPR since we
3306      then will no longer be able to replace it.  */
3307   linner = get_inner_reference (lhs, &lbitsize, &lbitpos, &offset, &lmode,
3308                                 &lunsignedp, &lvolatilep, false);
3309   if (linner == lhs || lbitsize == GET_MODE_BITSIZE (lmode) || lbitsize < 0
3310       || offset != 0 || TREE_CODE (linner) == PLACEHOLDER_EXPR)
3311     return 0;
3312
3313  if (!const_p)
3314    {
3315      /* If this is not a constant, we can only do something if bit positions,
3316         sizes, and signedness are the same.  */
3317      rinner = get_inner_reference (rhs, &rbitsize, &rbitpos, &offset, &rmode,
3318                                    &runsignedp, &rvolatilep, false);
3319
3320      if (rinner == rhs || lbitpos != rbitpos || lbitsize != rbitsize
3321          || lunsignedp != runsignedp || offset != 0
3322          || TREE_CODE (rinner) == PLACEHOLDER_EXPR)
3323        return 0;
3324    }
3325
3326   /* See if we can find a mode to refer to this field.  We should be able to,
3327      but fail if we can't.  */
3328   nmode = get_best_mode (lbitsize, lbitpos,
3329                          const_p ? TYPE_ALIGN (TREE_TYPE (linner))
3330                          : MIN (TYPE_ALIGN (TREE_TYPE (linner)),
3331                                 TYPE_ALIGN (TREE_TYPE (rinner))),
3332                          word_mode, lvolatilep || rvolatilep);
3333   if (nmode == VOIDmode)
3334     return 0;
3335
3336   /* Set signed and unsigned types of the precision of this mode for the
3337      shifts below.  */
3338   signed_type = lang_hooks.types.type_for_mode (nmode, 0);
3339   unsigned_type = lang_hooks.types.type_for_mode (nmode, 1);
3340
3341   /* Compute the bit position and size for the new reference and our offset
3342      within it. If the new reference is the same size as the original, we
3343      won't optimize anything, so return zero.  */
3344   nbitsize = GET_MODE_BITSIZE (nmode);
3345   nbitpos = lbitpos & ~ (nbitsize - 1);
3346   lbitpos -= nbitpos;
3347   if (nbitsize == lbitsize)
3348     return 0;
3349
3350   if (BYTES_BIG_ENDIAN)
3351     lbitpos = nbitsize - lbitsize - lbitpos;
3352
3353   /* Make the mask to be used against the extracted field.  */
3354   mask = build_int_cst (unsigned_type, -1);
3355   mask = force_fit_type (mask, 0, false, false);
3356   mask = fold_convert (unsigned_type, mask);
3357   mask = const_binop (LSHIFT_EXPR, mask, size_int (nbitsize - lbitsize), 0);
3358   mask = const_binop (RSHIFT_EXPR, mask,
3359                       size_int (nbitsize - lbitsize - lbitpos), 0);
3360
3361   if (! const_p)
3362     /* If not comparing with constant, just rework the comparison
3363        and return.  */
3364     return build2 (code, compare_type,
3365                    build2 (BIT_AND_EXPR, unsigned_type,
3366                            make_bit_field_ref (linner, unsigned_type,
3367                                                nbitsize, nbitpos, 1),
3368                            mask),
3369                    build2 (BIT_AND_EXPR, unsigned_type,
3370                            make_bit_field_ref (rinner, unsigned_type,
3371                                                nbitsize, nbitpos, 1),
3372                            mask));
3373
3374   /* Otherwise, we are handling the constant case. See if the constant is too
3375      big for the field.  Warn and return a tree of for 0 (false) if so.  We do
3376      this not only for its own sake, but to avoid having to test for this
3377      error case below.  If we didn't, we might generate wrong code.
3378
3379      For unsigned fields, the constant shifted right by the field length should
3380      be all zero.  For signed fields, the high-order bits should agree with
3381      the sign bit.  */
3382
3383   if (lunsignedp)
3384     {
3385       if (! integer_zerop (const_binop (RSHIFT_EXPR,
3386                                         fold_convert (unsigned_type, rhs),
3387                                         size_int (lbitsize), 0)))
3388         {
3389           warning (0, "comparison is always %d due to width of bit-field",
3390                    code == NE_EXPR);
3391           return constant_boolean_node (code == NE_EXPR, compare_type);
3392         }
3393     }
3394   else
3395     {
3396       tree tem = const_binop (RSHIFT_EXPR, fold_convert (signed_type, rhs),
3397                               size_int (lbitsize - 1), 0);
3398       if (! integer_zerop (tem) && ! integer_all_onesp (tem))
3399         {
3400           warning (0, "comparison is always %d due to width of bit-field",
3401                    code == NE_EXPR);
3402           return constant_boolean_node (code == NE_EXPR, compare_type);
3403         }
3404     }
3405
3406   /* Single-bit compares should always be against zero.  */
3407   if (lbitsize == 1 && ! integer_zerop (rhs))
3408     {
3409       code = code == EQ_EXPR ? NE_EXPR : EQ_EXPR;
3410       rhs = build_int_cst (type, 0);
3411     }
3412
3413   /* Make a new bitfield reference, shift the constant over the
3414      appropriate number of bits and mask it with the computed mask
3415      (in case this was a signed field).  If we changed it, make a new one.  */
3416   lhs = make_bit_field_ref (linner, unsigned_type, nbitsize, nbitpos, 1);
3417   if (lvolatilep)
3418     {
3419       TREE_SIDE_EFFECTS (lhs) = 1;
3420       TREE_THIS_VOLATILE (lhs) = 1;
3421     }
3422
3423   rhs = const_binop (BIT_AND_EXPR,
3424                      const_binop (LSHIFT_EXPR,
3425                                   fold_convert (unsigned_type, rhs),
3426                                   size_int (lbitpos), 0),
3427                      mask, 0);
3428
3429   return build2 (code, compare_type,
3430                  build2 (BIT_AND_EXPR, unsigned_type, lhs, mask),
3431                  rhs);
3432 }
3433 \f
3434 /* Subroutine for fold_truthop: decode a field reference.
3435
3436    If EXP is a comparison reference, we return the innermost reference.
3437
3438    *PBITSIZE is set to the number of bits in the reference, *PBITPOS is
3439    set to the starting bit number.
3440
3441    If the innermost field can be completely contained in a mode-sized
3442    unit, *PMODE is set to that mode.  Otherwise, it is set to VOIDmode.
3443
3444    *PVOLATILEP is set to 1 if the any expression encountered is volatile;
3445    otherwise it is not changed.
3446
3447    *PUNSIGNEDP is set to the signedness of the field.
3448
3449    *PMASK is set to the mask used.  This is either contained in a
3450    BIT_AND_EXPR or derived from the width of the field.
3451
3452    *PAND_MASK is set to the mask found in a BIT_AND_EXPR, if any.
3453
3454    Return 0 if this is not a component reference or is one that we can't
3455    do anything with.  */
3456
3457 static tree
3458 decode_field_reference (tree exp, HOST_WIDE_INT *pbitsize,
3459                         HOST_WIDE_INT *pbitpos, enum machine_mode *pmode,
3460                         int *punsignedp, int *pvolatilep,
3461                         tree *pmask, tree *pand_mask)
3462 {
3463   tree outer_type = 0;
3464   tree and_mask = 0;
3465   tree mask, inner, offset;
3466   tree unsigned_type;
3467   unsigned int precision;
3468
3469   /* All the optimizations using this function assume integer fields.
3470      There are problems with FP fields since the type_for_size call
3471      below can fail for, e.g., XFmode.  */
3472   if (! INTEGRAL_TYPE_P (TREE_TYPE (exp)))
3473     return 0;
3474
3475   /* We are interested in the bare arrangement of bits, so strip everything
3476      that doesn't affect the machine mode.  However, record the type of the
3477      outermost expression if it may matter below.  */
3478   if (TREE_CODE (exp) == NOP_EXPR
3479       || TREE_CODE (exp) == CONVERT_EXPR
3480       || TREE_CODE (exp) == NON_LVALUE_EXPR)
3481     outer_type = TREE_TYPE (exp);
3482   STRIP_NOPS (exp);