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