APInt.h revision 0b706b18bd0a7760d971727460a1f26bff8289b0
1//===-- llvm/Support/APInt.h - For Arbitrary Precision Integer -*- C++ -*--===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by Sheng Zhou and is distributed under the 6// University of Illinois Open Source License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements a class to represent arbitrary precision integral 11// constant values. 12// 13//===----------------------------------------------------------------------===// 14 15#ifndef LLVM_APINT_H 16#define LLVM_APINT_H 17 18#include "llvm/Support/DataTypes.h" 19#include <cassert> 20#include <string> 21 22namespace llvm { 23 24/// Forward declaration. 25class APInt; 26namespace APIntOps { 27 bool isIntN(unsigned N, const APInt& APIVal); 28 APInt ByteSwap(const APInt& APIVal); 29 APInt LogBase2(const APInt& APIVal); 30 APInt ashr(const APInt& LHS, unsigned shiftAmt); 31 APInt lshr(const APInt& LHS, unsigned shiftAmt); 32 APInt shl(const APInt& LHS, unsigned shiftAmt); 33 APInt sdiv(const APInt& LHS, const APInt& RHS); 34 APInt udiv(const APInt& LHS, const APInt& RHS); 35 APInt srem(const APInt& LHS, const APInt& RHS); 36 APInt urem(const APInt& LHS, const APInt& RHS); 37} 38 39//===----------------------------------------------------------------------===// 40// APInt Class 41//===----------------------------------------------------------------------===// 42 43/// APInt - This class represents arbitrary precision constant integral values. 44/// It is a functional replacement for common case unsigned integer type like 45/// "unsigned", "unsigned long" or "uint64_t", but also allows non-byte-width 46/// integer type and large integer value types such as 3-bits, 15-bits, or more 47/// than 64-bits of precision. APInt provides a variety of arithmetic operators 48/// and methods to manipulate integer values of any bit-width. It supports not 49/// only all the operations of uint64_t but also bitwise manipulation. 50/// 51/// @brief Class for arbitrary precision integers. 52/// 53/// Note: In this class, all bit/byte/word positions are zero-based. 54/// 55class APInt { 56 /// Friend Functions of APInt declared here. For detailed comments, 57 /// see bottom of this file. 58 friend bool APIntOps::isIntN(unsigned N, const APInt& APIVal); 59 friend APInt APIntOps::ByteSwap(const APInt& APIVal); 60 friend APInt APIntOps::LogBase2(const APInt& APIVal); 61 friend APInt APIntOps::ashr(const APInt& LHS, unsigned shiftAmt); 62 friend APInt APIntOps::lshr(const APInt& LHS, unsigned shiftAmt); 63 friend APInt APIntOps::shl(const APInt& LHS, unsigned shiftAmt); 64 friend APInt APIntOps::sdiv(const APInt& LHS, const APInt& RHS); 65 friend APInt APIntOps::udiv(const APInt& LHS, const APInt& RHS); 66 friend APInt APIntOps::srem(const APInt& LHS, const APInt& RHS); 67 friend APInt APIntOps::urem(const APInt& LHS, const APInt& RHS); 68 69 unsigned BitsNum; ///< The number of bits. 70 71 /// This union is used to store the integer value. When the 72 /// integer bit-width <= 64, it uses VAL; 73 /// otherwise it uses the pVal. 74 union { 75 uint64_t VAL; ///< Used to store the <= 64 bits integer value. 76 uint64_t *pVal; ///< Used to store the >64 bits integer value. 77 }; 78 79 /// This enum is just used to hold a constant we needed for APInt. 80 enum { 81 APINT_BITS_PER_WORD = sizeof(uint64_t) * 8 82 }; 83 84 /// Here one word's bitwidth equals to that of uint64_t. 85 /// @returns the number of words to hold the integer value of this APInt. 86 /// @brief Get the number of words. 87 inline unsigned getNumWords() const { 88 return (BitsNum + APINT_BITS_PER_WORD - 1) / APINT_BITS_PER_WORD; 89 } 90 91 /// @returns true if the number of bits <= 64, false otherwise. 92 /// @brief Determine if this APInt just has one word to store value. 93 inline bool isSingleWord() const 94 { return BitsNum <= APINT_BITS_PER_WORD; } 95 96 /// @returns the word position for the specified bit position. 97 static inline unsigned whichWord(unsigned bitPosition) 98 { return bitPosition / APINT_BITS_PER_WORD; } 99 100 /// @returns the byte position for the specified bit position. 101 static inline unsigned whichByte(unsigned bitPosition) 102 { return (bitPosition % APINT_BITS_PER_WORD) / 8; } 103 104 /// @returns the bit position in a word for the specified bit position 105 /// in APInt. 106 static inline unsigned whichBit(unsigned bitPosition) 107 { return bitPosition % APINT_BITS_PER_WORD; } 108 109 /// @returns a uint64_t type integer with just bit position at 110 /// "whichBit(bitPosition)" setting, others zero. 111 static inline uint64_t maskBit(unsigned bitPosition) 112 { return (static_cast<uint64_t>(1)) << whichBit(bitPosition); } 113 114 inline void TruncToBits() { 115 if (isSingleWord()) 116 VAL &= ~uint64_t(0ULL) >> (APINT_BITS_PER_WORD - BitsNum); 117 else 118 pVal[getNumWords() - 1] &= ~uint64_t(0ULL) >> 119 (APINT_BITS_PER_WORD - (whichBit(BitsNum - 1) + 1)); 120 } 121 122 /// @returns the corresponding word for the specified bit position. 123 inline uint64_t& getWord(unsigned bitPosition) 124 { return isSingleWord() ? VAL : pVal[whichWord(bitPosition)]; } 125 126 /// @returns the corresponding word for the specified bit position. 127 /// This is a constant version. 128 inline uint64_t getWord(unsigned bitPosition) const 129 { return isSingleWord() ? VAL : pVal[whichWord(bitPosition)]; } 130 131 /// @brief Converts a char array into an integer. 132 void StrToAPInt(const char *StrStart, unsigned slen, uint8_t radix); 133 134public: 135 /// @brief Create a new APInt of numBits bit-width, and initialized as val. 136 APInt(uint64_t val = 0, unsigned numBits = APINT_BITS_PER_WORD); 137 138 /// @brief Create a new APInt of numBits bit-width, and initialized as 139 /// bigVal[]. 140 APInt(unsigned numBits, uint64_t bigVal[]); 141 142 /// @brief Create a new APInt by translating the string represented 143 /// integer value. 144 APInt(const std::string& Val, uint8_t radix = 10); 145 146 /// @brief Create a new APInt by translating the char array represented 147 /// integer value. 148 APInt(const char StrStart[], unsigned slen, uint8_t radix); 149 150 /// @brief Copy Constructor. 151 APInt(const APInt& API); 152 153 /// @brief Destructor. 154 ~APInt(); 155 156 /// @brief Copy assignment operator. 157 APInt& operator=(const APInt& RHS); 158 159 /// Assigns an integer value to the APInt. 160 /// @brief Assignment operator. 161 APInt& operator=(uint64_t RHS); 162 163 /// Increments the APInt by one. 164 /// @brief Postfix increment operator. 165 inline const APInt operator++(int) { 166 APInt API(*this); 167 return ++API; 168 } 169 170 /// Increments the APInt by one. 171 /// @brief Prefix increment operator. 172 APInt& operator++(); 173 174 /// Decrements the APInt by one. 175 /// @brief Postfix decrement operator. 176 inline const APInt operator--(int) { 177 APInt API(*this); 178 return --API; 179 } 180 181 /// Decrements the APInt by one. 182 /// @brief Prefix decrement operator. 183 APInt& operator--(); 184 185 /// Performs bitwise AND operation on this APInt and the given APInt& RHS, 186 /// assigns the result to this APInt. 187 /// @brief Bitwise AND assignment operator. 188 APInt& operator&=(const APInt& RHS); 189 190 /// Performs bitwise OR operation on this APInt and the given APInt& RHS, 191 /// assigns the result to this APInt. 192 /// @brief Bitwise OR assignment operator. 193 APInt& operator|=(const APInt& RHS); 194 195 /// Performs bitwise XOR operation on this APInt and the given APInt& RHS, 196 /// assigns the result to this APInt. 197 /// @brief Bitwise XOR assignment operator. 198 APInt& operator^=(const APInt& RHS); 199 200 /// Performs a bitwise complement operation on this APInt. 201 /// @brief Bitwise complement operator. 202 APInt operator~() const; 203 204 /// Multiplies this APInt by the given APInt& RHS and 205 /// assigns the result to this APInt. 206 /// @brief Multiplication assignment operator. 207 APInt& operator*=(const APInt& RHS); 208 209 /// Adds this APInt by the given APInt& RHS and 210 /// assigns the result to this APInt. 211 /// @brief Addition assignment operator. 212 APInt& operator+=(const APInt& RHS); 213 214 /// Subtracts this APInt by the given APInt &RHS and 215 /// assigns the result to this APInt. 216 /// @brief Subtraction assignment operator. 217 APInt& operator-=(const APInt& RHS); 218 219 /// Performs bitwise AND operation on this APInt and 220 /// the given APInt& RHS. 221 /// @brief Bitwise AND operator. 222 APInt operator&(const APInt& RHS) const; 223 224 /// Performs bitwise OR operation on this APInt and the given APInt& RHS. 225 /// @brief Bitwise OR operator. 226 APInt operator|(const APInt& RHS) const; 227 228 /// Performs bitwise XOR operation on this APInt and the given APInt& RHS. 229 /// @brief Bitwise XOR operator. 230 APInt operator^(const APInt& RHS) const; 231 232 /// Performs logical AND operation on this APInt and the given APInt& RHS. 233 /// @brief Logical AND operator. 234 bool operator&&(const APInt& RHS) const; 235 236 /// Performs logical OR operation on this APInt and the given APInt& RHS. 237 /// @brief Logical OR operator. 238 bool operator||(const APInt& RHS) const; 239 240 /// Performs logical negation operation on this APInt. 241 /// @brief Logical negation operator. 242 bool operator !() const; 243 244 /// Multiplies this APInt by the given APInt& RHS. 245 /// @brief Multiplication operator. 246 APInt operator*(const APInt& RHS) const; 247 248 /// Adds this APInt by the given APInt& RHS. 249 /// @brief Addition operator. 250 APInt operator+(const APInt& RHS) const; 251 252 /// Subtracts this APInt by the given APInt& RHS 253 /// @brief Subtraction operator. 254 APInt operator-(const APInt& RHS) const; 255 256 /// 257 inline APInt operator-() const { 258 return APInt(0, BitsNum) - (*this); 259 } 260 261 /// @brief Array-indexing support. 262 bool operator[](unsigned bitPosition) const; 263 264 /// Compare this APInt with the given APInt& RHS 265 /// for the validity of the equality relationship. 266 /// @brief Equality operator. 267 bool operator==(const APInt& RHS) const; 268 269 /// Compare this APInt with the given uint64_t value 270 /// for the validity of the equality relationship. 271 /// @brief Equality operator. 272 bool operator==(uint64_t Val) const; 273 274 /// Compare this APInt with the given APInt& RHS 275 /// for the validity of the inequality relationship. 276 /// @brief Inequality operator. 277 inline bool operator!=(const APInt& RHS) const { 278 return !((*this) == RHS); 279 } 280 281 /// Compare this APInt with the given uint64_t value 282 /// for the validity of the inequality relationship. 283 /// @brief Inequality operator. 284 inline bool operator!=(uint64_t Val) const { 285 return !((*this) == Val); 286 } 287 288 /// Compare this APInt with the given APInt& RHS for 289 /// the validity of the less-than relationship. 290 /// @brief Less-than operator. 291 bool operator <(const APInt& RHS) const; 292 293 /// Compare this APInt with the given APInt& RHS for the validity 294 /// of the less-than-or-equal relationship. 295 /// @brief Less-than-or-equal operator. 296 bool operator<=(const APInt& RHS) const; 297 298 /// Compare this APInt with the given APInt& RHS for the validity 299 /// of the greater-than relationship. 300 /// @brief Greater-than operator. 301 bool operator> (const APInt& RHS) const; 302 303 /// @brief Greater-than-or-equal operator. 304 /// Compare this APInt with the given APInt& RHS for the validity 305 /// of the greater-than-or-equal relationship. 306 bool operator>=(const APInt& RHS) const; 307 308 /// @returns a uint64_t value from this APInt. If this APInt contains a single 309 /// word, just returns VAL, otherwise pVal[0]. 310 inline uint64_t getValue() { 311 if (isSingleWord()) 312 return VAL; 313 assert(0 && "This APInt's bitwidth > 64"); 314 } 315 316 /// @returns the largest value for an APInt of the specified bit-width and 317 /// if isSign == true, it should be largest signed value, otherwise largest 318 /// unsigned value. 319 /// @brief Gets max value of the APInt with bitwidth <= 64. 320 static APInt getMaxValue(unsigned numBits, bool isSign); 321 322 /// @returns the smallest value for an APInt of the given bit-width and 323 /// if isSign == true, it should be smallest signed value, otherwise zero. 324 /// @brief Gets min value of the APInt with bitwidth <= 64. 325 static APInt getMinValue(unsigned numBits, bool isSign); 326 327 /// @returns the all-ones value for an APInt of the specified bit-width. 328 /// @brief Get the all-ones value. 329 static APInt getAllOnesValue(unsigned numBits); 330 331 /// @brief Set every bit to 1. 332 APInt& set(); 333 334 /// Set the given bit to 1 whose position is given as "bitPosition". 335 /// @brief Set a given bit to 1. 336 APInt& set(unsigned bitPosition); 337 338 /// @returns the '0' value for an APInt of the specified bit-width. 339 /// @brief Get the '0' value. 340 static APInt getNullValue(unsigned numBits); 341 342 /// @brief Set every bit to 0. 343 APInt& clear(); 344 345 /// Set the given bit to 0 whose position is given as "bitPosition". 346 /// @brief Set a given bit to 0. 347 APInt& clear(unsigned bitPosition); 348 349 /// @brief Toggle every bit to its opposite value. 350 APInt& flip(); 351 352 /// Toggle a given bit to its opposite value whose position is given 353 /// as "bitPosition". 354 /// @brief Toggles a given bit to its opposite value. 355 APInt& flip(unsigned bitPosition); 356 357 /// @returns a character interpretation of the APInt. 358 std::string to_string(uint8_t radix = 10) const; 359 360 /// Get an APInt with the same BitsNum as this APInt, just zero mask 361 /// the low bits and right shift to the least significant bit. 362 /// @returns the high "numBits" bits of this APInt. 363 APInt HiBits(unsigned numBits) const; 364 365 /// Get an APInt with the same BitsNum as this APInt, just zero mask 366 /// the high bits. 367 /// @returns the low "numBits" bits of this APInt. 368 APInt LoBits(unsigned numBits) const; 369 370 /// @returns true if the argument APInt value is a power of two > 0. 371 inline const bool isPowerOf2() const { 372 return (!!*this) && !(*this & (*this - 1)); 373 } 374 375 /// @returns the number of zeros from the most significant bit to the first 376 /// one bits. 377 unsigned CountLeadingZeros() const; 378 379 /// @returns the number of zeros from the least significant bit to the first 380 /// one bit. 381 unsigned CountTrailingZeros() const; 382 383 /// @returns the number of set bits. 384 unsigned CountPopulation() const; 385 386 /// @returns the total number of bits. 387 inline unsigned getNumBits() const 388 { return BitsNum; } 389 390}; 391 392namespace APIntOps { 393 394/// @brief Check if the specified APInt has a N-bits integer value. 395inline bool isIntN(unsigned N, const APInt& APIVal) { 396 if (APIVal.isSingleWord()) { 397 APInt Tmp(N, APIVal.VAL); 398 return Tmp == APIVal; 399 } else { 400 APInt Tmp(N, APIVal.pVal); 401 return Tmp == APIVal; 402 } 403} 404 405/// @returns true if the argument APInt value is a sequence of ones 406/// starting at the least significant bit with the remainder zero. 407inline const bool isMask(unsigned numBits, const APInt& APIVal) { 408 return APIVal && ((APIVal + 1) & APIVal) == 0; 409} 410 411/// @returns true if the argument APInt value contains a sequence of ones 412/// with the remainder zero. 413inline const bool isShiftedMask(unsigned numBits, const APInt& APIVal) { 414 return isMask(numBits, (APIVal - 1) | APIVal); 415} 416 417/// @returns a byte-swapped representation of the specified APInt Value. 418APInt ByteSwap(const APInt& APIVal); 419 420/// @returns the floor log base 2 of the specified APInt value. 421inline APInt LogBase2(const APInt& APIVal) { 422 return APIVal.getNumWords() * APInt::APINT_BITS_PER_WORD - 423 APIVal.CountLeadingZeros(); 424} 425 426/// @returns the greatest common divisor of the two values 427/// using Euclid's algorithm. 428APInt GreatestCommonDivisor(const APInt& API1, const APInt& API2); 429 430/// Arithmetic right-shift the APInt by shiftAmt. 431/// @brief Arithmetic right-shift function. 432APInt ashr(const APInt& LHS, unsigned shiftAmt); 433 434/// Logical right-shift the APInt by shiftAmt. 435/// @brief Logical right-shift function. 436APInt lshr(const APInt& LHS, unsigned shiftAmt); 437 438/// Left-shift the APInt by shiftAmt. 439/// @brief Left-shift function. 440APInt shl(const APInt& LHS, unsigned shiftAmt); 441 442/// Signed divide APInt LHS by APInt RHS. 443/// @brief Signed division function for APInt. 444inline APInt sdiv(const APInt& LHS, const APInt& RHS) { 445 bool isSignedLHS = LHS[LHS.BitsNum - 1], isSignedRHS = RHS[RHS.BitsNum - 1]; 446 APInt API = udiv(isSignedLHS ? -LHS : LHS, isSignedRHS ? -RHS : RHS); 447 return isSignedLHS != isSignedRHS ? -API : API;; 448} 449 450/// Unsigned divide APInt LHS by APInt RHS. 451/// @brief Unsigned division function for APInt. 452APInt udiv(const APInt& LHS, const APInt& RHS); 453 454/// Signed remainder operation on APInt. 455/// @brief Function for signed remainder operation. 456inline APInt srem(const APInt& LHS, const APInt& RHS) { 457 bool isSignedLHS = LHS[LHS.BitsNum - 1], isSignedRHS = RHS[RHS.BitsNum - 1]; 458 APInt API = urem(isSignedLHS ? -LHS : LHS, isSignedRHS ? -RHS : RHS); 459 return isSignedLHS ? -API : API; 460} 461 462/// Unsigned remainder operation on APInt. 463/// @brief Function for unsigned remainder operation. 464APInt urem(const APInt& LHS, const APInt& RHS); 465 466/// Performs multiplication on APInt values. 467/// @brief Function for multiplication operation. 468inline APInt mul(const APInt& LHS, const APInt& RHS) { 469 return LHS * RHS; 470} 471 472/// Performs addition on APInt values. 473/// @brief Function for addition operation. 474inline APInt add(const APInt& LHS, const APInt& RHS) { 475 return LHS + RHS; 476} 477 478/// Performs subtraction on APInt values. 479/// @brief Function for subtraction operation. 480inline APInt sub(const APInt& LHS, const APInt& RHS) { 481 return LHS - RHS; 482} 483 484} // End of APIntOps namespace 485 486} // End of llvm namespace 487 488#endif 489