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