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