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