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