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 | #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. |
34 | using ::mlir::ceilDiv; |
35 | using ::mlir::floorDiv; |
36 | using ::mlir::mod; |
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; |
91 | detail::SlowMPInt valLarge; |
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: o.valLarge); |
162 | } |
163 | LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt &operator=(const MPInt &o) { |
164 | if (LLVM_LIKELY(o.isSmall())) { |
165 | initSmall(o: o.valSmall); |
166 | return *this; |
167 | } |
168 | initLarge(o: o.valLarge); |
169 | return *this; |
170 | } |
171 | LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt &operator=(int x) { |
172 | initSmall(o: 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(x: getSmall(), y: o.getSmall(), result&: 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(x: getSmall(), y: o.getSmall(), result&: 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(x: getSmall(), y: o.getSmall(), result&: 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: lhs.getSmall(), rhs: rhs.getSmall())); |
379 | } |
380 | return MPInt(ceilDiv(lhs: detail::SlowMPInt(lhs), rhs: 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: lhs.getSmall(), rhs: rhs.getSmall())); |
388 | } |
389 | return MPInt(floorDiv(lhs: detail::SlowMPInt(lhs), rhs: detail::SlowMPInt(rhs))); |
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: lhs.getSmall(), rhs: rhs.getSmall())); |
396 | return MPInt(mod(lhs: detail::SlowMPInt(lhs), rhs: 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(m: a.getSmall(), n: b.getSmall())); |
403 | return MPInt(gcd(a: detail::SlowMPInt(a), b: detail::SlowMPInt(b))); |
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(x: a); |
409 | MPInt y = abs(x: b); |
410 | return (x * y) / gcd(a: x, b: 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(x: getSmall(), y: 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(x: getSmall(), y: 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(x: getSmall(), y: 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 & |
487 | MPInt::divByPositiveInPlace(const MPInt &o) { |
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 |
618 | |