1 //===- MPInt.h - MLIR MPInt Class -------------------------------*- 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 // This is a simple class to represent arbitrary precision signed integers.
10 // Unlike APInt, one does not have to specify a fixed maximum size, and the
11 // integer can take on any arbitrary values. This is optimized for small-values
12 // by providing fast-paths for the cases when the value stored fits in 64-bits.
13 //
14 //===----------------------------------------------------------------------===//
15 
16 #ifndef MLIR_ANALYSIS_PRESBURGER_MPINT_H
17 #define MLIR_ANALYSIS_PRESBURGER_MPINT_H
18 
19 #include "mlir/Analysis/Presburger/SlowMPInt.h"
20 #include "mlir/Support/MathExtras.h"
21 #include "llvm/Support/raw_ostream.h"
22 
23 namespace mlir {
24 namespace presburger {
25 
26 /// Redefine these functions, which operate on 64-bit ints, to also be part of
27 /// the mlir::presburger namespace. This is useful because this file defines
28 /// identically-named functions that operate on MPInts, which would otherwie
29 /// become the only candidates of overload resolution when calling e.g. ceilDiv
30 /// from the mlir::presburger namespace. So to access the 64-bit overloads, an
31 /// explict call to mlir::ceilDiv would be required. These using declarations
32 /// allow overload resolution to transparently call the right function.
33 using ::mlir::ceilDiv;
34 using ::mlir::floorDiv;
35 using ::mlir::mod;
36 
37 namespace detail {
38 /// If builtin intrinsics for overflow-checked arithmetic are available,
39 /// use them. Otherwise, call through to LLVM's overflow-checked arithmetic
40 /// functionality. Those functions also have such macro-gated uses of intrinsics
41 /// but they are not always_inlined, which is important for us to achieve
42 /// high-performance; calling the functions directly would result in a slowdown
43 /// of 1.15x.
addOverflow(int64_t x,int64_t y,int64_t & result)44 LLVM_ATTRIBUTE_ALWAYS_INLINE bool addOverflow(int64_t x, int64_t y,
45                                               int64_t &result) {
46 #if __has_builtin(__builtin_add_overflow)
47   return __builtin_add_overflow(x, y, &result);
48 #else
49   return llvm::AddOverflow(x, y, result);
50 #endif
51 }
subOverflow(int64_t x,int64_t y,int64_t & result)52 LLVM_ATTRIBUTE_ALWAYS_INLINE bool subOverflow(int64_t x, int64_t y,
53                                               int64_t &result) {
54 #if __has_builtin(__builtin_sub_overflow)
55   return __builtin_sub_overflow(x, y, &result);
56 #else
57   return llvm::SubOverflow(x, y, result);
58 #endif
59 }
mulOverflow(int64_t x,int64_t y,int64_t & result)60 LLVM_ATTRIBUTE_ALWAYS_INLINE bool mulOverflow(int64_t x, int64_t y,
61                                               int64_t &result) {
62 #if __has_builtin(__builtin_mul_overflow)
63   return __builtin_mul_overflow(x, y, &result);
64 #else
65   return llvm::MulOverflow(x, y, result);
66 #endif
67 }
68 } // namespace detail
69 
70 /// This class provides support for multi-precision arithmetic.
71 ///
72 /// Unlike APInt, this extends the precision as necessary to prevent overflows
73 /// and supports operations between objects with differing internal precisions.
74 ///
75 /// This is optimized for small-values by providing fast-paths for the cases
76 /// when the value stored fits in 64-bits. We annotate all fastpaths by using
77 /// the LLVM_LIKELY/LLVM_UNLIKELY annotations. Removing these would result in
78 /// a 1.2x performance slowdown.
79 ///
80 /// We always_inline all operations; removing these results in a 1.5x
81 /// performance slowdown.
82 ///
83 /// When holdsLarge is true, a SlowMPInt is held in the union. If it is false,
84 /// the int64_t is held. Using std::variant instead would lead to significantly
85 /// worse performance.
86 class MPInt {
87 private:
88   union {
89     int64_t valSmall;
90     detail::SlowMPInt valLarge;
91   };
92   unsigned holdsLarge;
93 
initSmall(int64_t o)94   LLVM_ATTRIBUTE_ALWAYS_INLINE void initSmall(int64_t o) {
95     if (LLVM_UNLIKELY(isLarge()))
96       valLarge.detail::SlowMPInt::~SlowMPInt();
97     valSmall = o;
98     holdsLarge = false;
99   }
initLarge(const detail::SlowMPInt & o)100   LLVM_ATTRIBUTE_ALWAYS_INLINE void initLarge(const detail::SlowMPInt &o) {
101     if (LLVM_LIKELY(isSmall())) {
102       // The data in memory could be in an arbitrary state, not necessarily
103       // corresponding to any valid state of valLarge; we cannot call any member
104       // functions, e.g. the assignment operator on it, as they may access the
105       // invalid internal state. We instead construct a new object using
106       // placement new.
107       new (&valLarge) detail::SlowMPInt(o);
108     } else {
109       // In this case, we need to use the assignment operator, because if we use
110       // placement-new as above we would lose track of allocated memory
111       // and leak it.
112       valLarge = o;
113     }
114     holdsLarge = true;
115   }
116 
MPInt(const detail::SlowMPInt & val)117   LLVM_ATTRIBUTE_ALWAYS_INLINE explicit MPInt(const detail::SlowMPInt &val)
118       : valLarge(val), holdsLarge(true) {}
isSmall()119   LLVM_ATTRIBUTE_ALWAYS_INLINE bool isSmall() const { return !holdsLarge; }
isLarge()120   LLVM_ATTRIBUTE_ALWAYS_INLINE bool isLarge() const { return holdsLarge; }
121   /// Get the stored value. For getSmall/Large,
122   /// the stored value should be small/large.
getSmall()123   LLVM_ATTRIBUTE_ALWAYS_INLINE int64_t getSmall() const {
124     assert(isSmall() &&
125            "getSmall should only be called when the value stored is small!");
126     return valSmall;
127   }
getSmall()128   LLVM_ATTRIBUTE_ALWAYS_INLINE int64_t &getSmall() {
129     assert(isSmall() &&
130            "getSmall should only be called when the value stored is small!");
131     return valSmall;
132   }
getLarge()133   LLVM_ATTRIBUTE_ALWAYS_INLINE const detail::SlowMPInt &getLarge() const {
134     assert(isLarge() &&
135            "getLarge should only be called when the value stored is large!");
136     return valLarge;
137   }
getLarge()138   LLVM_ATTRIBUTE_ALWAYS_INLINE detail::SlowMPInt &getLarge() {
139     assert(isLarge() &&
140            "getLarge should only be called when the value stored is large!");
141     return valLarge;
142   }
SlowMPInt()143   explicit operator detail::SlowMPInt() const {
144     if (isSmall())
145       return detail::SlowMPInt(getSmall());
146     return getLarge();
147   }
148 
149 public:
MPInt(int64_t val)150   LLVM_ATTRIBUTE_ALWAYS_INLINE explicit MPInt(int64_t val)
151       : valSmall(val), holdsLarge(false) {}
MPInt()152   LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt() : MPInt(0) {}
~MPInt()153   LLVM_ATTRIBUTE_ALWAYS_INLINE ~MPInt() {
154     if (LLVM_UNLIKELY(isLarge()))
155       valLarge.detail::SlowMPInt::~SlowMPInt();
156   }
MPInt(const MPInt & o)157   LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt(const MPInt &o)
158       : valSmall(o.valSmall), holdsLarge(false) {
159     if (LLVM_UNLIKELY(o.isLarge()))
160       initLarge(o.valLarge);
161   }
162   LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt &operator=(const MPInt &o) {
163     if (LLVM_LIKELY(o.isSmall())) {
164       initSmall(o.valSmall);
165       return *this;
166     }
167     initLarge(o.valLarge);
168     return *this;
169   }
170   LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt &operator=(int x) {
171     initSmall(x);
172     return *this;
173   }
int64_t()174   LLVM_ATTRIBUTE_ALWAYS_INLINE explicit operator int64_t() const {
175     if (isSmall())
176       return getSmall();
177     return static_cast<int64_t>(getLarge());
178   }
179 
180   bool operator==(const MPInt &o) const;
181   bool operator!=(const MPInt &o) const;
182   bool operator>(const MPInt &o) const;
183   bool operator<(const MPInt &o) const;
184   bool operator<=(const MPInt &o) const;
185   bool operator>=(const MPInt &o) const;
186   MPInt operator+(const MPInt &o) const;
187   MPInt operator-(const MPInt &o) const;
188   MPInt operator*(const MPInt &o) const;
189   MPInt operator/(const MPInt &o) const;
190   MPInt operator%(const MPInt &o) const;
191   MPInt &operator+=(const MPInt &o);
192   MPInt &operator-=(const MPInt &o);
193   MPInt &operator*=(const MPInt &o);
194   MPInt &operator/=(const MPInt &o);
195   MPInt &operator%=(const MPInt &o);
196   MPInt operator-() const;
197   MPInt &operator++();
198   MPInt &operator--();
199 
200   // Divide by a number that is known to be positive.
201   // This is slightly more efficient because it saves an overflow check.
202   MPInt divByPositive(const MPInt &o) const;
203   MPInt &divByPositiveInPlace(const MPInt &o);
204 
205   friend MPInt abs(const MPInt &x);
206   friend MPInt gcdRange(ArrayRef<MPInt> range);
207   friend MPInt ceilDiv(const MPInt &lhs, const MPInt &rhs);
208   friend MPInt floorDiv(const MPInt &lhs, const MPInt &rhs);
209   // The operands must be non-negative for gcd.
210   friend MPInt gcd(const MPInt &a, const MPInt &b);
211   friend MPInt lcm(const MPInt &a, const MPInt &b);
212   friend MPInt mod(const MPInt &lhs, const MPInt &rhs);
213 
214   llvm::raw_ostream &print(llvm::raw_ostream &os) const;
215   void dump() const;
216 
217   /// ---------------------------------------------------------------------------
218   /// Convenience operator overloads for int64_t.
219   /// ---------------------------------------------------------------------------
220   friend MPInt &operator+=(MPInt &a, int64_t b);
221   friend MPInt &operator-=(MPInt &a, int64_t b);
222   friend MPInt &operator*=(MPInt &a, int64_t b);
223   friend MPInt &operator/=(MPInt &a, int64_t b);
224   friend MPInt &operator%=(MPInt &a, int64_t b);
225 
226   friend bool operator==(const MPInt &a, int64_t b);
227   friend bool operator!=(const MPInt &a, int64_t b);
228   friend bool operator>(const MPInt &a, int64_t b);
229   friend bool operator<(const MPInt &a, int64_t b);
230   friend bool operator<=(const MPInt &a, int64_t b);
231   friend bool operator>=(const MPInt &a, int64_t b);
232   friend MPInt operator+(const MPInt &a, int64_t b);
233   friend MPInt operator-(const MPInt &a, int64_t b);
234   friend MPInt operator*(const MPInt &a, int64_t b);
235   friend MPInt operator/(const MPInt &a, int64_t b);
236   friend MPInt operator%(const MPInt &a, int64_t b);
237 
238   friend bool operator==(int64_t a, const MPInt &b);
239   friend bool operator!=(int64_t a, const MPInt &b);
240   friend bool operator>(int64_t a, const MPInt &b);
241   friend bool operator<(int64_t a, const MPInt &b);
242   friend bool operator<=(int64_t a, const MPInt &b);
243   friend bool operator>=(int64_t a, const MPInt &b);
244   friend MPInt operator+(int64_t a, const MPInt &b);
245   friend MPInt operator-(int64_t a, const MPInt &b);
246   friend MPInt operator*(int64_t a, const MPInt &b);
247   friend MPInt operator/(int64_t a, const MPInt &b);
248   friend MPInt operator%(int64_t a, const MPInt &b);
249 
250   friend llvm::hash_code hash_value(const MPInt &x); // NOLINT
251 };
252 
253 /// Redeclarations of friend declaration above to
254 /// make it discoverable by lookups.
255 llvm::hash_code hash_value(const MPInt &x); // NOLINT
256 
257 /// This just calls through to the operator int64_t, but it's useful when a
258 /// function pointer is required. (Although this is marked inline, it is still
259 /// possible to obtain and use a function pointer to this.)
int64FromMPInt(const MPInt & x)260 static inline int64_t int64FromMPInt(const MPInt &x) { return int64_t(x); }
mpintFromInt64(int64_t x)261 LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt mpintFromInt64(int64_t x) {
262   return MPInt(x);
263 }
264 
265 llvm::raw_ostream &operator<<(llvm::raw_ostream &os, const MPInt &x);
266 
267 // The RHS is always expected to be positive, and the result
268 /// is always non-negative.
269 LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt mod(const MPInt &lhs, const MPInt &rhs);
270 
271 namespace detail {
272 // Division overflows only when trying to negate the minimal signed value.
divWouldOverflow(int64_t x,int64_t y)273 LLVM_ATTRIBUTE_ALWAYS_INLINE bool divWouldOverflow(int64_t x, int64_t y) {
274   return x == std::numeric_limits<int64_t>::min() && y == -1;
275 }
276 } // namespace detail
277 
278 /// We define the operations here in the header to facilitate inlining.
279 
280 /// ---------------------------------------------------------------------------
281 /// Comparison operators.
282 /// ---------------------------------------------------------------------------
283 LLVM_ATTRIBUTE_ALWAYS_INLINE bool MPInt::operator==(const MPInt &o) const {
284   if (LLVM_LIKELY(isSmall() && o.isSmall()))
285     return getSmall() == o.getSmall();
286   return detail::SlowMPInt(*this) == detail::SlowMPInt(o);
287 }
288 LLVM_ATTRIBUTE_ALWAYS_INLINE bool MPInt::operator!=(const MPInt &o) const {
289   if (LLVM_LIKELY(isSmall() && o.isSmall()))
290     return getSmall() != o.getSmall();
291   return detail::SlowMPInt(*this) != detail::SlowMPInt(o);
292 }
293 LLVM_ATTRIBUTE_ALWAYS_INLINE bool MPInt::operator>(const MPInt &o) const {
294   if (LLVM_LIKELY(isSmall() && o.isSmall()))
295     return getSmall() > o.getSmall();
296   return detail::SlowMPInt(*this) > detail::SlowMPInt(o);
297 }
298 LLVM_ATTRIBUTE_ALWAYS_INLINE bool MPInt::operator<(const MPInt &o) const {
299   if (LLVM_LIKELY(isSmall() && o.isSmall()))
300     return getSmall() < o.getSmall();
301   return detail::SlowMPInt(*this) < detail::SlowMPInt(o);
302 }
303 LLVM_ATTRIBUTE_ALWAYS_INLINE bool MPInt::operator<=(const MPInt &o) const {
304   if (LLVM_LIKELY(isSmall() && o.isSmall()))
305     return getSmall() <= o.getSmall();
306   return detail::SlowMPInt(*this) <= detail::SlowMPInt(o);
307 }
308 LLVM_ATTRIBUTE_ALWAYS_INLINE bool MPInt::operator>=(const MPInt &o) const {
309   if (LLVM_LIKELY(isSmall() && o.isSmall()))
310     return getSmall() >= o.getSmall();
311   return detail::SlowMPInt(*this) >= detail::SlowMPInt(o);
312 }
313 
314 /// ---------------------------------------------------------------------------
315 /// Arithmetic operators.
316 /// ---------------------------------------------------------------------------
317 LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt MPInt::operator+(const MPInt &o) const {
318   if (LLVM_LIKELY(isSmall() && o.isSmall())) {
319     MPInt result;
320     bool overflow =
321         detail::addOverflow(getSmall(), o.getSmall(), result.getSmall());
322     if (LLVM_LIKELY(!overflow))
323       return result;
324     return MPInt(detail::SlowMPInt(*this) + detail::SlowMPInt(o));
325   }
326   return MPInt(detail::SlowMPInt(*this) + detail::SlowMPInt(o));
327 }
328 LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt MPInt::operator-(const MPInt &o) const {
329   if (LLVM_LIKELY(isSmall() && o.isSmall())) {
330     MPInt result;
331     bool overflow =
332         detail::subOverflow(getSmall(), o.getSmall(), result.getSmall());
333     if (LLVM_LIKELY(!overflow))
334       return result;
335     return MPInt(detail::SlowMPInt(*this) - detail::SlowMPInt(o));
336   }
337   return MPInt(detail::SlowMPInt(*this) - detail::SlowMPInt(o));
338 }
339 LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt MPInt::operator*(const MPInt &o) const {
340   if (LLVM_LIKELY(isSmall() && o.isSmall())) {
341     MPInt result;
342     bool overflow =
343         detail::mulOverflow(getSmall(), o.getSmall(), result.getSmall());
344     if (LLVM_LIKELY(!overflow))
345       return result;
346     return MPInt(detail::SlowMPInt(*this) * detail::SlowMPInt(o));
347   }
348   return MPInt(detail::SlowMPInt(*this) * detail::SlowMPInt(o));
349 }
350 
351 // Division overflows only occur when negating the minimal possible value.
divByPositive(const MPInt & o)352 LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt MPInt::divByPositive(const MPInt &o) const {
353   assert(o > 0);
354   if (LLVM_LIKELY(isSmall() && o.isSmall()))
355     return MPInt(getSmall() / o.getSmall());
356   return MPInt(detail::SlowMPInt(*this) / detail::SlowMPInt(o));
357 }
358 
359 LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt MPInt::operator/(const MPInt &o) const {
360   if (LLVM_LIKELY(isSmall() && o.isSmall())) {
361     // Division overflows only occur when negating the minimal possible value.
362     if (LLVM_UNLIKELY(detail::divWouldOverflow(getSmall(), o.getSmall())))
363       return -*this;
364     return MPInt(getSmall() / o.getSmall());
365   }
366   return MPInt(detail::SlowMPInt(*this) / detail::SlowMPInt(o));
367 }
368 
abs(const MPInt & x)369 LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt abs(const MPInt &x) {
370   return MPInt(x >= 0 ? x : -x);
371 }
372 // Division overflows only occur when negating the minimal possible value.
ceilDiv(const MPInt & lhs,const MPInt & rhs)373 LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt ceilDiv(const MPInt &lhs, const MPInt &rhs) {
374   if (LLVM_LIKELY(lhs.isSmall() && rhs.isSmall())) {
375     if (LLVM_UNLIKELY(detail::divWouldOverflow(lhs.getSmall(), rhs.getSmall())))
376       return -lhs;
377     return MPInt(ceilDiv(lhs.getSmall(), rhs.getSmall()));
378   }
379   return MPInt(ceilDiv(detail::SlowMPInt(lhs), detail::SlowMPInt(rhs)));
380 }
floorDiv(const MPInt & lhs,const MPInt & rhs)381 LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt floorDiv(const MPInt &lhs,
382                                             const MPInt &rhs) {
383   if (LLVM_LIKELY(lhs.isSmall() && rhs.isSmall())) {
384     if (LLVM_UNLIKELY(detail::divWouldOverflow(lhs.getSmall(), rhs.getSmall())))
385       return -lhs;
386     return MPInt(floorDiv(lhs.getSmall(), rhs.getSmall()));
387   }
388   return MPInt(floorDiv(detail::SlowMPInt(lhs), detail::SlowMPInt(rhs)));
389 }
390 // The RHS is always expected to be positive, and the result
391 /// is always non-negative.
mod(const MPInt & lhs,const MPInt & rhs)392 LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt mod(const MPInt &lhs, const MPInt &rhs) {
393   if (LLVM_LIKELY(lhs.isSmall() && rhs.isSmall()))
394     return MPInt(mod(lhs.getSmall(), rhs.getSmall()));
395   return MPInt(mod(detail::SlowMPInt(lhs), detail::SlowMPInt(rhs)));
396 }
397 
gcd(const MPInt & a,const MPInt & b)398 LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt gcd(const MPInt &a, const MPInt &b) {
399   assert(a >= 0 && b >= 0 && "operands must be non-negative!");
400   if (LLVM_LIKELY(a.isSmall() && b.isSmall()))
401     return MPInt(llvm::greatestCommonDivisor(a.getSmall(), b.getSmall()));
402   return MPInt(gcd(detail::SlowMPInt(a), detail::SlowMPInt(b)));
403 }
404 
405 /// Returns the least common multiple of 'a' and 'b'.
lcm(const MPInt & a,const MPInt & b)406 LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt lcm(const MPInt &a, const MPInt &b) {
407   MPInt x = abs(a);
408   MPInt y = abs(b);
409   return (x * y) / gcd(x, y);
410 }
411 
412 /// This operation cannot overflow.
413 LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt MPInt::operator%(const MPInt &o) const {
414   if (LLVM_LIKELY(isSmall() && o.isSmall()))
415     return MPInt(getSmall() % o.getSmall());
416   return MPInt(detail::SlowMPInt(*this) % detail::SlowMPInt(o));
417 }
418 
419 LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt MPInt::operator-() const {
420   if (LLVM_LIKELY(isSmall())) {
421     if (LLVM_LIKELY(getSmall() != std::numeric_limits<int64_t>::min()))
422       return MPInt(-getSmall());
423     return MPInt(-detail::SlowMPInt(*this));
424   }
425   return MPInt(-detail::SlowMPInt(*this));
426 }
427 
428 /// ---------------------------------------------------------------------------
429 /// Assignment operators, preincrement, predecrement.
430 /// ---------------------------------------------------------------------------
431 LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt &MPInt::operator+=(const MPInt &o) {
432   if (LLVM_LIKELY(isSmall() && o.isSmall())) {
433     int64_t result = getSmall();
434     bool overflow = detail::addOverflow(getSmall(), o.getSmall(), result);
435     if (LLVM_LIKELY(!overflow)) {
436       getSmall() = result;
437       return *this;
438     }
439     // Note: this return is not strictly required but
440     // removing it leads to a performance regression.
441     return *this = MPInt(detail::SlowMPInt(*this) + detail::SlowMPInt(o));
442   }
443   return *this = MPInt(detail::SlowMPInt(*this) + detail::SlowMPInt(o));
444 }
445 LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt &MPInt::operator-=(const MPInt &o) {
446   if (LLVM_LIKELY(isSmall() && o.isSmall())) {
447     int64_t result = getSmall();
448     bool overflow = detail::subOverflow(getSmall(), o.getSmall(), result);
449     if (LLVM_LIKELY(!overflow)) {
450       getSmall() = result;
451       return *this;
452     }
453     // Note: this return is not strictly required but
454     // removing it leads to a performance regression.
455     return *this = MPInt(detail::SlowMPInt(*this) - detail::SlowMPInt(o));
456   }
457   return *this = MPInt(detail::SlowMPInt(*this) - detail::SlowMPInt(o));
458 }
459 LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt &MPInt::operator*=(const MPInt &o) {
460   if (LLVM_LIKELY(isSmall() && o.isSmall())) {
461     int64_t result = getSmall();
462     bool overflow = detail::mulOverflow(getSmall(), o.getSmall(), result);
463     if (LLVM_LIKELY(!overflow)) {
464       getSmall() = result;
465       return *this;
466     }
467     // Note: this return is not strictly required but
468     // removing it leads to a performance regression.
469     return *this = MPInt(detail::SlowMPInt(*this) * detail::SlowMPInt(o));
470   }
471   return *this = MPInt(detail::SlowMPInt(*this) * detail::SlowMPInt(o));
472 }
473 LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt &MPInt::operator/=(const MPInt &o) {
474   if (LLVM_LIKELY(isSmall() && o.isSmall())) {
475     // Division overflows only occur when negating the minimal possible value.
476     if (LLVM_UNLIKELY(detail::divWouldOverflow(getSmall(), o.getSmall())))
477       return *this = -*this;
478     getSmall() /= o.getSmall();
479     return *this;
480   }
481   return *this = MPInt(detail::SlowMPInt(*this) / detail::SlowMPInt(o));
482 }
483 
484 // Division overflows only occur when the divisor is -1.
485 LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt &
divByPositiveInPlace(const MPInt & o)486 MPInt::divByPositiveInPlace(const MPInt &o) {
487   assert(o > 0);
488   if (LLVM_LIKELY(isSmall() && o.isSmall())) {
489     getSmall() /= o.getSmall();
490     return *this;
491   }
492   return *this = MPInt(detail::SlowMPInt(*this) / detail::SlowMPInt(o));
493 }
494 
495 LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt &MPInt::operator%=(const MPInt &o) {
496   return *this = *this % o;
497 }
498 LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt &MPInt::operator++() { return *this += 1; }
499 LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt &MPInt::operator--() { return *this -= 1; }
500 
501 /// ----------------------------------------------------------------------------
502 /// Convenience operator overloads for int64_t.
503 /// ----------------------------------------------------------------------------
504 LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt &operator+=(MPInt &a, int64_t b) {
505   return a = a + b;
506 }
507 LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt &operator-=(MPInt &a, int64_t b) {
508   return a = a - b;
509 }
510 LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt &operator*=(MPInt &a, int64_t b) {
511   return a = a * b;
512 }
513 LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt &operator/=(MPInt &a, int64_t b) {
514   return a = a / b;
515 }
516 LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt &operator%=(MPInt &a, int64_t b) {
517   return a = a % b;
518 }
519 LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt operator+(const MPInt &a, int64_t b) {
520   return a + MPInt(b);
521 }
522 LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt operator-(const MPInt &a, int64_t b) {
523   return a - MPInt(b);
524 }
525 LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt operator*(const MPInt &a, int64_t b) {
526   return a * MPInt(b);
527 }
528 LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt operator/(const MPInt &a, int64_t b) {
529   return a / MPInt(b);
530 }
531 LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt operator%(const MPInt &a, int64_t b) {
532   return a % MPInt(b);
533 }
534 LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt operator+(int64_t a, const MPInt &b) {
535   return MPInt(a) + b;
536 }
537 LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt operator-(int64_t a, const MPInt &b) {
538   return MPInt(a) - b;
539 }
540 LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt operator*(int64_t a, const MPInt &b) {
541   return MPInt(a) * b;
542 }
543 LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt operator/(int64_t a, const MPInt &b) {
544   return MPInt(a) / b;
545 }
546 LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt operator%(int64_t a, const MPInt &b) {
547   return MPInt(a) % b;
548 }
549 
550 /// We provide special implementations of the comparison operators rather than
551 /// calling through as above, as this would result in a 1.2x slowdown.
552 LLVM_ATTRIBUTE_ALWAYS_INLINE bool operator==(const MPInt &a, int64_t b) {
553   if (LLVM_LIKELY(a.isSmall()))
554     return a.getSmall() == b;
555   return a.getLarge() == b;
556 }
557 LLVM_ATTRIBUTE_ALWAYS_INLINE bool operator!=(const MPInt &a, int64_t b) {
558   if (LLVM_LIKELY(a.isSmall()))
559     return a.getSmall() != b;
560   return a.getLarge() != b;
561 }
562 LLVM_ATTRIBUTE_ALWAYS_INLINE bool operator>(const MPInt &a, int64_t b) {
563   if (LLVM_LIKELY(a.isSmall()))
564     return a.getSmall() > b;
565   return a.getLarge() > b;
566 }
567 LLVM_ATTRIBUTE_ALWAYS_INLINE bool operator<(const MPInt &a, int64_t b) {
568   if (LLVM_LIKELY(a.isSmall()))
569     return a.getSmall() < b;
570   return a.getLarge() < b;
571 }
572 LLVM_ATTRIBUTE_ALWAYS_INLINE bool operator<=(const MPInt &a, int64_t b) {
573   if (LLVM_LIKELY(a.isSmall()))
574     return a.getSmall() <= b;
575   return a.getLarge() <= b;
576 }
577 LLVM_ATTRIBUTE_ALWAYS_INLINE bool operator>=(const MPInt &a, int64_t b) {
578   if (LLVM_LIKELY(a.isSmall()))
579     return a.getSmall() >= b;
580   return a.getLarge() >= b;
581 }
582 LLVM_ATTRIBUTE_ALWAYS_INLINE bool operator==(int64_t a, const MPInt &b) {
583   if (LLVM_LIKELY(b.isSmall()))
584     return a == b.getSmall();
585   return a == b.getLarge();
586 }
587 LLVM_ATTRIBUTE_ALWAYS_INLINE bool operator!=(int64_t a, const MPInt &b) {
588   if (LLVM_LIKELY(b.isSmall()))
589     return a != b.getSmall();
590   return a != b.getLarge();
591 }
592 LLVM_ATTRIBUTE_ALWAYS_INLINE bool operator>(int64_t a, const MPInt &b) {
593   if (LLVM_LIKELY(b.isSmall()))
594     return a > b.getSmall();
595   return a > b.getLarge();
596 }
597 LLVM_ATTRIBUTE_ALWAYS_INLINE bool operator<(int64_t a, const MPInt &b) {
598   if (LLVM_LIKELY(b.isSmall()))
599     return a < b.getSmall();
600   return a < b.getLarge();
601 }
602 LLVM_ATTRIBUTE_ALWAYS_INLINE bool operator<=(int64_t a, const MPInt &b) {
603   if (LLVM_LIKELY(b.isSmall()))
604     return a <= b.getSmall();
605   return a <= b.getLarge();
606 }
607 LLVM_ATTRIBUTE_ALWAYS_INLINE bool operator>=(int64_t a, const MPInt &b) {
608   if (LLVM_LIKELY(b.isSmall()))
609     return a >= b.getSmall();
610   return a >= b.getLarge();
611 }
612 
613 } // namespace presburger
614 } // namespace mlir
615 
616 #endif // MLIR_ANALYSIS_PRESBURGER_MPINT_H
617