WebSVN – QNX 8.QNX8 LLVM/Clang compiler suite – Blame – //llvm-build/x86_64/include/llvm/ADT/APInt.h

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

Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

QNX 8.QNX8 LLVM/Clang compiler suite//llvm-build/x86_64/include/llvm/ADT/APInt.h – Rev 14