llvm/llvm/include/llvm/ADT/APInt.h

//===-- llvm/ADT/APInt.h - For Arbitrary Precision Integer -----*- C++ -*--===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
///
/// \file
/// This file implements a class to represent arbitrary precision
/// integral constant values and operations on them.
///
//===----------------------------------------------------------------------===//

#ifndef LLVM_ADT_APINT_H
#define LLVM_ADT_APINT_H

#include "llvm/Support/Compiler.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/float128.h"
#include <cassert>
#include <climits>
#include <cstring>
#include <optional>
#include <utility>

namespace llvm {
class FoldingSetNodeID;
class StringRef;
class hash_code;
class raw_ostream;
struct Align;
class DynamicAPInt;

template <typename T> class SmallVectorImpl;
template <typename T> class ArrayRef;
template <typename T, typename Enable> struct DenseMapInfo;

class APInt;

inline APInt operator-(APInt);

//===----------------------------------------------------------------------===//
//                              APInt Class
//===----------------------------------------------------------------------===//

/// Class for arbitrary precision integers.
///
/// APInt is a functional replacement for common case unsigned integer type like
/// "unsigned", "unsigned long" or "uint64_t", but also allows non-byte-width
/// integer sizes and large integer value types such as 3-bits, 15-bits, or more
/// than 64-bits of precision. APInt provides a variety of arithmetic operators
/// and methods to manipulate integer values of any bit-width. It supports both
/// the typical integer arithmetic and comparison operations as well as bitwise
/// manipulation.
///
/// The class has several invariants worth noting:
///   * All bit, byte, and word positions are zero-based.
///   * Once the bit width is set, it doesn't change except by the Truncate,
///     SignExtend, or ZeroExtend operations.
///   * All binary operators must be on APInt instances of the same bit width.
///     Attempting to use these operators on instances with different bit
///     widths will yield an assertion.
///   * The value is stored canonically as an unsigned value. For operations
///     where it makes a difference, there are both signed and unsigned variants
///     of the operation. For example, sdiv and udiv. However, because the bit
///     widths must be the same, operations such as Mul and Add produce the same
///     results regardless of whether the values are interpreted as signed or
///     not.
///   * In general, the class tries to follow the style of computation that LLVM
///     uses in its IR. This simplifies its use for LLVM.
///   * APInt supports zero-bit-width values, but operations that require bits
///     are not defined on it (e.g. you cannot ask for the sign of a zero-bit
///     integer).  This means that operations like zero extension and logical
///     shifts are defined, but sign extension and ashr is not.  Zero bit values
///     compare and hash equal to themselves, and countLeadingZeros returns 0.
///
class [[nodiscard]] APInt { … };

inline bool operator==(uint64_t V1, const APInt &V2) { … }

inline bool operator!=(uint64_t V1, const APInt &V2) { … }

/// Unary bitwise complement operator.
///
/// \returns an APInt that is the bitwise complement of \p v.
inline APInt operator~(APInt v) { … }

inline APInt operator&(APInt a, const APInt &b) { … }

inline APInt operator&(const APInt &a, APInt &&b) { … }

inline APInt operator&(APInt a, uint64_t RHS) { … }

inline APInt operator&(uint64_t LHS, APInt b) { … }

inline APInt operator|(APInt a, const APInt &b) { … }

inline APInt operator|(const APInt &a, APInt &&b) { … }

inline APInt operator|(APInt a, uint64_t RHS) { … }

inline APInt operator|(uint64_t LHS, APInt b) { … }

inline APInt operator^(APInt a, const APInt &b) { … }

inline APInt operator^(const APInt &a, APInt &&b) { … }

inline APInt operator^(APInt a, uint64_t RHS) { … }

inline APInt operator^(uint64_t LHS, APInt b) { … }

inline raw_ostream &operator<<(raw_ostream &OS, const APInt &I) { … }

inline APInt operator-(APInt v) { … }

inline APInt operator+(APInt a, const APInt &b) { … }

inline APInt operator+(const APInt &a, APInt &&b) { … }

inline APInt operator+(APInt a, uint64_t RHS) { … }

inline APInt operator+(uint64_t LHS, APInt b) { … }

inline APInt operator-(APInt a, const APInt &b) { … }

inline APInt operator-(const APInt &a, APInt &&b) { … }

inline APInt operator-(APInt a, uint64_t RHS) { … }

inline APInt operator-(uint64_t LHS, APInt b) { … }

inline APInt operator*(APInt a, uint64_t RHS) { … }

inline APInt operator*(uint64_t LHS, APInt b) { … }

namespace APIntOps {

/// Determine the smaller of two APInts considered to be signed.
inline const APInt &smin(const APInt &A, const APInt &B) { … }

/// Determine the larger of two APInts considered to be signed.
inline const APInt &smax(const APInt &A, const APInt &B) { … }

/// Determine the smaller of two APInts considered to be unsigned.
inline const APInt &umin(const APInt &A, const APInt &B) { … }

/// Determine the larger of two APInts considered to be unsigned.
inline const APInt &umax(const APInt &A, const APInt &B) { … }

/// Determine the absolute difference of two APInts considered to be signed.
inline const APInt abds(const APInt &A, const APInt &B) { … }

/// Determine the absolute difference of two APInts considered to be unsigned.
inline const APInt abdu(const APInt &A, const APInt &B) { … }

/// Compute the floor of the signed average of C1 and C2
APInt avgFloorS(const APInt &C1, const APInt &C2);

/// Compute the floor of the unsigned average of C1 and C2
APInt avgFloorU(const APInt &C1, const APInt &C2);

/// Compute the ceil of the signed average of C1 and C2
APInt avgCeilS(const APInt &C1, const APInt &C2);

/// Compute the ceil of the unsigned average of C1 and C2
APInt avgCeilU(const APInt &C1, const APInt &C2);

/// Performs (2*N)-bit multiplication on sign-extended operands.
/// Returns the high N bits of the multiplication result.
APInt mulhs(const APInt &C1, const APInt &C2);

/// Performs (2*N)-bit multiplication on zero-extended operands.
/// Returns the high N bits of the multiplication result.
APInt mulhu(const APInt &C1, const APInt &C2);

/// Compute GCD of two unsigned APInt values.
///
/// This function returns the greatest common divisor of the two APInt values
/// using Stein's algorithm.
///
/// \returns the greatest common divisor of A and B.
APInt GreatestCommonDivisor(APInt A, APInt B);

/// Converts the given APInt to a double value.
///
/// Treats the APInt as an unsigned value for conversion purposes.
inline double RoundAPIntToDouble(const APInt &APIVal) { … }

/// Converts the given APInt to a double value.
///
/// Treats the APInt as a signed value for conversion purposes.
inline double RoundSignedAPIntToDouble(const APInt &APIVal) { … }

/// Converts the given APInt to a float value.
inline float RoundAPIntToFloat(const APInt &APIVal) { … }

/// Converts the given APInt to a float value.
///
/// Treats the APInt as a signed value for conversion purposes.
inline float RoundSignedAPIntToFloat(const APInt &APIVal) { … }

/// Converts the given double value into a APInt.
///
/// This function convert a double value to an APInt value.
APInt RoundDoubleToAPInt(double Double, unsigned width);

/// Converts a float value into a APInt.
///
/// Converts a float value into an APInt value.
inline APInt RoundFloatToAPInt(float Float, unsigned width) { … }

/// Return A unsign-divided by B, rounded by the given rounding mode.
APInt RoundingUDiv(const APInt &A, const APInt &B, APInt::Rounding RM);

/// Return A sign-divided by B, rounded by the given rounding mode.
APInt RoundingSDiv(const APInt &A, const APInt &B, APInt::Rounding RM);

/// Let q(n) = An^2 + Bn + C, and BW = bit width of the value range
/// (e.g. 32 for i32).
/// This function finds the smallest number n, such that
/// (a) n >= 0 and q(n) = 0, or
/// (b) n >= 1 and q(n-1) and q(n), when evaluated in the set of all
///     integers, belong to two different intervals [Rk, Rk+R),
///     where R = 2^BW, and k is an integer.
/// The idea here is to find when q(n) "overflows" 2^BW, while at the
/// same time "allowing" subtraction. In unsigned modulo arithmetic a
/// subtraction (treated as addition of negated numbers) would always
/// count as an overflow, but here we want to allow values to decrease
/// and increase as long as they are within the same interval.
/// Specifically, adding of two negative numbers should not cause an
/// overflow (as long as the magnitude does not exceed the bit width).
/// On the other hand, given a positive number, adding a negative
/// number to it can give a negative result, which would cause the
/// value to go from [-2^BW, 0) to [0, 2^BW). In that sense, zero is
/// treated as a special case of an overflow.
///
/// This function returns std::nullopt if after finding k that minimizes the
/// positive solution to q(n) = kR, both solutions are contained between
/// two consecutive integers.
///
/// There are cases where q(n) > T, and q(n+1) < T (assuming evaluation
/// in arithmetic modulo 2^BW, and treating the values as signed) by the
/// virtue of *signed* overflow. This function will *not* find such an n,
/// however it may find a value of n satisfying the inequalities due to
/// an *unsigned* overflow (if the values are treated as unsigned).
/// To find a solution for a signed overflow, treat it as a problem of
/// finding an unsigned overflow with a range with of BW-1.
///
/// The returned value may have a different bit width from the input
/// coefficients.
std::optional<APInt> SolveQuadraticEquationWrap(APInt A, APInt B, APInt C,
                                                unsigned RangeWidth);

/// Compare two values, and if they are different, return the position of the
/// most significant bit that is different in the values.
std::optional<unsigned> GetMostSignificantDifferentBit(const APInt &A,
                                                       const APInt &B);

/// Splat/Merge neighboring bits to widen/narrow the bitmask represented
/// by \param A to \param NewBitWidth bits.
///
/// MatchAnyBits: (Default)
/// e.g. ScaleBitMask(0b0101, 8) -> 0b00110011
/// e.g. ScaleBitMask(0b00011011, 4) -> 0b0111
///
/// MatchAllBits:
/// e.g. ScaleBitMask(0b0101, 8) -> 0b00110011
/// e.g. ScaleBitMask(0b00011011, 4) -> 0b0001
/// A.getBitwidth() or NewBitWidth must be a whole multiples of the other.
APInt ScaleBitMask(const APInt &A, unsigned NewBitWidth,
                   bool MatchAllBits = false);
} // namespace APIntOps

// See friend declaration above. This additional declaration is required in
// order to compile LLVM with IBM xlC compiler.
hash_code hash_value(const APInt &Arg);

/// StoreIntToMemory - Fills the StoreBytes bytes of memory starting from Dst
/// with the integer held in IntVal.
void StoreIntToMemory(const APInt &IntVal, uint8_t *Dst, unsigned StoreBytes);

/// LoadIntFromMemory - Loads the integer stored in the LoadBytes bytes starting
/// from Src into IntVal, which is assumed to be wide enough and to hold zero.
void LoadIntFromMemory(APInt &IntVal, const uint8_t *Src, unsigned LoadBytes);

/// Provide DenseMapInfo for APInt.
template <> struct DenseMapInfo<APInt, void> { … };

} // namespace llvm

#endif