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