gcc/double-int.h

   1 /* Operations with long integers.
   2    Copyright (C) 2006, 2007, 2008, 2010, 2012 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify it
   7 under the terms of the GNU General Public License as published by the
   8 Free Software Foundation; either version 3, or (at your option) any
   9 later version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT
  12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING3.  If not see
  18 <http://www.gnu.org/licenses/>.  */
  19
  20 #ifndef DOUBLE_INT_H
  21 #define DOUBLE_INT_H
  22
  23 #ifndef GENERATOR_FILE
  24 #include <gmp.h>
  25 #endif
  26
  27 /* A large integer is currently represented as a pair of HOST_WIDE_INTs.
  28    It therefore represents a number with precision of
  29    2 * HOST_BITS_PER_WIDE_INT bits (it is however possible that the
  30    internal representation will change, if numbers with greater precision
  31    are needed, so the users should not rely on it).  The representation does
  32    not contain any information about signedness of the represented value, so
  33    it can be used to represent both signed and unsigned numbers.  For
  34    operations where the results depend on signedness (division, comparisons),
  35    it must be specified separately.  For each such operation, there are three
  36    versions of the function -- double_int_op, that takes an extra UNS argument
  37    giving the signedness of the values, and double_int_sop and double_int_uop
  38    that stand for its specializations for signed and unsigned values.
  39
  40    You may also represent with numbers in smaller precision using double_int.
  41    You however need to use double_int_ext (that fills in the bits of the
  42    number over the prescribed precision with zeros or with the sign bit) before
  43    operations that do not perform arithmetics modulo 2^precision (comparisons,
  44    division), and possibly before storing the results, if you want to keep
  45    them in some canonical form).  In general, the signedness of double_int_ext
  46    should match the signedness of the operation.
  47
  48    ??? The components of double_int differ in signedness mostly for
  49    historical reasons (they replace an older structure used to represent
  50    numbers with precision higher than HOST_WIDE_INT).  It might be less
  51    confusing to have them both signed or both unsigned.  */
  52
  53 struct double_int
  54 {
  55   /* Normally, we would define constructors to create instances.
  56      Two things prevent us from doing so.
  57      First, defining a constructor makes the class non-POD in C++03,
  58      and we certainly want double_int to be a POD.
  59      Second, the GCC conding conventions prefer explicit conversion,
  60      and explicit conversion operators are not available until C++11.  */
  61
  62   static double_int from_uhwi (unsigned HOST_WIDE_INT cst);
  63   static double_int from_shwi (HOST_WIDE_INT cst);
  64   static double_int from_pair (HOST_WIDE_INT high, unsigned HOST_WIDE_INT low);
  65
  66   /* No copy assignment operator or destructor to keep the type a POD.  */
  67
  68   /* There are some special value-creation static member functions.  */
  69
  70   static double_int mask (unsigned prec);
  71   static double_int max_value (unsigned int prec, bool uns);
  72   static double_int min_value (unsigned int prec, bool uns);
  73
  74   /* The following functions are mutating operations.  */
  75
  76   double_int &operator ++ (); // prefix
  77   double_int &operator -- (); // prefix
  78   double_int &operator *= (double_int);
  79   double_int &operator += (double_int);
  80   double_int &operator -= (double_int);
  81   double_int &operator &= (double_int);
  82   double_int &operator ^= (double_int);
  83   double_int &operator |= (double_int);
  84
  85   /* The following functions are non-mutating operations.  */
  86
  87   /* Conversion functions.  */
  88
  89   HOST_WIDE_INT to_shwi () const;
  90   unsigned HOST_WIDE_INT to_uhwi () const;
  91
  92   /* Conversion query functions.  */
  93
  94   bool fits_uhwi () const;
  95   bool fits_shwi () const;
  96   bool fits_hwi (bool uns) const;
  97
  98   /* Attribute query functions.  */
  99
 100   int trailing_zeros () const;
 101   int popcount () const;
 102
 103   /* Arithmetic query operations.  */
 104
 105   bool multiple_of (double_int, bool, double_int *) const;
 106
 107   /* Arithmetic operation functions.  */
 108
 109   /* The following operations perform arithmetics modulo 2^precision, so you
 110      do not need to call .ext between them, even if you are representing
 111      numbers with precision less than HOST_BITS_PER_DOUBLE_INT bits.  */
 112
 113   double_int set_bit (unsigned) const;
 114   double_int mul_with_sign (double_int, bool unsigned_p, bool *overflow) const;
 115   double_int wide_mul_with_sign (double_int, bool unsigned_p,
 116                                  double_int *higher, bool *overflow) const;
 117   double_int add_with_sign (double_int, bool unsigned_p, bool *overflow) const;
 118   double_int sub_with_overflow (double_int, bool *overflow) const;
 119   double_int neg_with_overflow (bool *overflow) const;
 120
 121   double_int operator * (double_int) const;
 122   double_int operator + (double_int) const;
 123   double_int operator - (double_int) const;
 124   double_int operator - () const;
 125   double_int operator ~ () const;
 126   double_int operator & (double_int) const;
 127   double_int operator | (double_int) const;
 128   double_int operator ^ (double_int) const;
 129   double_int and_not (double_int) const;
 130
 131   double_int lshift (HOST_WIDE_INT count, unsigned int prec, bool arith) const;
 132   double_int rshift (HOST_WIDE_INT count, unsigned int prec, bool arith) const;
 133   double_int alshift (HOST_WIDE_INT count, unsigned int prec) const;
 134   double_int arshift (HOST_WIDE_INT count, unsigned int prec) const;
 135   double_int llshift (HOST_WIDE_INT count, unsigned int prec) const;
 136   double_int lrshift (HOST_WIDE_INT count, unsigned int prec) const;
 137   double_int lrotate (HOST_WIDE_INT count, unsigned int prec) const;
 138   double_int rrotate (HOST_WIDE_INT count, unsigned int prec) const;
 139
 140   /* You must ensure that double_int::ext is called on the operands
 141      of the following operations, if the precision of the numbers
 142      is less than HOST_BITS_PER_DOUBLE_INT bits.  */
 143
 144   double_int div (double_int, bool, unsigned) const;
 145   double_int sdiv (double_int, unsigned) const;
 146   double_int udiv (double_int, unsigned) const;
 147   double_int mod (double_int, bool, unsigned) const;
 148   double_int smod (double_int, unsigned) const;
 149   double_int umod (double_int, unsigned) const;
 150   double_int divmod_with_overflow (double_int, bool, unsigned,
 151                                    double_int *, bool *) const;
 152   double_int divmod (double_int, bool, unsigned, double_int *) const;
 153   double_int sdivmod (double_int, unsigned, double_int *) const;
 154   double_int udivmod (double_int, unsigned, double_int *) const;
 155
 156   /* Precision control functions.  */
 157
 158   double_int ext (unsigned prec, bool uns) const;
 159   double_int zext (unsigned prec) const;
 160   double_int sext (unsigned prec) const;
 161
 162   /* Comparative functions.  */
 163
 164   bool is_zero () const;
 165   bool is_one () const;
 166   bool is_minus_one () const;
 167   bool is_negative () const;
 168
 169   int cmp (double_int b, bool uns) const;
 170   int ucmp (double_int b) const;
 171   int scmp (double_int b) const;
 172
 173   bool ult (double_int b) const;
 174   bool ule (double_int b) const;
 175   bool ugt (double_int b) const;
 176   bool slt (double_int b) const;
 177   bool sle (double_int b) const;
 178   bool sgt (double_int b) const;
 179
 180   double_int max (double_int b, bool uns);
 181   double_int smax (double_int b);
 182   double_int umax (double_int b);
 183
 184   double_int min (double_int b, bool uns);
 185   double_int smin (double_int b);
 186   double_int umin (double_int b);
 187
 188   bool operator == (double_int cst2) const;
 189   bool operator != (double_int cst2) const;
 190
 191   /* Please migrate away from using these member variables publically.  */
 192
 193   unsigned HOST_WIDE_INT low;
 194   HOST_WIDE_INT high;
 195
 196 };
 197
 198 #define HOST_BITS_PER_DOUBLE_INT (2 * HOST_BITS_PER_WIDE_INT)
 199
 200 /* Constructors and conversions.  */
 201
 202 /* Constructs double_int from integer CST.  The bits over the precision of
 203    HOST_WIDE_INT are filled with the sign bit.  */
 204
 205 inline double_int
 206 double_int::from_shwi (HOST_WIDE_INT cst)
 207 {
 208   double_int r;
 209   r.low = (unsigned HOST_WIDE_INT) cst;
 210   r.high = cst < 0 ? -1 : 0;
 211   return r;
 212 }
 213
 214 /* Some useful constants.  */
 215 /* FIXME(crowl): Maybe remove after converting callers?
 216    The problem is that a named constant would not be as optimizable,
 217    while the functional syntax is more verbose.  */
 218
 219 #define double_int_minus_one (double_int::from_shwi (-1))
 220 #define double_int_zero (double_int::from_shwi (0))
 221 #define double_int_one (double_int::from_shwi (1))
 222 #define double_int_two (double_int::from_shwi (2))
 223 #define double_int_ten (double_int::from_shwi (10))
 224
 225 /* Constructs double_int from unsigned integer CST.  The bits over the
 226    precision of HOST_WIDE_INT are filled with zeros.  */
 227
 228 inline double_int
 229 double_int::from_uhwi (unsigned HOST_WIDE_INT cst)
 230 {
 231   double_int r;
 232   r.low = cst;
 233   r.high = 0;
 234   return r;
 235 }
 236
 237 inline double_int
 238 double_int::from_pair (HOST_WIDE_INT high, unsigned HOST_WIDE_INT low)
 239 {
 240   double_int r;
 241   r.low = low;
 242   r.high = high;
 243   return r;
 244 }
 245
 246 inline double_int &
 247 double_int::operator ++ ()
 248 {
 249   *this += double_int_one;
 250   return *this;
 251 }
 252
 253 inline double_int &
 254 double_int::operator -- ()
 255 {
 256   *this -= double_int_one;
 257   return *this;
 258 }
 259
 260 inline double_int &
 261 double_int::operator *= (double_int b)
 262 {
 263   *this = *this * b;
 264   return *this;
 265 }
 266
 267 inline double_int &
 268 double_int::operator += (double_int b)
 269 {
 270   *this = *this + b;
 271   return *this;
 272 }
 273
 274 inline double_int &
 275 double_int::operator -= (double_int b)
 276 {
 277   *this = *this - b;
 278   return *this;
 279 }
 280
 281 inline double_int &
 282 double_int::operator &= (double_int b)
 283 {
 284   *this = *this & b;
 285   return *this;
 286 }
 287
 288 inline double_int &
 289 double_int::operator ^= (double_int b)
 290 {
 291   *this = *this ^ b;
 292   return *this;
 293 }
 294
 295 inline double_int &
 296 double_int::operator |= (double_int b)
 297 {
 298   *this = *this | b;
 299   return *this;
 300 }
 301
 302 /* Returns value of CST as a signed number.  CST must satisfy
 303    double_int::fits_signed.  */
 304
 305 inline HOST_WIDE_INT
 306 double_int::to_shwi () const
 307 {
 308   return (HOST_WIDE_INT) low;
 309 }
 310
 311 /* Returns value of CST as an unsigned number.  CST must satisfy
 312    double_int::fits_unsigned.  */
 313
 314 inline unsigned HOST_WIDE_INT
 315 double_int::to_uhwi () const
 316 {
 317   return low;
 318 }
 319
 320 /* Returns true if CST fits in unsigned HOST_WIDE_INT.  */
 321
 322 inline bool
 323 double_int::fits_uhwi () const
 324 {
 325   return high == 0;
 326 }
 327
 328 /* Logical operations.  */
 329
 330 /* Returns ~A.  */
 331
 332 inline double_int
 333 double_int::operator ~ () const
 334 {
 335   double_int result;
 336   result.low = ~low;
 337   result.high = ~high;
 338   return result;
 339 }
 340
 341 /* Returns A | B.  */
 342
 343 inline double_int
 344 double_int::operator | (double_int b) const
 345 {
 346   double_int result;
 347   result.low = low | b.low;
 348   result.high = high | b.high;
 349   return result;
 350 }
 351
 352 /* Returns A & B.  */
 353
 354 inline double_int
 355 double_int::operator & (double_int b) const
 356 {
 357   double_int result;
 358   result.low = low & b.low;
 359   result.high = high & b.high;
 360   return result;
 361 }
 362
 363 /* Returns A & ~B.  */
 364
 365 inline double_int
 366 double_int::and_not (double_int b) const
 367 {
 368   double_int result;
 369   result.low = low & ~b.low;
 370   result.high = high & ~b.high;
 371   return result;
 372 }
 373
 374 /* Returns A ^ B.  */
 375
 376 inline double_int
 377 double_int::operator ^ (double_int b) const
 378 {
 379   double_int result;
 380   result.low = low ^ b.low;
 381   result.high = high ^ b.high;
 382   return result;
 383 }
 384
 385 void dump_double_int (FILE *, double_int, bool);
 386
 387 #define ALL_ONES (~((unsigned HOST_WIDE_INT) 0))
 388
 389 /* The operands of the following comparison functions must be processed
 390    with double_int_ext, if their precision is less than
 391    HOST_BITS_PER_DOUBLE_INT bits.  */
 392
 393 /* Returns true if CST is zero.  */
 394
 395 inline bool
 396 double_int::is_zero () const
 397 {
 398   return low == 0 && high == 0;
 399 }
 400
 401 /* Returns true if CST is one.  */
 402
 403 inline bool
 404 double_int::is_one () const
 405 {
 406   return low == 1 && high == 0;
 407 }
 408
 409 /* Returns true if CST is minus one.  */
 410
 411 inline bool
 412 double_int::is_minus_one () const
 413 {
 414   return low == ALL_ONES && high == -1;
 415 }
 416
 417 /* Returns true if CST is negative.  */
 418
 419 inline bool
 420 double_int::is_negative () const
 421 {
 422   return high < 0;
 423 }
 424
 425 /* Returns true if CST1 == CST2.  */
 426
 427 inline bool
 428 double_int::operator == (double_int cst2) const
 429 {
 430   return low == cst2.low && high == cst2.high;
 431 }
 432
 433 /* Returns true if CST1 != CST2.  */
 434
 435 inline bool
 436 double_int::operator != (double_int cst2) const
 437 {
 438   return low != cst2.low || high != cst2.high;
 439 }
 440
 441 /* Return number of set bits of CST.  */
 442
 443 inline int
 444 double_int::popcount () const
 445 {
 446   return popcount_hwi (high) + popcount_hwi (low);
 447 }
 448
 449
 450 #ifndef GENERATOR_FILE
 451 /* Conversion to and from GMP integer representations.  */
 452
 453 void mpz_set_double_int (mpz_t, double_int, bool);
 454 double_int mpz_get_double_int (const_tree, mpz_t, bool);
 455 #endif
 456
 457 #endif /* DOUBLE_INT_H */