• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 //===-- llvm/ADT/APInt.h - For Arbitrary Precision Integer -----*- C++ -*--===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 ///
9 /// \file
10 /// This file implements a class to represent arbitrary precision
11 /// integral constant values and operations on them.
12 ///
13 //===----------------------------------------------------------------------===//
14 
15 #ifndef LLVM_ADT_APINT_H
16 #define LLVM_ADT_APINT_H
17 
18 #include "llvm/Support/Compiler.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 FoldingSetNodeID;
27 class StringRef;
28 class hash_code;
29 class raw_ostream;
30 
31 template <typename T> class SmallVectorImpl;
32 template <typename T> class ArrayRef;
33 template <typename T> class Optional;
34 
35 class APInt;
36 
37 inline APInt operator-(APInt);
38 
39 //===----------------------------------------------------------------------===//
40 //                              APInt Class
41 //===----------------------------------------------------------------------===//
42 
43 /// Class for arbitrary precision integers.
44 ///
45 /// APInt is a functional replacement for common case unsigned integer type like
46 /// "unsigned", "unsigned long" or "uint64_t", but also allows non-byte-width
47 /// integer sizes and large integer value types such as 3-bits, 15-bits, or more
48 /// than 64-bits of precision. APInt provides a variety of arithmetic operators
49 /// and methods to manipulate integer values of any bit-width. It supports both
50 /// the typical integer arithmetic and comparison operations as well as bitwise
51 /// manipulation.
52 ///
53 /// The class has several invariants worth noting:
54 ///   * All bit, byte, and word positions are zero-based.
55 ///   * Once the bit width is set, it doesn't change except by the Truncate,
56 ///     SignExtend, or ZeroExtend operations.
57 ///   * All binary operators must be on APInt instances of the same bit width.
58 ///     Attempting to use these operators on instances with different bit
59 ///     widths will yield an assertion.
60 ///   * The value is stored canonically as an unsigned value. For operations
61 ///     where it makes a difference, there are both signed and unsigned variants
62 ///     of the operation. For example, sdiv and udiv. However, because the bit
63 ///     widths must be the same, operations such as Mul and Add produce the same
64 ///     results regardless of whether the values are interpreted as signed or
65 ///     not.
66 ///   * In general, the class tries to follow the style of computation that LLVM
67 ///     uses in its IR. This simplifies its use for LLVM.
68 ///
69 class LLVM_NODISCARD APInt {
70 public:
71   typedef uint64_t WordType;
72 
73   /// This enum is used to hold the constants we needed for APInt.
74   enum : unsigned {
75     /// Byte size of a word.
76     APINT_WORD_SIZE = sizeof(WordType),
77     /// Bits in a word.
78     APINT_BITS_PER_WORD = APINT_WORD_SIZE * CHAR_BIT
79   };
80 
81   enum class Rounding {
82     DOWN,
83     TOWARD_ZERO,
84     UP,
85   };
86 
87   static const WordType WORDTYPE_MAX = ~WordType(0);
88 
89 private:
90   /// This union is used to store the integer value. When the
91   /// integer bit-width <= 64, it uses VAL, otherwise it uses pVal.
92   union {
93     uint64_t VAL;   ///< Used to store the <= 64 bits integer value.
94     uint64_t *pVal; ///< Used to store the >64 bits integer value.
95   } U;
96 
97   unsigned BitWidth; ///< The number of bits in this APInt.
98 
99   friend struct DenseMapAPIntKeyInfo;
100 
101   friend class APSInt;
102 
103   /// Fast internal constructor
104   ///
105   /// This constructor is used only internally for speed of construction of
106   /// temporaries. It is unsafe for general use so it is not public.
APInt(uint64_t * val,unsigned bits)107   APInt(uint64_t *val, unsigned bits) : BitWidth(bits) {
108     U.pVal = val;
109   }
110 
111   /// Determine if this APInt just has one word to store value.
112   ///
113   /// \returns true if the number of bits <= 64, false otherwise.
isSingleWord()114   bool isSingleWord() const { return BitWidth <= APINT_BITS_PER_WORD; }
115 
116   /// Determine which word a bit is in.
117   ///
118   /// \returns the word position for the specified bit position.
whichWord(unsigned bitPosition)119   static unsigned whichWord(unsigned bitPosition) {
120     return bitPosition / APINT_BITS_PER_WORD;
121   }
122 
123   /// Determine which bit in a word a bit is in.
124   ///
125   /// \returns the bit position in a word for the specified bit position
126   /// in the APInt.
whichBit(unsigned bitPosition)127   static unsigned whichBit(unsigned bitPosition) {
128     return bitPosition % APINT_BITS_PER_WORD;
129   }
130 
131   /// Get a single bit mask.
132   ///
133   /// \returns a uint64_t with only bit at "whichBit(bitPosition)" set
134   /// This method generates and returns a uint64_t (word) mask for a single
135   /// bit at a specific bit position. This is used to mask the bit in the
136   /// corresponding word.
maskBit(unsigned bitPosition)137   static uint64_t maskBit(unsigned bitPosition) {
138     return 1ULL << whichBit(bitPosition);
139   }
140 
141   /// Clear unused high order bits
142   ///
143   /// This method is used internally to clear the top "N" bits in the high order
144   /// word that are not used by the APInt. This is needed after the most
145   /// significant word is assigned a value to ensure that those bits are
146   /// zero'd out.
clearUnusedBits()147   APInt &clearUnusedBits() {
148     // Compute how many bits are used in the final word
149     unsigned WordBits = ((BitWidth-1) % APINT_BITS_PER_WORD) + 1;
150 
151     // Mask out the high bits.
152     uint64_t mask = WORDTYPE_MAX >> (APINT_BITS_PER_WORD - WordBits);
153     if (isSingleWord())
154       U.VAL &= mask;
155     else
156       U.pVal[getNumWords() - 1] &= mask;
157     return *this;
158   }
159 
160   /// Get the word corresponding to a bit position
161   /// \returns the corresponding word for the specified bit position.
getWord(unsigned bitPosition)162   uint64_t getWord(unsigned bitPosition) const {
163     return isSingleWord() ? U.VAL : U.pVal[whichWord(bitPosition)];
164   }
165 
166   /// Utility method to change the bit width of this APInt to new bit width,
167   /// allocating and/or deallocating as necessary. There is no guarantee on the
168   /// value of any bits upon return. Caller should populate the bits after.
169   void reallocate(unsigned NewBitWidth);
170 
171   /// Convert a char array into an APInt
172   ///
173   /// \param radix 2, 8, 10, 16, or 36
174   /// Converts a string into a number.  The string must be non-empty
175   /// and well-formed as a number of the given base. The bit-width
176   /// must be sufficient to hold the result.
177   ///
178   /// This is used by the constructors that take string arguments.
179   ///
180   /// StringRef::getAsInteger is superficially similar but (1) does
181   /// not assume that the string is well-formed and (2) grows the
182   /// result to hold the input.
183   void fromString(unsigned numBits, StringRef str, uint8_t radix);
184 
185   /// An internal division function for dividing APInts.
186   ///
187   /// This is used by the toString method to divide by the radix. It simply
188   /// provides a more convenient form of divide for internal use since KnuthDiv
189   /// has specific constraints on its inputs. If those constraints are not met
190   /// then it provides a simpler form of divide.
191   static void divide(const WordType *LHS, unsigned lhsWords,
192                      const WordType *RHS, unsigned rhsWords, WordType *Quotient,
193                      WordType *Remainder);
194 
195   /// out-of-line slow case for inline constructor
196   void initSlowCase(uint64_t val, bool isSigned);
197 
198   /// shared code between two array constructors
199   void initFromArray(ArrayRef<uint64_t> array);
200 
201   /// out-of-line slow case for inline copy constructor
202   void initSlowCase(const APInt &that);
203 
204   /// out-of-line slow case for shl
205   void shlSlowCase(unsigned ShiftAmt);
206 
207   /// out-of-line slow case for lshr.
208   void lshrSlowCase(unsigned ShiftAmt);
209 
210   /// out-of-line slow case for ashr.
211   void ashrSlowCase(unsigned ShiftAmt);
212 
213   /// out-of-line slow case for operator=
214   void AssignSlowCase(const APInt &RHS);
215 
216   /// out-of-line slow case for operator==
217   bool EqualSlowCase(const APInt &RHS) const LLVM_READONLY;
218 
219   /// out-of-line slow case for countLeadingZeros
220   unsigned countLeadingZerosSlowCase() const LLVM_READONLY;
221 
222   /// out-of-line slow case for countLeadingOnes.
223   unsigned countLeadingOnesSlowCase() const LLVM_READONLY;
224 
225   /// out-of-line slow case for countTrailingZeros.
226   unsigned countTrailingZerosSlowCase() const LLVM_READONLY;
227 
228   /// out-of-line slow case for countTrailingOnes
229   unsigned countTrailingOnesSlowCase() const LLVM_READONLY;
230 
231   /// out-of-line slow case for countPopulation
232   unsigned countPopulationSlowCase() const LLVM_READONLY;
233 
234   /// out-of-line slow case for intersects.
235   bool intersectsSlowCase(const APInt &RHS) const LLVM_READONLY;
236 
237   /// out-of-line slow case for isSubsetOf.
238   bool isSubsetOfSlowCase(const APInt &RHS) const LLVM_READONLY;
239 
240   /// out-of-line slow case for setBits.
241   void setBitsSlowCase(unsigned loBit, unsigned hiBit);
242 
243   /// out-of-line slow case for flipAllBits.
244   void flipAllBitsSlowCase();
245 
246   /// out-of-line slow case for operator&=.
247   void AndAssignSlowCase(const APInt& RHS);
248 
249   /// out-of-line slow case for operator|=.
250   void OrAssignSlowCase(const APInt& RHS);
251 
252   /// out-of-line slow case for operator^=.
253   void XorAssignSlowCase(const APInt& RHS);
254 
255   /// Unsigned comparison. Returns -1, 0, or 1 if this APInt is less than, equal
256   /// to, or greater than RHS.
257   int compare(const APInt &RHS) const LLVM_READONLY;
258 
259   /// Signed comparison. Returns -1, 0, or 1 if this APInt is less than, equal
260   /// to, or greater than RHS.
261   int compareSigned(const APInt &RHS) const LLVM_READONLY;
262 
263 public:
264   /// \name Constructors
265   /// @{
266 
267   /// Create a new APInt of numBits width, initialized as val.
268   ///
269   /// If isSigned is true then val is treated as if it were a signed value
270   /// (i.e. as an int64_t) and the appropriate sign extension to the bit width
271   /// will be done. Otherwise, no sign extension occurs (high order bits beyond
272   /// the range of val are zero filled).
273   ///
274   /// \param numBits the bit width of the constructed APInt
275   /// \param val the initial value of the APInt
276   /// \param isSigned how to treat signedness of val
277   APInt(unsigned numBits, uint64_t val, bool isSigned = false)
BitWidth(numBits)278       : BitWidth(numBits) {
279     assert(BitWidth && "bitwidth too small");
280     if (isSingleWord()) {
281       U.VAL = val;
282       clearUnusedBits();
283     } else {
284       initSlowCase(val, isSigned);
285     }
286   }
287 
288   /// Construct an APInt of numBits width, initialized as bigVal[].
289   ///
290   /// Note that bigVal.size() can be smaller or larger than the corresponding
291   /// bit width but any extraneous bits will be dropped.
292   ///
293   /// \param numBits the bit width of the constructed APInt
294   /// \param bigVal a sequence of words to form the initial value of the APInt
295   APInt(unsigned numBits, ArrayRef<uint64_t> bigVal);
296 
297   /// Equivalent to APInt(numBits, ArrayRef<uint64_t>(bigVal, numWords)), but
298   /// deprecated because this constructor is prone to ambiguity with the
299   /// APInt(unsigned, uint64_t, bool) constructor.
300   ///
301   /// If this overload is ever deleted, care should be taken to prevent calls
302   /// from being incorrectly captured by the APInt(unsigned, uint64_t, bool)
303   /// constructor.
304   APInt(unsigned numBits, unsigned numWords, const uint64_t bigVal[]);
305 
306   /// Construct an APInt from a string representation.
307   ///
308   /// This constructor interprets the string \p str in the given radix. The
309   /// interpretation stops when the first character that is not suitable for the
310   /// radix is encountered, or the end of the string. Acceptable radix values
311   /// are 2, 8, 10, 16, and 36. It is an error for the value implied by the
312   /// string to require more bits than numBits.
313   ///
314   /// \param numBits the bit width of the constructed APInt
315   /// \param str the string to be interpreted
316   /// \param radix the radix to use for the conversion
317   APInt(unsigned numBits, StringRef str, uint8_t radix);
318 
319   /// Simply makes *this a copy of that.
320   /// Copy Constructor.
APInt(const APInt & that)321   APInt(const APInt &that) : BitWidth(that.BitWidth) {
322     if (isSingleWord())
323       U.VAL = that.U.VAL;
324     else
325       initSlowCase(that);
326   }
327 
328   /// Move Constructor.
APInt(APInt && that)329   APInt(APInt &&that) : BitWidth(that.BitWidth) {
330     memcpy(&U, &that.U, sizeof(U));
331     that.BitWidth = 0;
332   }
333 
334   /// Destructor.
~APInt()335   ~APInt() {
336     if (needsCleanup())
337       delete[] U.pVal;
338   }
339 
340   /// Default constructor that creates an uninteresting APInt
341   /// representing a 1-bit zero value.
342   ///
343   /// This is useful for object deserialization (pair this with the static
344   ///  method Read).
APInt()345   explicit APInt() : BitWidth(1) { U.VAL = 0; }
346 
347   /// Returns whether this instance allocated memory.
needsCleanup()348   bool needsCleanup() const { return !isSingleWord(); }
349 
350   /// Used to insert APInt objects, or objects that contain APInt objects, into
351   ///  FoldingSets.
352   void Profile(FoldingSetNodeID &id) const;
353 
354   /// @}
355   /// \name Value Tests
356   /// @{
357 
358   /// Determine sign of this APInt.
359   ///
360   /// This tests the high bit of this APInt to determine if it is set.
361   ///
362   /// \returns true if this APInt is negative, false otherwise
isNegative()363   bool isNegative() const { return (*this)[BitWidth - 1]; }
364 
365   /// Determine if this APInt Value is non-negative (>= 0)
366   ///
367   /// This tests the high bit of the APInt to determine if it is unset.
isNonNegative()368   bool isNonNegative() const { return !isNegative(); }
369 
370   /// Determine if sign bit of this APInt is set.
371   ///
372   /// This tests the high bit of this APInt to determine if it is set.
373   ///
374   /// \returns true if this APInt has its sign bit set, false otherwise.
isSignBitSet()375   bool isSignBitSet() const { return (*this)[BitWidth-1]; }
376 
377   /// Determine if sign bit of this APInt is clear.
378   ///
379   /// This tests the high bit of this APInt to determine if it is clear.
380   ///
381   /// \returns true if this APInt has its sign bit clear, false otherwise.
isSignBitClear()382   bool isSignBitClear() const { return !isSignBitSet(); }
383 
384   /// Determine if this APInt Value is positive.
385   ///
386   /// This tests if the value of this APInt is positive (> 0). Note
387   /// that 0 is not a positive value.
388   ///
389   /// \returns true if this APInt is positive.
isStrictlyPositive()390   bool isStrictlyPositive() const { return isNonNegative() && !isNullValue(); }
391 
392   /// Determine if this APInt Value is non-positive (<= 0).
393   ///
394   /// \returns true if this APInt is non-positive.
isNonPositive()395   bool isNonPositive() const { return !isStrictlyPositive(); }
396 
397   /// Determine if all bits are set
398   ///
399   /// This checks to see if the value has all bits of the APInt are set or not.
isAllOnesValue()400   bool isAllOnesValue() const {
401     if (isSingleWord())
402       return U.VAL == WORDTYPE_MAX >> (APINT_BITS_PER_WORD - BitWidth);
403     return countTrailingOnesSlowCase() == BitWidth;
404   }
405 
406   /// Determine if all bits are clear
407   ///
408   /// This checks to see if the value has all bits of the APInt are clear or
409   /// not.
isNullValue()410   bool isNullValue() const { return !*this; }
411 
412   /// Determine if this is a value of 1.
413   ///
414   /// This checks to see if the value of this APInt is one.
isOneValue()415   bool isOneValue() const {
416     if (isSingleWord())
417       return U.VAL == 1;
418     return countLeadingZerosSlowCase() == BitWidth - 1;
419   }
420 
421   /// Determine if this is the largest unsigned value.
422   ///
423   /// This checks to see if the value of this APInt is the maximum unsigned
424   /// value for the APInt's bit width.
isMaxValue()425   bool isMaxValue() const { return isAllOnesValue(); }
426 
427   /// Determine if this is the largest signed value.
428   ///
429   /// This checks to see if the value of this APInt is the maximum signed
430   /// value for the APInt's bit width.
isMaxSignedValue()431   bool isMaxSignedValue() const {
432     if (isSingleWord())
433       return U.VAL == ((WordType(1) << (BitWidth - 1)) - 1);
434     return !isNegative() && countTrailingOnesSlowCase() == BitWidth - 1;
435   }
436 
437   /// Determine if this is the smallest unsigned value.
438   ///
439   /// This checks to see if the value of this APInt is the minimum unsigned
440   /// value for the APInt's bit width.
isMinValue()441   bool isMinValue() const { return isNullValue(); }
442 
443   /// Determine if this is the smallest signed value.
444   ///
445   /// This checks to see if the value of this APInt is the minimum signed
446   /// value for the APInt's bit width.
isMinSignedValue()447   bool isMinSignedValue() const {
448     if (isSingleWord())
449       return U.VAL == (WordType(1) << (BitWidth - 1));
450     return isNegative() && countTrailingZerosSlowCase() == BitWidth - 1;
451   }
452 
453   /// Check if this APInt has an N-bits unsigned integer value.
isIntN(unsigned N)454   bool isIntN(unsigned N) const {
455     assert(N && "N == 0 ???");
456     return getActiveBits() <= N;
457   }
458 
459   /// Check if this APInt has an N-bits signed integer value.
isSignedIntN(unsigned N)460   bool isSignedIntN(unsigned N) const {
461     assert(N && "N == 0 ???");
462     return getMinSignedBits() <= N;
463   }
464 
465   /// Check if this APInt's value is a power of two greater than zero.
466   ///
467   /// \returns true if the argument APInt value is a power of two > 0.
isPowerOf2()468   bool isPowerOf2() const {
469     if (isSingleWord())
470       return isPowerOf2_64(U.VAL);
471     return countPopulationSlowCase() == 1;
472   }
473 
474   /// Check if the APInt's value is returned by getSignMask.
475   ///
476   /// \returns true if this is the value returned by getSignMask.
isSignMask()477   bool isSignMask() const { return isMinSignedValue(); }
478 
479   /// Convert APInt to a boolean value.
480   ///
481   /// This converts the APInt to a boolean value as a test against zero.
getBoolValue()482   bool getBoolValue() const { return !!*this; }
483 
484   /// If this value is smaller than the specified limit, return it, otherwise
485   /// return the limit value.  This causes the value to saturate to the limit.
486   uint64_t getLimitedValue(uint64_t Limit = UINT64_MAX) const {
487     return ugt(Limit) ? Limit : getZExtValue();
488   }
489 
490   /// Check if the APInt consists of a repeated bit pattern.
491   ///
492   /// e.g. 0x01010101 satisfies isSplat(8).
493   /// \param SplatSizeInBits The size of the pattern in bits. Must divide bit
494   /// width without remainder.
495   bool isSplat(unsigned SplatSizeInBits) const;
496 
497   /// \returns true if this APInt value is a sequence of \param numBits ones
498   /// starting at the least significant bit with the remainder zero.
isMask(unsigned numBits)499   bool isMask(unsigned numBits) const {
500     assert(numBits != 0 && "numBits must be non-zero");
501     assert(numBits <= BitWidth && "numBits out of range");
502     if (isSingleWord())
503       return U.VAL == (WORDTYPE_MAX >> (APINT_BITS_PER_WORD - numBits));
504     unsigned Ones = countTrailingOnesSlowCase();
505     return (numBits == Ones) &&
506            ((Ones + countLeadingZerosSlowCase()) == BitWidth);
507   }
508 
509   /// \returns true if this APInt is a non-empty sequence of ones starting at
510   /// the least significant bit with the remainder zero.
511   /// Ex. isMask(0x0000FFFFU) == true.
isMask()512   bool isMask() const {
513     if (isSingleWord())
514       return isMask_64(U.VAL);
515     unsigned Ones = countTrailingOnesSlowCase();
516     return (Ones > 0) && ((Ones + countLeadingZerosSlowCase()) == BitWidth);
517   }
518 
519   /// Return true if this APInt value contains a sequence of ones with
520   /// the remainder zero.
isShiftedMask()521   bool isShiftedMask() const {
522     if (isSingleWord())
523       return isShiftedMask_64(U.VAL);
524     unsigned Ones = countPopulationSlowCase();
525     unsigned LeadZ = countLeadingZerosSlowCase();
526     return (Ones + LeadZ + countTrailingZeros()) == BitWidth;
527   }
528 
529   /// @}
530   /// \name Value Generators
531   /// @{
532 
533   /// Gets maximum unsigned value of APInt for specific bit width.
getMaxValue(unsigned numBits)534   static APInt getMaxValue(unsigned numBits) {
535     return getAllOnesValue(numBits);
536   }
537 
538   /// Gets maximum signed value of APInt for a specific bit width.
getSignedMaxValue(unsigned numBits)539   static APInt getSignedMaxValue(unsigned numBits) {
540     APInt API = getAllOnesValue(numBits);
541     API.clearBit(numBits - 1);
542     return API;
543   }
544 
545   /// Gets minimum unsigned value of APInt for a specific bit width.
getMinValue(unsigned numBits)546   static APInt getMinValue(unsigned numBits) { return APInt(numBits, 0); }
547 
548   /// Gets minimum signed value of APInt for a specific bit width.
getSignedMinValue(unsigned numBits)549   static APInt getSignedMinValue(unsigned numBits) {
550     APInt API(numBits, 0);
551     API.setBit(numBits - 1);
552     return API;
553   }
554 
555   /// Get the SignMask for a specific bit width.
556   ///
557   /// This is just a wrapper function of getSignedMinValue(), and it helps code
558   /// readability when we want to get a SignMask.
getSignMask(unsigned BitWidth)559   static APInt getSignMask(unsigned BitWidth) {
560     return getSignedMinValue(BitWidth);
561   }
562 
563   /// Get the all-ones value.
564   ///
565   /// \returns the all-ones value for an APInt of the specified bit-width.
getAllOnesValue(unsigned numBits)566   static APInt getAllOnesValue(unsigned numBits) {
567     return APInt(numBits, WORDTYPE_MAX, true);
568   }
569 
570   /// Get the '0' value.
571   ///
572   /// \returns the '0' value for an APInt of the specified bit-width.
getNullValue(unsigned numBits)573   static APInt getNullValue(unsigned numBits) { return APInt(numBits, 0); }
574 
575   /// Compute an APInt containing numBits highbits from this APInt.
576   ///
577   /// Get an APInt with the same BitWidth as this APInt, just zero mask
578   /// the low bits and right shift to the least significant bit.
579   ///
580   /// \returns the high "numBits" bits of this APInt.
581   APInt getHiBits(unsigned numBits) const;
582 
583   /// Compute an APInt containing numBits lowbits from this APInt.
584   ///
585   /// Get an APInt with the same BitWidth as this APInt, just zero mask
586   /// the high bits.
587   ///
588   /// \returns the low "numBits" bits of this APInt.
589   APInt getLoBits(unsigned numBits) const;
590 
591   /// Return an APInt with exactly one bit set in the result.
getOneBitSet(unsigned numBits,unsigned BitNo)592   static APInt getOneBitSet(unsigned numBits, unsigned BitNo) {
593     APInt Res(numBits, 0);
594     Res.setBit(BitNo);
595     return Res;
596   }
597 
598   /// Get a value with a block of bits set.
599   ///
600   /// Constructs an APInt value that has a contiguous range of bits set. The
601   /// bits from loBit (inclusive) to hiBit (exclusive) will be set. All other
602   /// bits will be zero. For example, with parameters(32, 0, 16) you would get
603   /// 0x0000FFFF. Please call getBitsSetWithWrap if \p loBit may be greater than
604   /// \p hiBit.
605   ///
606   /// \param numBits the intended bit width of the result
607   /// \param loBit the index of the lowest bit set.
608   /// \param hiBit the index of the highest bit set.
609   ///
610   /// \returns An APInt value with the requested bits set.
getBitsSet(unsigned numBits,unsigned loBit,unsigned hiBit)611   static APInt getBitsSet(unsigned numBits, unsigned loBit, unsigned hiBit) {
612     assert(loBit <= hiBit && "loBit greater than hiBit");
613     APInt Res(numBits, 0);
614     Res.setBits(loBit, hiBit);
615     return Res;
616   }
617 
618   /// Wrap version of getBitsSet.
619   /// If \p hiBit is no less than \p loBit, this is same with getBitsSet.
620   /// If \p hiBit is less than \p loBit, the set bits "wrap". For example, with
621   /// parameters (32, 28, 4), you would get 0xF000000F.
getBitsSetWithWrap(unsigned numBits,unsigned loBit,unsigned hiBit)622   static APInt getBitsSetWithWrap(unsigned numBits, unsigned loBit,
623                                   unsigned hiBit) {
624     APInt Res(numBits, 0);
625     Res.setBitsWithWrap(loBit, hiBit);
626     return Res;
627   }
628 
629   /// Get a value with upper bits starting at loBit set.
630   ///
631   /// Constructs an APInt value that has a contiguous range of bits set. The
632   /// bits from loBit (inclusive) to numBits (exclusive) will be set. All other
633   /// bits will be zero. For example, with parameters(32, 12) you would get
634   /// 0xFFFFF000.
635   ///
636   /// \param numBits the intended bit width of the result
637   /// \param loBit the index of the lowest bit to set.
638   ///
639   /// \returns An APInt value with the requested bits set.
getBitsSetFrom(unsigned numBits,unsigned loBit)640   static APInt getBitsSetFrom(unsigned numBits, unsigned loBit) {
641     APInt Res(numBits, 0);
642     Res.setBitsFrom(loBit);
643     return Res;
644   }
645 
646   /// Get a value with high bits set
647   ///
648   /// Constructs an APInt value that has the top hiBitsSet bits set.
649   ///
650   /// \param numBits the bitwidth of the result
651   /// \param hiBitsSet the number of high-order bits set in the result.
getHighBitsSet(unsigned numBits,unsigned hiBitsSet)652   static APInt getHighBitsSet(unsigned numBits, unsigned hiBitsSet) {
653     APInt Res(numBits, 0);
654     Res.setHighBits(hiBitsSet);
655     return Res;
656   }
657 
658   /// Get a value with low bits set
659   ///
660   /// Constructs an APInt value that has the bottom loBitsSet bits set.
661   ///
662   /// \param numBits the bitwidth of the result
663   /// \param loBitsSet the number of low-order bits set in the result.
getLowBitsSet(unsigned numBits,unsigned loBitsSet)664   static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet) {
665     APInt Res(numBits, 0);
666     Res.setLowBits(loBitsSet);
667     return Res;
668   }
669 
670   /// Return a value containing V broadcasted over NewLen bits.
671   static APInt getSplat(unsigned NewLen, const APInt &V);
672 
673   /// Determine if two APInts have the same value, after zero-extending
674   /// one of them (if needed!) to ensure that the bit-widths match.
isSameValue(const APInt & I1,const APInt & I2)675   static bool isSameValue(const APInt &I1, const APInt &I2) {
676     if (I1.getBitWidth() == I2.getBitWidth())
677       return I1 == I2;
678 
679     if (I1.getBitWidth() > I2.getBitWidth())
680       return I1 == I2.zext(I1.getBitWidth());
681 
682     return I1.zext(I2.getBitWidth()) == I2;
683   }
684 
685   /// Overload to compute a hash_code for an APInt value.
686   friend hash_code hash_value(const APInt &Arg);
687 
688   /// This function returns a pointer to the internal storage of the APInt.
689   /// This is useful for writing out the APInt in binary form without any
690   /// conversions.
getRawData()691   const uint64_t *getRawData() const {
692     if (isSingleWord())
693       return &U.VAL;
694     return &U.pVal[0];
695   }
696 
697   /// @}
698   /// \name Unary Operators
699   /// @{
700 
701   /// Postfix increment operator.
702   ///
703   /// Increments *this by 1.
704   ///
705   /// \returns a new APInt value representing the original value of *this.
706   const APInt operator++(int) {
707     APInt API(*this);
708     ++(*this);
709     return API;
710   }
711 
712   /// Prefix increment operator.
713   ///
714   /// \returns *this incremented by one
715   APInt &operator++();
716 
717   /// Postfix decrement operator.
718   ///
719   /// Decrements *this by 1.
720   ///
721   /// \returns a new APInt value representing the original value of *this.
722   const APInt operator--(int) {
723     APInt API(*this);
724     --(*this);
725     return API;
726   }
727 
728   /// Prefix decrement operator.
729   ///
730   /// \returns *this decremented by one.
731   APInt &operator--();
732 
733   /// Logical negation operator.
734   ///
735   /// Performs logical negation operation on this APInt.
736   ///
737   /// \returns true if *this is zero, false otherwise.
738   bool operator!() const {
739     if (isSingleWord())
740       return U.VAL == 0;
741     return countLeadingZerosSlowCase() == BitWidth;
742   }
743 
744   /// @}
745   /// \name Assignment Operators
746   /// @{
747 
748   /// Copy assignment operator.
749   ///
750   /// \returns *this after assignment of RHS.
751   APInt &operator=(const APInt &RHS) {
752     // If the bitwidths are the same, we can avoid mucking with memory
753     if (isSingleWord() && RHS.isSingleWord()) {
754       U.VAL = RHS.U.VAL;
755       BitWidth = RHS.BitWidth;
756       return clearUnusedBits();
757     }
758 
759     AssignSlowCase(RHS);
760     return *this;
761   }
762 
763   /// Move assignment operator.
764   APInt &operator=(APInt &&that) {
765 #ifdef _MSC_VER
766     // The MSVC std::shuffle implementation still does self-assignment.
767     if (this == &that)
768       return *this;
769 #endif
770     assert(this != &that && "Self-move not supported");
771     if (!isSingleWord())
772       delete[] U.pVal;
773 
774     // Use memcpy so that type based alias analysis sees both VAL and pVal
775     // as modified.
776     memcpy(&U, &that.U, sizeof(U));
777 
778     BitWidth = that.BitWidth;
779     that.BitWidth = 0;
780 
781     return *this;
782   }
783 
784   /// Assignment operator.
785   ///
786   /// The RHS value is assigned to *this. If the significant bits in RHS exceed
787   /// the bit width, the excess bits are truncated. If the bit width is larger
788   /// than 64, the value is zero filled in the unspecified high order bits.
789   ///
790   /// \returns *this after assignment of RHS value.
791   APInt &operator=(uint64_t RHS) {
792     if (isSingleWord()) {
793       U.VAL = RHS;
794       clearUnusedBits();
795     } else {
796       U.pVal[0] = RHS;
797       memset(U.pVal+1, 0, (getNumWords() - 1) * APINT_WORD_SIZE);
798     }
799     return *this;
800   }
801 
802   /// Bitwise AND assignment operator.
803   ///
804   /// Performs a bitwise AND operation on this APInt and RHS. The result is
805   /// assigned to *this.
806   ///
807   /// \returns *this after ANDing with RHS.
808   APInt &operator&=(const APInt &RHS) {
809     assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
810     if (isSingleWord())
811       U.VAL &= RHS.U.VAL;
812     else
813       AndAssignSlowCase(RHS);
814     return *this;
815   }
816 
817   /// Bitwise AND assignment operator.
818   ///
819   /// Performs a bitwise AND operation on this APInt and RHS. RHS is
820   /// logically zero-extended or truncated to match the bit-width of
821   /// the LHS.
822   APInt &operator&=(uint64_t RHS) {
823     if (isSingleWord()) {
824       U.VAL &= RHS;
825       return *this;
826     }
827     U.pVal[0] &= RHS;
828     memset(U.pVal+1, 0, (getNumWords() - 1) * APINT_WORD_SIZE);
829     return *this;
830   }
831 
832   /// Bitwise OR assignment operator.
833   ///
834   /// Performs a bitwise OR operation on this APInt and RHS. The result is
835   /// assigned *this;
836   ///
837   /// \returns *this after ORing with RHS.
838   APInt &operator|=(const APInt &RHS) {
839     assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
840     if (isSingleWord())
841       U.VAL |= RHS.U.VAL;
842     else
843       OrAssignSlowCase(RHS);
844     return *this;
845   }
846 
847   /// Bitwise OR assignment operator.
848   ///
849   /// Performs a bitwise OR operation on this APInt and RHS. RHS is
850   /// logically zero-extended or truncated to match the bit-width of
851   /// the LHS.
852   APInt &operator|=(uint64_t RHS) {
853     if (isSingleWord()) {
854       U.VAL |= RHS;
855       clearUnusedBits();
856     } else {
857       U.pVal[0] |= RHS;
858     }
859     return *this;
860   }
861 
862   /// Bitwise XOR assignment operator.
863   ///
864   /// Performs a bitwise XOR operation on this APInt and RHS. The result is
865   /// assigned to *this.
866   ///
867   /// \returns *this after XORing with RHS.
868   APInt &operator^=(const APInt &RHS) {
869     assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
870     if (isSingleWord())
871       U.VAL ^= RHS.U.VAL;
872     else
873       XorAssignSlowCase(RHS);
874     return *this;
875   }
876 
877   /// Bitwise XOR assignment operator.
878   ///
879   /// Performs a bitwise XOR operation on this APInt and RHS. RHS is
880   /// logically zero-extended or truncated to match the bit-width of
881   /// the LHS.
882   APInt &operator^=(uint64_t RHS) {
883     if (isSingleWord()) {
884       U.VAL ^= RHS;
885       clearUnusedBits();
886     } else {
887       U.pVal[0] ^= RHS;
888     }
889     return *this;
890   }
891 
892   /// Multiplication assignment operator.
893   ///
894   /// Multiplies this APInt by RHS and assigns the result to *this.
895   ///
896   /// \returns *this
897   APInt &operator*=(const APInt &RHS);
898   APInt &operator*=(uint64_t RHS);
899 
900   /// Addition assignment operator.
901   ///
902   /// Adds RHS to *this and assigns the result to *this.
903   ///
904   /// \returns *this
905   APInt &operator+=(const APInt &RHS);
906   APInt &operator+=(uint64_t RHS);
907 
908   /// Subtraction assignment operator.
909   ///
910   /// Subtracts RHS from *this and assigns the result to *this.
911   ///
912   /// \returns *this
913   APInt &operator-=(const APInt &RHS);
914   APInt &operator-=(uint64_t RHS);
915 
916   /// Left-shift assignment function.
917   ///
918   /// Shifts *this left by shiftAmt and assigns the result to *this.
919   ///
920   /// \returns *this after shifting left by ShiftAmt
921   APInt &operator<<=(unsigned ShiftAmt) {
922     assert(ShiftAmt <= BitWidth && "Invalid shift amount");
923     if (isSingleWord()) {
924       if (ShiftAmt == BitWidth)
925         U.VAL = 0;
926       else
927         U.VAL <<= ShiftAmt;
928       return clearUnusedBits();
929     }
930     shlSlowCase(ShiftAmt);
931     return *this;
932   }
933 
934   /// Left-shift assignment function.
935   ///
936   /// Shifts *this left by shiftAmt and assigns the result to *this.
937   ///
938   /// \returns *this after shifting left by ShiftAmt
939   APInt &operator<<=(const APInt &ShiftAmt);
940 
941   /// @}
942   /// \name Binary Operators
943   /// @{
944 
945   /// Multiplication operator.
946   ///
947   /// Multiplies this APInt by RHS and returns the result.
948   APInt operator*(const APInt &RHS) const;
949 
950   /// Left logical shift operator.
951   ///
952   /// Shifts this APInt left by \p Bits and returns the result.
953   APInt operator<<(unsigned Bits) const { return shl(Bits); }
954 
955   /// Left logical shift operator.
956   ///
957   /// Shifts this APInt left by \p Bits and returns the result.
958   APInt operator<<(const APInt &Bits) const { return shl(Bits); }
959 
960   /// Arithmetic right-shift function.
961   ///
962   /// Arithmetic right-shift this APInt by shiftAmt.
ashr(unsigned ShiftAmt)963   APInt ashr(unsigned ShiftAmt) const {
964     APInt R(*this);
965     R.ashrInPlace(ShiftAmt);
966     return R;
967   }
968 
969   /// Arithmetic right-shift this APInt by ShiftAmt in place.
ashrInPlace(unsigned ShiftAmt)970   void ashrInPlace(unsigned ShiftAmt) {
971     assert(ShiftAmt <= BitWidth && "Invalid shift amount");
972     if (isSingleWord()) {
973       int64_t SExtVAL = SignExtend64(U.VAL, BitWidth);
974       if (ShiftAmt == BitWidth)
975         U.VAL = SExtVAL >> (APINT_BITS_PER_WORD - 1); // Fill with sign bit.
976       else
977         U.VAL = SExtVAL >> ShiftAmt;
978       clearUnusedBits();
979       return;
980     }
981     ashrSlowCase(ShiftAmt);
982   }
983 
984   /// Logical right-shift function.
985   ///
986   /// Logical right-shift this APInt by shiftAmt.
lshr(unsigned shiftAmt)987   APInt lshr(unsigned shiftAmt) const {
988     APInt R(*this);
989     R.lshrInPlace(shiftAmt);
990     return R;
991   }
992 
993   /// Logical right-shift this APInt by ShiftAmt in place.
lshrInPlace(unsigned ShiftAmt)994   void lshrInPlace(unsigned ShiftAmt) {
995     assert(ShiftAmt <= BitWidth && "Invalid shift amount");
996     if (isSingleWord()) {
997       if (ShiftAmt == BitWidth)
998         U.VAL = 0;
999       else
1000         U.VAL >>= ShiftAmt;
1001       return;
1002     }
1003     lshrSlowCase(ShiftAmt);
1004   }
1005 
1006   /// Left-shift function.
1007   ///
1008   /// Left-shift this APInt by shiftAmt.
shl(unsigned shiftAmt)1009   APInt shl(unsigned shiftAmt) const {
1010     APInt R(*this);
1011     R <<= shiftAmt;
1012     return R;
1013   }
1014 
1015   /// Rotate left by rotateAmt.
1016   APInt rotl(unsigned rotateAmt) const;
1017 
1018   /// Rotate right by rotateAmt.
1019   APInt rotr(unsigned rotateAmt) const;
1020 
1021   /// Arithmetic right-shift function.
1022   ///
1023   /// Arithmetic right-shift this APInt by shiftAmt.
ashr(const APInt & ShiftAmt)1024   APInt ashr(const APInt &ShiftAmt) const {
1025     APInt R(*this);
1026     R.ashrInPlace(ShiftAmt);
1027     return R;
1028   }
1029 
1030   /// Arithmetic right-shift this APInt by shiftAmt in place.
1031   void ashrInPlace(const APInt &shiftAmt);
1032 
1033   /// Logical right-shift function.
1034   ///
1035   /// Logical right-shift this APInt by shiftAmt.
lshr(const APInt & ShiftAmt)1036   APInt lshr(const APInt &ShiftAmt) const {
1037     APInt R(*this);
1038     R.lshrInPlace(ShiftAmt);
1039     return R;
1040   }
1041 
1042   /// Logical right-shift this APInt by ShiftAmt in place.
1043   void lshrInPlace(const APInt &ShiftAmt);
1044 
1045   /// Left-shift function.
1046   ///
1047   /// Left-shift this APInt by shiftAmt.
shl(const APInt & ShiftAmt)1048   APInt shl(const APInt &ShiftAmt) const {
1049     APInt R(*this);
1050     R <<= ShiftAmt;
1051     return R;
1052   }
1053 
1054   /// Rotate left by rotateAmt.
1055   APInt rotl(const APInt &rotateAmt) const;
1056 
1057   /// Rotate right by rotateAmt.
1058   APInt rotr(const APInt &rotateAmt) const;
1059 
1060   /// Unsigned division operation.
1061   ///
1062   /// Perform an unsigned divide operation on this APInt by RHS. Both this and
1063   /// RHS are treated as unsigned quantities for purposes of this division.
1064   ///
1065   /// \returns a new APInt value containing the division result, rounded towards
1066   /// zero.
1067   APInt udiv(const APInt &RHS) const;
1068   APInt udiv(uint64_t RHS) const;
1069 
1070   /// Signed division function for APInt.
1071   ///
1072   /// Signed divide this APInt by APInt RHS.
1073   ///
1074   /// The result is rounded towards zero.
1075   APInt sdiv(const APInt &RHS) const;
1076   APInt sdiv(int64_t RHS) const;
1077 
1078   /// Unsigned remainder operation.
1079   ///
1080   /// Perform an unsigned remainder operation on this APInt with RHS being the
1081   /// divisor. Both this and RHS are treated as unsigned quantities for purposes
1082   /// of this operation. Note that this is a true remainder operation and not a
1083   /// modulo operation because the sign follows the sign of the dividend which
1084   /// is *this.
1085   ///
1086   /// \returns a new APInt value containing the remainder result
1087   APInt urem(const APInt &RHS) const;
1088   uint64_t urem(uint64_t RHS) const;
1089 
1090   /// Function for signed remainder operation.
1091   ///
1092   /// Signed remainder operation on APInt.
1093   APInt srem(const APInt &RHS) const;
1094   int64_t srem(int64_t RHS) const;
1095 
1096   /// Dual division/remainder interface.
1097   ///
1098   /// Sometimes it is convenient to divide two APInt values and obtain both the
1099   /// quotient and remainder. This function does both operations in the same
1100   /// computation making it a little more efficient. The pair of input arguments
1101   /// may overlap with the pair of output arguments. It is safe to call
1102   /// udivrem(X, Y, X, Y), for example.
1103   static void udivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient,
1104                       APInt &Remainder);
1105   static void udivrem(const APInt &LHS, uint64_t RHS, APInt &Quotient,
1106                       uint64_t &Remainder);
1107 
1108   static void sdivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient,
1109                       APInt &Remainder);
1110   static void sdivrem(const APInt &LHS, int64_t RHS, APInt &Quotient,
1111                       int64_t &Remainder);
1112 
1113   // Operations that return overflow indicators.
1114   APInt sadd_ov(const APInt &RHS, bool &Overflow) const;
1115   APInt uadd_ov(const APInt &RHS, bool &Overflow) const;
1116   APInt ssub_ov(const APInt &RHS, bool &Overflow) const;
1117   APInt usub_ov(const APInt &RHS, bool &Overflow) const;
1118   APInt sdiv_ov(const APInt &RHS, bool &Overflow) const;
1119   APInt smul_ov(const APInt &RHS, bool &Overflow) const;
1120   APInt umul_ov(const APInt &RHS, bool &Overflow) const;
1121   APInt sshl_ov(const APInt &Amt, bool &Overflow) const;
1122   APInt ushl_ov(const APInt &Amt, bool &Overflow) const;
1123 
1124   // Operations that saturate
1125   APInt sadd_sat(const APInt &RHS) const;
1126   APInt uadd_sat(const APInt &RHS) const;
1127   APInt ssub_sat(const APInt &RHS) const;
1128   APInt usub_sat(const APInt &RHS) const;
1129   APInt smul_sat(const APInt &RHS) const;
1130   APInt umul_sat(const APInt &RHS) const;
1131   APInt sshl_sat(const APInt &RHS) const;
1132   APInt ushl_sat(const APInt &RHS) const;
1133 
1134   /// Array-indexing support.
1135   ///
1136   /// \returns the bit value at bitPosition
1137   bool operator[](unsigned bitPosition) const {
1138     assert(bitPosition < getBitWidth() && "Bit position out of bounds!");
1139     return (maskBit(bitPosition) & getWord(bitPosition)) != 0;
1140   }
1141 
1142   /// @}
1143   /// \name Comparison Operators
1144   /// @{
1145 
1146   /// Equality operator.
1147   ///
1148   /// Compares this APInt with RHS for the validity of the equality
1149   /// relationship.
1150   bool operator==(const APInt &RHS) const {
1151     assert(BitWidth == RHS.BitWidth && "Comparison requires equal bit widths");
1152     if (isSingleWord())
1153       return U.VAL == RHS.U.VAL;
1154     return EqualSlowCase(RHS);
1155   }
1156 
1157   /// Equality operator.
1158   ///
1159   /// Compares this APInt with a uint64_t for the validity of the equality
1160   /// relationship.
1161   ///
1162   /// \returns true if *this == Val
1163   bool operator==(uint64_t Val) const {
1164     return (isSingleWord() || getActiveBits() <= 64) && getZExtValue() == Val;
1165   }
1166 
1167   /// Equality comparison.
1168   ///
1169   /// Compares this APInt with RHS for the validity of the equality
1170   /// relationship.
1171   ///
1172   /// \returns true if *this == Val
eq(const APInt & RHS)1173   bool eq(const APInt &RHS) const { return (*this) == RHS; }
1174 
1175   /// Inequality operator.
1176   ///
1177   /// Compares this APInt with RHS for the validity of the inequality
1178   /// relationship.
1179   ///
1180   /// \returns true if *this != Val
1181   bool operator!=(const APInt &RHS) const { return !((*this) == RHS); }
1182 
1183   /// Inequality operator.
1184   ///
1185   /// Compares this APInt with a uint64_t for the validity of the inequality
1186   /// relationship.
1187   ///
1188   /// \returns true if *this != Val
1189   bool operator!=(uint64_t Val) const { return !((*this) == Val); }
1190 
1191   /// Inequality comparison
1192   ///
1193   /// Compares this APInt with RHS for the validity of the inequality
1194   /// relationship.
1195   ///
1196   /// \returns true if *this != Val
ne(const APInt & RHS)1197   bool ne(const APInt &RHS) const { return !((*this) == RHS); }
1198 
1199   /// Unsigned less than comparison
1200   ///
1201   /// Regards both *this and RHS as unsigned quantities and compares them for
1202   /// the validity of the less-than relationship.
1203   ///
1204   /// \returns true if *this < RHS when both are considered unsigned.
ult(const APInt & RHS)1205   bool ult(const APInt &RHS) const { return compare(RHS) < 0; }
1206 
1207   /// Unsigned less than comparison
1208   ///
1209   /// Regards both *this as an unsigned quantity and compares it with RHS for
1210   /// the validity of the less-than relationship.
1211   ///
1212   /// \returns true if *this < RHS when considered unsigned.
ult(uint64_t RHS)1213   bool ult(uint64_t RHS) const {
1214     // Only need to check active bits if not a single word.
1215     return (isSingleWord() || getActiveBits() <= 64) && getZExtValue() < RHS;
1216   }
1217 
1218   /// Signed less than comparison
1219   ///
1220   /// Regards both *this and RHS as signed quantities and compares them for
1221   /// validity of the less-than relationship.
1222   ///
1223   /// \returns true if *this < RHS when both are considered signed.
slt(const APInt & RHS)1224   bool slt(const APInt &RHS) const { return compareSigned(RHS) < 0; }
1225 
1226   /// Signed less than comparison
1227   ///
1228   /// Regards both *this as a signed quantity and compares it with RHS for
1229   /// the validity of the less-than relationship.
1230   ///
1231   /// \returns true if *this < RHS when considered signed.
slt(int64_t RHS)1232   bool slt(int64_t RHS) const {
1233     return (!isSingleWord() && getMinSignedBits() > 64) ? isNegative()
1234                                                         : getSExtValue() < RHS;
1235   }
1236 
1237   /// Unsigned less or equal comparison
1238   ///
1239   /// Regards both *this and RHS as unsigned quantities and compares them for
1240   /// validity of the less-or-equal relationship.
1241   ///
1242   /// \returns true if *this <= RHS when both are considered unsigned.
ule(const APInt & RHS)1243   bool ule(const APInt &RHS) const { return compare(RHS) <= 0; }
1244 
1245   /// Unsigned less or equal comparison
1246   ///
1247   /// Regards both *this as an unsigned quantity and compares it with RHS for
1248   /// the validity of the less-or-equal relationship.
1249   ///
1250   /// \returns true if *this <= RHS when considered unsigned.
ule(uint64_t RHS)1251   bool ule(uint64_t RHS) const { return !ugt(RHS); }
1252 
1253   /// Signed less or equal comparison
1254   ///
1255   /// Regards both *this and RHS as signed quantities and compares them for
1256   /// validity of the less-or-equal relationship.
1257   ///
1258   /// \returns true if *this <= RHS when both are considered signed.
sle(const APInt & RHS)1259   bool sle(const APInt &RHS) const { return compareSigned(RHS) <= 0; }
1260 
1261   /// Signed less or equal comparison
1262   ///
1263   /// Regards both *this as a signed quantity and compares it with RHS for the
1264   /// validity of the less-or-equal relationship.
1265   ///
1266   /// \returns true if *this <= RHS when considered signed.
sle(uint64_t RHS)1267   bool sle(uint64_t RHS) const { return !sgt(RHS); }
1268 
1269   /// Unsigned greater than comparison
1270   ///
1271   /// Regards both *this and RHS as unsigned quantities and compares them for
1272   /// the validity of the greater-than relationship.
1273   ///
1274   /// \returns true if *this > RHS when both are considered unsigned.
ugt(const APInt & RHS)1275   bool ugt(const APInt &RHS) const { return !ule(RHS); }
1276 
1277   /// Unsigned greater than comparison
1278   ///
1279   /// Regards both *this as an unsigned quantity and compares it with RHS for
1280   /// the validity of the greater-than relationship.
1281   ///
1282   /// \returns true if *this > RHS when considered unsigned.
ugt(uint64_t RHS)1283   bool ugt(uint64_t RHS) const {
1284     // Only need to check active bits if not a single word.
1285     return (!isSingleWord() && getActiveBits() > 64) || getZExtValue() > RHS;
1286   }
1287 
1288   /// Signed greater than comparison
1289   ///
1290   /// Regards both *this and RHS as signed quantities and compares them for the
1291   /// validity of the greater-than relationship.
1292   ///
1293   /// \returns true if *this > RHS when both are considered signed.
sgt(const APInt & RHS)1294   bool sgt(const APInt &RHS) const { return !sle(RHS); }
1295 
1296   /// Signed greater than comparison
1297   ///
1298   /// Regards both *this as a signed quantity and compares it with RHS for
1299   /// the validity of the greater-than relationship.
1300   ///
1301   /// \returns true if *this > RHS when considered signed.
sgt(int64_t RHS)1302   bool sgt(int64_t RHS) const {
1303     return (!isSingleWord() && getMinSignedBits() > 64) ? !isNegative()
1304                                                         : getSExtValue() > RHS;
1305   }
1306 
1307   /// Unsigned greater or equal comparison
1308   ///
1309   /// Regards both *this and RHS as unsigned quantities and compares them for
1310   /// validity of the greater-or-equal relationship.
1311   ///
1312   /// \returns true if *this >= RHS when both are considered unsigned.
uge(const APInt & RHS)1313   bool uge(const APInt &RHS) const { return !ult(RHS); }
1314 
1315   /// Unsigned greater or equal comparison
1316   ///
1317   /// Regards both *this as an unsigned quantity and compares it with RHS for
1318   /// the validity of the greater-or-equal relationship.
1319   ///
1320   /// \returns true if *this >= RHS when considered unsigned.
uge(uint64_t RHS)1321   bool uge(uint64_t RHS) const { return !ult(RHS); }
1322 
1323   /// Signed greater or equal comparison
1324   ///
1325   /// Regards both *this and RHS as signed quantities and compares them for
1326   /// validity of the greater-or-equal relationship.
1327   ///
1328   /// \returns true if *this >= RHS when both are considered signed.
sge(const APInt & RHS)1329   bool sge(const APInt &RHS) const { return !slt(RHS); }
1330 
1331   /// Signed greater or equal comparison
1332   ///
1333   /// Regards both *this as a signed quantity and compares it with RHS for
1334   /// the validity of the greater-or-equal relationship.
1335   ///
1336   /// \returns true if *this >= RHS when considered signed.
sge(int64_t RHS)1337   bool sge(int64_t RHS) const { return !slt(RHS); }
1338 
1339   /// This operation tests if there are any pairs of corresponding bits
1340   /// between this APInt and RHS that are both set.
intersects(const APInt & RHS)1341   bool intersects(const APInt &RHS) const {
1342     assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1343     if (isSingleWord())
1344       return (U.VAL & RHS.U.VAL) != 0;
1345     return intersectsSlowCase(RHS);
1346   }
1347 
1348   /// This operation checks that all bits set in this APInt are also set in RHS.
isSubsetOf(const APInt & RHS)1349   bool isSubsetOf(const APInt &RHS) const {
1350     assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1351     if (isSingleWord())
1352       return (U.VAL & ~RHS.U.VAL) == 0;
1353     return isSubsetOfSlowCase(RHS);
1354   }
1355 
1356   /// @}
1357   /// \name Resizing Operators
1358   /// @{
1359 
1360   /// Truncate to new width.
1361   ///
1362   /// Truncate the APInt to a specified width. It is an error to specify a width
1363   /// that is greater than or equal to the current width.
1364   APInt trunc(unsigned width) const;
1365 
1366   /// Truncate to new width with unsigned saturation.
1367   ///
1368   /// If the APInt, treated as unsigned integer, can be losslessly truncated to
1369   /// the new bitwidth, then return truncated APInt. Else, return max value.
1370   APInt truncUSat(unsigned width) const;
1371 
1372   /// Truncate to new width with signed saturation.
1373   ///
1374   /// If this APInt, treated as signed integer, can be losslessly truncated to
1375   /// the new bitwidth, then return truncated APInt. Else, return either
1376   /// signed min value if the APInt was negative, or signed max value.
1377   APInt truncSSat(unsigned width) const;
1378 
1379   /// Sign extend to a new width.
1380   ///
1381   /// This operation sign extends the APInt to a new width. If the high order
1382   /// bit is set, the fill on the left will be done with 1 bits, otherwise zero.
1383   /// It is an error to specify a width that is less than or equal to the
1384   /// current width.
1385   APInt sext(unsigned width) const;
1386 
1387   /// Zero extend to a new width.
1388   ///
1389   /// This operation zero extends the APInt to a new width. The high order bits
1390   /// are filled with 0 bits.  It is an error to specify a width that is less
1391   /// than or equal to the current width.
1392   APInt zext(unsigned width) const;
1393 
1394   /// Sign extend or truncate to width
1395   ///
1396   /// Make this APInt have the bit width given by \p width. The value is sign
1397   /// extended, truncated, or left alone to make it that width.
1398   APInt sextOrTrunc(unsigned width) const;
1399 
1400   /// Zero extend or truncate to width
1401   ///
1402   /// Make this APInt have the bit width given by \p width. The value is zero
1403   /// extended, truncated, or left alone to make it that width.
1404   APInt zextOrTrunc(unsigned width) const;
1405 
1406   /// Sign extend or truncate to width
1407   ///
1408   /// Make this APInt have the bit width given by \p width. The value is sign
1409   /// extended, or left alone to make it that width.
1410   APInt sextOrSelf(unsigned width) const;
1411 
1412   /// Zero extend or truncate to width
1413   ///
1414   /// Make this APInt have the bit width given by \p width. The value is zero
1415   /// extended, or left alone to make it that width.
1416   APInt zextOrSelf(unsigned width) const;
1417 
1418   /// @}
1419   /// \name Bit Manipulation Operators
1420   /// @{
1421 
1422   /// Set every bit to 1.
setAllBits()1423   void setAllBits() {
1424     if (isSingleWord())
1425       U.VAL = WORDTYPE_MAX;
1426     else
1427       // Set all the bits in all the words.
1428       memset(U.pVal, -1, getNumWords() * APINT_WORD_SIZE);
1429     // Clear the unused ones
1430     clearUnusedBits();
1431   }
1432 
1433   /// Set a given bit to 1.
1434   ///
1435   /// Set the given bit to 1 whose position is given as "bitPosition".
setBit(unsigned BitPosition)1436   void setBit(unsigned BitPosition) {
1437     assert(BitPosition < BitWidth && "BitPosition out of range");
1438     WordType Mask = maskBit(BitPosition);
1439     if (isSingleWord())
1440       U.VAL |= Mask;
1441     else
1442       U.pVal[whichWord(BitPosition)] |= Mask;
1443   }
1444 
1445   /// Set the sign bit to 1.
setSignBit()1446   void setSignBit() {
1447     setBit(BitWidth - 1);
1448   }
1449 
1450   /// Set the bits from loBit (inclusive) to hiBit (exclusive) to 1.
1451   /// This function handles "wrap" case when \p loBit > \p hiBit, and calls
1452   /// setBits when \p loBit <= \p hiBit.
setBitsWithWrap(unsigned loBit,unsigned hiBit)1453   void setBitsWithWrap(unsigned loBit, unsigned hiBit) {
1454     assert(hiBit <= BitWidth && "hiBit out of range");
1455     assert(loBit <= BitWidth && "loBit out of range");
1456     if (loBit <= hiBit) {
1457       setBits(loBit, hiBit);
1458       return;
1459     }
1460     setLowBits(hiBit);
1461     setHighBits(BitWidth - loBit);
1462   }
1463 
1464   /// Set the bits from loBit (inclusive) to hiBit (exclusive) to 1.
1465   /// This function handles case when \p loBit <= \p hiBit.
setBits(unsigned loBit,unsigned hiBit)1466   void setBits(unsigned loBit, unsigned hiBit) {
1467     assert(hiBit <= BitWidth && "hiBit out of range");
1468     assert(loBit <= BitWidth && "loBit out of range");
1469     assert(loBit <= hiBit && "loBit greater than hiBit");
1470     if (loBit == hiBit)
1471       return;
1472     if (loBit < APINT_BITS_PER_WORD && hiBit <= APINT_BITS_PER_WORD) {
1473       uint64_t mask = WORDTYPE_MAX >> (APINT_BITS_PER_WORD - (hiBit - loBit));
1474       mask <<= loBit;
1475       if (isSingleWord())
1476         U.VAL |= mask;
1477       else
1478         U.pVal[0] |= mask;
1479     } else {
1480       setBitsSlowCase(loBit, hiBit);
1481     }
1482   }
1483 
1484   /// Set the top bits starting from loBit.
setBitsFrom(unsigned loBit)1485   void setBitsFrom(unsigned loBit) {
1486     return setBits(loBit, BitWidth);
1487   }
1488 
1489   /// Set the bottom loBits bits.
setLowBits(unsigned loBits)1490   void setLowBits(unsigned loBits) {
1491     return setBits(0, loBits);
1492   }
1493 
1494   /// Set the top hiBits bits.
setHighBits(unsigned hiBits)1495   void setHighBits(unsigned hiBits) {
1496     return setBits(BitWidth - hiBits, BitWidth);
1497   }
1498 
1499   /// Set every bit to 0.
clearAllBits()1500   void clearAllBits() {
1501     if (isSingleWord())
1502       U.VAL = 0;
1503     else
1504       memset(U.pVal, 0, getNumWords() * APINT_WORD_SIZE);
1505   }
1506 
1507   /// Set a given bit to 0.
1508   ///
1509   /// Set the given bit to 0 whose position is given as "bitPosition".
clearBit(unsigned BitPosition)1510   void clearBit(unsigned BitPosition) {
1511     assert(BitPosition < BitWidth && "BitPosition out of range");
1512     WordType Mask = ~maskBit(BitPosition);
1513     if (isSingleWord())
1514       U.VAL &= Mask;
1515     else
1516       U.pVal[whichWord(BitPosition)] &= Mask;
1517   }
1518 
1519   /// Set bottom loBits bits to 0.
clearLowBits(unsigned loBits)1520   void clearLowBits(unsigned loBits) {
1521     assert(loBits <= BitWidth && "More bits than bitwidth");
1522     APInt Keep = getHighBitsSet(BitWidth, BitWidth - loBits);
1523     *this &= Keep;
1524   }
1525 
1526   /// Set the sign bit to 0.
clearSignBit()1527   void clearSignBit() {
1528     clearBit(BitWidth - 1);
1529   }
1530 
1531   /// Toggle every bit to its opposite value.
flipAllBits()1532   void flipAllBits() {
1533     if (isSingleWord()) {
1534       U.VAL ^= WORDTYPE_MAX;
1535       clearUnusedBits();
1536     } else {
1537       flipAllBitsSlowCase();
1538     }
1539   }
1540 
1541   /// Toggles a given bit to its opposite value.
1542   ///
1543   /// Toggle a given bit to its opposite value whose position is given
1544   /// as "bitPosition".
1545   void flipBit(unsigned bitPosition);
1546 
1547   /// Negate this APInt in place.
negate()1548   void negate() {
1549     flipAllBits();
1550     ++(*this);
1551   }
1552 
1553   /// Insert the bits from a smaller APInt starting at bitPosition.
1554   void insertBits(const APInt &SubBits, unsigned bitPosition);
1555   void insertBits(uint64_t SubBits, unsigned bitPosition, unsigned numBits);
1556 
1557   /// Return an APInt with the extracted bits [bitPosition,bitPosition+numBits).
1558   APInt extractBits(unsigned numBits, unsigned bitPosition) const;
1559   uint64_t extractBitsAsZExtValue(unsigned numBits, unsigned bitPosition) const;
1560 
1561   /// @}
1562   /// \name Value Characterization Functions
1563   /// @{
1564 
1565   /// Return the number of bits in the APInt.
getBitWidth()1566   unsigned getBitWidth() const { return BitWidth; }
1567 
1568   /// Get the number of words.
1569   ///
1570   /// Here one word's bitwidth equals to that of uint64_t.
1571   ///
1572   /// \returns the number of words to hold the integer value of this APInt.
getNumWords()1573   unsigned getNumWords() const { return getNumWords(BitWidth); }
1574 
1575   /// Get the number of words.
1576   ///
1577   /// *NOTE* Here one word's bitwidth equals to that of uint64_t.
1578   ///
1579   /// \returns the number of words to hold the integer value with a given bit
1580   /// width.
getNumWords(unsigned BitWidth)1581   static unsigned getNumWords(unsigned BitWidth) {
1582     return ((uint64_t)BitWidth + APINT_BITS_PER_WORD - 1) / APINT_BITS_PER_WORD;
1583   }
1584 
1585   /// Compute the number of active bits in the value
1586   ///
1587   /// This function returns the number of active bits which is defined as the
1588   /// bit width minus the number of leading zeros. This is used in several
1589   /// computations to see how "wide" the value is.
getActiveBits()1590   unsigned getActiveBits() const { return BitWidth - countLeadingZeros(); }
1591 
1592   /// Compute the number of active words in the value of this APInt.
1593   ///
1594   /// This is used in conjunction with getActiveData to extract the raw value of
1595   /// the APInt.
getActiveWords()1596   unsigned getActiveWords() const {
1597     unsigned numActiveBits = getActiveBits();
1598     return numActiveBits ? whichWord(numActiveBits - 1) + 1 : 1;
1599   }
1600 
1601   /// Get the minimum bit size for this signed APInt
1602   ///
1603   /// Computes the minimum bit width for this APInt while considering it to be a
1604   /// signed (and probably negative) value. If the value is not negative, this
1605   /// function returns the same value as getActiveBits()+1. Otherwise, it
1606   /// returns the smallest bit width that will retain the negative value. For
1607   /// example, -1 can be written as 0b1 or 0xFFFFFFFFFF. 0b1 is shorter and so
1608   /// for -1, this function will always return 1.
getMinSignedBits()1609   unsigned getMinSignedBits() const {
1610     if (isNegative())
1611       return BitWidth - countLeadingOnes() + 1;
1612     return getActiveBits() + 1;
1613   }
1614 
1615   /// Get zero extended value
1616   ///
1617   /// This method attempts to return the value of this APInt as a zero extended
1618   /// uint64_t. The bitwidth must be <= 64 or the value must fit within a
1619   /// uint64_t. Otherwise an assertion will result.
getZExtValue()1620   uint64_t getZExtValue() const {
1621     if (isSingleWord())
1622       return U.VAL;
1623     assert(getActiveBits() <= 64 && "Too many bits for uint64_t");
1624     return U.pVal[0];
1625   }
1626 
1627   /// Get sign extended value
1628   ///
1629   /// This method attempts to return the value of this APInt as a sign extended
1630   /// int64_t. The bit width must be <= 64 or the value must fit within an
1631   /// int64_t. Otherwise an assertion will result.
getSExtValue()1632   int64_t getSExtValue() const {
1633     if (isSingleWord())
1634       return SignExtend64(U.VAL, BitWidth);
1635     assert(getMinSignedBits() <= 64 && "Too many bits for int64_t");
1636     return int64_t(U.pVal[0]);
1637   }
1638 
1639   /// Get bits required for string value.
1640   ///
1641   /// This method determines how many bits are required to hold the APInt
1642   /// equivalent of the string given by \p str.
1643   static unsigned getBitsNeeded(StringRef str, uint8_t radix);
1644 
1645   /// The APInt version of the countLeadingZeros functions in
1646   ///   MathExtras.h.
1647   ///
1648   /// It counts the number of zeros from the most significant bit to the first
1649   /// one bit.
1650   ///
1651   /// \returns BitWidth if the value is zero, otherwise returns the number of
1652   ///   zeros from the most significant bit to the first one bits.
countLeadingZeros()1653   unsigned countLeadingZeros() const {
1654     if (isSingleWord()) {
1655       unsigned unusedBits = APINT_BITS_PER_WORD - BitWidth;
1656       return llvm::countLeadingZeros(U.VAL) - unusedBits;
1657     }
1658     return countLeadingZerosSlowCase();
1659   }
1660 
1661   /// Count the number of leading one bits.
1662   ///
1663   /// This function is an APInt version of the countLeadingOnes
1664   /// functions in MathExtras.h. It counts the number of ones from the most
1665   /// significant bit to the first zero bit.
1666   ///
1667   /// \returns 0 if the high order bit is not set, otherwise returns the number
1668   /// of 1 bits from the most significant to the least
countLeadingOnes()1669   unsigned countLeadingOnes() const {
1670     if (isSingleWord())
1671       return llvm::countLeadingOnes(U.VAL << (APINT_BITS_PER_WORD - BitWidth));
1672     return countLeadingOnesSlowCase();
1673   }
1674 
1675   /// Computes the number of leading bits of this APInt that are equal to its
1676   /// sign bit.
getNumSignBits()1677   unsigned getNumSignBits() const {
1678     return isNegative() ? countLeadingOnes() : countLeadingZeros();
1679   }
1680 
1681   /// Count the number of trailing zero bits.
1682   ///
1683   /// This function is an APInt version of the countTrailingZeros
1684   /// functions in MathExtras.h. It counts the number of zeros from the least
1685   /// significant bit to the first set bit.
1686   ///
1687   /// \returns BitWidth if the value is zero, otherwise returns the number of
1688   /// zeros from the least significant bit to the first one bit.
countTrailingZeros()1689   unsigned countTrailingZeros() const {
1690     if (isSingleWord())
1691       return std::min(unsigned(llvm::countTrailingZeros(U.VAL)), BitWidth);
1692     return countTrailingZerosSlowCase();
1693   }
1694 
1695   /// Count the number of trailing one bits.
1696   ///
1697   /// This function is an APInt version of the countTrailingOnes
1698   /// functions in MathExtras.h. It counts the number of ones from the least
1699   /// significant bit to the first zero bit.
1700   ///
1701   /// \returns BitWidth if the value is all ones, otherwise returns the number
1702   /// of ones from the least significant bit to the first zero bit.
countTrailingOnes()1703   unsigned countTrailingOnes() const {
1704     if (isSingleWord())
1705       return llvm::countTrailingOnes(U.VAL);
1706     return countTrailingOnesSlowCase();
1707   }
1708 
1709   /// Count the number of bits set.
1710   ///
1711   /// This function is an APInt version of the countPopulation functions
1712   /// in MathExtras.h. It counts the number of 1 bits in the APInt value.
1713   ///
1714   /// \returns 0 if the value is zero, otherwise returns the number of set bits.
countPopulation()1715   unsigned countPopulation() const {
1716     if (isSingleWord())
1717       return llvm::countPopulation(U.VAL);
1718     return countPopulationSlowCase();
1719   }
1720 
1721   /// @}
1722   /// \name Conversion Functions
1723   /// @{
1724   void print(raw_ostream &OS, bool isSigned) const;
1725 
1726   /// Converts an APInt to a string and append it to Str.  Str is commonly a
1727   /// SmallString.
1728   void toString(SmallVectorImpl<char> &Str, unsigned Radix, bool Signed,
1729                 bool formatAsCLiteral = false) const;
1730 
1731   /// Considers the APInt to be unsigned and converts it into a string in the
1732   /// radix given. The radix can be 2, 8, 10 16, or 36.
1733   void toStringUnsigned(SmallVectorImpl<char> &Str, unsigned Radix = 10) const {
1734     toString(Str, Radix, false, false);
1735   }
1736 
1737   /// Considers the APInt to be signed and converts it into a string in the
1738   /// radix given. The radix can be 2, 8, 10, 16, or 36.
1739   void toStringSigned(SmallVectorImpl<char> &Str, unsigned Radix = 10) const {
1740     toString(Str, Radix, true, false);
1741   }
1742 
1743   /// Return the APInt as a std::string.
1744   ///
1745   /// Note that this is an inefficient method.  It is better to pass in a
1746   /// SmallVector/SmallString to the methods above to avoid thrashing the heap
1747   /// for the string.
1748   std::string toString(unsigned Radix, bool Signed) const;
1749 
1750   /// \returns a byte-swapped representation of this APInt Value.
1751   APInt byteSwap() const;
1752 
1753   /// \returns the value with the bit representation reversed of this APInt
1754   /// Value.
1755   APInt reverseBits() const;
1756 
1757   /// Converts this APInt to a double value.
1758   double roundToDouble(bool isSigned) const;
1759 
1760   /// Converts this unsigned APInt to a double value.
roundToDouble()1761   double roundToDouble() const { return roundToDouble(false); }
1762 
1763   /// Converts this signed APInt to a double value.
signedRoundToDouble()1764   double signedRoundToDouble() const { return roundToDouble(true); }
1765 
1766   /// Converts APInt bits to a double
1767   ///
1768   /// The conversion does not do a translation from integer to double, it just
1769   /// re-interprets the bits as a double. Note that it is valid to do this on
1770   /// any bit width. Exactly 64 bits will be translated.
bitsToDouble()1771   double bitsToDouble() const {
1772     return BitsToDouble(getWord(0));
1773   }
1774 
1775   /// Converts APInt bits to a float
1776   ///
1777   /// The conversion does not do a translation from integer to float, it just
1778   /// re-interprets the bits as a float. Note that it is valid to do this on
1779   /// any bit width. Exactly 32 bits will be translated.
bitsToFloat()1780   float bitsToFloat() const {
1781     return BitsToFloat(static_cast<uint32_t>(getWord(0)));
1782   }
1783 
1784   /// Converts a double to APInt bits.
1785   ///
1786   /// The conversion does not do a translation from double to integer, it just
1787   /// re-interprets the bits of the double.
doubleToBits(double V)1788   static APInt doubleToBits(double V) {
1789     return APInt(sizeof(double) * CHAR_BIT, DoubleToBits(V));
1790   }
1791 
1792   /// Converts a float to APInt bits.
1793   ///
1794   /// The conversion does not do a translation from float to integer, it just
1795   /// re-interprets the bits of the float.
floatToBits(float V)1796   static APInt floatToBits(float V) {
1797     return APInt(sizeof(float) * CHAR_BIT, FloatToBits(V));
1798   }
1799 
1800   /// @}
1801   /// \name Mathematics Operations
1802   /// @{
1803 
1804   /// \returns the floor log base 2 of this APInt.
logBase2()1805   unsigned logBase2() const { return getActiveBits() -  1; }
1806 
1807   /// \returns the ceil log base 2 of this APInt.
ceilLogBase2()1808   unsigned ceilLogBase2() const {
1809     APInt temp(*this);
1810     --temp;
1811     return temp.getActiveBits();
1812   }
1813 
1814   /// \returns the nearest log base 2 of this APInt. Ties round up.
1815   ///
1816   /// NOTE: When we have a BitWidth of 1, we define:
1817   ///
1818   ///   log2(0) = UINT32_MAX
1819   ///   log2(1) = 0
1820   ///
1821   /// to get around any mathematical concerns resulting from
1822   /// referencing 2 in a space where 2 does no exist.
nearestLogBase2()1823   unsigned nearestLogBase2() const {
1824     // Special case when we have a bitwidth of 1. If VAL is 1, then we
1825     // get 0. If VAL is 0, we get WORDTYPE_MAX which gets truncated to
1826     // UINT32_MAX.
1827     if (BitWidth == 1)
1828       return U.VAL - 1;
1829 
1830     // Handle the zero case.
1831     if (isNullValue())
1832       return UINT32_MAX;
1833 
1834     // The non-zero case is handled by computing:
1835     //
1836     //   nearestLogBase2(x) = logBase2(x) + x[logBase2(x)-1].
1837     //
1838     // where x[i] is referring to the value of the ith bit of x.
1839     unsigned lg = logBase2();
1840     return lg + unsigned((*this)[lg - 1]);
1841   }
1842 
1843   /// \returns the log base 2 of this APInt if its an exact power of two, -1
1844   /// otherwise
exactLogBase2()1845   int32_t exactLogBase2() const {
1846     if (!isPowerOf2())
1847       return -1;
1848     return logBase2();
1849   }
1850 
1851   /// Compute the square root
1852   APInt sqrt() const;
1853 
1854   /// Get the absolute value;
1855   ///
1856   /// If *this is < 0 then return -(*this), otherwise *this;
abs()1857   APInt abs() const {
1858     if (isNegative())
1859       return -(*this);
1860     return *this;
1861   }
1862 
1863   /// \returns the multiplicative inverse for a given modulo.
1864   APInt multiplicativeInverse(const APInt &modulo) const;
1865 
1866   /// @}
1867   /// \name Support for division by constant
1868   /// @{
1869 
1870   /// Calculate the magic number for signed division by a constant.
1871   struct ms;
1872   ms magic() const;
1873 
1874   /// Calculate the magic number for unsigned division by a constant.
1875   struct mu;
1876   mu magicu(unsigned LeadingZeros = 0) const;
1877 
1878   /// @}
1879   /// \name Building-block Operations for APInt and APFloat
1880   /// @{
1881 
1882   // These building block operations operate on a representation of arbitrary
1883   // precision, two's-complement, bignum integer values. They should be
1884   // sufficient to implement APInt and APFloat bignum requirements. Inputs are
1885   // generally a pointer to the base of an array of integer parts, representing
1886   // an unsigned bignum, and a count of how many parts there are.
1887 
1888   /// Sets the least significant part of a bignum to the input value, and zeroes
1889   /// out higher parts.
1890   static void tcSet(WordType *, WordType, unsigned);
1891 
1892   /// Assign one bignum to another.
1893   static void tcAssign(WordType *, const WordType *, unsigned);
1894 
1895   /// Returns true if a bignum is zero, false otherwise.
1896   static bool tcIsZero(const WordType *, unsigned);
1897 
1898   /// Extract the given bit of a bignum; returns 0 or 1.  Zero-based.
1899   static int tcExtractBit(const WordType *, unsigned bit);
1900 
1901   /// Copy the bit vector of width srcBITS from SRC, starting at bit srcLSB, to
1902   /// DST, of dstCOUNT parts, such that the bit srcLSB becomes the least
1903   /// significant bit of DST.  All high bits above srcBITS in DST are
1904   /// zero-filled.
1905   static void tcExtract(WordType *, unsigned dstCount,
1906                         const WordType *, unsigned srcBits,
1907                         unsigned srcLSB);
1908 
1909   /// Set the given bit of a bignum.  Zero-based.
1910   static void tcSetBit(WordType *, unsigned bit);
1911 
1912   /// Clear the given bit of a bignum.  Zero-based.
1913   static void tcClearBit(WordType *, unsigned bit);
1914 
1915   /// Returns the bit number of the least or most significant set bit of a
1916   /// number.  If the input number has no bits set -1U is returned.
1917   static unsigned tcLSB(const WordType *, unsigned n);
1918   static unsigned tcMSB(const WordType *parts, unsigned n);
1919 
1920   /// Negate a bignum in-place.
1921   static void tcNegate(WordType *, unsigned);
1922 
1923   /// DST += RHS + CARRY where CARRY is zero or one.  Returns the carry flag.
1924   static WordType tcAdd(WordType *, const WordType *,
1925                         WordType carry, unsigned);
1926   /// DST += RHS.  Returns the carry flag.
1927   static WordType tcAddPart(WordType *, WordType, unsigned);
1928 
1929   /// DST -= RHS + CARRY where CARRY is zero or one. Returns the carry flag.
1930   static WordType tcSubtract(WordType *, const WordType *,
1931                              WordType carry, unsigned);
1932   /// DST -= RHS.  Returns the carry flag.
1933   static WordType tcSubtractPart(WordType *, WordType, unsigned);
1934 
1935   /// DST += SRC * MULTIPLIER + PART   if add is true
1936   /// DST  = SRC * MULTIPLIER + PART   if add is false
1937   ///
1938   /// Requires 0 <= DSTPARTS <= SRCPARTS + 1.  If DST overlaps SRC they must
1939   /// start at the same point, i.e. DST == SRC.
1940   ///
1941   /// If DSTPARTS == SRC_PARTS + 1 no overflow occurs and zero is returned.
1942   /// Otherwise DST is filled with the least significant DSTPARTS parts of the
1943   /// result, and if all of the omitted higher parts were zero return zero,
1944   /// otherwise overflow occurred and return one.
1945   static int tcMultiplyPart(WordType *dst, const WordType *src,
1946                             WordType multiplier, WordType carry,
1947                             unsigned srcParts, unsigned dstParts,
1948                             bool add);
1949 
1950   /// DST = LHS * RHS, where DST has the same width as the operands and is
1951   /// filled with the least significant parts of the result.  Returns one if
1952   /// overflow occurred, otherwise zero.  DST must be disjoint from both
1953   /// operands.
1954   static int tcMultiply(WordType *, const WordType *, const WordType *,
1955                         unsigned);
1956 
1957   /// DST = LHS * RHS, where DST has width the sum of the widths of the
1958   /// operands. No overflow occurs. DST must be disjoint from both operands.
1959   static void tcFullMultiply(WordType *, const WordType *,
1960                              const WordType *, unsigned, unsigned);
1961 
1962   /// If RHS is zero LHS and REMAINDER are left unchanged, return one.
1963   /// Otherwise set LHS to LHS / RHS with the fractional part discarded, set
1964   /// REMAINDER to the remainder, return zero.  i.e.
1965   ///
1966   ///  OLD_LHS = RHS * LHS + REMAINDER
1967   ///
1968   /// SCRATCH is a bignum of the same size as the operands and result for use by
1969   /// the routine; its contents need not be initialized and are destroyed.  LHS,
1970   /// REMAINDER and SCRATCH must be distinct.
1971   static int tcDivide(WordType *lhs, const WordType *rhs,
1972                       WordType *remainder, WordType *scratch,
1973                       unsigned parts);
1974 
1975   /// Shift a bignum left Count bits. Shifted in bits are zero. There are no
1976   /// restrictions on Count.
1977   static void tcShiftLeft(WordType *, unsigned Words, unsigned Count);
1978 
1979   /// Shift a bignum right Count bits.  Shifted in bits are zero.  There are no
1980   /// restrictions on Count.
1981   static void tcShiftRight(WordType *, unsigned Words, unsigned Count);
1982 
1983   /// The obvious AND, OR and XOR and complement operations.
1984   static void tcAnd(WordType *, const WordType *, unsigned);
1985   static void tcOr(WordType *, const WordType *, unsigned);
1986   static void tcXor(WordType *, const WordType *, unsigned);
1987   static void tcComplement(WordType *, unsigned);
1988 
1989   /// Comparison (unsigned) of two bignums.
1990   static int tcCompare(const WordType *, const WordType *, unsigned);
1991 
1992   /// Increment a bignum in-place.  Return the carry flag.
tcIncrement(WordType * dst,unsigned parts)1993   static WordType tcIncrement(WordType *dst, unsigned parts) {
1994     return tcAddPart(dst, 1, parts);
1995   }
1996 
1997   /// Decrement a bignum in-place.  Return the borrow flag.
tcDecrement(WordType * dst,unsigned parts)1998   static WordType tcDecrement(WordType *dst, unsigned parts) {
1999     return tcSubtractPart(dst, 1, parts);
2000   }
2001 
2002   /// Set the least significant BITS and clear the rest.
2003   static void tcSetLeastSignificantBits(WordType *, unsigned, unsigned bits);
2004 
2005   /// debug method
2006   void dump() const;
2007 
2008   /// @}
2009 };
2010 
2011 /// Magic data for optimising signed division by a constant.
2012 struct APInt::ms {
2013   APInt m;    ///< magic number
2014   unsigned s; ///< shift amount
2015 };
2016 
2017 /// Magic data for optimising unsigned division by a constant.
2018 struct APInt::mu {
2019   APInt m;    ///< magic number
2020   bool a;     ///< add indicator
2021   unsigned s; ///< shift amount
2022 };
2023 
2024 inline bool operator==(uint64_t V1, const APInt &V2) { return V2 == V1; }
2025 
2026 inline bool operator!=(uint64_t V1, const APInt &V2) { return V2 != V1; }
2027 
2028 /// Unary bitwise complement operator.
2029 ///
2030 /// \returns an APInt that is the bitwise complement of \p v.
2031 inline APInt operator~(APInt v) {
2032   v.flipAllBits();
2033   return v;
2034 }
2035 
2036 inline APInt operator&(APInt a, const APInt &b) {
2037   a &= b;
2038   return a;
2039 }
2040 
2041 inline APInt operator&(const APInt &a, APInt &&b) {
2042   b &= a;
2043   return std::move(b);
2044 }
2045 
2046 inline APInt operator&(APInt a, uint64_t RHS) {
2047   a &= RHS;
2048   return a;
2049 }
2050 
2051 inline APInt operator&(uint64_t LHS, APInt b) {
2052   b &= LHS;
2053   return b;
2054 }
2055 
2056 inline APInt operator|(APInt a, const APInt &b) {
2057   a |= b;
2058   return a;
2059 }
2060 
2061 inline APInt operator|(const APInt &a, APInt &&b) {
2062   b |= a;
2063   return std::move(b);
2064 }
2065 
2066 inline APInt operator|(APInt a, uint64_t RHS) {
2067   a |= RHS;
2068   return a;
2069 }
2070 
2071 inline APInt operator|(uint64_t LHS, APInt b) {
2072   b |= LHS;
2073   return b;
2074 }
2075 
2076 inline APInt operator^(APInt a, const APInt &b) {
2077   a ^= b;
2078   return a;
2079 }
2080 
2081 inline APInt operator^(const APInt &a, APInt &&b) {
2082   b ^= a;
2083   return std::move(b);
2084 }
2085 
2086 inline APInt operator^(APInt a, uint64_t RHS) {
2087   a ^= RHS;
2088   return a;
2089 }
2090 
2091 inline APInt operator^(uint64_t LHS, APInt b) {
2092   b ^= LHS;
2093   return b;
2094 }
2095 
2096 inline raw_ostream &operator<<(raw_ostream &OS, const APInt &I) {
2097   I.print(OS, true);
2098   return OS;
2099 }
2100 
2101 inline APInt operator-(APInt v) {
2102   v.negate();
2103   return v;
2104 }
2105 
2106 inline APInt operator+(APInt a, const APInt &b) {
2107   a += b;
2108   return a;
2109 }
2110 
2111 inline APInt operator+(const APInt &a, APInt &&b) {
2112   b += a;
2113   return std::move(b);
2114 }
2115 
2116 inline APInt operator+(APInt a, uint64_t RHS) {
2117   a += RHS;
2118   return a;
2119 }
2120 
2121 inline APInt operator+(uint64_t LHS, APInt b) {
2122   b += LHS;
2123   return b;
2124 }
2125 
2126 inline APInt operator-(APInt a, const APInt &b) {
2127   a -= b;
2128   return a;
2129 }
2130 
2131 inline APInt operator-(const APInt &a, APInt &&b) {
2132   b.negate();
2133   b += a;
2134   return std::move(b);
2135 }
2136 
2137 inline APInt operator-(APInt a, uint64_t RHS) {
2138   a -= RHS;
2139   return a;
2140 }
2141 
2142 inline APInt operator-(uint64_t LHS, APInt b) {
2143   b.negate();
2144   b += LHS;
2145   return b;
2146 }
2147 
2148 inline APInt operator*(APInt a, uint64_t RHS) {
2149   a *= RHS;
2150   return a;
2151 }
2152 
2153 inline APInt operator*(uint64_t LHS, APInt b) {
2154   b *= LHS;
2155   return b;
2156 }
2157 
2158 
2159 namespace APIntOps {
2160 
2161 /// Determine the smaller of two APInts considered to be signed.
smin(const APInt & A,const APInt & B)2162 inline const APInt &smin(const APInt &A, const APInt &B) {
2163   return A.slt(B) ? A : B;
2164 }
2165 
2166 /// Determine the larger of two APInts considered to be signed.
smax(const APInt & A,const APInt & B)2167 inline const APInt &smax(const APInt &A, const APInt &B) {
2168   return A.sgt(B) ? A : B;
2169 }
2170 
2171 /// Determine the smaller of two APInts considered to be signed.
umin(const APInt & A,const APInt & B)2172 inline const APInt &umin(const APInt &A, const APInt &B) {
2173   return A.ult(B) ? A : B;
2174 }
2175 
2176 /// Determine the larger of two APInts considered to be unsigned.
umax(const APInt & A,const APInt & B)2177 inline const APInt &umax(const APInt &A, const APInt &B) {
2178   return A.ugt(B) ? A : B;
2179 }
2180 
2181 /// Compute GCD of two unsigned APInt values.
2182 ///
2183 /// This function returns the greatest common divisor of the two APInt values
2184 /// using Stein's algorithm.
2185 ///
2186 /// \returns the greatest common divisor of A and B.
2187 APInt GreatestCommonDivisor(APInt A, APInt B);
2188 
2189 /// Converts the given APInt to a double value.
2190 ///
2191 /// Treats the APInt as an unsigned value for conversion purposes.
RoundAPIntToDouble(const APInt & APIVal)2192 inline double RoundAPIntToDouble(const APInt &APIVal) {
2193   return APIVal.roundToDouble();
2194 }
2195 
2196 /// Converts the given APInt to a double value.
2197 ///
2198 /// Treats the APInt as a signed value for conversion purposes.
RoundSignedAPIntToDouble(const APInt & APIVal)2199 inline double RoundSignedAPIntToDouble(const APInt &APIVal) {
2200   return APIVal.signedRoundToDouble();
2201 }
2202 
2203 /// Converts the given APInt to a float vlalue.
RoundAPIntToFloat(const APInt & APIVal)2204 inline float RoundAPIntToFloat(const APInt &APIVal) {
2205   return float(RoundAPIntToDouble(APIVal));
2206 }
2207 
2208 /// Converts the given APInt to a float value.
2209 ///
2210 /// Treats the APInt as a signed value for conversion purposes.
RoundSignedAPIntToFloat(const APInt & APIVal)2211 inline float RoundSignedAPIntToFloat(const APInt &APIVal) {
2212   return float(APIVal.signedRoundToDouble());
2213 }
2214 
2215 /// Converts the given double value into a APInt.
2216 ///
2217 /// This function convert a double value to an APInt value.
2218 APInt RoundDoubleToAPInt(double Double, unsigned width);
2219 
2220 /// Converts a float value into a APInt.
2221 ///
2222 /// Converts a float value into an APInt value.
RoundFloatToAPInt(float Float,unsigned width)2223 inline APInt RoundFloatToAPInt(float Float, unsigned width) {
2224   return RoundDoubleToAPInt(double(Float), width);
2225 }
2226 
2227 /// Return A unsign-divided by B, rounded by the given rounding mode.
2228 APInt RoundingUDiv(const APInt &A, const APInt &B, APInt::Rounding RM);
2229 
2230 /// Return A sign-divided by B, rounded by the given rounding mode.
2231 APInt RoundingSDiv(const APInt &A, const APInt &B, APInt::Rounding RM);
2232 
2233 /// Let q(n) = An^2 + Bn + C, and BW = bit width of the value range
2234 /// (e.g. 32 for i32).
2235 /// This function finds the smallest number n, such that
2236 /// (a) n >= 0 and q(n) = 0, or
2237 /// (b) n >= 1 and q(n-1) and q(n), when evaluated in the set of all
2238 ///     integers, belong to two different intervals [Rk, Rk+R),
2239 ///     where R = 2^BW, and k is an integer.
2240 /// The idea here is to find when q(n) "overflows" 2^BW, while at the
2241 /// same time "allowing" subtraction. In unsigned modulo arithmetic a
2242 /// subtraction (treated as addition of negated numbers) would always
2243 /// count as an overflow, but here we want to allow values to decrease
2244 /// and increase as long as they are within the same interval.
2245 /// Specifically, adding of two negative numbers should not cause an
2246 /// overflow (as long as the magnitude does not exceed the bit width).
2247 /// On the other hand, given a positive number, adding a negative
2248 /// number to it can give a negative result, which would cause the
2249 /// value to go from [-2^BW, 0) to [0, 2^BW). In that sense, zero is
2250 /// treated as a special case of an overflow.
2251 ///
2252 /// This function returns None if after finding k that minimizes the
2253 /// positive solution to q(n) = kR, both solutions are contained between
2254 /// two consecutive integers.
2255 ///
2256 /// There are cases where q(n) > T, and q(n+1) < T (assuming evaluation
2257 /// in arithmetic modulo 2^BW, and treating the values as signed) by the
2258 /// virtue of *signed* overflow. This function will *not* find such an n,
2259 /// however it may find a value of n satisfying the inequalities due to
2260 /// an *unsigned* overflow (if the values are treated as unsigned).
2261 /// To find a solution for a signed overflow, treat it as a problem of
2262 /// finding an unsigned overflow with a range with of BW-1.
2263 ///
2264 /// The returned value may have a different bit width from the input
2265 /// coefficients.
2266 Optional<APInt> SolveQuadraticEquationWrap(APInt A, APInt B, APInt C,
2267                                            unsigned RangeWidth);
2268 
2269 /// Compare two values, and if they are different, return the position of the
2270 /// most significant bit that is different in the values.
2271 Optional<unsigned> GetMostSignificantDifferentBit(const APInt &A,
2272                                                   const APInt &B);
2273 
2274 } // End of APIntOps namespace
2275 
2276 // See friend declaration above. This additional declaration is required in
2277 // order to compile LLVM with IBM xlC compiler.
2278 hash_code hash_value(const APInt &Arg);
2279 
2280 /// StoreIntToMemory - Fills the StoreBytes bytes of memory starting from Dst
2281 /// with the integer held in IntVal.
2282 void StoreIntToMemory(const APInt &IntVal, uint8_t *Dst, unsigned StoreBytes);
2283 
2284 /// LoadIntFromMemory - Loads the integer stored in the LoadBytes bytes starting
2285 /// from Src into IntVal, which is assumed to be wide enough and to hold zero.
2286 void LoadIntFromMemory(APInt &IntVal, uint8_t *Src, unsigned LoadBytes);
2287 
2288 } // namespace llvm
2289 
2290 #endif
2291