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