b08564ca733203550036cf1bc735871a2a7c571c
[oota-llvm.git] / include / llvm / ADT / APInt.h
1 //===-- llvm/ADT/APInt.h - For Arbitrary Precision Integer -----*- C++ -*--===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements a class to represent arbitrary precision integral
11 // constant values and operations on them.
12 //
13 //===----------------------------------------------------------------------===//
14
15 #ifndef LLVM_APINT_H
16 #define LLVM_APINT_H
17
18 #include "llvm/ADT/ArrayRef.h"
19 #include "llvm/Support/MathExtras.h"
20 #include <cassert>
21 #include <climits>
22 #include <cstring>
23 #include <string>
24
25 namespace llvm {
26   class Deserializer;
27   class FoldingSetNodeID;
28   class Serializer;
29   class StringRef;
30   class hash_code;
31   class raw_ostream;
32
33   template<typename T>
34   class SmallVectorImpl;
35
36   // An unsigned host type used as a single part of a multi-part
37   // bignum.
38   typedef uint64_t integerPart;
39
40   const unsigned int host_char_bit = 8;
41   const unsigned int integerPartWidth = host_char_bit *
42     static_cast<unsigned int>(sizeof(integerPart));
43
44 //===----------------------------------------------------------------------===//
45 //                              APInt Class
46 //===----------------------------------------------------------------------===//
47
48 /// APInt - This class represents arbitrary precision constant integral values.
49 /// It is a functional replacement for common case unsigned integer type like
50 /// "unsigned", "unsigned long" or "uint64_t", but also allows non-byte-width
51 /// integer sizes and large integer value types such as 3-bits, 15-bits, or more
52 /// than 64-bits of precision. APInt provides a variety of arithmetic operators
53 /// and methods to manipulate integer values of any bit-width. It supports both
54 /// the typical integer arithmetic and comparison operations as well as bitwise
55 /// manipulation.
56 ///
57 /// The class has several invariants worth noting:
58 ///   * All bit, byte, and word positions are zero-based.
59 ///   * Once the bit width is set, it doesn't change except by the Truncate,
60 ///     SignExtend, or ZeroExtend operations.
61 ///   * All binary operators must be on APInt instances of the same bit width.
62 ///     Attempting to use these operators on instances with different bit
63 ///     widths will yield an assertion.
64 ///   * The value is stored canonically as an unsigned value. For operations
65 ///     where it makes a difference, there are both signed and unsigned variants
66 ///     of the operation. For example, sdiv and udiv. However, because the bit
67 ///     widths must be the same, operations such as Mul and Add produce the same
68 ///     results regardless of whether the values are interpreted as signed or
69 ///     not.
70 ///   * In general, the class tries to follow the style of computation that LLVM
71 ///     uses in its IR. This simplifies its use for LLVM.
72 ///
73 /// @brief Class for arbitrary precision integers.
74 class APInt {
75   unsigned BitWidth;      ///< The number of bits in this APInt.
76
77   /// This union is used to store the integer value. When the
78   /// integer bit-width <= 64, it uses VAL, otherwise it uses pVal.
79   union {
80     uint64_t VAL;    ///< Used to store the <= 64 bits integer value.
81     uint64_t *pVal;  ///< Used to store the >64 bits integer value.
82   };
83
84   /// This enum is used to hold the constants we needed for APInt.
85   enum {
86     /// Bits in a word
87     APINT_BITS_PER_WORD = static_cast<unsigned int>(sizeof(uint64_t)) *
88                           CHAR_BIT,
89     /// Byte size of a word
90     APINT_WORD_SIZE = static_cast<unsigned int>(sizeof(uint64_t))
91   };
92
93   /// This constructor is used only internally for speed of construction of
94   /// temporaries. It is unsafe for general use so it is not public.
95   /// @brief Fast internal constructor
96   APInt(uint64_t* val, unsigned bits) : BitWidth(bits), pVal(val) { }
97
98   /// @returns true if the number of bits <= 64, false otherwise.
99   /// @brief Determine if this APInt just has one word to store value.
100   bool isSingleWord() const {
101     return BitWidth <= APINT_BITS_PER_WORD;
102   }
103
104   /// @returns the word position for the specified bit position.
105   /// @brief Determine which word a bit is in.
106   static unsigned whichWord(unsigned bitPosition) {
107     return bitPosition / APINT_BITS_PER_WORD;
108   }
109
110   /// @returns the bit position in a word for the specified bit position
111   /// in the APInt.
112   /// @brief Determine which bit in a word a bit is in.
113   static unsigned whichBit(unsigned bitPosition) {
114     return bitPosition % APINT_BITS_PER_WORD;
115   }
116
117   /// This method generates and returns a uint64_t (word) mask for a single
118   /// bit at a specific bit position. This is used to mask the bit in the
119   /// corresponding word.
120   /// @returns a uint64_t with only bit at "whichBit(bitPosition)" set
121   /// @brief Get a single bit mask.
122   static uint64_t maskBit(unsigned bitPosition) {
123     return 1ULL << whichBit(bitPosition);
124   }
125
126   /// This method is used internally to clear the to "N" bits in the high order
127   /// word that are not used by the APInt. This is needed after the most
128   /// significant word is assigned a value to ensure that those bits are
129   /// zero'd out.
130   /// @brief Clear unused high order bits
131   APInt& clearUnusedBits() {
132     // Compute how many bits are used in the final word
133     unsigned wordBits = BitWidth % APINT_BITS_PER_WORD;
134     if (wordBits == 0)
135       // If all bits are used, we want to leave the value alone. This also
136       // avoids the undefined behavior of >> when the shift is the same size as
137       // the word size (64).
138       return *this;
139
140     // Mask out the high bits.
141     uint64_t mask = ~uint64_t(0ULL) >> (APINT_BITS_PER_WORD - wordBits);
142     if (isSingleWord())
143       VAL &= mask;
144     else
145       pVal[getNumWords() - 1] &= mask;
146     return *this;
147   }
148
149   /// @returns the corresponding word for the specified bit position.
150   /// @brief Get the word corresponding to a bit position
151   uint64_t getWord(unsigned bitPosition) const {
152     return isSingleWord() ? VAL : pVal[whichWord(bitPosition)];
153   }
154
155   /// Converts a string into a number.  The string must be non-empty
156   /// and well-formed as a number of the given base. The bit-width
157   /// must be sufficient to hold the result.
158   ///
159   /// This is used by the constructors that take string arguments.
160   ///
161   /// StringRef::getAsInteger is superficially similar but (1) does
162   /// not assume that the string is well-formed and (2) grows the
163   /// result to hold the input.
164   ///
165   /// @param radix 2, 8, 10, 16, or 36
166   /// @brief Convert a char array into an APInt
167   void fromString(unsigned numBits, StringRef str, uint8_t radix);
168
169   /// This is used by the toString method to divide by the radix. It simply
170   /// provides a more convenient form of divide for internal use since KnuthDiv
171   /// has specific constraints on its inputs. If those constraints are not met
172   /// then it provides a simpler form of divide.
173   /// @brief An internal division function for dividing APInts.
174   static void divide(const APInt LHS, unsigned lhsWords,
175                      const APInt &RHS, unsigned rhsWords,
176                      APInt *Quotient, APInt *Remainder);
177
178   /// out-of-line slow case for inline constructor
179   void initSlowCase(unsigned numBits, uint64_t val, bool isSigned);
180
181   /// shared code between two array constructors
182   void initFromArray(ArrayRef<uint64_t> array);
183
184   /// out-of-line slow case for inline copy constructor
185   void initSlowCase(const APInt& that);
186
187   /// out-of-line slow case for shl
188   APInt shlSlowCase(unsigned shiftAmt) const;
189
190   /// out-of-line slow case for operator&
191   APInt AndSlowCase(const APInt& RHS) const;
192
193   /// out-of-line slow case for operator|
194   APInt OrSlowCase(const APInt& RHS) const;
195
196   /// out-of-line slow case for operator^
197   APInt XorSlowCase(const APInt& RHS) const;
198
199   /// out-of-line slow case for operator=
200   APInt& AssignSlowCase(const APInt& RHS);
201
202   /// out-of-line slow case for operator==
203   bool EqualSlowCase(const APInt& RHS) const;
204
205   /// out-of-line slow case for operator==
206   bool EqualSlowCase(uint64_t Val) const;
207
208   /// out-of-line slow case for countLeadingZeros
209   unsigned countLeadingZerosSlowCase() const;
210
211   /// out-of-line slow case for countTrailingOnes
212   unsigned countTrailingOnesSlowCase() const;
213
214   /// out-of-line slow case for countPopulation
215   unsigned countPopulationSlowCase() const;
216
217 public:
218   /// @name Constructors
219   /// @{
220   /// If isSigned is true then val is treated as if it were a signed value
221   /// (i.e. as an int64_t) and the appropriate sign extension to the bit width
222   /// will be done. Otherwise, no sign extension occurs (high order bits beyond
223   /// the range of val are zero filled).
224   /// @param numBits the bit width of the constructed APInt
225   /// @param val the initial value of the APInt
226   /// @param isSigned how to treat signedness of val
227   /// @brief Create a new APInt of numBits width, initialized as val.
228   APInt(unsigned numBits, uint64_t val, bool isSigned = false)
229     : BitWidth(numBits), VAL(0) {
230     assert(BitWidth && "bitwidth too small");
231     if (isSingleWord())
232       VAL = val;
233     else
234       initSlowCase(numBits, val, isSigned);
235     clearUnusedBits();
236   }
237
238   /// Note that bigVal.size() can be smaller or larger than the corresponding
239   /// bit width but any extraneous bits will be dropped.
240   /// @param numBits the bit width of the constructed APInt
241   /// @param bigVal a sequence of words to form the initial value of the APInt
242   /// @brief Construct an APInt of numBits width, initialized as bigVal[].
243   APInt(unsigned numBits, ArrayRef<uint64_t> bigVal);
244   /// Equivalent to APInt(numBits, ArrayRef<uint64_t>(bigVal, numWords)), but
245   /// deprecated because this constructor is prone to ambiguity with the
246   /// APInt(unsigned, uint64_t, bool) constructor.
247   ///
248   /// If this overload is ever deleted, care should be taken to prevent calls
249   /// from being incorrectly captured by the APInt(unsigned, uint64_t, bool)
250   /// constructor.
251   APInt(unsigned numBits, unsigned numWords, const uint64_t bigVal[]);
252
253   /// This constructor interprets the string \arg str in the given radix. The
254   /// interpretation stops when the first character that is not suitable for the
255   /// radix is encountered, or the end of the string. Acceptable radix values
256   /// are 2, 8, 10, 16, and 36. It is an error for the value implied by the 
257   /// string to require more bits than numBits.
258   ///
259   /// @param numBits the bit width of the constructed APInt
260   /// @param str the string to be interpreted
261   /// @param radix the radix to use for the conversion 
262   /// @brief Construct an APInt from a string representation.
263   APInt(unsigned numBits, StringRef str, uint8_t radix);
264
265   /// Simply makes *this a copy of that.
266   /// @brief Copy Constructor.
267   APInt(const APInt& that)
268     : BitWidth(that.BitWidth), VAL(0) {
269     assert(BitWidth && "bitwidth too small");
270     if (isSingleWord())
271       VAL = that.VAL;
272     else
273       initSlowCase(that);
274   }
275
276   /// @brief Destructor.
277   ~APInt() {
278     if (!isSingleWord())
279       delete [] pVal;
280   }
281
282   /// Default constructor that creates an uninitialized APInt.  This is useful
283   ///  for object deserialization (pair this with the static method Read).
284   explicit APInt() : BitWidth(1) {}
285
286   /// Profile - Used to insert APInt objects, or objects that contain APInt
287   ///  objects, into FoldingSets.
288   void Profile(FoldingSetNodeID& id) const;
289
290   /// @}
291   /// @name Value Tests
292   /// @{
293   /// This tests the high bit of this APInt to determine if it is set.
294   /// @returns true if this APInt is negative, false otherwise
295   /// @brief Determine sign of this APInt.
296   bool isNegative() const {
297     return (*this)[BitWidth - 1];
298   }
299
300   /// This tests the high bit of the APInt to determine if it is unset.
301   /// @brief Determine if this APInt Value is non-negative (>= 0)
302   bool isNonNegative() const {
303     return !isNegative();
304   }
305
306   /// This tests if the value of this APInt is positive (> 0). Note
307   /// that 0 is not a positive value.
308   /// @returns true if this APInt is positive.
309   /// @brief Determine if this APInt Value is positive.
310   bool isStrictlyPositive() const {
311     return isNonNegative() && !!*this;
312   }
313
314   /// This checks to see if the value has all bits of the APInt are set or not.
315   /// @brief Determine if all bits are set
316   bool isAllOnesValue() const {
317     return countPopulation() == BitWidth;
318   }
319
320   /// This checks to see if the value of this APInt is the maximum unsigned
321   /// value for the APInt's bit width.
322   /// @brief Determine if this is the largest unsigned value.
323   bool isMaxValue() const {
324     return countPopulation() == BitWidth;
325   }
326
327   /// This checks to see if the value of this APInt is the maximum signed
328   /// value for the APInt's bit width.
329   /// @brief Determine if this is the largest signed value.
330   bool isMaxSignedValue() const {
331     return BitWidth == 1 ? VAL == 0 :
332                           !isNegative() && countPopulation() == BitWidth - 1;
333   }
334
335   /// This checks to see if the value of this APInt is the minimum unsigned
336   /// value for the APInt's bit width.
337   /// @brief Determine if this is the smallest unsigned value.
338   bool isMinValue() const {
339     return !*this;
340   }
341
342   /// This checks to see if the value of this APInt is the minimum signed
343   /// value for the APInt's bit width.
344   /// @brief Determine if this is the smallest signed value.
345   bool isMinSignedValue() const {
346     return BitWidth == 1 ? VAL == 1 : isNegative() && isPowerOf2();
347   }
348
349   /// @brief Check if this APInt has an N-bits unsigned integer value.
350   bool isIntN(unsigned N) const {
351     assert(N && "N == 0 ???");
352     if (N >= getBitWidth())
353       return true;
354
355     if (isSingleWord())
356       return isUIntN(N, VAL);
357     return APInt(N, makeArrayRef(pVal, getNumWords())).zext(getBitWidth())
358       == (*this);
359   }
360
361   /// @brief Check if this APInt has an N-bits signed integer value.
362   bool isSignedIntN(unsigned N) const {
363     assert(N && "N == 0 ???");
364     return getMinSignedBits() <= N;
365   }
366
367   /// @returns true if the argument APInt value is a power of two > 0.
368   bool isPowerOf2() const {
369     if (isSingleWord())
370       return isPowerOf2_64(VAL);
371     return countPopulationSlowCase() == 1;
372   }
373
374   /// isSignBit - Return true if this is the value returned by getSignBit.
375   bool isSignBit() const { return isMinSignedValue(); }
376
377   /// This converts the APInt to a boolean value as a test against zero.
378   /// @brief Boolean conversion function.
379   bool getBoolValue() const {
380     return !!*this;
381   }
382
383   /// getLimitedValue - If this value is smaller than the specified limit,
384   /// return it, otherwise return the limit value.  This causes the value
385   /// to saturate to the limit.
386   uint64_t getLimitedValue(uint64_t Limit = ~0ULL) const {
387     return (getActiveBits() > 64 || getZExtValue() > Limit) ?
388       Limit :  getZExtValue();
389   }
390
391   /// @}
392   /// @name Value Generators
393   /// @{
394   /// @brief Gets maximum unsigned value of APInt for specific bit width.
395   static APInt getMaxValue(unsigned numBits) {
396     return getAllOnesValue(numBits);
397   }
398
399   /// @brief Gets maximum signed value of APInt for a specific bit width.
400   static APInt getSignedMaxValue(unsigned numBits) {
401     APInt API = getAllOnesValue(numBits);
402     API.clearBit(numBits - 1);
403     return API;
404   }
405
406   /// @brief Gets minimum unsigned value of APInt for a specific bit width.
407   static APInt getMinValue(unsigned numBits) {
408     return APInt(numBits, 0);
409   }
410
411   /// @brief Gets minimum signed value of APInt for a specific bit width.
412   static APInt getSignedMinValue(unsigned numBits) {
413     APInt API(numBits, 0);
414     API.setBit(numBits - 1);
415     return API;
416   }
417
418   /// getSignBit - This is just a wrapper function of getSignedMinValue(), and
419   /// it helps code readability when we want to get a SignBit.
420   /// @brief Get the SignBit for a specific bit width.
421   static APInt getSignBit(unsigned BitWidth) {
422     return getSignedMinValue(BitWidth);
423   }
424
425   /// @returns the all-ones value for an APInt of the specified bit-width.
426   /// @brief Get the all-ones value.
427   static APInt getAllOnesValue(unsigned numBits) {
428     return APInt(numBits, -1ULL, true);
429   }
430
431   /// @returns the '0' value for an APInt of the specified bit-width.
432   /// @brief Get the '0' value.
433   static APInt getNullValue(unsigned numBits) {
434     return APInt(numBits, 0);
435   }
436
437   /// Get an APInt with the same BitWidth as this APInt, just zero mask
438   /// the low bits and right shift to the least significant bit.
439   /// @returns the high "numBits" bits of this APInt.
440   APInt getHiBits(unsigned numBits) const;
441
442   /// Get an APInt with the same BitWidth as this APInt, just zero mask
443   /// the high bits.
444   /// @returns the low "numBits" bits of this APInt.
445   APInt getLoBits(unsigned numBits) const;
446
447   /// getOneBitSet - Return an APInt with exactly one bit set in the result.
448   static APInt getOneBitSet(unsigned numBits, unsigned BitNo) {
449     APInt Res(numBits, 0);
450     Res.setBit(BitNo);
451     return Res;
452   }
453   
454   /// Constructs an APInt value that has a contiguous range of bits set. The
455   /// bits from loBit (inclusive) to hiBit (exclusive) will be set. All other
456   /// bits will be zero. For example, with parameters(32, 0, 16) you would get
457   /// 0x0000FFFF. If hiBit is less than loBit then the set bits "wrap". For
458   /// example, with parameters (32, 28, 4), you would get 0xF000000F.
459   /// @param numBits the intended bit width of the result
460   /// @param loBit the index of the lowest bit set.
461   /// @param hiBit the index of the highest bit set.
462   /// @returns An APInt value with the requested bits set.
463   /// @brief Get a value with a block of bits set.
464   static APInt getBitsSet(unsigned numBits, unsigned loBit, unsigned hiBit) {
465     assert(hiBit <= numBits && "hiBit out of range");
466     assert(loBit < numBits && "loBit out of range");
467     if (hiBit < loBit)
468       return getLowBitsSet(numBits, hiBit) |
469              getHighBitsSet(numBits, numBits-loBit);
470     return getLowBitsSet(numBits, hiBit-loBit).shl(loBit);
471   }
472
473   /// Constructs an APInt value that has the top hiBitsSet bits set.
474   /// @param numBits the bitwidth of the result
475   /// @param hiBitsSet the number of high-order bits set in the result.
476   /// @brief Get a value with high bits set
477   static APInt getHighBitsSet(unsigned numBits, unsigned hiBitsSet) {
478     assert(hiBitsSet <= numBits && "Too many bits to set!");
479     // Handle a degenerate case, to avoid shifting by word size
480     if (hiBitsSet == 0)
481       return APInt(numBits, 0);
482     unsigned shiftAmt = numBits - hiBitsSet;
483     // For small values, return quickly
484     if (numBits <= APINT_BITS_PER_WORD)
485       return APInt(numBits, ~0ULL << shiftAmt);
486     return getAllOnesValue(numBits).shl(shiftAmt);
487   }
488
489   /// Constructs an APInt value that has the bottom loBitsSet bits set.
490   /// @param numBits the bitwidth of the result
491   /// @param loBitsSet the number of low-order bits set in the result.
492   /// @brief Get a value with low bits set
493   static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet) {
494     assert(loBitsSet <= numBits && "Too many bits to set!");
495     // Handle a degenerate case, to avoid shifting by word size
496     if (loBitsSet == 0)
497       return APInt(numBits, 0);
498     if (loBitsSet == APINT_BITS_PER_WORD)
499       return APInt(numBits, -1ULL);
500     // For small values, return quickly.
501     if (loBitsSet <= APINT_BITS_PER_WORD)
502       return APInt(numBits, -1ULL >> (APINT_BITS_PER_WORD - loBitsSet));
503     return getAllOnesValue(numBits).lshr(numBits - loBitsSet);
504   }
505
506   /// \brief Overload to compute a hash_code for an APInt value.
507   friend hash_code hash_value(const APInt &Arg);
508
509   /// This function returns a pointer to the internal storage of the APInt.
510   /// This is useful for writing out the APInt in binary form without any
511   /// conversions.
512   const uint64_t* getRawData() const {
513     if (isSingleWord())
514       return &VAL;
515     return &pVal[0];
516   }
517
518   /// @}
519   /// @name Unary Operators
520   /// @{
521   /// @returns a new APInt value representing *this incremented by one
522   /// @brief Postfix increment operator.
523   const APInt operator++(int) {
524     APInt API(*this);
525     ++(*this);
526     return API;
527   }
528
529   /// @returns *this incremented by one
530   /// @brief Prefix increment operator.
531   APInt& operator++();
532
533   /// @returns a new APInt representing *this decremented by one.
534   /// @brief Postfix decrement operator.
535   const APInt operator--(int) {
536     APInt API(*this);
537     --(*this);
538     return API;
539   }
540
541   /// @returns *this decremented by one.
542   /// @brief Prefix decrement operator.
543   APInt& operator--();
544
545   /// Performs a bitwise complement operation on this APInt.
546   /// @returns an APInt that is the bitwise complement of *this
547   /// @brief Unary bitwise complement operator.
548   APInt operator~() const {
549     APInt Result(*this);
550     Result.flipAllBits();
551     return Result;
552   }
553
554   /// Negates *this using two's complement logic.
555   /// @returns An APInt value representing the negation of *this.
556   /// @brief Unary negation operator
557   APInt operator-() const {
558     return APInt(BitWidth, 0) - (*this);
559   }
560
561   /// Performs logical negation operation on this APInt.
562   /// @returns true if *this is zero, false otherwise.
563   /// @brief Logical negation operator.
564   bool operator!() const;
565
566   /// @}
567   /// @name Assignment Operators
568   /// @{
569   /// @returns *this after assignment of RHS.
570   /// @brief Copy assignment operator.
571   APInt& operator=(const APInt& RHS) {
572     // If the bitwidths are the same, we can avoid mucking with memory
573     if (isSingleWord() && RHS.isSingleWord()) {
574       VAL = RHS.VAL;
575       BitWidth = RHS.BitWidth;
576       return clearUnusedBits();
577     }
578
579     return AssignSlowCase(RHS);
580   }
581
582   /// The RHS value is assigned to *this. If the significant bits in RHS exceed
583   /// the bit width, the excess bits are truncated. If the bit width is larger
584   /// than 64, the value is zero filled in the unspecified high order bits.
585   /// @returns *this after assignment of RHS value.
586   /// @brief Assignment operator.
587   APInt& operator=(uint64_t RHS);
588
589   /// Performs a bitwise AND operation on this APInt and RHS. The result is
590   /// assigned to *this.
591   /// @returns *this after ANDing with RHS.
592   /// @brief Bitwise AND assignment operator.
593   APInt& operator&=(const APInt& RHS);
594
595   /// Performs a bitwise OR operation on this APInt and RHS. The result is
596   /// assigned *this;
597   /// @returns *this after ORing with RHS.
598   /// @brief Bitwise OR assignment operator.
599   APInt& operator|=(const APInt& RHS);
600
601   /// Performs a bitwise OR operation on this APInt and RHS. RHS is
602   /// logically zero-extended or truncated to match the bit-width of
603   /// the LHS.
604   /// 
605   /// @brief Bitwise OR assignment operator.
606   APInt& operator|=(uint64_t RHS) {
607     if (isSingleWord()) {
608       VAL |= RHS;
609       clearUnusedBits();
610     } else {
611       pVal[0] |= RHS;
612     }
613     return *this;
614   }
615
616   /// Performs a bitwise XOR operation on this APInt and RHS. The result is
617   /// assigned to *this.
618   /// @returns *this after XORing with RHS.
619   /// @brief Bitwise XOR assignment operator.
620   APInt& operator^=(const APInt& RHS);
621
622   /// Multiplies this APInt by RHS and assigns the result to *this.
623   /// @returns *this
624   /// @brief Multiplication assignment operator.
625   APInt& operator*=(const APInt& RHS);
626
627   /// Adds RHS to *this and assigns the result to *this.
628   /// @returns *this
629   /// @brief Addition assignment operator.
630   APInt& operator+=(const APInt& RHS);
631
632   /// Subtracts RHS from *this and assigns the result to *this.
633   /// @returns *this
634   /// @brief Subtraction assignment operator.
635   APInt& operator-=(const APInt& RHS);
636
637   /// Shifts *this left by shiftAmt and assigns the result to *this.
638   /// @returns *this after shifting left by shiftAmt
639   /// @brief Left-shift assignment function.
640   APInt& operator<<=(unsigned shiftAmt) {
641     *this = shl(shiftAmt);
642     return *this;
643   }
644
645   /// @}
646   /// @name Binary Operators
647   /// @{
648   /// Performs a bitwise AND operation on *this and RHS.
649   /// @returns An APInt value representing the bitwise AND of *this and RHS.
650   /// @brief Bitwise AND operator.
651   APInt operator&(const APInt& RHS) const {
652     assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
653     if (isSingleWord())
654       return APInt(getBitWidth(), VAL & RHS.VAL);
655     return AndSlowCase(RHS);
656   }
657   APInt And(const APInt& RHS) const {
658     return this->operator&(RHS);
659   }
660
661   /// Performs a bitwise OR operation on *this and RHS.
662   /// @returns An APInt value representing the bitwise OR of *this and RHS.
663   /// @brief Bitwise OR operator.
664   APInt operator|(const APInt& RHS) const {
665     assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
666     if (isSingleWord())
667       return APInt(getBitWidth(), VAL | RHS.VAL);
668     return OrSlowCase(RHS);
669   }
670   APInt Or(const APInt& RHS) const {
671     return this->operator|(RHS);
672   }
673
674   /// Performs a bitwise XOR operation on *this and RHS.
675   /// @returns An APInt value representing the bitwise XOR of *this and RHS.
676   /// @brief Bitwise XOR operator.
677   APInt operator^(const APInt& RHS) const {
678     assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
679     if (isSingleWord())
680       return APInt(BitWidth, VAL ^ RHS.VAL);
681     return XorSlowCase(RHS);
682   }
683   APInt Xor(const APInt& RHS) const {
684     return this->operator^(RHS);
685   }
686
687   /// Multiplies this APInt by RHS and returns the result.
688   /// @brief Multiplication operator.
689   APInt operator*(const APInt& RHS) const;
690
691   /// Adds RHS to this APInt and returns the result.
692   /// @brief Addition operator.
693   APInt operator+(const APInt& RHS) const;
694   APInt operator+(uint64_t RHS) const {
695     return (*this) + APInt(BitWidth, RHS);
696   }
697
698   /// Subtracts RHS from this APInt and returns the result.
699   /// @brief Subtraction operator.
700   APInt operator-(const APInt& RHS) const;
701   APInt operator-(uint64_t RHS) const {
702     return (*this) - APInt(BitWidth, RHS);
703   }
704
705   APInt operator<<(unsigned Bits) const {
706     return shl(Bits);
707   }
708
709   APInt operator<<(const APInt &Bits) const {
710     return shl(Bits);
711   }
712
713   /// Arithmetic right-shift this APInt by shiftAmt.
714   /// @brief Arithmetic right-shift function.
715   APInt ashr(unsigned shiftAmt) const;
716
717   /// Logical right-shift this APInt by shiftAmt.
718   /// @brief Logical right-shift function.
719   APInt lshr(unsigned shiftAmt) const;
720
721   /// Left-shift this APInt by shiftAmt.
722   /// @brief Left-shift function.
723   APInt shl(unsigned shiftAmt) const {
724     assert(shiftAmt <= BitWidth && "Invalid shift amount");
725     if (isSingleWord()) {
726       if (shiftAmt == BitWidth)
727         return APInt(BitWidth, 0); // avoid undefined shift results
728       return APInt(BitWidth, VAL << shiftAmt);
729     }
730     return shlSlowCase(shiftAmt);
731   }
732
733   /// @brief Rotate left by rotateAmt.
734   APInt rotl(unsigned rotateAmt) const;
735
736   /// @brief Rotate right by rotateAmt.
737   APInt rotr(unsigned rotateAmt) const;
738
739   /// Arithmetic right-shift this APInt by shiftAmt.
740   /// @brief Arithmetic right-shift function.
741   APInt ashr(const APInt &shiftAmt) const;
742
743   /// Logical right-shift this APInt by shiftAmt.
744   /// @brief Logical right-shift function.
745   APInt lshr(const APInt &shiftAmt) const;
746
747   /// Left-shift this APInt by shiftAmt.
748   /// @brief Left-shift function.
749   APInt shl(const APInt &shiftAmt) const;
750
751   /// @brief Rotate left by rotateAmt.
752   APInt rotl(const APInt &rotateAmt) const;
753
754   /// @brief Rotate right by rotateAmt.
755   APInt rotr(const APInt &rotateAmt) const;
756
757   /// Perform an unsigned divide operation on this APInt by RHS. Both this and
758   /// RHS are treated as unsigned quantities for purposes of this division.
759   /// @returns a new APInt value containing the division result
760   /// @brief Unsigned division operation.
761   APInt udiv(const APInt &RHS) const;
762
763   /// Signed divide this APInt by APInt RHS.
764   /// @brief Signed division function for APInt.
765   APInt sdiv(const APInt &RHS) const {
766     if (isNegative())
767       if (RHS.isNegative())
768         return (-(*this)).udiv(-RHS);
769       else
770         return -((-(*this)).udiv(RHS));
771     else if (RHS.isNegative())
772       return -(this->udiv(-RHS));
773     return this->udiv(RHS);
774   }
775
776   /// Perform an unsigned remainder operation on this APInt with RHS being the
777   /// divisor. Both this and RHS are treated as unsigned quantities for purposes
778   /// of this operation. Note that this is a true remainder operation and not
779   /// a modulo operation because the sign follows the sign of the dividend
780   /// which is *this.
781   /// @returns a new APInt value containing the remainder result
782   /// @brief Unsigned remainder operation.
783   APInt urem(const APInt &RHS) const;
784
785   /// Signed remainder operation on APInt.
786   /// @brief Function for signed remainder operation.
787   APInt srem(const APInt &RHS) const {
788     if (isNegative())
789       if (RHS.isNegative())
790         return -((-(*this)).urem(-RHS));
791       else
792         return -((-(*this)).urem(RHS));
793     else if (RHS.isNegative())
794       return this->urem(-RHS);
795     return this->urem(RHS);
796   }
797
798   /// Sometimes it is convenient to divide two APInt values and obtain both the
799   /// quotient and remainder. This function does both operations in the same
800   /// computation making it a little more efficient. The pair of input arguments
801   /// may overlap with the pair of output arguments. It is safe to call
802   /// udivrem(X, Y, X, Y), for example.
803   /// @brief Dual division/remainder interface.
804   static void udivrem(const APInt &LHS, const APInt &RHS,
805                       APInt &Quotient, APInt &Remainder);
806
807   static void sdivrem(const APInt &LHS, const APInt &RHS,
808                       APInt &Quotient, APInt &Remainder) {
809     if (LHS.isNegative()) {
810       if (RHS.isNegative())
811         APInt::udivrem(-LHS, -RHS, Quotient, Remainder);
812       else
813         APInt::udivrem(-LHS, RHS, Quotient, Remainder);
814       Quotient = -Quotient;
815       Remainder = -Remainder;
816     } else if (RHS.isNegative()) {
817       APInt::udivrem(LHS, -RHS, Quotient, Remainder);
818       Quotient = -Quotient;
819     } else {
820       APInt::udivrem(LHS, RHS, Quotient, Remainder);
821     }
822   }
823   
824   
825   // Operations that return overflow indicators.
826   APInt sadd_ov(const APInt &RHS, bool &Overflow) const;
827   APInt uadd_ov(const APInt &RHS, bool &Overflow) const;
828   APInt ssub_ov(const APInt &RHS, bool &Overflow) const;
829   APInt usub_ov(const APInt &RHS, bool &Overflow) const;
830   APInt sdiv_ov(const APInt &RHS, bool &Overflow) const;
831   APInt smul_ov(const APInt &RHS, bool &Overflow) const;
832   APInt umul_ov(const APInt &RHS, bool &Overflow) const;
833   APInt sshl_ov(unsigned Amt, bool &Overflow) const;
834
835   /// @returns the bit value at bitPosition
836   /// @brief Array-indexing support.
837   bool operator[](unsigned bitPosition) const;
838
839   /// @}
840   /// @name Comparison Operators
841   /// @{
842   /// Compares this APInt with RHS for the validity of the equality
843   /// relationship.
844   /// @brief Equality operator.
845   bool operator==(const APInt& RHS) const {
846     assert(BitWidth == RHS.BitWidth && "Comparison requires equal bit widths");
847     if (isSingleWord())
848       return VAL == RHS.VAL;
849     return EqualSlowCase(RHS);
850   }
851
852   /// Compares this APInt with a uint64_t for the validity of the equality
853   /// relationship.
854   /// @returns true if *this == Val
855   /// @brief Equality operator.
856   bool operator==(uint64_t Val) const {
857     if (isSingleWord())
858       return VAL == Val;
859     return EqualSlowCase(Val);
860   }
861
862   /// Compares this APInt with RHS for the validity of the equality
863   /// relationship.
864   /// @returns true if *this == Val
865   /// @brief Equality comparison.
866   bool eq(const APInt &RHS) const {
867     return (*this) == RHS;
868   }
869
870   /// Compares this APInt with RHS for the validity of the inequality
871   /// relationship.
872   /// @returns true if *this != Val
873   /// @brief Inequality operator.
874   bool operator!=(const APInt& RHS) const {
875     return !((*this) == RHS);
876   }
877
878   /// Compares this APInt with a uint64_t for the validity of the inequality
879   /// relationship.
880   /// @returns true if *this != Val
881   /// @brief Inequality operator.
882   bool operator!=(uint64_t Val) const {
883     return !((*this) == Val);
884   }
885
886   /// Compares this APInt with RHS for the validity of the inequality
887   /// relationship.
888   /// @returns true if *this != Val
889   /// @brief Inequality comparison
890   bool ne(const APInt &RHS) const {
891     return !((*this) == RHS);
892   }
893
894   /// Regards both *this and RHS as unsigned quantities and compares them for
895   /// the validity of the less-than relationship.
896   /// @returns true if *this < RHS when both are considered unsigned.
897   /// @brief Unsigned less than comparison
898   bool ult(const APInt &RHS) const;
899
900   /// Regards both *this as an unsigned quantity and compares it with RHS for
901   /// the validity of the less-than relationship.
902   /// @returns true if *this < RHS when considered unsigned.
903   /// @brief Unsigned less than comparison
904   bool ult(uint64_t RHS) const {
905     return ult(APInt(getBitWidth(), RHS));
906   }
907
908   /// Regards both *this and RHS as signed quantities and compares them for
909   /// validity of the less-than relationship.
910   /// @returns true if *this < RHS when both are considered signed.
911   /// @brief Signed less than comparison
912   bool slt(const APInt& RHS) const;
913
914   /// Regards both *this as a signed quantity and compares it with RHS for
915   /// the validity of the less-than relationship.
916   /// @returns true if *this < RHS when considered signed.
917   /// @brief Signed less than comparison
918   bool slt(uint64_t RHS) const {
919     return slt(APInt(getBitWidth(), RHS));
920   }
921
922   /// Regards both *this and RHS as unsigned quantities and compares them for
923   /// validity of the less-or-equal relationship.
924   /// @returns true if *this <= RHS when both are considered unsigned.
925   /// @brief Unsigned less or equal comparison
926   bool ule(const APInt& RHS) const {
927     return ult(RHS) || eq(RHS);
928   }
929
930   /// Regards both *this as an unsigned quantity and compares it with RHS for
931   /// the validity of the less-or-equal relationship.
932   /// @returns true if *this <= RHS when considered unsigned.
933   /// @brief Unsigned less or equal comparison
934   bool ule(uint64_t RHS) const {
935     return ule(APInt(getBitWidth(), RHS));
936   }
937
938   /// Regards both *this and RHS as signed quantities and compares them for
939   /// validity of the less-or-equal relationship.
940   /// @returns true if *this <= RHS when both are considered signed.
941   /// @brief Signed less or equal comparison
942   bool sle(const APInt& RHS) const {
943     return slt(RHS) || eq(RHS);
944   }
945
946   /// Regards both *this as a signed quantity and compares it with RHS for
947   /// the validity of the less-or-equal relationship.
948   /// @returns true if *this <= RHS when considered signed.
949   /// @brief Signed less or equal comparison
950   bool sle(uint64_t RHS) const {
951     return sle(APInt(getBitWidth(), RHS));
952   }
953
954   /// Regards both *this and RHS as unsigned quantities and compares them for
955   /// the validity of the greater-than relationship.
956   /// @returns true if *this > RHS when both are considered unsigned.
957   /// @brief Unsigned greather than comparison
958   bool ugt(const APInt& RHS) const {
959     return !ult(RHS) && !eq(RHS);
960   }
961
962   /// Regards both *this as an unsigned quantity and compares it with RHS for
963   /// the validity of the greater-than relationship.
964   /// @returns true if *this > RHS when considered unsigned.
965   /// @brief Unsigned greater than comparison
966   bool ugt(uint64_t RHS) const {
967     return ugt(APInt(getBitWidth(), RHS));
968   }
969
970   /// Regards both *this and RHS as signed quantities and compares them for
971   /// the validity of the greater-than relationship.
972   /// @returns true if *this > RHS when both are considered signed.
973   /// @brief Signed greather than comparison
974   bool sgt(const APInt& RHS) const {
975     return !slt(RHS) && !eq(RHS);
976   }
977
978   /// Regards both *this as a signed quantity and compares it with RHS for
979   /// the validity of the greater-than relationship.
980   /// @returns true if *this > RHS when considered signed.
981   /// @brief Signed greater than comparison
982   bool sgt(uint64_t RHS) const {
983     return sgt(APInt(getBitWidth(), RHS));
984   }
985
986   /// Regards both *this and RHS as unsigned quantities and compares them for
987   /// validity of the greater-or-equal relationship.
988   /// @returns true if *this >= RHS when both are considered unsigned.
989   /// @brief Unsigned greater or equal comparison
990   bool uge(const APInt& RHS) const {
991     return !ult(RHS);
992   }
993
994   /// Regards both *this as an unsigned quantity and compares it with RHS for
995   /// the validity of the greater-or-equal relationship.
996   /// @returns true if *this >= RHS when considered unsigned.
997   /// @brief Unsigned greater or equal comparison
998   bool uge(uint64_t RHS) const {
999     return uge(APInt(getBitWidth(), RHS));
1000   }
1001
1002   /// Regards both *this and RHS as signed quantities and compares them for
1003   /// validity of the greater-or-equal relationship.
1004   /// @returns true if *this >= RHS when both are considered signed.
1005   /// @brief Signed greather or equal comparison
1006   bool sge(const APInt& RHS) const {
1007     return !slt(RHS);
1008   }
1009
1010   /// Regards both *this as a signed quantity and compares it with RHS for
1011   /// the validity of the greater-or-equal relationship.
1012   /// @returns true if *this >= RHS when considered signed.
1013   /// @brief Signed greater or equal comparison
1014   bool sge(uint64_t RHS) const {
1015     return sge(APInt(getBitWidth(), RHS));
1016   }
1017
1018   
1019   
1020   
1021   /// This operation tests if there are any pairs of corresponding bits
1022   /// between this APInt and RHS that are both set.
1023   bool intersects(const APInt &RHS) const {
1024     return (*this & RHS) != 0;
1025   }
1026
1027   /// @}
1028   /// @name Resizing Operators
1029   /// @{
1030   /// Truncate the APInt to a specified width. It is an error to specify a width
1031   /// that is greater than or equal to the current width.
1032   /// @brief Truncate to new width.
1033   APInt trunc(unsigned width) const;
1034
1035   /// This operation sign extends the APInt to a new width. If the high order
1036   /// bit is set, the fill on the left will be done with 1 bits, otherwise zero.
1037   /// It is an error to specify a width that is less than or equal to the
1038   /// current width.
1039   /// @brief Sign extend to a new width.
1040   APInt sext(unsigned width) const;
1041
1042   /// This operation zero extends the APInt to a new width. The high order bits
1043   /// are filled with 0 bits.  It is an error to specify a width that is less
1044   /// than or equal to the current width.
1045   /// @brief Zero extend to a new width.
1046   APInt zext(unsigned width) const;
1047
1048   /// Make this APInt have the bit width given by \p width. The value is sign
1049   /// extended, truncated, or left alone to make it that width.
1050   /// @brief Sign extend or truncate to width
1051   APInt sextOrTrunc(unsigned width) const;
1052
1053   /// Make this APInt have the bit width given by \p width. The value is zero
1054   /// extended, truncated, or left alone to make it that width.
1055   /// @brief Zero extend or truncate to width
1056   APInt zextOrTrunc(unsigned width) const;
1057
1058   /// Make this APInt have the bit width given by \p width. The value is sign
1059   /// extended, or left alone to make it that width.
1060   /// @brief Sign extend or truncate to width
1061   APInt sextOrSelf(unsigned width) const;
1062
1063   /// Make this APInt have the bit width given by \p width. The value is zero
1064   /// extended, or left alone to make it that width.
1065   /// @brief Zero extend or truncate to width
1066   APInt zextOrSelf(unsigned width) const;
1067
1068   /// @}
1069   /// @name Bit Manipulation Operators
1070   /// @{
1071   /// @brief Set every bit to 1.
1072   void setAllBits() {
1073     if (isSingleWord())
1074       VAL = -1ULL;
1075     else {
1076       // Set all the bits in all the words.
1077       for (unsigned i = 0; i < getNumWords(); ++i)
1078         pVal[i] = -1ULL;
1079     }
1080     // Clear the unused ones
1081     clearUnusedBits();
1082   }
1083
1084   /// Set the given bit to 1 whose position is given as "bitPosition".
1085   /// @brief Set a given bit to 1.
1086   void setBit(unsigned bitPosition);
1087
1088   /// @brief Set every bit to 0.
1089   void clearAllBits() {
1090     if (isSingleWord())
1091       VAL = 0;
1092     else
1093       memset(pVal, 0, getNumWords() * APINT_WORD_SIZE);
1094   }
1095
1096   /// Set the given bit to 0 whose position is given as "bitPosition".
1097   /// @brief Set a given bit to 0.
1098   void clearBit(unsigned bitPosition);
1099
1100   /// @brief Toggle every bit to its opposite value.
1101   void flipAllBits() {
1102     if (isSingleWord())
1103       VAL ^= -1ULL;
1104     else {
1105       for (unsigned i = 0; i < getNumWords(); ++i)
1106         pVal[i] ^= -1ULL;
1107     }
1108     clearUnusedBits();
1109   }
1110
1111   /// Toggle a given bit to its opposite value whose position is given
1112   /// as "bitPosition".
1113   /// @brief Toggles a given bit to its opposite value.
1114   void flipBit(unsigned bitPosition);
1115
1116   /// @}
1117   /// @name Value Characterization Functions
1118   /// @{
1119
1120   /// @returns the total number of bits.
1121   unsigned getBitWidth() const {
1122     return BitWidth;
1123   }
1124
1125   /// Here one word's bitwidth equals to that of uint64_t.
1126   /// @returns the number of words to hold the integer value of this APInt.
1127   /// @brief Get the number of words.
1128   unsigned getNumWords() const {
1129     return getNumWords(BitWidth);
1130   }
1131
1132   /// Here one word's bitwidth equals to that of uint64_t.
1133   /// @returns the number of words to hold the integer value with a
1134   /// given bit width.
1135   /// @brief Get the number of words.
1136   static unsigned getNumWords(unsigned BitWidth) {
1137     return (BitWidth + APINT_BITS_PER_WORD - 1) / APINT_BITS_PER_WORD;
1138   }
1139
1140   /// This function returns the number of active bits which is defined as the
1141   /// bit width minus the number of leading zeros. This is used in several
1142   /// computations to see how "wide" the value is.
1143   /// @brief Compute the number of active bits in the value
1144   unsigned getActiveBits() const {
1145     return BitWidth - countLeadingZeros();
1146   }
1147
1148   /// This function returns the number of active words in the value of this
1149   /// APInt. This is used in conjunction with getActiveData to extract the raw
1150   /// value of the APInt.
1151   unsigned getActiveWords() const {
1152     return whichWord(getActiveBits()-1) + 1;
1153   }
1154
1155   /// Computes the minimum bit width for this APInt while considering it to be
1156   /// a signed (and probably negative) value. If the value is not negative,
1157   /// this function returns the same value as getActiveBits()+1. Otherwise, it
1158   /// returns the smallest bit width that will retain the negative value. For
1159   /// example, -1 can be written as 0b1 or 0xFFFFFFFFFF. 0b1 is shorter and so
1160   /// for -1, this function will always return 1.
1161   /// @brief Get the minimum bit size for this signed APInt
1162   unsigned getMinSignedBits() const {
1163     if (isNegative())
1164       return BitWidth - countLeadingOnes() + 1;
1165     return getActiveBits()+1;
1166   }
1167
1168   /// This method attempts to return the value of this APInt as a zero extended
1169   /// uint64_t. The bitwidth must be <= 64 or the value must fit within a
1170   /// uint64_t. Otherwise an assertion will result.
1171   /// @brief Get zero extended value
1172   uint64_t getZExtValue() const {
1173     if (isSingleWord())
1174       return VAL;
1175     assert(getActiveBits() <= 64 && "Too many bits for uint64_t");
1176     return pVal[0];
1177   }
1178
1179   /// This method attempts to return the value of this APInt as a sign extended
1180   /// int64_t. The bit width must be <= 64 or the value must fit within an
1181   /// int64_t. Otherwise an assertion will result.
1182   /// @brief Get sign extended value
1183   int64_t getSExtValue() const {
1184     if (isSingleWord())
1185       return int64_t(VAL << (APINT_BITS_PER_WORD - BitWidth)) >>
1186                      (APINT_BITS_PER_WORD - BitWidth);
1187     assert(getMinSignedBits() <= 64 && "Too many bits for int64_t");
1188     return int64_t(pVal[0]);
1189   }
1190
1191   /// This method determines how many bits are required to hold the APInt
1192   /// equivalent of the string given by \arg str.
1193   /// @brief Get bits required for string value.
1194   static unsigned getBitsNeeded(StringRef str, uint8_t radix);
1195
1196   /// countLeadingZeros - This function is an APInt version of the
1197   /// countLeadingZeros_{32,64} functions in MathExtras.h. It counts the number
1198   /// of zeros from the most significant bit to the first one bit.
1199   /// @returns BitWidth if the value is zero.
1200   /// @returns the number of zeros from the most significant bit to the first
1201   /// one bits.
1202   unsigned countLeadingZeros() const {
1203     if (isSingleWord()) {
1204       unsigned unusedBits = APINT_BITS_PER_WORD - BitWidth;
1205       return CountLeadingZeros_64(VAL) - unusedBits;
1206     }
1207     return countLeadingZerosSlowCase();
1208   }
1209
1210   /// countLeadingOnes - This function is an APInt version of the
1211   /// countLeadingOnes_{32,64} functions in MathExtras.h. It counts the number
1212   /// of ones from the most significant bit to the first zero bit.
1213   /// @returns 0 if the high order bit is not set
1214   /// @returns the number of 1 bits from the most significant to the least
1215   /// @brief Count the number of leading one bits.
1216   unsigned countLeadingOnes() const;
1217
1218   /// Computes the number of leading bits of this APInt that are equal to its
1219   /// sign bit.
1220   unsigned getNumSignBits() const {
1221     return isNegative() ? countLeadingOnes() : countLeadingZeros();
1222   }
1223
1224   /// countTrailingZeros - This function is an APInt version of the
1225   /// countTrailingZeros_{32,64} functions in MathExtras.h. It counts
1226   /// the number of zeros from the least significant bit to the first set bit.
1227   /// @returns BitWidth if the value is zero.
1228   /// @returns the number of zeros from the least significant bit to the first
1229   /// one bit.
1230   /// @brief Count the number of trailing zero bits.
1231   unsigned countTrailingZeros() const;
1232
1233   /// countTrailingOnes - This function is an APInt version of the
1234   /// countTrailingOnes_{32,64} functions in MathExtras.h. It counts
1235   /// the number of ones from the least significant bit to the first zero bit.
1236   /// @returns BitWidth if the value is all ones.
1237   /// @returns the number of ones from the least significant bit to the first
1238   /// zero bit.
1239   /// @brief Count the number of trailing one bits.
1240   unsigned countTrailingOnes() const {
1241     if (isSingleWord())
1242       return CountTrailingOnes_64(VAL);
1243     return countTrailingOnesSlowCase();
1244   }
1245
1246   /// countPopulation - This function is an APInt version of the
1247   /// countPopulation_{32,64} functions in MathExtras.h. It counts the number
1248   /// of 1 bits in the APInt value.
1249   /// @returns 0 if the value is zero.
1250   /// @returns the number of set bits.
1251   /// @brief Count the number of bits set.
1252   unsigned countPopulation() const {
1253     if (isSingleWord())
1254       return CountPopulation_64(VAL);
1255     return countPopulationSlowCase();
1256   }
1257
1258   /// @}
1259   /// @name Conversion Functions
1260   /// @{
1261   void print(raw_ostream &OS, bool isSigned) const;
1262
1263   /// toString - Converts an APInt to a string and append it to Str.  Str is
1264   /// commonly a SmallString.
1265   void toString(SmallVectorImpl<char> &Str, unsigned Radix, bool Signed,
1266                 bool formatAsCLiteral = false) const;
1267
1268   /// Considers the APInt to be unsigned and converts it into a string in the
1269   /// radix given. The radix can be 2, 8, 10 16, or 36.
1270   void toStringUnsigned(SmallVectorImpl<char> &Str, unsigned Radix = 10) const {
1271     toString(Str, Radix, false, false);
1272   }
1273
1274   /// Considers the APInt to be signed and converts it into a string in the
1275   /// radix given. The radix can be 2, 8, 10, 16, or 36.
1276   void toStringSigned(SmallVectorImpl<char> &Str, unsigned Radix = 10) const {
1277     toString(Str, Radix, true, false);
1278   }
1279
1280   /// toString - This returns the APInt as a std::string.  Note that this is an
1281   /// inefficient method.  It is better to pass in a SmallVector/SmallString
1282   /// to the methods above to avoid thrashing the heap for the string.
1283   std::string toString(unsigned Radix, bool Signed) const;
1284
1285
1286   /// @returns a byte-swapped representation of this APInt Value.
1287   APInt byteSwap() const;
1288
1289   /// @brief Converts this APInt to a double value.
1290   double roundToDouble(bool isSigned) const;
1291
1292   /// @brief Converts this unsigned APInt to a double value.
1293   double roundToDouble() const {
1294     return roundToDouble(false);
1295   }
1296
1297   /// @brief Converts this signed APInt to a double value.
1298   double signedRoundToDouble() const {
1299     return roundToDouble(true);
1300   }
1301
1302   /// The conversion does not do a translation from integer to double, it just
1303   /// re-interprets the bits as a double. Note that it is valid to do this on
1304   /// any bit width. Exactly 64 bits will be translated.
1305   /// @brief Converts APInt bits to a double
1306   double bitsToDouble() const {
1307     union {
1308       uint64_t I;
1309       double D;
1310     } T;
1311     T.I = (isSingleWord() ? VAL : pVal[0]);
1312     return T.D;
1313   }
1314
1315   /// The conversion does not do a translation from integer to float, it just
1316   /// re-interprets the bits as a float. Note that it is valid to do this on
1317   /// any bit width. Exactly 32 bits will be translated.
1318   /// @brief Converts APInt bits to a double
1319   float bitsToFloat() const {
1320     union {
1321       unsigned I;
1322       float F;
1323     } T;
1324     T.I = unsigned((isSingleWord() ? VAL : pVal[0]));
1325     return T.F;
1326   }
1327
1328   /// The conversion does not do a translation from double to integer, it just
1329   /// re-interprets the bits of the double.
1330   /// @brief Converts a double to APInt bits.
1331   static APInt doubleToBits(double V) {
1332     union {
1333       uint64_t I;
1334       double D;
1335     } T;
1336     T.D = V;
1337     return APInt(sizeof T * CHAR_BIT, T.I);
1338   }
1339
1340   /// The conversion does not do a translation from float to integer, it just
1341   /// re-interprets the bits of the float.
1342   /// @brief Converts a float to APInt bits.
1343   static APInt floatToBits(float V) {
1344     union {
1345       unsigned I;
1346       float F;
1347     } T;
1348     T.F = V;
1349     return APInt(sizeof T * CHAR_BIT, T.I);
1350   }
1351
1352   /// @}
1353   /// @name Mathematics Operations
1354   /// @{
1355
1356   /// @returns the floor log base 2 of this APInt.
1357   unsigned logBase2() const {
1358     return BitWidth - 1 - countLeadingZeros();
1359   }
1360
1361   /// @returns the ceil log base 2 of this APInt.
1362   unsigned ceilLogBase2() const {
1363     return BitWidth - (*this - 1).countLeadingZeros();
1364   }
1365
1366   /// @returns the log base 2 of this APInt if its an exact power of two, -1
1367   /// otherwise
1368   int32_t exactLogBase2() const {
1369     if (!isPowerOf2())
1370       return -1;
1371     return logBase2();
1372   }
1373
1374   /// @brief Compute the square root
1375   APInt sqrt() const;
1376
1377   /// If *this is < 0 then return -(*this), otherwise *this;
1378   /// @brief Get the absolute value;
1379   APInt abs() const {
1380     if (isNegative())
1381       return -(*this);
1382     return *this;
1383   }
1384
1385   /// @returns the multiplicative inverse for a given modulo.
1386   APInt multiplicativeInverse(const APInt& modulo) const;
1387
1388   /// @}
1389   /// @name Support for division by constant
1390   /// @{
1391
1392   /// Calculate the magic number for signed division by a constant.
1393   struct ms;
1394   ms magic() const;
1395
1396   /// Calculate the magic number for unsigned division by a constant.
1397   struct mu;
1398   mu magicu(unsigned LeadingZeros = 0) const;
1399
1400   /// @}
1401   /// @name Building-block Operations for APInt and APFloat
1402   /// @{
1403
1404   // These building block operations operate on a representation of
1405   // arbitrary precision, two's-complement, bignum integer values.
1406   // They should be sufficient to implement APInt and APFloat bignum
1407   // requirements.  Inputs are generally a pointer to the base of an
1408   // array of integer parts, representing an unsigned bignum, and a
1409   // count of how many parts there are.
1410
1411   /// Sets the least significant part of a bignum to the input value,
1412   /// and zeroes out higher parts.  */
1413   static void tcSet(integerPart *, integerPart, unsigned int);
1414
1415   /// Assign one bignum to another.
1416   static void tcAssign(integerPart *, const integerPart *, unsigned int);
1417
1418   /// Returns true if a bignum is zero, false otherwise.
1419   static bool tcIsZero(const integerPart *, unsigned int);
1420
1421   /// Extract the given bit of a bignum; returns 0 or 1.  Zero-based.
1422   static int tcExtractBit(const integerPart *, unsigned int bit);
1423
1424   /// Copy the bit vector of width srcBITS from SRC, starting at bit
1425   /// srcLSB, to DST, of dstCOUNT parts, such that the bit srcLSB
1426   /// becomes the least significant bit of DST.  All high bits above
1427   /// srcBITS in DST are zero-filled.
1428   static void tcExtract(integerPart *, unsigned int dstCount,
1429                         const integerPart *,
1430                         unsigned int srcBits, unsigned int srcLSB);
1431
1432   /// Set the given bit of a bignum.  Zero-based.
1433   static void tcSetBit(integerPart *, unsigned int bit);
1434
1435   /// Clear the given bit of a bignum.  Zero-based.
1436   static void tcClearBit(integerPart *, unsigned int bit);
1437
1438   /// Returns the bit number of the least or most significant set bit
1439   /// of a number.  If the input number has no bits set -1U is
1440   /// returned.
1441   static unsigned int tcLSB(const integerPart *, unsigned int);
1442   static unsigned int tcMSB(const integerPart *parts, unsigned int n);
1443
1444   /// Negate a bignum in-place.
1445   static void tcNegate(integerPart *, unsigned int);
1446
1447   /// DST += RHS + CARRY where CARRY is zero or one.  Returns the
1448   /// carry flag.
1449   static integerPart tcAdd(integerPart *, const integerPart *,
1450                            integerPart carry, unsigned);
1451
1452   /// DST -= RHS + CARRY where CARRY is zero or one.  Returns the
1453   /// carry flag.
1454   static integerPart tcSubtract(integerPart *, const integerPart *,
1455                                 integerPart carry, unsigned);
1456
1457   ///  DST += SRC * MULTIPLIER + PART   if add is true
1458   ///  DST  = SRC * MULTIPLIER + PART   if add is false
1459   ///
1460   ///  Requires 0 <= DSTPARTS <= SRCPARTS + 1.  If DST overlaps SRC
1461   ///  they must start at the same point, i.e. DST == SRC.
1462   ///
1463   ///  If DSTPARTS == SRC_PARTS + 1 no overflow occurs and zero is
1464   ///  returned.  Otherwise DST is filled with the least significant
1465   ///  DSTPARTS parts of the result, and if all of the omitted higher
1466   ///  parts were zero return zero, otherwise overflow occurred and
1467   ///  return one.
1468   static int tcMultiplyPart(integerPart *dst, const integerPart *src,
1469                             integerPart multiplier, integerPart carry,
1470                             unsigned int srcParts, unsigned int dstParts,
1471                             bool add);
1472
1473   /// DST = LHS * RHS, where DST has the same width as the operands
1474   /// and is filled with the least significant parts of the result.
1475   /// Returns one if overflow occurred, otherwise zero.  DST must be
1476   /// disjoint from both operands.
1477   static int tcMultiply(integerPart *, const integerPart *,
1478                         const integerPart *, unsigned);
1479
1480   /// DST = LHS * RHS, where DST has width the sum of the widths of
1481   /// the operands.  No overflow occurs.  DST must be disjoint from
1482   /// both operands. Returns the number of parts required to hold the
1483   /// result.
1484   static unsigned int tcFullMultiply(integerPart *, const integerPart *,
1485                                      const integerPart *, unsigned, unsigned);
1486
1487   /// If RHS is zero LHS and REMAINDER are left unchanged, return one.
1488   /// Otherwise set LHS to LHS / RHS with the fractional part
1489   /// discarded, set REMAINDER to the remainder, return zero.  i.e.
1490   ///
1491   ///  OLD_LHS = RHS * LHS + REMAINDER
1492   ///
1493   ///  SCRATCH is a bignum of the same size as the operands and result
1494   ///  for use by the routine; its contents need not be initialized
1495   ///  and are destroyed.  LHS, REMAINDER and SCRATCH must be
1496   ///  distinct.
1497   static int tcDivide(integerPart *lhs, const integerPart *rhs,
1498                       integerPart *remainder, integerPart *scratch,
1499                       unsigned int parts);
1500
1501   /// Shift a bignum left COUNT bits.  Shifted in bits are zero.
1502   /// There are no restrictions on COUNT.
1503   static void tcShiftLeft(integerPart *, unsigned int parts,
1504                           unsigned int count);
1505
1506   /// Shift a bignum right COUNT bits.  Shifted in bits are zero.
1507   /// There are no restrictions on COUNT.
1508   static void tcShiftRight(integerPart *, unsigned int parts,
1509                            unsigned int count);
1510
1511   /// The obvious AND, OR and XOR and complement operations.
1512   static void tcAnd(integerPart *, const integerPart *, unsigned int);
1513   static void tcOr(integerPart *, const integerPart *, unsigned int);
1514   static void tcXor(integerPart *, const integerPart *, unsigned int);
1515   static void tcComplement(integerPart *, unsigned int);
1516
1517   /// Comparison (unsigned) of two bignums.
1518   static int tcCompare(const integerPart *, const integerPart *,
1519                        unsigned int);
1520
1521   /// Increment a bignum in-place.  Return the carry flag.
1522   static integerPart tcIncrement(integerPart *, unsigned int);
1523
1524   /// Set the least significant BITS and clear the rest.
1525   static void tcSetLeastSignificantBits(integerPart *, unsigned int,
1526                                         unsigned int bits);
1527
1528   /// @brief debug method
1529   void dump() const;
1530
1531   /// @}
1532 };
1533
1534 /// Magic data for optimising signed division by a constant.
1535 struct APInt::ms {
1536   APInt m;  ///< magic number
1537   unsigned s;  ///< shift amount
1538 };
1539
1540 /// Magic data for optimising unsigned division by a constant.
1541 struct APInt::mu {
1542   APInt m;     ///< magic number
1543   bool a;      ///< add indicator
1544   unsigned s;  ///< shift amount
1545 };
1546
1547 inline bool operator==(uint64_t V1, const APInt& V2) {
1548   return V2 == V1;
1549 }
1550
1551 inline bool operator!=(uint64_t V1, const APInt& V2) {
1552   return V2 != V1;
1553 }
1554
1555 inline raw_ostream &operator<<(raw_ostream &OS, const APInt &I) {
1556   I.print(OS, true);
1557   return OS;
1558 }
1559
1560 namespace APIntOps {
1561
1562 /// @brief Determine the smaller of two APInts considered to be signed.
1563 inline APInt smin(const APInt &A, const APInt &B) {
1564   return A.slt(B) ? A : B;
1565 }
1566
1567 /// @brief Determine the larger of two APInts considered to be signed.
1568 inline APInt smax(const APInt &A, const APInt &B) {
1569   return A.sgt(B) ? A : B;
1570 }
1571
1572 /// @brief Determine the smaller of two APInts considered to be signed.
1573 inline APInt umin(const APInt &A, const APInt &B) {
1574   return A.ult(B) ? A : B;
1575 }
1576
1577 /// @brief Determine the larger of two APInts considered to be unsigned.
1578 inline APInt umax(const APInt &A, const APInt &B) {
1579   return A.ugt(B) ? A : B;
1580 }
1581
1582 /// @brief Check if the specified APInt has a N-bits unsigned integer value.
1583 inline bool isIntN(unsigned N, const APInt& APIVal) {
1584   return APIVal.isIntN(N);
1585 }
1586
1587 /// @brief Check if the specified APInt has a N-bits signed integer value.
1588 inline bool isSignedIntN(unsigned N, const APInt& APIVal) {
1589   return APIVal.isSignedIntN(N);
1590 }
1591
1592 /// @returns true if the argument APInt value is a sequence of ones
1593 /// starting at the least significant bit with the remainder zero.
1594 inline bool isMask(unsigned numBits, const APInt& APIVal) {
1595   return numBits <= APIVal.getBitWidth() &&
1596     APIVal == APInt::getLowBitsSet(APIVal.getBitWidth(), numBits);
1597 }
1598
1599 /// @returns true if the argument APInt value contains a sequence of ones
1600 /// with the remainder zero.
1601 inline bool isShiftedMask(unsigned numBits, const APInt& APIVal) {
1602   return isMask(numBits, (APIVal - APInt(numBits,1)) | APIVal);
1603 }
1604
1605 /// @returns a byte-swapped representation of the specified APInt Value.
1606 inline APInt byteSwap(const APInt& APIVal) {
1607   return APIVal.byteSwap();
1608 }
1609
1610 /// @returns the floor log base 2 of the specified APInt value.
1611 inline unsigned logBase2(const APInt& APIVal) {
1612   return APIVal.logBase2();
1613 }
1614
1615 /// GreatestCommonDivisor - This function returns the greatest common
1616 /// divisor of the two APInt values using Euclid's algorithm.
1617 /// @returns the greatest common divisor of Val1 and Val2
1618 /// @brief Compute GCD of two APInt values.
1619 APInt GreatestCommonDivisor(const APInt& Val1, const APInt& Val2);
1620
1621 /// Treats the APInt as an unsigned value for conversion purposes.
1622 /// @brief Converts the given APInt to a double value.
1623 inline double RoundAPIntToDouble(const APInt& APIVal) {
1624   return APIVal.roundToDouble();
1625 }
1626
1627 /// Treats the APInt as a signed value for conversion purposes.
1628 /// @brief Converts the given APInt to a double value.
1629 inline double RoundSignedAPIntToDouble(const APInt& APIVal) {
1630   return APIVal.signedRoundToDouble();
1631 }
1632
1633 /// @brief Converts the given APInt to a float vlalue.
1634 inline float RoundAPIntToFloat(const APInt& APIVal) {
1635   return float(RoundAPIntToDouble(APIVal));
1636 }
1637
1638 /// Treast the APInt as a signed value for conversion purposes.
1639 /// @brief Converts the given APInt to a float value.
1640 inline float RoundSignedAPIntToFloat(const APInt& APIVal) {
1641   return float(APIVal.signedRoundToDouble());
1642 }
1643
1644 /// RoundDoubleToAPInt - This function convert a double value to an APInt value.
1645 /// @brief Converts the given double value into a APInt.
1646 APInt RoundDoubleToAPInt(double Double, unsigned width);
1647
1648 /// RoundFloatToAPInt - Converts a float value into an APInt value.
1649 /// @brief Converts a float value into a APInt.
1650 inline APInt RoundFloatToAPInt(float Float, unsigned width) {
1651   return RoundDoubleToAPInt(double(Float), width);
1652 }
1653
1654 /// Arithmetic right-shift the APInt by shiftAmt.
1655 /// @brief Arithmetic right-shift function.
1656 inline APInt ashr(const APInt& LHS, unsigned shiftAmt) {
1657   return LHS.ashr(shiftAmt);
1658 }
1659
1660 /// Logical right-shift the APInt by shiftAmt.
1661 /// @brief Logical right-shift function.
1662 inline APInt lshr(const APInt& LHS, unsigned shiftAmt) {
1663   return LHS.lshr(shiftAmt);
1664 }
1665
1666 /// Left-shift the APInt by shiftAmt.
1667 /// @brief Left-shift function.
1668 inline APInt shl(const APInt& LHS, unsigned shiftAmt) {
1669   return LHS.shl(shiftAmt);
1670 }
1671
1672 /// Signed divide APInt LHS by APInt RHS.
1673 /// @brief Signed division function for APInt.
1674 inline APInt sdiv(const APInt& LHS, const APInt& RHS) {
1675   return LHS.sdiv(RHS);
1676 }
1677
1678 /// Unsigned divide APInt LHS by APInt RHS.
1679 /// @brief Unsigned division function for APInt.
1680 inline APInt udiv(const APInt& LHS, const APInt& RHS) {
1681   return LHS.udiv(RHS);
1682 }
1683
1684 /// Signed remainder operation on APInt.
1685 /// @brief Function for signed remainder operation.
1686 inline APInt srem(const APInt& LHS, const APInt& RHS) {
1687   return LHS.srem(RHS);
1688 }
1689
1690 /// Unsigned remainder operation on APInt.
1691 /// @brief Function for unsigned remainder operation.
1692 inline APInt urem(const APInt& LHS, const APInt& RHS) {
1693   return LHS.urem(RHS);
1694 }
1695
1696 /// Performs multiplication on APInt values.
1697 /// @brief Function for multiplication operation.
1698 inline APInt mul(const APInt& LHS, const APInt& RHS) {
1699   return LHS * RHS;
1700 }
1701
1702 /// Performs addition on APInt values.
1703 /// @brief Function for addition operation.
1704 inline APInt add(const APInt& LHS, const APInt& RHS) {
1705   return LHS + RHS;
1706 }
1707
1708 /// Performs subtraction on APInt values.
1709 /// @brief Function for subtraction operation.
1710 inline APInt sub(const APInt& LHS, const APInt& RHS) {
1711   return LHS - RHS;
1712 }
1713
1714 /// Performs bitwise AND operation on APInt LHS and
1715 /// APInt RHS.
1716 /// @brief Bitwise AND function for APInt.
1717 inline APInt And(const APInt& LHS, const APInt& RHS) {
1718   return LHS & RHS;
1719 }
1720
1721 /// Performs bitwise OR operation on APInt LHS and APInt RHS.
1722 /// @brief Bitwise OR function for APInt.
1723 inline APInt Or(const APInt& LHS, const APInt& RHS) {
1724   return LHS | RHS;
1725 }
1726
1727 /// Performs bitwise XOR operation on APInt.
1728 /// @brief Bitwise XOR function for APInt.
1729 inline APInt Xor(const APInt& LHS, const APInt& RHS) {
1730   return LHS ^ RHS;
1731 }
1732
1733 /// Performs a bitwise complement operation on APInt.
1734 /// @brief Bitwise complement function.
1735 inline APInt Not(const APInt& APIVal) {
1736   return ~APIVal;
1737 }
1738
1739 } // End of APIntOps namespace
1740
1741 } // End of llvm namespace
1742
1743 #endif