16 #ifndef MLIR_ANALYSIS_PRESBURGER_MPINT_H
17 #define MLIR_ANALYSIS_PRESBURGER_MPINT_H
21 #include "llvm/Support/raw_ostream.h"
25 namespace presburger {
45 LLVM_ATTRIBUTE_ALWAYS_INLINE
bool addOverflow(int64_t x, int64_t y,
47 #if __has_builtin(__builtin_add_overflow)
48 return __builtin_add_overflow(x, y, &result);
50 return llvm::AddOverflow(x, y, result);
53 LLVM_ATTRIBUTE_ALWAYS_INLINE
bool subOverflow(int64_t x, int64_t y,
55 #if __has_builtin(__builtin_sub_overflow)
56 return __builtin_sub_overflow(x, y, &result);
58 return llvm::SubOverflow(x, y, result);
61 LLVM_ATTRIBUTE_ALWAYS_INLINE
bool mulOverflow(int64_t x, int64_t y,
63 #if __has_builtin(__builtin_mul_overflow)
64 return __builtin_mul_overflow(x, y, &result);
66 return llvm::MulOverflow(x, y, result);
95 LLVM_ATTRIBUTE_ALWAYS_INLINE
void initSmall(int64_t o) {
96 if (LLVM_UNLIKELY(isLarge()))
97 valLarge.detail::SlowMPInt::~SlowMPInt();
101 LLVM_ATTRIBUTE_ALWAYS_INLINE
void initLarge(
const detail::SlowMPInt &o) {
102 if (LLVM_LIKELY(isSmall())) {
108 new (&
valLarge) detail::SlowMPInt(o);
118 LLVM_ATTRIBUTE_ALWAYS_INLINE
explicit MPInt(
const detail::SlowMPInt &val)
119 :
valLarge(val), holdsLarge(true) {}
120 LLVM_ATTRIBUTE_ALWAYS_INLINE
bool isSmall()
const {
return !holdsLarge; }
121 LLVM_ATTRIBUTE_ALWAYS_INLINE
bool isLarge()
const {
return holdsLarge; }
124 LLVM_ATTRIBUTE_ALWAYS_INLINE int64_t getSmall()
const {
126 "getSmall should only be called when the value stored is small!");
129 LLVM_ATTRIBUTE_ALWAYS_INLINE int64_t &getSmall() {
131 "getSmall should only be called when the value stored is small!");
134 LLVM_ATTRIBUTE_ALWAYS_INLINE
const detail::SlowMPInt &getLarge()
const {
136 "getLarge should only be called when the value stored is large!");
139 LLVM_ATTRIBUTE_ALWAYS_INLINE detail::SlowMPInt &getLarge() {
141 "getLarge should only be called when the value stored is large!");
144 explicit operator detail::SlowMPInt()
const {
146 return detail::SlowMPInt(getSmall());
151 LLVM_ATTRIBUTE_ALWAYS_INLINE
explicit MPInt(int64_t val)
152 :
valSmall(val), holdsLarge(false) {}
155 if (LLVM_UNLIKELY(isLarge()))
156 valLarge.detail::SlowMPInt::~SlowMPInt();
160 if (LLVM_UNLIKELY(o.isLarge()))
164 if (LLVM_LIKELY(o.isSmall())) {
175 LLVM_ATTRIBUTE_ALWAYS_INLINE
explicit operator int64_t()
const {
178 return static_cast<int64_t
>(getLarge());
215 llvm::raw_ostream &
print(llvm::raw_ostream &os)
const;
266 llvm::raw_ostream &
operator<<(llvm::raw_ostream &os,
const MPInt &x);
270 LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt
mod(
const MPInt &lhs,
const MPInt &rhs);
285 if (LLVM_LIKELY(isSmall() && o.isSmall()))
286 return getSmall() == o.getSmall();
290 if (LLVM_LIKELY(isSmall() && o.isSmall()))
291 return getSmall() != o.getSmall();
295 if (LLVM_LIKELY(isSmall() && o.isSmall()))
296 return getSmall() > o.getSmall();
300 if (LLVM_LIKELY(isSmall() && o.isSmall()))
301 return getSmall() < o.getSmall();
305 if (LLVM_LIKELY(isSmall() && o.isSmall()))
306 return getSmall() <= o.getSmall();
310 if (LLVM_LIKELY(isSmall() && o.isSmall()))
311 return getSmall() >= o.getSmall();
319 if (LLVM_LIKELY(isSmall() && o.isSmall())) {
323 if (LLVM_LIKELY(!overflow))
330 if (LLVM_LIKELY(isSmall() && o.isSmall())) {
334 if (LLVM_LIKELY(!overflow))
341 if (LLVM_LIKELY(isSmall() && o.isSmall())) {
345 if (LLVM_LIKELY(!overflow))
355 if (LLVM_LIKELY(isSmall() && o.isSmall()))
356 return MPInt(getSmall() / o.getSmall());
361 if (LLVM_LIKELY(isSmall() && o.isSmall())) {
365 return MPInt(getSmall() / o.getSmall());
371 return MPInt(x >= 0 ? x : -x);
375 if (LLVM_LIKELY(lhs.isSmall() && rhs.isSmall())) {
384 if (LLVM_LIKELY(lhs.isSmall() && rhs.isSmall())) {
394 if (LLVM_LIKELY(lhs.isSmall() && rhs.isSmall()))
395 return MPInt(
mod(lhs.getSmall(), rhs.getSmall()));
400 assert(a >= 0 && b >= 0 &&
"operands must be non-negative!");
401 if (LLVM_LIKELY(a.isSmall() && b.isSmall()))
410 return (x * y) /
gcd(x, y);
415 if (LLVM_LIKELY(isSmall() && o.isSmall()))
416 return MPInt(getSmall() % o.getSmall());
421 if (LLVM_LIKELY(isSmall())) {
423 return MPInt(-getSmall());
433 if (LLVM_LIKELY(isSmall() && o.isSmall())) {
434 int64_t result = getSmall();
436 if (LLVM_LIKELY(!overflow)) {
447 if (LLVM_LIKELY(isSmall() && o.isSmall())) {
448 int64_t result = getSmall();
450 if (LLVM_LIKELY(!overflow)) {
461 if (LLVM_LIKELY(isSmall() && o.isSmall())) {
462 int64_t result = getSmall();
464 if (LLVM_LIKELY(!overflow)) {
475 if (LLVM_LIKELY(isSmall() && o.isSmall())) {
478 return *
this = -*
this;
479 getSmall() /= o.getSmall();
486 LLVM_ATTRIBUTE_ALWAYS_INLINE
MPInt &
489 if (LLVM_LIKELY(isSmall() && o.isSmall())) {
490 getSmall() /= o.getSmall();
497 return *
this = *
this % o;
554 if (LLVM_LIKELY(a.isSmall()))
555 return a.getSmall() == b;
556 return a.getLarge() == b;
559 if (LLVM_LIKELY(a.isSmall()))
560 return a.getSmall() != b;
561 return a.getLarge() != b;
564 if (LLVM_LIKELY(a.isSmall()))
565 return a.getSmall() > b;
566 return a.getLarge() > b;
569 if (LLVM_LIKELY(a.isSmall()))
570 return a.getSmall() < b;
571 return a.getLarge() < b;
574 if (LLVM_LIKELY(a.isSmall()))
575 return a.getSmall() <= b;
576 return a.getLarge() <= b;
579 if (LLVM_LIKELY(a.isSmall()))
580 return a.getSmall() >= b;
581 return a.getLarge() >= b;
584 if (LLVM_LIKELY(b.isSmall()))
585 return a == b.getSmall();
586 return a == b.getLarge();
589 if (LLVM_LIKELY(b.isSmall()))
590 return a != b.getSmall();
591 return a != b.getLarge();
594 if (LLVM_LIKELY(b.isSmall()))
595 return a > b.getSmall();
596 return a > b.getLarge();
599 if (LLVM_LIKELY(b.isSmall()))
600 return a < b.getSmall();
601 return a < b.getLarge();
604 if (LLVM_LIKELY(b.isSmall()))
605 return a <= b.getSmall();
606 return a <= b.getLarge();
609 if (LLVM_LIKELY(b.isSmall()))
610 return a >= b.getSmall();
611 return a >= b.getLarge();
static Value min(ImplicitLocOpBuilder &builder, Value value, Value bound)
This class provides support for multi-precision arithmetic.
LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt & operator=(int x)
friend MPInt mod(const MPInt &lhs, const MPInt &rhs)
is always non-negative.
friend llvm::hash_code hash_value(const MPInt &x)
Redeclarations of friend declaration above to make it discoverable by lookups.
MPInt divByPositive(const MPInt &o) const
MPInt & operator-=(const MPInt &o)
MPInt & operator/=(const MPInt &o)
MPInt & operator*=(const MPInt &o)
bool operator<(const MPInt &o) const
LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt()
MPInt & divByPositiveInPlace(const MPInt &o)
MPInt & operator+=(const MPInt &o)
friend MPInt floorDiv(const MPInt &lhs, const MPInt &rhs)
bool operator<=(const MPInt &o) const
bool operator!=(const MPInt &o) const
friend MPInt lcm(const MPInt &a, const MPInt &b)
Returns the least common multiple of 'a' and 'b'.
friend MPInt gcdRange(ArrayRef< MPInt > range)
Compute the gcd of the range.
MPInt operator%(const MPInt &o) const
This operation cannot overflow.
friend MPInt ceilDiv(const MPInt &lhs, const MPInt &rhs)
LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt(const MPInt &o)
friend MPInt gcd(const MPInt &a, const MPInt &b)
MPInt & operator%=(const MPInt &o)
MPInt operator*(const MPInt &o) const
MPInt operator/(const MPInt &o) const
bool operator>(const MPInt &o) const
detail::SlowMPInt valLarge
LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt & operator=(const MPInt &o)
LLVM_ATTRIBUTE_ALWAYS_INLINE ~MPInt()
friend MPInt abs(const MPInt &x)
bool operator==(const MPInt &o) const
We define the operations here in the header to facilitate inlining.
bool operator>=(const MPInt &o) const
MPInt operator+(const MPInt &o) const
LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt(int64_t val)
llvm::raw_ostream & print(llvm::raw_ostream &os) const
A simple class providing multi-precision arithmetic.
LLVM_ATTRIBUTE_ALWAYS_INLINE bool subOverflow(int64_t x, int64_t y, int64_t &result)
LLVM_ATTRIBUTE_ALWAYS_INLINE bool mulOverflow(int64_t x, int64_t y, int64_t &result)
LLVM_ATTRIBUTE_ALWAYS_INLINE bool addOverflow(int64_t x, int64_t y, int64_t &result)
If builtin intrinsics for overflow-checked arithmetic are available, use them.
LLVM_ATTRIBUTE_ALWAYS_INLINE bool divWouldOverflow(int64_t x, int64_t y)
LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt gcd(const MPInt &a, const MPInt &b)
llvm::raw_ostream & operator<<(llvm::raw_ostream &os, const Fraction &x)
LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt mod(const MPInt &lhs, const MPInt &rhs)
is always non-negative.
llvm::hash_code hash_value(const MPInt &x)
Redeclarations of friend declaration above to make it discoverable by lookups.
Fraction & operator-=(Fraction &x, const Fraction &y)
Fraction operator+(const Fraction &x, const Fraction &y)
LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt ceilDiv(const MPInt &lhs, const MPInt &rhs)
bool operator==(const Fraction &x, const Fraction &y)
bool operator>(const Fraction &x, const Fraction &y)
bool operator<(const Fraction &x, const Fraction &y)
LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt abs(const MPInt &x)
static int64_t int64FromMPInt(const MPInt &x)
This just calls through to the operator int64_t, but it's useful when a function pointer is required.
bool operator>=(const Fraction &x, const Fraction &y)
Fraction operator-(const Fraction &x)
bool operator<=(const Fraction &x, const Fraction &y)
LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt mpintFromInt64(int64_t x)
Fraction & operator*=(Fraction &x, const Fraction &y)
LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt operator%(const MPInt &a, int64_t b)
Fraction & operator/=(Fraction &x, const Fraction &y)
LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt & operator%=(MPInt &a, int64_t b)
bool operator!=(const Fraction &x, const Fraction &y)
Fraction & operator+=(Fraction &x, const Fraction &y)
Fraction operator*(const Fraction &x, const Fraction &y)
LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt lcm(const MPInt &a, const MPInt &b)
Returns the least common multiple of 'a' and 'b'.
Fraction operator/(const Fraction &x, const Fraction &y)
LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt floorDiv(const MPInt &lhs, const MPInt &rhs)
Include the generated interface declarations.