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