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