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  /// Array-indexing support.
1109  ///
1110  /// \returns the bit value at bitPosition
1111  bool operator[](unsigned bitPosition) const {
1112  assert(bitPosition < getBitWidth() && "Bit position out of bounds!");
1113  return (maskBit(bitPosition) & getWord(bitPosition)) != 0;
1114  }
1115 
1116  /// @}
1117  /// \name Comparison Operators
1118  /// @{
1119 
1120  /// Equality operator.
1121  ///
1122  /// Compares this APInt with RHS for the validity of the equality
1123  /// relationship.
1124  bool operator==(const APInt &RHS) const {
1125  assert(BitWidth == RHS.BitWidth && "Comparison requires equal bit widths");
1126  if (isSingleWord())
1127  return U.VAL == RHS.U.VAL;
1128  return EqualSlowCase(RHS);
1129  }
1130 
1131  /// Equality operator.
1132  ///
1133  /// Compares this APInt with a uint64_t for the validity of the equality
1134  /// relationship.
1135  ///
1136  /// \returns true if *this == Val
1137  bool operator==(uint64_t Val) const {
1138  return (isSingleWord() || getActiveBits() <= 64) && getZExtValue() == Val;
1139  }
1140 
1141  /// Equality comparison.
1142  ///
1143  /// Compares this APInt with RHS for the validity of the equality
1144  /// relationship.
1145  ///
1146  /// \returns true if *this == Val
1147  bool eq(const APInt &RHS) const { return (*this) == RHS; }
1148 
1149  /// Inequality operator.
1150  ///
1151  /// Compares this APInt with RHS for the validity of the inequality
1152  /// relationship.
1153  ///
1154  /// \returns true if *this != Val
1155  bool operator!=(const APInt &RHS) const { return !((*this) == RHS); }
1156 
1157  /// Inequality operator.
1158  ///
1159  /// Compares this APInt with a uint64_t for the validity of the inequality
1160  /// relationship.
1161  ///
1162  /// \returns true if *this != Val
1163  bool operator!=(uint64_t Val) const { return !((*this) == Val); }
1164 
1165  /// Inequality comparison
1166  ///
1167  /// Compares this APInt with RHS for the validity of the inequality
1168  /// relationship.
1169  ///
1170  /// \returns true if *this != Val
1171  bool ne(const APInt &RHS) const { return !((*this) == RHS); }
1172 
1173  /// Unsigned less than comparison
1174  ///
1175  /// Regards both *this and RHS as unsigned quantities and compares them for
1176  /// the validity of the less-than relationship.
1177  ///
1178  /// \returns true if *this < RHS when both are considered unsigned.
1179  bool ult(const APInt &RHS) const { return compare(RHS) < 0; }
1180 
1181  /// Unsigned less than comparison
1182  ///
1183  /// Regards both *this as an unsigned quantity and compares it with RHS for
1184  /// the validity of the less-than relationship.
1185  ///
1186  /// \returns true if *this < RHS when considered unsigned.
1187  bool ult(uint64_t RHS) const {
1188  // Only need to check active bits if not a single word.
1189  return (isSingleWord() || getActiveBits() <= 64) && getZExtValue() < RHS;
1190  }
1191 
1192  /// Signed less than comparison
1193  ///
1194  /// Regards both *this and RHS as signed quantities and compares them for
1195  /// validity of the less-than relationship.
1196  ///
1197  /// \returns true if *this < RHS when both are considered signed.
1198  bool slt(const APInt &RHS) const { return compareSigned(RHS) < 0; }
1199 
1200  /// Signed less than comparison
1201  ///
1202  /// Regards both *this as a signed quantity and compares it with RHS for
1203  /// the validity of the less-than relationship.
1204  ///
1205  /// \returns true if *this < RHS when considered signed.
1206  bool slt(int64_t RHS) const {
1207  return (!isSingleWord() && getMinSignedBits() > 64) ? isNegative()
1208  : getSExtValue() < RHS;
1209  }
1210 
1211  /// Unsigned less or equal comparison
1212  ///
1213  /// Regards both *this and RHS as unsigned quantities and compares them for
1214  /// validity of the less-or-equal relationship.
1215  ///
1216  /// \returns true if *this <= RHS when both are considered unsigned.
1217  bool ule(const APInt &RHS) const { return compare(RHS) <= 0; }
1218 
1219  /// Unsigned less or equal comparison
1220  ///
1221  /// Regards both *this as an unsigned quantity and compares it with RHS for
1222  /// the validity of the less-or-equal relationship.
1223  ///
1224  /// \returns true if *this <= RHS when considered unsigned.
1225  bool ule(uint64_t RHS) const { return !ugt(RHS); }
1226 
1227  /// Signed less or equal comparison
1228  ///
1229  /// Regards both *this and RHS as signed quantities and compares them for
1230  /// validity of the less-or-equal relationship.
1231  ///
1232  /// \returns true if *this <= RHS when both are considered signed.
1233  bool sle(const APInt &RHS) const { return compareSigned(RHS) <= 0; }
1234 
1235  /// Signed less or equal comparison
1236  ///
1237  /// Regards both *this as a signed quantity and compares it with RHS for the
1238  /// validity of the less-or-equal relationship.
1239  ///
1240  /// \returns true if *this <= RHS when considered signed.
1241  bool sle(uint64_t RHS) const { return !sgt(RHS); }
1242 
1243  /// Unsigned greather than comparison
1244  ///
1245  /// Regards both *this and RHS as unsigned quantities and compares them for
1246  /// the validity of the greater-than relationship.
1247  ///
1248  /// \returns true if *this > RHS when both are considered unsigned.
1249  bool ugt(const APInt &RHS) const { return !ule(RHS); }
1250 
1251  /// Unsigned greater than comparison
1252  ///
1253  /// Regards both *this as an unsigned quantity and compares it with RHS for
1254  /// the validity of the greater-than relationship.
1255  ///
1256  /// \returns true if *this > RHS when considered unsigned.
1257  bool ugt(uint64_t RHS) const {
1258  // Only need to check active bits if not a single word.
1259  return (!isSingleWord() && getActiveBits() > 64) || getZExtValue() > RHS;
1260  }
1261 
1262  /// Signed greather than comparison
1263  ///
1264  /// Regards both *this and RHS as signed quantities and compares them for the
1265  /// validity of the greater-than relationship.
1266  ///
1267  /// \returns true if *this > RHS when both are considered signed.
1268  bool sgt(const APInt &RHS) const { return !sle(RHS); }
1269 
1270  /// Signed greater than comparison
1271  ///
1272  /// Regards both *this as a signed quantity and compares it with RHS for
1273  /// the validity of the greater-than relationship.
1274  ///
1275  /// \returns true if *this > RHS when considered signed.
1276  bool sgt(int64_t RHS) const {
1277  return (!isSingleWord() && getMinSignedBits() > 64) ? !isNegative()
1278  : getSExtValue() > RHS;
1279  }
1280 
1281  /// Unsigned greater or equal comparison
1282  ///
1283  /// Regards both *this and RHS as unsigned quantities and compares them for
1284  /// validity of the greater-or-equal relationship.
1285  ///
1286  /// \returns true if *this >= RHS when both are considered unsigned.
1287  bool uge(const APInt &RHS) const { return !ult(RHS); }
1288 
1289  /// Unsigned greater or equal comparison
1290  ///
1291  /// Regards both *this as an unsigned quantity and compares it with RHS for
1292  /// the validity of the greater-or-equal relationship.
1293  ///
1294  /// \returns true if *this >= RHS when considered unsigned.
1295  bool uge(uint64_t RHS) const { return !ult(RHS); }
1296 
1297  /// Signed greater or equal comparison
1298  ///
1299  /// Regards both *this and RHS as signed quantities and compares them for
1300  /// validity of the greater-or-equal relationship.
1301  ///
1302  /// \returns true if *this >= RHS when both are considered signed.
1303  bool sge(const APInt &RHS) const { return !slt(RHS); }
1304 
1305  /// Signed greater or equal comparison
1306  ///
1307  /// Regards both *this as a signed quantity and compares it with RHS for
1308  /// the validity of the greater-or-equal relationship.
1309  ///
1310  /// \returns true if *this >= RHS when considered signed.
1311  bool sge(int64_t RHS) const { return !slt(RHS); }
1312 
1313  /// This operation tests if there are any pairs of corresponding bits
1314  /// between this APInt and RHS that are both set.
1315  bool intersects(const APInt &RHS) const {
1316  assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1317  if (isSingleWord())
1318  return (U.VAL & RHS.U.VAL) != 0;
1319  return intersectsSlowCase(RHS);
1320  }
1321 
1322  /// This operation checks that all bits set in this APInt are also set in RHS.
1323  bool isSubsetOf(const APInt &RHS) const {
1324  assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1325  if (isSingleWord())
1326  return (U.VAL & ~RHS.U.VAL) == 0;
1327  return isSubsetOfSlowCase(RHS);
1328  }
1329 
1330  /// @}
1331  /// \name Resizing Operators
1332  /// @{
1333 
1334  /// Truncate to new width.
1335  ///
1336  /// Truncate the APInt to a specified width. It is an error to specify a width
1337  /// that is greater than or equal to the current width.
1338  APInt trunc(unsigned width) const;
1339 
1340  /// Sign extend to a new width.
1341  ///
1342  /// This operation sign extends the APInt to a new width. If the high order
1343  /// bit is set, the fill on the left will be done with 1 bits, otherwise zero.
1344  /// It is an error to specify a width that is less than or equal to the
1345  /// current width.
1346  APInt sext(unsigned width) const;
1347 
1348  /// Zero extend to a new width.
1349  ///
1350  /// This operation zero extends the APInt to a new width. The high order bits
1351  /// are filled with 0 bits. It is an error to specify a width that is less
1352  /// than or equal to the current width.
1353  APInt zext(unsigned width) const;
1354 
1355  /// Sign extend or truncate to width
1356  ///
1357  /// Make this APInt have the bit width given by \p width. The value is sign
1358  /// extended, truncated, or left alone to make it that width.
1359  APInt sextOrTrunc(unsigned width) const;
1360 
1361  /// Zero extend or truncate to width
1362  ///
1363  /// Make this APInt have the bit width given by \p width. The value is zero
1364  /// extended, truncated, or left alone to make it that width.
1365  APInt zextOrTrunc(unsigned width) const;
1366 
1367  /// Sign extend or truncate to width
1368  ///
1369  /// Make this APInt have the bit width given by \p width. The value is sign
1370  /// extended, or left alone to make it that width.
1371  APInt sextOrSelf(unsigned width) const;
1372 
1373  /// Zero extend or truncate to width
1374  ///
1375  /// Make this APInt have the bit width given by \p width. The value is zero
1376  /// extended, or left alone to make it that width.
1377  APInt zextOrSelf(unsigned width) const;
1378 
1379  /// @}
1380  /// \name Bit Manipulation Operators
1381  /// @{
1382 
1383  /// Set every bit to 1.
1384  void setAllBits() {
1385  if (isSingleWord())
1386  U.VAL = WORDTYPE_MAX;
1387  else
1388  // Set all the bits in all the words.
1389  memset(U.pVal, -1, getNumWords() * APINT_WORD_SIZE);
1390  // Clear the unused ones
1391  clearUnusedBits();
1392  }
1393 
1394  /// Set a given bit to 1.
1395  ///
1396  /// Set the given bit to 1 whose position is given as "bitPosition".
1397  void setBit(unsigned BitPosition) {
1398  assert(BitPosition <= BitWidth && "BitPosition out of range");
1399  WordType Mask = maskBit(BitPosition);
1400  if (isSingleWord())
1401  U.VAL |= Mask;
1402  else
1403  U.pVal[whichWord(BitPosition)] |= Mask;
1404  }
1405 
1406  /// Set the sign bit to 1.
1407  void setSignBit() {
1408  setBit(BitWidth - 1);
1409  }
1410 
1411  /// Set the bits from loBit (inclusive) to hiBit (exclusive) to 1.
1412  void setBits(unsigned loBit, unsigned hiBit) {
1413  assert(hiBit <= BitWidth && "hiBit out of range");
1414  assert(loBit <= BitWidth && "loBit out of range");
1415  assert(loBit <= hiBit && "loBit greater than hiBit");
1416  if (loBit == hiBit)
1417  return;
1418  if (loBit < APINT_BITS_PER_WORD && hiBit <= APINT_BITS_PER_WORD) {
1419  uint64_t mask = WORDTYPE_MAX >> (APINT_BITS_PER_WORD - (hiBit - loBit));
1420  mask <<= loBit;
1421  if (isSingleWord())
1422  U.VAL |= mask;
1423  else
1424  U.pVal[0] |= mask;
1425  } else {
1426  setBitsSlowCase(loBit, hiBit);
1427  }
1428  }
1429 
1430  /// Set the top bits starting from loBit.
1431  void setBitsFrom(unsigned loBit) {
1432  return setBits(loBit, BitWidth);
1433  }
1434 
1435  /// Set the bottom loBits bits.
1436  void setLowBits(unsigned loBits) {
1437  return setBits(0, loBits);
1438  }
1439 
1440  /// Set the top hiBits bits.
1441  void setHighBits(unsigned hiBits) {
1442  return setBits(BitWidth - hiBits, BitWidth);
1443  }
1444 
1445  /// Set every bit to 0.
1446  void clearAllBits() {
1447  if (isSingleWord())
1448  U.VAL = 0;
1449  else
1450  memset(U.pVal, 0, getNumWords() * APINT_WORD_SIZE);
1451  }
1452 
1453  /// Set a given bit to 0.
1454  ///
1455  /// Set the given bit to 0 whose position is given as "bitPosition".
1456  void clearBit(unsigned BitPosition) {
1457  assert(BitPosition <= BitWidth && "BitPosition out of range");
1458  WordType Mask = ~maskBit(BitPosition);
1459  if (isSingleWord())
1460  U.VAL &= Mask;
1461  else
1462  U.pVal[whichWord(BitPosition)] &= Mask;
1463  }
1464 
1465  /// Set the sign bit to 0.
1466  void clearSignBit() {
1467  clearBit(BitWidth - 1);
1468  }
1469 
1470  /// Toggle every bit to its opposite value.
1471  void flipAllBits() {
1472  if (isSingleWord()) {
1473  U.VAL ^= WORDTYPE_MAX;
1474  clearUnusedBits();
1475  } else {
1476  flipAllBitsSlowCase();
1477  }
1478  }
1479 
1480  /// Toggles a given bit to its opposite value.
1481  ///
1482  /// Toggle a given bit to its opposite value whose position is given
1483  /// as "bitPosition".
1484  void flipBit(unsigned bitPosition);
1485 
1486  /// Negate this APInt in place.
1487  void negate() {
1488  flipAllBits();
1489  ++(*this);
1490  }
1491 
1492  /// Insert the bits from a smaller APInt starting at bitPosition.
1493  void insertBits(const APInt &SubBits, unsigned bitPosition);
1494 
1495  /// Return an APInt with the extracted bits [bitPosition,bitPosition+numBits).
1496  APInt extractBits(unsigned numBits, unsigned bitPosition) const;
1497 
1498  /// @}
1499  /// \name Value Characterization Functions
1500  /// @{
1501 
1502  /// Return the number of bits in the APInt.
1503  unsigned getBitWidth() const { return BitWidth; }
1504 
1505  /// Get the number of words.
1506  ///
1507  /// Here one word's bitwidth equals to that of uint64_t.
1508  ///
1509  /// \returns the number of words to hold the integer value of this APInt.
1510  unsigned getNumWords() const { return getNumWords(BitWidth); }
1511 
1512  /// Get the number of words.
1513  ///
1514  /// *NOTE* Here one word's bitwidth equals to that of uint64_t.
1515  ///
1516  /// \returns the number of words to hold the integer value with a given bit
1517  /// width.
1518  static unsigned getNumWords(unsigned BitWidth) {
1519  return ((uint64_t)BitWidth + APINT_BITS_PER_WORD - 1) / APINT_BITS_PER_WORD;
1520  }
1521 
1522  /// Compute the number of active bits in the value
1523  ///
1524  /// This function returns the number of active bits which is defined as the
1525  /// bit width minus the number of leading zeros. This is used in several
1526  /// computations to see how "wide" the value is.
1527  unsigned getActiveBits() const { return BitWidth - countLeadingZeros(); }
1528 
1529  /// Compute the number of active words in the value of this APInt.
1530  ///
1531  /// This is used in conjunction with getActiveData to extract the raw value of
1532  /// the APInt.
1533  unsigned getActiveWords() const {
1534  unsigned numActiveBits = getActiveBits();
1535  return numActiveBits ? whichWord(numActiveBits - 1) + 1 : 1;
1536  }
1537 
1538  /// Get the minimum bit size for this signed APInt
1539  ///
1540  /// Computes the minimum bit width for this APInt while considering it to be a
1541  /// signed (and probably negative) value. If the value is not negative, this
1542  /// function returns the same value as getActiveBits()+1. Otherwise, it
1543  /// returns the smallest bit width that will retain the negative value. For
1544  /// example, -1 can be written as 0b1 or 0xFFFFFFFFFF. 0b1 is shorter and so
1545  /// for -1, this function will always return 1.
1546  unsigned getMinSignedBits() const {
1547  if (isNegative())
1548  return BitWidth - countLeadingOnes() + 1;
1549  return getActiveBits() + 1;
1550  }
1551 
1552  /// Get zero extended value
1553  ///
1554  /// This method attempts to return the value of this APInt as a zero extended
1555  /// uint64_t. The bitwidth must be <= 64 or the value must fit within a
1556  /// uint64_t. Otherwise an assertion will result.
1557  uint64_t getZExtValue() const {
1558  if (isSingleWord())
1559  return U.VAL;
1560  assert(getActiveBits() <= 64 && "Too many bits for uint64_t");
1561  return U.pVal[0];
1562  }
1563 
1564  /// Get sign extended value
1565  ///
1566  /// This method attempts to return the value of this APInt as a sign extended
1567  /// int64_t. The bit width must be <= 64 or the value must fit within an
1568  /// int64_t. Otherwise an assertion will result.
1569  int64_t getSExtValue() const {
1570  if (isSingleWord())
1571  return SignExtend64(U.VAL, BitWidth);
1572  assert(getMinSignedBits() <= 64 && "Too many bits for int64_t");
1573  return int64_t(U.pVal[0]);
1574  }
1575 
1576  /// Get bits required for string value.
1577  ///
1578  /// This method determines how many bits are required to hold the APInt
1579  /// equivalent of the string given by \p str.
1580  static unsigned getBitsNeeded(StringRef str, uint8_t radix);
1581 
1582  /// The APInt version of the countLeadingZeros functions in
1583  /// MathExtras.h.
1584  ///
1585  /// It counts the number of zeros from the most significant bit to the first
1586  /// one bit.
1587  ///
1588  /// \returns BitWidth if the value is zero, otherwise returns the number of
1589  /// zeros from the most significant bit to the first one bits.
1590  unsigned countLeadingZeros() const {
1591  if (isSingleWord()) {
1592  unsigned unusedBits = APINT_BITS_PER_WORD - BitWidth;
1593  return llvm::countLeadingZeros(U.VAL) - unusedBits;
1594  }
1595  return countLeadingZerosSlowCase();
1596  }
1597 
1598  /// Count the number of leading one bits.
1599  ///
1600  /// This function is an APInt version of the countLeadingOnes
1601  /// functions in MathExtras.h. It counts the number of ones from the most
1602  /// significant bit to the first zero bit.
1603  ///
1604  /// \returns 0 if the high order bit is not set, otherwise returns the number
1605  /// of 1 bits from the most significant to the least
1606  unsigned countLeadingOnes() const {
1607  if (isSingleWord())
1608  return llvm::countLeadingOnes(U.VAL << (APINT_BITS_PER_WORD - BitWidth));
1609  return countLeadingOnesSlowCase();
1610  }
1611 
1612  /// Computes the number of leading bits of this APInt that are equal to its
1613  /// sign bit.
1614  unsigned getNumSignBits() const {
1615  return isNegative() ? countLeadingOnes() : countLeadingZeros();
1616  }
1617 
1618  /// Count the number of trailing zero bits.
1619  ///
1620  /// This function is an APInt version of the countTrailingZeros
1621  /// functions in MathExtras.h. It counts the number of zeros from the least
1622  /// significant bit to the first set bit.
1623  ///
1624  /// \returns BitWidth if the value is zero, otherwise returns the number of
1625  /// zeros from the least significant bit to the first one bit.
1626  unsigned countTrailingZeros() const {
1627  if (isSingleWord())
1628  return std::min(unsigned(llvm::countTrailingZeros(U.VAL)), BitWidth);
1629  return countTrailingZerosSlowCase();
1630  }
1631 
1632  /// Count the number of trailing one bits.
1633  ///
1634  /// This function is an APInt version of the countTrailingOnes
1635  /// functions in MathExtras.h. It counts the number of ones from the least
1636  /// significant bit to the first zero bit.
1637  ///
1638  /// \returns BitWidth if the value is all ones, otherwise returns the number
1639  /// of ones from the least significant bit to the first zero bit.
1640  unsigned countTrailingOnes() const {
1641  if (isSingleWord())
1642  return llvm::countTrailingOnes(U.VAL);
1643  return countTrailingOnesSlowCase();
1644  }
1645 
1646  /// Count the number of bits set.
1647  ///
1648  /// This function is an APInt version of the countPopulation functions
1649  /// in MathExtras.h. It counts the number of 1 bits in the APInt value.
1650  ///
1651  /// \returns 0 if the value is zero, otherwise returns the number of set bits.
1652  unsigned countPopulation() const {
1653  if (isSingleWord())
1654  return llvm::countPopulation(U.VAL);
1655  return countPopulationSlowCase();
1656  }
1657 
1658  /// @}
1659  /// \name Conversion Functions
1660  /// @{
1661  void print(raw_ostream &OS, bool isSigned) const;
1662 
1663  /// Converts an APInt to a string and append it to Str. Str is commonly a
1664  /// SmallString.
1665  void toString(SmallVectorImpl<char> &Str, unsigned Radix, bool Signed,
1666  bool formatAsCLiteral = false) const;
1667 
1668  /// Considers the APInt to be unsigned and converts it into a string in the
1669  /// radix given. The radix can be 2, 8, 10 16, or 36.
1670  void toStringUnsigned(SmallVectorImpl<char> &Str, unsigned Radix = 10) const {
1671  toString(Str, Radix, false, false);
1672  }
1673 
1674  /// Considers the APInt to be signed and converts it into a string in the
1675  /// radix given. The radix can be 2, 8, 10, 16, or 36.
1676  void toStringSigned(SmallVectorImpl<char> &Str, unsigned Radix = 10) const {
1677  toString(Str, Radix, true, false);
1678  }
1679 
1680  /// Return the APInt as a std::string.
1681  ///
1682  /// Note that this is an inefficient method. It is better to pass in a
1683  /// SmallVector/SmallString to the methods above to avoid thrashing the heap
1684  /// for the string.
1685  std::string toString(unsigned Radix, bool Signed) const;
1686 
1687  /// \returns a byte-swapped representation of this APInt Value.
1688  APInt byteSwap() const;
1689 
1690  /// \returns the value with the bit representation reversed of this APInt
1691  /// Value.
1692  APInt reverseBits() const;
1693 
1694  /// Converts this APInt to a double value.
1695  double roundToDouble(bool isSigned) const;
1696 
1697  /// Converts this unsigned APInt to a double value.
1698  double roundToDouble() const { return roundToDouble(false); }
1699 
1700  /// Converts this signed APInt to a double value.
1701  double signedRoundToDouble() const { return roundToDouble(true); }
1702 
1703  /// Converts APInt bits to a double
1704  ///
1705  /// The conversion does not do a translation from integer to double, it just
1706  /// re-interprets the bits as a double. Note that it is valid to do this on
1707  /// any bit width. Exactly 64 bits will be translated.
1708  double bitsToDouble() const {
1709  return BitsToDouble(getWord(0));
1710  }
1711 
1712  /// Converts APInt bits to a double
1713  ///
1714  /// The conversion does not do a translation from integer to float, it just
1715  /// re-interprets the bits as a float. Note that it is valid to do this on
1716  /// any bit width. Exactly 32 bits will be translated.
1717  float bitsToFloat() const {
1718  return BitsToFloat(getWord(0));
1719  }
1720 
1721  /// Converts a double to APInt bits.
1722  ///
1723  /// The conversion does not do a translation from double to integer, it just
1724  /// re-interprets the bits of the double.
1725  static APInt doubleToBits(double V) {
1726  return APInt(sizeof(double) * CHAR_BIT, DoubleToBits(V));
1727  }
1728 
1729  /// Converts a float to APInt bits.
1730  ///
1731  /// The conversion does not do a translation from float to integer, it just
1732  /// re-interprets the bits of the float.
1733  static APInt floatToBits(float V) {
1734  return APInt(sizeof(float) * CHAR_BIT, FloatToBits(V));
1735  }
1736 
1737  /// @}
1738  /// \name Mathematics Operations
1739  /// @{
1740 
1741  /// \returns the floor log base 2 of this APInt.
1742  unsigned logBase2() const { return getActiveBits() - 1; }
1743 
1744  /// \returns the ceil log base 2 of this APInt.
1745  unsigned ceilLogBase2() const {
1746  APInt temp(*this);
1747  --temp;
1748  return temp.getActiveBits();
1749  }
1750 
1751  /// \returns the nearest log base 2 of this APInt. Ties round up.
1752  ///
1753  /// NOTE: When we have a BitWidth of 1, we define:
1754  ///
1755  /// log2(0) = UINT32_MAX
1756  /// log2(1) = 0
1757  ///
1758  /// to get around any mathematical concerns resulting from
1759  /// referencing 2 in a space where 2 does no exist.
1760  unsigned nearestLogBase2() const {
1761  // Special case when we have a bitwidth of 1. If VAL is 1, then we
1762  // get 0. If VAL is 0, we get WORDTYPE_MAX which gets truncated to
1763  // UINT32_MAX.
1764  if (BitWidth == 1)
1765  return U.VAL - 1;
1766 
1767  // Handle the zero case.
1768  if (isNullValue())
1769  return UINT32_MAX;
1770 
1771  // The non-zero case is handled by computing:
1772  //
1773  // nearestLogBase2(x) = logBase2(x) + x[logBase2(x)-1].
1774  //
1775  // where x[i] is referring to the value of the ith bit of x.
1776  unsigned lg = logBase2();
1777  return lg + unsigned((*this)[lg - 1]);
1778  }
1779 
1780  /// \returns the log base 2 of this APInt if its an exact power of two, -1
1781  /// otherwise
1782  int32_t exactLogBase2() const {
1783  if (!isPowerOf2())
1784  return -1;
1785  return logBase2();
1786  }
1787 
1788  /// Compute the square root
1789  APInt sqrt() const;
1790 
1791  /// Get the absolute value;
1792  ///
1793  /// If *this is < 0 then return -(*this), otherwise *this;
1794  APInt abs() const {
1795  if (isNegative())
1796  return -(*this);
1797  return *this;
1798  }
1799 
1800  /// \returns the multiplicative inverse for a given modulo.
1801  APInt multiplicativeInverse(const APInt &modulo) const;
1802 
1803  /// @}
1804  /// \name Support for division by constant
1805  /// @{
1806 
1807  /// Calculate the magic number for signed division by a constant.
1808  struct ms;
1809  ms magic() const;
1810 
1811  /// Calculate the magic number for unsigned division by a constant.
1812  struct mu;
1813  mu magicu(unsigned LeadingZeros = 0) const;
1814 
1815  /// @}
1816  /// \name Building-block Operations for APInt and APFloat
1817  /// @{
1818 
1819  // These building block operations operate on a representation of arbitrary
1820  // precision, two's-complement, bignum integer values. They should be
1821  // sufficient to implement APInt and APFloat bignum requirements. Inputs are
1822  // generally a pointer to the base of an array of integer parts, representing
1823  // an unsigned bignum, and a count of how many parts there are.
1824 
1825  /// Sets the least significant part of a bignum to the input value, and zeroes
1826  /// out higher parts.
1827  static void tcSet(WordType *, WordType, unsigned);
1828 
1829  /// Assign one bignum to another.
1830  static void tcAssign(WordType *, const WordType *, unsigned);
1831 
1832  /// Returns true if a bignum is zero, false otherwise.
1833  static bool tcIsZero(const WordType *, unsigned);
1834 
1835  /// Extract the given bit of a bignum; returns 0 or 1. Zero-based.
1836  static int tcExtractBit(const WordType *, unsigned bit);
1837 
1838  /// Copy the bit vector of width srcBITS from SRC, starting at bit srcLSB, to
1839  /// DST, of dstCOUNT parts, such that the bit srcLSB becomes the least
1840  /// significant bit of DST. All high bits above srcBITS in DST are
1841  /// zero-filled.
1842  static void tcExtract(WordType *, unsigned dstCount,
1843  const WordType *, unsigned srcBits,
1844  unsigned srcLSB);
1845 
1846  /// Set the given bit of a bignum. Zero-based.
1847  static void tcSetBit(WordType *, unsigned bit);
1848 
1849  /// Clear the given bit of a bignum. Zero-based.
1850  static void tcClearBit(WordType *, unsigned bit);
1851 
1852  /// Returns the bit number of the least or most significant set bit of a
1853  /// number. If the input number has no bits set -1U is returned.
1854  static unsigned tcLSB(const WordType *, unsigned n);
1855  static unsigned tcMSB(const WordType *parts, unsigned n);
1856 
1857  /// Negate a bignum in-place.
1858  static void tcNegate(WordType *, unsigned);
1859 
1860  /// DST += RHS + CARRY where CARRY is zero or one. Returns the carry flag.
1861  static WordType tcAdd(WordType *, const WordType *,
1862  WordType carry, unsigned);
1863  /// DST += RHS. Returns the carry flag.
1864  static WordType tcAddPart(WordType *, WordType, unsigned);
1865 
1866  /// DST -= RHS + CARRY where CARRY is zero or one. Returns the carry flag.
1867  static WordType tcSubtract(WordType *, const WordType *,
1868  WordType carry, unsigned);
1869  /// DST -= RHS. Returns the carry flag.
1870  static WordType tcSubtractPart(WordType *, WordType, unsigned);
1871 
1872  /// DST += SRC * MULTIPLIER + PART if add is true
1873  /// DST = SRC * MULTIPLIER + PART if add is false
1874  ///
1875  /// Requires 0 <= DSTPARTS <= SRCPARTS + 1. If DST overlaps SRC they must
1876  /// start at the same point, i.e. DST == SRC.
1877  ///
1878  /// If DSTPARTS == SRC_PARTS + 1 no overflow occurs and zero is returned.
1879  /// Otherwise DST is filled with the least significant DSTPARTS parts of the
1880  /// result, and if all of the omitted higher parts were zero return zero,
1881  /// otherwise overflow occurred and return one.
1882  static int tcMultiplyPart(WordType *dst, const WordType *src,
1883  WordType multiplier, WordType carry,
1884  unsigned srcParts, unsigned dstParts,
1885  bool add);
1886 
1887  /// DST = LHS * RHS, where DST has the same width as the operands and is
1888  /// filled with the least significant parts of the result. Returns one if
1889  /// overflow occurred, otherwise zero. DST must be disjoint from both
1890  /// operands.
1891  static int tcMultiply(WordType *, const WordType *, const WordType *,
1892  unsigned);
1893 
1894  /// DST = LHS * RHS, where DST has width the sum of the widths of the
1895  /// operands. No overflow occurs. DST must be disjoint from both operands.
1896  static void tcFullMultiply(WordType *, const WordType *,
1897  const WordType *, unsigned, unsigned);
1898 
1899  /// If RHS is zero LHS and REMAINDER are left unchanged, return one.
1900  /// Otherwise set LHS to LHS / RHS with the fractional part discarded, set
1901  /// REMAINDER to the remainder, return zero. i.e.
1902  ///
1903  /// OLD_LHS = RHS * LHS + REMAINDER
1904  ///
1905  /// SCRATCH is a bignum of the same size as the operands and result for use by
1906  /// the routine; its contents need not be initialized and are destroyed. LHS,
1907  /// REMAINDER and SCRATCH must be distinct.
1908  static int tcDivide(WordType *lhs, const WordType *rhs,
1909  WordType *remainder, WordType *scratch,
1910  unsigned parts);
1911 
1912  /// Shift a bignum left Count bits. Shifted in bits are zero. There are no
1913  /// restrictions on Count.
1914  static void tcShiftLeft(WordType *, unsigned Words, unsigned Count);
1915 
1916  /// Shift a bignum right Count bits. Shifted in bits are zero. There are no
1917  /// restrictions on Count.
1918  static void tcShiftRight(WordType *, unsigned Words, unsigned Count);
1919 
1920  /// The obvious AND, OR and XOR and complement operations.
1921  static void tcAnd(WordType *, const WordType *, unsigned);
1922  static void tcOr(WordType *, const WordType *, unsigned);
1923  static void tcXor(WordType *, const WordType *, unsigned);
1924  static void tcComplement(WordType *, unsigned);
1925 
1926  /// Comparison (unsigned) of two bignums.
1927  static int tcCompare(const WordType *, const WordType *, unsigned);
1928 
1929  /// Increment a bignum in-place. Return the carry flag.
1930  static WordType tcIncrement(WordType *dst, unsigned parts) {
1931  return tcAddPart(dst, 1, parts);
1932  }
1933 
1934  /// Decrement a bignum in-place. Return the borrow flag.
1935  static WordType tcDecrement(WordType *dst, unsigned parts) {
1936  return tcSubtractPart(dst, 1, parts);
1937  }
1938 
1939  /// Set the least significant BITS and clear the rest.
1940  static void tcSetLeastSignificantBits(WordType *, unsigned, unsigned bits);
1941 
1942  /// debug method
1943  void dump() const;
1944 
1945  /// @}
1946 };
1947 
1948 /// Magic data for optimising signed division by a constant.
1949 struct APInt::ms {
1950  APInt m; ///< magic number
1951  unsigned s; ///< shift amount
1952 };
1953 
1954 /// Magic data for optimising unsigned division by a constant.
1955 struct APInt::mu {
1956  APInt m; ///< magic number
1957  bool a; ///< add indicator
1958  unsigned s; ///< shift amount
1959 };
1960 
1961 inline bool operator==(uint64_t V1, const APInt &V2) { return V2 == V1; }
1962 
1963 inline bool operator!=(uint64_t V1, const APInt &V2) { return V2 != V1; }
1964 
1965 /// Unary bitwise complement operator.
1966 ///
1967 /// \returns an APInt that is the bitwise complement of \p v.
1968 inline APInt operator~(APInt v) {
1969  v.flipAllBits();
1970  return v;
1971 }
1972 
1973 inline APInt operator&(APInt a, const APInt &b) {
1974  a &= b;
1975  return a;
1976 }
1977 
1978 inline APInt operator&(const APInt &a, APInt &&b) {
1979  b &= a;
1980  return std::move(b);
1981 }
1982 
1983 inline APInt operator&(APInt a, uint64_t RHS) {
1984  a &= RHS;
1985  return a;
1986 }
1987 
1988 inline APInt operator&(uint64_t LHS, APInt b) {
1989  b &= LHS;
1990  return b;
1991 }
1992 
1993 inline APInt operator|(APInt a, const APInt &b) {
1994  a |= b;
1995  return a;
1996 }
1997 
1998 inline APInt operator|(const APInt &a, APInt &&b) {
1999  b |= a;
2000  return std::move(b);
2001 }
2002 
2003 inline APInt operator|(APInt a, uint64_t RHS) {
2004  a |= RHS;
2005  return a;
2006 }
2007 
2008 inline APInt operator|(uint64_t LHS, APInt b) {
2009  b |= LHS;
2010  return b;
2011 }
2012 
2013 inline APInt operator^(APInt a, const APInt &b) {
2014  a ^= b;
2015  return a;
2016 }
2017 
2018 inline APInt operator^(const APInt &a, APInt &&b) {
2019  b ^= a;
2020  return std::move(b);
2021 }
2022 
2023 inline APInt operator^(APInt a, uint64_t RHS) {
2024  a ^= RHS;
2025  return a;
2026 }
2027 
2028 inline APInt operator^(uint64_t LHS, APInt b) {
2029  b ^= LHS;
2030  return b;
2031 }
2032 
2033 inline raw_ostream &operator<<(raw_ostream &OS, const APInt &I) {
2034  I.print(OS, true);
2035  return OS;
2036 }
2037 
2038 inline APInt operator-(APInt v) {
2039  v.negate();
2040  return v;
2041 }
2042 
2043 inline APInt operator+(APInt a, const APInt &b) {
2044  a += b;
2045  return a;
2046 }
2047 
2048 inline APInt operator+(const APInt &a, APInt &&b) {
2049  b += a;
2050  return std::move(b);
2051 }
2052 
2053 inline APInt operator+(APInt a, uint64_t RHS) {
2054  a += RHS;
2055  return a;
2056 }
2057 
2058 inline APInt operator+(uint64_t LHS, APInt b) {
2059  b += LHS;
2060  return b;
2061 }
2062 
2063 inline APInt operator-(APInt a, const APInt &b) {
2064  a -= b;
2065  return a;
2066 }
2067 
2068 inline APInt operator-(const APInt &a, APInt &&b) {
2069  b.negate();
2070  b += a;
2071  return std::move(b);
2072 }
2073 
2074 inline APInt operator-(APInt a, uint64_t RHS) {
2075  a -= RHS;
2076  return a;
2077 }
2078 
2079 inline APInt operator-(uint64_t LHS, APInt b) {
2080  b.negate();
2081  b += LHS;
2082  return b;
2083 }
2084 
2085 inline APInt operator*(APInt a, uint64_t RHS) {
2086  a *= RHS;
2087  return a;
2088 }
2089 
2090 inline APInt operator*(uint64_t LHS, APInt b) {
2091  b *= LHS;
2092  return b;
2093 }
2094 
2095 
2096 namespace APIntOps {
2097 
2098 /// Determine the smaller of two APInts considered to be signed.
2099 inline const APInt &smin(const APInt &A, const APInt &B) {
2100  return A.slt(B) ? A : B;
2101 }
2102 
2103 /// Determine the larger of two APInts considered to be signed.
2104 inline const APInt &smax(const APInt &A, const APInt &B) {
2105  return A.sgt(B) ? A : B;
2106 }
2107 
2108 /// Determine the smaller of two APInts considered to be signed.
2109 inline const APInt &umin(const APInt &A, const APInt &B) {
2110  return A.ult(B) ? A : B;
2111 }
2112 
2113 /// Determine the larger of two APInts considered to be unsigned.
2114 inline const APInt &umax(const APInt &A, const APInt &B) {
2115  return A.ugt(B) ? A : B;
2116 }
2117 
2118 /// Compute GCD of two unsigned APInt values.
2119 ///
2120 /// This function returns the greatest common divisor of the two APInt values
2121 /// using Stein's algorithm.
2122 ///
2123 /// \returns the greatest common divisor of A and B.
2125 
2126 /// Converts the given APInt to a double value.
2127 ///
2128 /// Treats the APInt as an unsigned value for conversion purposes.
2129 inline double RoundAPIntToDouble(const APInt &APIVal) {
2130  return APIVal.roundToDouble();
2131 }
2132 
2133 /// Converts the given APInt to a double value.
2134 ///
2135 /// Treats the APInt as a signed value for conversion purposes.
2136 inline double RoundSignedAPIntToDouble(const APInt &APIVal) {
2137  return APIVal.signedRoundToDouble();
2138 }
2139 
2140 /// Converts the given APInt to a float vlalue.
2141 inline float RoundAPIntToFloat(const APInt &APIVal) {
2142  return float(RoundAPIntToDouble(APIVal));
2143 }
2144 
2145 /// Converts the given APInt to a float value.
2146 ///
2147 /// Treast the APInt as a signed value for conversion purposes.
2148 inline float RoundSignedAPIntToFloat(const APInt &APIVal) {
2149  return float(APIVal.signedRoundToDouble());
2150 }
2151 
2152 /// Converts the given double value into a APInt.
2153 ///
2154 /// This function convert a double value to an APInt value.
2155 APInt RoundDoubleToAPInt(double Double, unsigned width);
2156 
2157 /// Converts a float value into a APInt.
2158 ///
2159 /// Converts a float value into an APInt value.
2160 inline APInt RoundFloatToAPInt(float Float, unsigned width) {
2161  return RoundDoubleToAPInt(double(Float), width);
2162 }
2163 
2164 /// Return A unsign-divided by B, rounded by the given rounding mode.
2165 APInt RoundingUDiv(const APInt &A, const APInt &B, APInt::Rounding RM);
2166 
2167 /// Return A sign-divided by B, rounded by the given rounding mode.
2168 APInt RoundingSDiv(const APInt &A, const APInt &B, APInt::Rounding RM);
2169 
2170 /// Let q(n) = An^2 + Bn + C, and BW = bit width of the value range
2171 /// (e.g. 32 for i32).
2172 /// This function finds the smallest number n, such that
2173 /// (a) n >= 0 and q(n) = 0, or
2174 /// (b) n >= 1 and q(n-1) and q(n), when evaluated in the set of all
2175 /// integers, belong to two different intervals [Rk, Rk+R),
2176 /// where R = 2^BW, and k is an integer.
2177 /// The idea here is to find when q(n) "overflows" 2^BW, while at the
2178 /// same time "allowing" subtraction. In unsigned modulo arithmetic a
2179 /// subtraction (treated as addition of negated numbers) would always
2180 /// count as an overflow, but here we want to allow values to decrease
2181 /// and increase as long as they are within the same interval.
2182 /// Specifically, adding of two negative numbers should not cause an
2183 /// overflow (as long as the magnitude does not exceed the bith width).
2184 /// On the other hand, given a positive number, adding a negative
2185 /// number to it can give a negative result, which would cause the
2186 /// value to go from [-2^BW, 0) to [0, 2^BW). In that sense, zero is
2187 /// treated as a special case of an overflow.
2188 ///
2189 /// This function returns None if after finding k that minimizes the
2190 /// positive solution to q(n) = kR, both solutions are contained between
2191 /// two consecutive integers.
2192 ///
2193 /// There are cases where q(n) > T, and q(n+1) < T (assuming evaluation
2194 /// in arithmetic modulo 2^BW, and treating the values as signed) by the
2195 /// virtue of *signed* overflow. This function will *not* find such an n,
2196 /// however it may find a value of n satisfying the inequalities due to
2197 /// an *unsigned* overflow (if the values are treated as unsigned).
2198 /// To find a solution for a signed overflow, treat it as a problem of
2199 /// finding an unsigned overflow with a range with of BW-1.
2200 ///
2201 /// The returned value may have a different bit width from the input
2202 /// coefficients.
2204  unsigned RangeWidth);
2205 } // End of APIntOps namespace
2206 
2207 // See friend declaration above. This additional declaration is required in
2208 // order to compile LLVM with IBM xlC compiler.
2209 hash_code hash_value(const APInt &Arg);
2210 } // End of llvm namespace
2211 
2212 #endif
void clearAllBits()
Set every bit to 0.
Definition: APInt.h:1446
APInt abs() const
Get the absolute value;.
Definition: APInt.h:1794
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:1407
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:1137
void flipAllBits()
Toggle every bit to its opposite value.
Definition: APInt.h:1471
uint64_t getZExtValue() const
Get zero extended value.
Definition: APInt.h:1557
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:2653
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:1412
APInt operator+(APInt a, const APInt &b)
Definition: APInt.h:2043
double RoundAPIntToDouble(const APInt &APIVal)
Converts the given APInt to a double value.
Definition: APInt.h:2129
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:2141
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:1670
unsigned getNumWords() const
Get the number of words.
Definition: APInt.h:1510
unsigned s
shift amount
Definition: APInt.h:1951
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:1111
bool slt(const APInt &RHS) const
Signed less than comparison.
Definition: APInt.h:1198
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:1323
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:1676
APInt operator^(APInt a, const APInt &b)
Definition: APInt.h:2013
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:1268
demanded bits
void setAllBits()
Set every bit to 1.
Definition: APInt.h:1384
APInt operator &(APInt a, const APInt &b)
Definition: APInt.h:1973
void setBitsFrom(unsigned loBit)
Set the top bits starting from loBit.
Definition: APInt.h:1431
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:2671
bool sle(const APInt &RHS) const
Signed less or equal comparison.
Definition: APInt.h:1233
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:1955
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:1503
~APInt()
Destructor.
Definition: APInt.h:336
unsigned countTrailingZeros() const
Count the number of trailing zero bits.
Definition: APInt.h:1626
#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:1397
void setHighBits(unsigned hiBits)
Set the top hiBits bits.
Definition: APInt.h:1441
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:1725
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:1698
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:2085
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:2104
unsigned getActiveBits() const
Compute the number of active bits in the value.
Definition: APInt.h:1527
const APInt & smin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be signed.
Definition: APInt.h:2099
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:1569
bool getBoolValue() const
Convert APInt to a boolean value.
Definition: APInt.h:478
bool ne(const APInt &RHS) const
Inequality comparison.
Definition: APInt.h:1171
bool operator==(const APInt &RHS) const
Equality operator.
Definition: APInt.h:1124
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:1456
int32_t exactLogBase2() const
Definition: APInt.h:1782
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:2148
APInt operator~(APInt v)
Unary bitwise complement operator.
Definition: APInt.h:1968
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:1206
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:1930
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:1652
bool ult(const APInt &RHS) const
Unsigned less than comparison.
Definition: APInt.h:1179
bool ugt(uint64_t RHS) const
Unsigned greater than comparison.
Definition: APInt.h:1257
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:1187
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:1760
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:1311
static unsigned getNumWords(unsigned BitWidth)
Get the number of words.
Definition: APInt.h:1518
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:1466
bool eq(const APInt &RHS) const
Equality comparison.
Definition: APInt.h:1147
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:1745
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:1533
bool sgt(int64_t RHS) const
Signed greater than comparison.
Definition: APInt.h:1276
APInt lshr(unsigned shiftAmt) const
Logical right-shift function.
Definition: APInt.h:971
bool operator!=(const APInt &RHS) const
Inequality operator.
Definition: APInt.h:1155
const APInt & umin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be signed.
Definition: APInt.h:2109
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:1225
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:1956
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:1487
bool sle(uint64_t RHS) const
Signed less or equal comparison.
Definition: APInt.h:1241
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:1287
void print(raw_ostream &OS, bool isSigned) const
Definition: APInt.cpp:2135
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:1742
uint64_t WordType
Definition: APInt.h:72
unsigned countTrailingOnes() const
Count the number of trailing one bits.
Definition: APInt.h:1640
Class for arbitrary precision integers.
Definition: APInt.h:70
bool ule(const APInt &RHS) const
Unsigned less or equal comparison.
Definition: APInt.h:1217
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:1303
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:2114
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:2160
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:1963
bool ugt(const APInt &RHS) const
Unsigned greather than comparison.
Definition: APInt.h:1249
Magic data for optimising signed division by a constant.
Definition: APInt.h:1949
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:1315
unsigned s
shift amount
Definition: APInt.h:1958
APInt m
magic number
Definition: APInt.h:1950
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:2702
#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:2038
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:2033
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:1717
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool uge(uint64_t RHS) const
Unsigned greater or equal comparison.
Definition: APInt.h:1295
unsigned getMinSignedBits() const
Get the minimum bit size for this signed APInt.
Definition: APInt.h:1546
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:1614
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:1935
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:1606
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:1590
bool operator==(uint64_t V1, const APInt &V2)
Definition: APInt.h:1961
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:1993
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:1733
double bitsToDouble() const
Converts APInt bits to a double.
Definition: APInt.h:1708
double RoundSignedAPIntToDouble(const APInt &APIVal)
Converts the given APInt to a double value.
Definition: APInt.h:2136
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:1163
double signedRoundToDouble() const
Converts this signed APInt to a double value.
Definition: APInt.h:1701
void setLowBits(unsigned loBits)
Set the bottom loBits bits.
Definition: APInt.h:1436
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:1957