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