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