llvm/ADT/DynamicAPInt.h

0001 //===- DynamicAPInt.h - DynamicAPInt Class ----------------------*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 //
0009 // This is a simple class to represent arbitrary precision signed integers.
0010 // Unlike APInt, one does not have to specify a fixed maximum size, and the
0011 // integer can take on any arbitrary values. This is optimized for small-values
0012 // by providing fast-paths for the cases when the value stored fits in 64-bits.
0013 //
0014 //===----------------------------------------------------------------------===//
0015
0016 #ifndef LLVM_ADT_DYNAMICAPINT_H
0017 #define LLVM_ADT_DYNAMICAPINT_H
0018
0019 #include "llvm/ADT/SlowDynamicAPInt.h"
0020 #include "llvm/Support/MathExtras.h"
0021 #include <numeric>
0022
0023 namespace llvm {
0024
0025 class raw_ostream;
0026
0027 /// This class provides support for dynamic arbitrary-precision arithmetic.
0028 ///
0029 /// Unlike APInt, this extends the precision as necessary to prevent overflows
0030 /// and supports operations between objects with differing internal precisions.
0031 ///
0032 /// This is optimized for small-values by providing fast-paths for the cases
0033 /// when the value stored fits in 64-bits. We annotate all fastpaths by using
0034 /// the LLVM_LIKELY/LLVM_UNLIKELY annotations. Removing these would result in
0035 /// a 1.2x performance slowdown.
0036 ///
0037 /// We always_inline all operations; removing these results in a 1.5x
0038 /// performance slowdown.
0039 ///
0040 /// When isLarge returns true, a SlowMPInt is held in the union. If isSmall
0041 /// returns true, the int64_t is held. We don't have a separate field for
0042 /// indicating this, and instead "steal" memory from ValLarge when it is not in
0043 /// use because we know that the memory layout of APInt is such that BitWidth
0044 /// doesn't overlap with ValSmall (see static_assert_layout). Using std::variant
0045 /// instead would lead to significantly worse performance.
0046 class DynamicAPInt {
0047   union {
0048     int64_t ValSmall;
0049     detail::SlowDynamicAPInt ValLarge;
0050   };
0051
0052   LLVM_ATTRIBUTE_ALWAYS_INLINE void initSmall(int64_t O) {
0053     if (LLVM_UNLIKELY(isLarge()))
0054       ValLarge.detail::SlowDynamicAPInt::~SlowDynamicAPInt();
0055     ValSmall = O;
0056     ValLarge.Val.BitWidth = 0;
0057   }
0058   LLVM_ATTRIBUTE_ALWAYS_INLINE void
0059   initLarge(const detail::SlowDynamicAPInt &O) {
0060     if (LLVM_LIKELY(isSmall())) {
0061       // The data in memory could be in an arbitrary state, not necessarily
0062       // corresponding to any valid state of ValLarge; we cannot call any member
0063       // functions, e.g. the assignment operator on it, as they may access the
0064       // invalid internal state. We instead construct a new object using
0065       // placement new.
0066       new (&ValLarge) detail::SlowDynamicAPInt(O);
0067     } else {
0068       // In this case, we need to use the assignment operator, because if we use
0069       // placement-new as above we would lose track of allocated memory
0070       // and leak it.
0071       ValLarge = O;
0072     }
0073   }
0074
0075   LLVM_ATTRIBUTE_ALWAYS_INLINE explicit DynamicAPInt(
0076       const detail::SlowDynamicAPInt &Val)
0077       : ValLarge(Val) {}
0078   LLVM_ATTRIBUTE_ALWAYS_INLINE constexpr bool isSmall() const {
0079     return ValLarge.Val.BitWidth == 0;
0080   }
0081   LLVM_ATTRIBUTE_ALWAYS_INLINE constexpr bool isLarge() const {
0082     return !isSmall();
0083   }
0084   /// Get the stored value. For getSmall/Large,
0085   /// the stored value should be small/large.
0086   LLVM_ATTRIBUTE_ALWAYS_INLINE int64_t getSmall() const {
0087     assert(isSmall() &&
0088            "getSmall should only be called when the value stored is small!");
0089     return ValSmall;
0090   }
0091   LLVM_ATTRIBUTE_ALWAYS_INLINE int64_t &getSmall() {
0092     assert(isSmall() &&
0093            "getSmall should only be called when the value stored is small!");
0094     return ValSmall;
0095   }
0096   LLVM_ATTRIBUTE_ALWAYS_INLINE const detail::SlowDynamicAPInt &
0097   getLarge() const {
0098     assert(isLarge() &&
0099            "getLarge should only be called when the value stored is large!");
0100     return ValLarge;
0101   }
0102   LLVM_ATTRIBUTE_ALWAYS_INLINE detail::SlowDynamicAPInt &getLarge() {
0103     assert(isLarge() &&
0104            "getLarge should only be called when the value stored is large!");
0105     return ValLarge;
0106   }
0107   explicit operator detail::SlowDynamicAPInt() const {
0108     if (isSmall())
0109       return detail::SlowDynamicAPInt(getSmall());
0110     return getLarge();
0111   }
0112
0113 public:
0114   LLVM_ATTRIBUTE_ALWAYS_INLINE explicit DynamicAPInt(int64_t Val)
0115       : ValSmall(Val) {
0116     ValLarge.Val.BitWidth = 0;
0117   }
0118   LLVM_ATTRIBUTE_ALWAYS_INLINE DynamicAPInt() : DynamicAPInt(0) {}
0119   LLVM_ATTRIBUTE_ALWAYS_INLINE ~DynamicAPInt() {
0120     if (LLVM_UNLIKELY(isLarge()))
0121       ValLarge.detail::SlowDynamicAPInt::~SlowDynamicAPInt();
0122   }
0123   LLVM_ATTRIBUTE_ALWAYS_INLINE DynamicAPInt(const DynamicAPInt &O)
0124       : ValSmall(O.ValSmall) {
0125     ValLarge.Val.BitWidth = 0;
0126     if (LLVM_UNLIKELY(O.isLarge()))
0127       initLarge(O.ValLarge);
0128   }
0129   LLVM_ATTRIBUTE_ALWAYS_INLINE DynamicAPInt &operator=(const DynamicAPInt &O) {
0130     if (LLVM_LIKELY(O.isSmall())) {
0131       initSmall(O.ValSmall);
0132       return *this;
0133     }
0134     initLarge(O.ValLarge);
0135     return *this;
0136   }
0137   LLVM_ATTRIBUTE_ALWAYS_INLINE DynamicAPInt &operator=(int X) {
0138     initSmall(X);
0139     return *this;
0140   }
0141   LLVM_ATTRIBUTE_ALWAYS_INLINE explicit operator int64_t() const {
0142     if (isSmall())
0143       return getSmall();
0144     return static_cast<int64_t>(getLarge());
0145   }
0146
0147   bool operator==(const DynamicAPInt &O) const;
0148   bool operator!=(const DynamicAPInt &O) const;
0149   bool operator>(const DynamicAPInt &O) const;
0150   bool operator<(const DynamicAPInt &O) const;
0151   bool operator<=(const DynamicAPInt &O) const;
0152   bool operator>=(const DynamicAPInt &O) const;
0153   DynamicAPInt operator+(const DynamicAPInt &O) const;
0154   DynamicAPInt operator-(const DynamicAPInt &O) const;
0155   DynamicAPInt operator*(const DynamicAPInt &O) const;
0156   DynamicAPInt operator/(const DynamicAPInt &O) const;
0157   DynamicAPInt operator%(const DynamicAPInt &O) const;
0158   DynamicAPInt &operator+=(const DynamicAPInt &O);
0159   DynamicAPInt &operator-=(const DynamicAPInt &O);
0160   DynamicAPInt &operator*=(const DynamicAPInt &O);
0161   DynamicAPInt &operator/=(const DynamicAPInt &O);
0162   DynamicAPInt &operator%=(const DynamicAPInt &O);
0163   DynamicAPInt operator-() const;
0164   DynamicAPInt &operator++();
0165   DynamicAPInt &operator--();
0166
0167   // Divide by a number that is known to be positive.
0168   // This is slightly more efficient because it saves an overflow check.
0169   DynamicAPInt divByPositive(const DynamicAPInt &O) const;
0170   DynamicAPInt &divByPositiveInPlace(const DynamicAPInt &O);
0171
0172   friend DynamicAPInt abs(const DynamicAPInt &X);
0173   friend DynamicAPInt ceilDiv(const DynamicAPInt &LHS, const DynamicAPInt &RHS);
0174   friend DynamicAPInt floorDiv(const DynamicAPInt &LHS,
0175                                const DynamicAPInt &RHS);
0176   // The operands must be non-negative for gcd.
0177   friend DynamicAPInt gcd(const DynamicAPInt &A, const DynamicAPInt &B);
0178   friend DynamicAPInt lcm(const DynamicAPInt &A, const DynamicAPInt &B);
0179   friend DynamicAPInt mod(const DynamicAPInt &LHS, const DynamicAPInt &RHS);
0180
0181   /// ---------------------------------------------------------------------------
0182   /// Convenience operator overloads for int64_t.
0183   /// ---------------------------------------------------------------------------
0184   friend DynamicAPInt &operator+=(DynamicAPInt &A, int64_t B);
0185   friend DynamicAPInt &operator-=(DynamicAPInt &A, int64_t B);
0186   friend DynamicAPInt &operator*=(DynamicAPInt &A, int64_t B);
0187   friend DynamicAPInt &operator/=(DynamicAPInt &A, int64_t B);
0188   friend DynamicAPInt &operator%=(DynamicAPInt &A, int64_t B);
0189
0190   friend bool operator==(const DynamicAPInt &A, int64_t B);
0191   friend bool operator!=(const DynamicAPInt &A, int64_t B);
0192   friend bool operator>(const DynamicAPInt &A, int64_t B);
0193   friend bool operator<(const DynamicAPInt &A, int64_t B);
0194   friend bool operator<=(const DynamicAPInt &A, int64_t B);
0195   friend bool operator>=(const DynamicAPInt &A, int64_t B);
0196   friend DynamicAPInt operator+(const DynamicAPInt &A, int64_t B);
0197   friend DynamicAPInt operator-(const DynamicAPInt &A, int64_t B);
0198   friend DynamicAPInt operator*(const DynamicAPInt &A, int64_t B);
0199   friend DynamicAPInt operator/(const DynamicAPInt &A, int64_t B);
0200   friend DynamicAPInt operator%(const DynamicAPInt &A, int64_t B);
0201
0202   friend bool operator==(int64_t A, const DynamicAPInt &B);
0203   friend bool operator!=(int64_t A, const DynamicAPInt &B);
0204   friend bool operator>(int64_t A, const DynamicAPInt &B);
0205   friend bool operator<(int64_t A, const DynamicAPInt &B);
0206   friend bool operator<=(int64_t A, const DynamicAPInt &B);
0207   friend bool operator>=(int64_t A, const DynamicAPInt &B);
0208   friend DynamicAPInt operator+(int64_t A, const DynamicAPInt &B);
0209   friend DynamicAPInt operator-(int64_t A, const DynamicAPInt &B);
0210   friend DynamicAPInt operator*(int64_t A, const DynamicAPInt &B);
0211   friend DynamicAPInt operator/(int64_t A, const DynamicAPInt &B);
0212   friend DynamicAPInt operator%(int64_t A, const DynamicAPInt &B);
0213
0214   friend hash_code hash_value(const DynamicAPInt &x); // NOLINT
0215
0216   void static_assert_layout(); // NOLINT
0217
0218   raw_ostream &print(raw_ostream &OS) const;
0219   LLVM_DUMP_METHOD void dump() const;
0220 };
0221
0222 inline raw_ostream &operator<<(raw_ostream &OS, const DynamicAPInt &X) {
0223   X.print(OS);
0224   return OS;
0225 }
0226
0227 /// Redeclarations of friend declaration above to
0228 /// make it discoverable by lookups.
0229 hash_code hash_value(const DynamicAPInt &X); // NOLINT
0230
0231 /// This just calls through to the operator int64_t, but it's useful when a
0232 /// function pointer is required. (Although this is marked inline, it is still
0233 /// possible to obtain and use a function pointer to this.)
0234 static inline int64_t int64fromDynamicAPInt(const DynamicAPInt &X) {
0235   return int64_t(X);
0236 }
0237 LLVM_ATTRIBUTE_ALWAYS_INLINE DynamicAPInt dynamicAPIntFromInt64(int64_t X) {
0238   return DynamicAPInt(X);
0239 }
0240
0241 // The RHS is always expected to be positive, and the result
0242 /// is always non-negative.
0243 LLVM_ATTRIBUTE_ALWAYS_INLINE DynamicAPInt mod(const DynamicAPInt &LHS,
0244                                               const DynamicAPInt &RHS);
0245
0246 /// We define the operations here in the header to facilitate inlining.
0247
0248 /// ---------------------------------------------------------------------------
0249 /// Comparison operators.
0250 /// ---------------------------------------------------------------------------
0251 LLVM_ATTRIBUTE_ALWAYS_INLINE bool
0252 DynamicAPInt::operator==(const DynamicAPInt &O) const {
0253   if (LLVM_LIKELY(isSmall() && O.isSmall()))
0254     return getSmall() == O.getSmall();
0255   return detail::SlowDynamicAPInt(*this) == detail::SlowDynamicAPInt(O);
0256 }
0257 LLVM_ATTRIBUTE_ALWAYS_INLINE bool
0258 DynamicAPInt::operator!=(const DynamicAPInt &O) const {
0259   if (LLVM_LIKELY(isSmall() && O.isSmall()))
0260     return getSmall() != O.getSmall();
0261   return detail::SlowDynamicAPInt(*this) != detail::SlowDynamicAPInt(O);
0262 }
0263 LLVM_ATTRIBUTE_ALWAYS_INLINE bool
0264 DynamicAPInt::operator>(const DynamicAPInt &O) const {
0265   if (LLVM_LIKELY(isSmall() && O.isSmall()))
0266     return getSmall() > O.getSmall();
0267   return detail::SlowDynamicAPInt(*this) > detail::SlowDynamicAPInt(O);
0268 }
0269 LLVM_ATTRIBUTE_ALWAYS_INLINE bool
0270 DynamicAPInt::operator<(const DynamicAPInt &O) const {
0271   if (LLVM_LIKELY(isSmall() && O.isSmall()))
0272     return getSmall() < O.getSmall();
0273   return detail::SlowDynamicAPInt(*this) < detail::SlowDynamicAPInt(O);
0274 }
0275 LLVM_ATTRIBUTE_ALWAYS_INLINE bool
0276 DynamicAPInt::operator<=(const DynamicAPInt &O) const {
0277   if (LLVM_LIKELY(isSmall() && O.isSmall()))
0278     return getSmall() <= O.getSmall();
0279   return detail::SlowDynamicAPInt(*this) <= detail::SlowDynamicAPInt(O);
0280 }
0281 LLVM_ATTRIBUTE_ALWAYS_INLINE bool
0282 DynamicAPInt::operator>=(const DynamicAPInt &O) const {
0283   if (LLVM_LIKELY(isSmall() && O.isSmall()))
0284     return getSmall() >= O.getSmall();
0285   return detail::SlowDynamicAPInt(*this) >= detail::SlowDynamicAPInt(O);
0286 }
0287
0288 /// ---------------------------------------------------------------------------
0289 /// Arithmetic operators.
0290 /// ---------------------------------------------------------------------------
0291
0292 LLVM_ATTRIBUTE_ALWAYS_INLINE DynamicAPInt
0293 DynamicAPInt::operator+(const DynamicAPInt &O) const {
0294   if (LLVM_LIKELY(isSmall() && O.isSmall())) {
0295     DynamicAPInt Result;
0296     bool Overflow = AddOverflow(getSmall(), O.getSmall(), Result.getSmall());
0297     if (LLVM_LIKELY(!Overflow))
0298       return Result;
0299     return DynamicAPInt(detail::SlowDynamicAPInt(*this) +
0300                         detail::SlowDynamicAPInt(O));
0301   }
0302   return DynamicAPInt(detail::SlowDynamicAPInt(*this) +
0303                       detail::SlowDynamicAPInt(O));
0304 }
0305 LLVM_ATTRIBUTE_ALWAYS_INLINE DynamicAPInt
0306 DynamicAPInt::operator-(const DynamicAPInt &O) const {
0307   if (LLVM_LIKELY(isSmall() && O.isSmall())) {
0308     DynamicAPInt Result;
0309     bool Overflow = SubOverflow(getSmall(), O.getSmall(), Result.getSmall());
0310     if (LLVM_LIKELY(!Overflow))
0311       return Result;
0312     return DynamicAPInt(detail::SlowDynamicAPInt(*this) -
0313                         detail::SlowDynamicAPInt(O));
0314   }
0315   return DynamicAPInt(detail::SlowDynamicAPInt(*this) -
0316                       detail::SlowDynamicAPInt(O));
0317 }
0318 LLVM_ATTRIBUTE_ALWAYS_INLINE DynamicAPInt
0319 DynamicAPInt::operator*(const DynamicAPInt &O) const {
0320   if (LLVM_LIKELY(isSmall() && O.isSmall())) {
0321     DynamicAPInt Result;
0322     bool Overflow = MulOverflow(getSmall(), O.getSmall(), Result.getSmall());
0323     if (LLVM_LIKELY(!Overflow))
0324       return Result;
0325     return DynamicAPInt(detail::SlowDynamicAPInt(*this) *
0326                         detail::SlowDynamicAPInt(O));
0327   }
0328   return DynamicAPInt(detail::SlowDynamicAPInt(*this) *
0329                       detail::SlowDynamicAPInt(O));
0330 }
0331
0332 // Division overflows only occur when negating the minimal possible value.
0333 LLVM_ATTRIBUTE_ALWAYS_INLINE DynamicAPInt
0334 DynamicAPInt::divByPositive(const DynamicAPInt &O) const {
0335   assert(O > 0);
0336   if (LLVM_LIKELY(isSmall() && O.isSmall()))
0337     return DynamicAPInt(getSmall() / O.getSmall());
0338   return DynamicAPInt(detail::SlowDynamicAPInt(*this) /
0339                       detail::SlowDynamicAPInt(O));
0340 }
0341
0342 LLVM_ATTRIBUTE_ALWAYS_INLINE DynamicAPInt
0343 DynamicAPInt::operator/(const DynamicAPInt &O) const {
0344   if (LLVM_LIKELY(isSmall() && O.isSmall())) {
0345     // Division overflows only occur when negating the minimal possible value.
0346     if (LLVM_UNLIKELY(divideSignedWouldOverflow(getSmall(), O.getSmall())))
0347       return -*this;
0348     return DynamicAPInt(getSmall() / O.getSmall());
0349   }
0350   return DynamicAPInt(detail::SlowDynamicAPInt(*this) /
0351                       detail::SlowDynamicAPInt(O));
0352 }
0353
0354 LLVM_ATTRIBUTE_ALWAYS_INLINE DynamicAPInt abs(const DynamicAPInt &X) {
0355   return DynamicAPInt(X >= 0 ? X : -X);
0356 }
0357 // Division overflows only occur when negating the minimal possible value.
0358 LLVM_ATTRIBUTE_ALWAYS_INLINE DynamicAPInt ceilDiv(const DynamicAPInt &LHS,
0359                                                   const DynamicAPInt &RHS) {
0360   if (LLVM_LIKELY(LHS.isSmall() && RHS.isSmall())) {
0361     if (LLVM_UNLIKELY(
0362             divideSignedWouldOverflow(LHS.getSmall(), RHS.getSmall())))
0363       return -LHS;
0364     return DynamicAPInt(divideCeilSigned(LHS.getSmall(), RHS.getSmall()));
0365   }
0366   return DynamicAPInt(
0367       ceilDiv(detail::SlowDynamicAPInt(LHS), detail::SlowDynamicAPInt(RHS)));
0368 }
0369 LLVM_ATTRIBUTE_ALWAYS_INLINE DynamicAPInt floorDiv(const DynamicAPInt &LHS,
0370                                                    const DynamicAPInt &RHS) {
0371   if (LLVM_LIKELY(LHS.isSmall() && RHS.isSmall())) {
0372     if (LLVM_UNLIKELY(
0373             divideSignedWouldOverflow(LHS.getSmall(), RHS.getSmall())))
0374       return -LHS;
0375     return DynamicAPInt(divideFloorSigned(LHS.getSmall(), RHS.getSmall()));
0376   }
0377   return DynamicAPInt(
0378       floorDiv(detail::SlowDynamicAPInt(LHS), detail::SlowDynamicAPInt(RHS)));
0379 }
0380 // The RHS is always expected to be positive, and the result
0381 /// is always non-negative.
0382 LLVM_ATTRIBUTE_ALWAYS_INLINE DynamicAPInt mod(const DynamicAPInt &LHS,
0383                                               const DynamicAPInt &RHS) {
0384   if (LLVM_LIKELY(LHS.isSmall() && RHS.isSmall()))
0385     return DynamicAPInt(mod(LHS.getSmall(), RHS.getSmall()));
0386   return DynamicAPInt(
0387       mod(detail::SlowDynamicAPInt(LHS), detail::SlowDynamicAPInt(RHS)));
0388 }
0389
0390 LLVM_ATTRIBUTE_ALWAYS_INLINE DynamicAPInt gcd(const DynamicAPInt &A,
0391                                               const DynamicAPInt &B) {
0392   assert(A >= 0 && B >= 0 && "operands must be non-negative!");
0393   if (LLVM_LIKELY(A.isSmall() && B.isSmall()))
0394     return DynamicAPInt(std::gcd(A.getSmall(), B.getSmall()));
0395   return DynamicAPInt(
0396       gcd(detail::SlowDynamicAPInt(A), detail::SlowDynamicAPInt(B)));
0397 }
0398
0399 /// Returns the least common multiple of A and B.
0400 LLVM_ATTRIBUTE_ALWAYS_INLINE DynamicAPInt lcm(const DynamicAPInt &A,
0401                                               const DynamicAPInt &B) {
0402   DynamicAPInt X = abs(A);
0403   DynamicAPInt Y = abs(B);
0404   return (X * Y) / gcd(X, Y);
0405 }
0406
0407 /// This operation cannot overflow.
0408 LLVM_ATTRIBUTE_ALWAYS_INLINE DynamicAPInt
0409 DynamicAPInt::operator%(const DynamicAPInt &O) const {
0410   if (LLVM_LIKELY(isSmall() && O.isSmall()))
0411     return DynamicAPInt(getSmall() % O.getSmall());
0412   return DynamicAPInt(detail::SlowDynamicAPInt(*this) %
0413                       detail::SlowDynamicAPInt(O));
0414 }
0415
0416 LLVM_ATTRIBUTE_ALWAYS_INLINE DynamicAPInt DynamicAPInt::operator-() const {
0417   if (LLVM_LIKELY(isSmall())) {
0418     if (LLVM_LIKELY(getSmall() != std::numeric_limits<int64_t>::min()))
0419       return DynamicAPInt(-getSmall());
0420     return DynamicAPInt(-detail::SlowDynamicAPInt(*this));
0421   }
0422   return DynamicAPInt(-detail::SlowDynamicAPInt(*this));
0423 }
0424
0425 /// ---------------------------------------------------------------------------
0426 /// Assignment operators, preincrement, predecrement.
0427 /// ---------------------------------------------------------------------------
0428 LLVM_ATTRIBUTE_ALWAYS_INLINE DynamicAPInt &
0429 DynamicAPInt::operator+=(const DynamicAPInt &O) {
0430   if (LLVM_LIKELY(isSmall() && O.isSmall())) {
0431     int64_t Result = getSmall();
0432     bool Overflow = AddOverflow(getSmall(), O.getSmall(), Result);
0433     if (LLVM_LIKELY(!Overflow)) {
0434       getSmall() = Result;
0435       return *this;
0436     }
0437     // Note: this return is not strictly required but
0438     // removing it leads to a performance regression.
0439     return *this = DynamicAPInt(detail::SlowDynamicAPInt(*this) +
0440                                 detail::SlowDynamicAPInt(O));
0441   }
0442   return *this = DynamicAPInt(detail::SlowDynamicAPInt(*this) +
0443                               detail::SlowDynamicAPInt(O));
0444 }
0445 LLVM_ATTRIBUTE_ALWAYS_INLINE DynamicAPInt &
0446 DynamicAPInt::operator-=(const DynamicAPInt &O) {
0447   if (LLVM_LIKELY(isSmall() && O.isSmall())) {
0448     int64_t Result = getSmall();
0449     bool Overflow = SubOverflow(getSmall(), O.getSmall(), Result);
0450     if (LLVM_LIKELY(!Overflow)) {
0451       getSmall() = Result;
0452       return *this;
0453     }
0454     // Note: this return is not strictly required but
0455     // removing it leads to a performance regression.
0456     return *this = DynamicAPInt(detail::SlowDynamicAPInt(*this) -
0457                                 detail::SlowDynamicAPInt(O));
0458   }
0459   return *this = DynamicAPInt(detail::SlowDynamicAPInt(*this) -
0460                               detail::SlowDynamicAPInt(O));
0461 }
0462 LLVM_ATTRIBUTE_ALWAYS_INLINE DynamicAPInt &
0463 DynamicAPInt::operator*=(const DynamicAPInt &O) {
0464   if (LLVM_LIKELY(isSmall() && O.isSmall())) {
0465     int64_t Result = getSmall();
0466     bool Overflow = MulOverflow(getSmall(), O.getSmall(), Result);
0467     if (LLVM_LIKELY(!Overflow)) {
0468       getSmall() = Result;
0469       return *this;
0470     }
0471     // Note: this return is not strictly required but
0472     // removing it leads to a performance regression.
0473     return *this = DynamicAPInt(detail::SlowDynamicAPInt(*this) *
0474                                 detail::SlowDynamicAPInt(O));
0475   }
0476   return *this = DynamicAPInt(detail::SlowDynamicAPInt(*this) *
0477                               detail::SlowDynamicAPInt(O));
0478 }
0479 LLVM_ATTRIBUTE_ALWAYS_INLINE DynamicAPInt &
0480 DynamicAPInt::operator/=(const DynamicAPInt &O) {
0481   if (LLVM_LIKELY(isSmall() && O.isSmall())) {
0482     // Division overflows only occur when negating the minimal possible value.
0483     if (LLVM_UNLIKELY(divideSignedWouldOverflow(getSmall(), O.getSmall())))
0484       return *this = -*this;
0485     getSmall() /= O.getSmall();
0486     return *this;
0487   }
0488   return *this = DynamicAPInt(detail::SlowDynamicAPInt(*this) /
0489                               detail::SlowDynamicAPInt(O));
0490 }
0491
0492 // Division overflows only occur when the divisor is -1.
0493 LLVM_ATTRIBUTE_ALWAYS_INLINE DynamicAPInt &
0494 DynamicAPInt::divByPositiveInPlace(const DynamicAPInt &O) {
0495   assert(O > 0);
0496   if (LLVM_LIKELY(isSmall() && O.isSmall())) {
0497     getSmall() /= O.getSmall();
0498     return *this;
0499   }
0500   return *this = DynamicAPInt(detail::SlowDynamicAPInt(*this) /
0501                               detail::SlowDynamicAPInt(O));
0502 }
0503
0504 LLVM_ATTRIBUTE_ALWAYS_INLINE DynamicAPInt &
0505 DynamicAPInt::operator%=(const DynamicAPInt &O) {
0506   return *this = *this % O;
0507 }
0508 LLVM_ATTRIBUTE_ALWAYS_INLINE DynamicAPInt &DynamicAPInt::operator++() {
0509   return *this += 1;
0510 }
0511 LLVM_ATTRIBUTE_ALWAYS_INLINE DynamicAPInt &DynamicAPInt::operator--() {
0512   return *this -= 1;
0513 }
0514
0515 /// ----------------------------------------------------------------------------
0516 /// Convenience operator overloads for int64_t.
0517 /// ----------------------------------------------------------------------------
0518 LLVM_ATTRIBUTE_ALWAYS_INLINE DynamicAPInt &operator+=(DynamicAPInt &A,
0519                                                       int64_t B) {
0520   return A = A + B;
0521 }
0522 LLVM_ATTRIBUTE_ALWAYS_INLINE DynamicAPInt &operator-=(DynamicAPInt &A,
0523                                                       int64_t B) {
0524   return A = A - B;
0525 }
0526 LLVM_ATTRIBUTE_ALWAYS_INLINE DynamicAPInt &operator*=(DynamicAPInt &A,
0527                                                       int64_t B) {
0528   return A = A * B;
0529 }
0530 LLVM_ATTRIBUTE_ALWAYS_INLINE DynamicAPInt &operator/=(DynamicAPInt &A,
0531                                                       int64_t B) {
0532   return A = A / B;
0533 }
0534 LLVM_ATTRIBUTE_ALWAYS_INLINE DynamicAPInt &operator%=(DynamicAPInt &A,
0535                                                       int64_t B) {
0536   return A = A % B;
0537 }
0538 LLVM_ATTRIBUTE_ALWAYS_INLINE DynamicAPInt operator+(const DynamicAPInt &A,
0539                                                     int64_t B) {
0540   return A + DynamicAPInt(B);
0541 }
0542 LLVM_ATTRIBUTE_ALWAYS_INLINE DynamicAPInt operator-(const DynamicAPInt &A,
0543                                                     int64_t B) {
0544   return A - DynamicAPInt(B);
0545 }
0546 LLVM_ATTRIBUTE_ALWAYS_INLINE DynamicAPInt operator*(const DynamicAPInt &A,
0547                                                     int64_t B) {
0548   return A * DynamicAPInt(B);
0549 }
0550 LLVM_ATTRIBUTE_ALWAYS_INLINE DynamicAPInt operator/(const DynamicAPInt &A,
0551                                                     int64_t B) {
0552   return A / DynamicAPInt(B);
0553 }
0554 LLVM_ATTRIBUTE_ALWAYS_INLINE DynamicAPInt operator%(const DynamicAPInt &A,
0555                                                     int64_t B) {
0556   return A % DynamicAPInt(B);
0557 }
0558 LLVM_ATTRIBUTE_ALWAYS_INLINE DynamicAPInt operator+(int64_t A,
0559                                                     const DynamicAPInt &B) {
0560   return DynamicAPInt(A) + B;
0561 }
0562 LLVM_ATTRIBUTE_ALWAYS_INLINE DynamicAPInt operator-(int64_t A,
0563                                                     const DynamicAPInt &B) {
0564   return DynamicAPInt(A) - B;
0565 }
0566 LLVM_ATTRIBUTE_ALWAYS_INLINE DynamicAPInt operator*(int64_t A,
0567                                                     const DynamicAPInt &B) {
0568   return DynamicAPInt(A) * B;
0569 }
0570 LLVM_ATTRIBUTE_ALWAYS_INLINE DynamicAPInt operator/(int64_t A,
0571                                                     const DynamicAPInt &B) {
0572   return DynamicAPInt(A) / B;
0573 }
0574 LLVM_ATTRIBUTE_ALWAYS_INLINE DynamicAPInt operator%(int64_t A,
0575                                                     const DynamicAPInt &B) {
0576   return DynamicAPInt(A) % B;
0577 }
0578
0579 /// We provide special implementations of the comparison operators rather than
0580 /// calling through as above, as this would result in a 1.2x slowdown.
0581 LLVM_ATTRIBUTE_ALWAYS_INLINE bool operator==(const DynamicAPInt &A, int64_t B) {
0582   if (LLVM_LIKELY(A.isSmall()))
0583     return A.getSmall() == B;
0584   return A.getLarge() == B;
0585 }
0586 LLVM_ATTRIBUTE_ALWAYS_INLINE bool operator!=(const DynamicAPInt &A, int64_t B) {
0587   if (LLVM_LIKELY(A.isSmall()))
0588     return A.getSmall() != B;
0589   return A.getLarge() != B;
0590 }
0591 LLVM_ATTRIBUTE_ALWAYS_INLINE bool operator>(const DynamicAPInt &A, int64_t B) {
0592   if (LLVM_LIKELY(A.isSmall()))
0593     return A.getSmall() > B;
0594   return A.getLarge() > B;
0595 }
0596 LLVM_ATTRIBUTE_ALWAYS_INLINE bool operator<(const DynamicAPInt &A, int64_t B) {
0597   if (LLVM_LIKELY(A.isSmall()))
0598     return A.getSmall() < B;
0599   return A.getLarge() < B;
0600 }
0601 LLVM_ATTRIBUTE_ALWAYS_INLINE bool operator<=(const DynamicAPInt &A, int64_t B) {
0602   if (LLVM_LIKELY(A.isSmall()))
0603     return A.getSmall() <= B;
0604   return A.getLarge() <= B;
0605 }
0606 LLVM_ATTRIBUTE_ALWAYS_INLINE bool operator>=(const DynamicAPInt &A, int64_t B) {
0607   if (LLVM_LIKELY(A.isSmall()))
0608     return A.getSmall() >= B;
0609   return A.getLarge() >= B;
0610 }
0611 LLVM_ATTRIBUTE_ALWAYS_INLINE bool operator==(int64_t A, const DynamicAPInt &B) {
0612   if (LLVM_LIKELY(B.isSmall()))
0613     return A == B.getSmall();
0614   return A == B.getLarge();
0615 }
0616 LLVM_ATTRIBUTE_ALWAYS_INLINE bool operator!=(int64_t A, const DynamicAPInt &B) {
0617   if (LLVM_LIKELY(B.isSmall()))
0618     return A != B.getSmall();
0619   return A != B.getLarge();
0620 }
0621 LLVM_ATTRIBUTE_ALWAYS_INLINE bool operator>(int64_t A, const DynamicAPInt &B) {
0622   if (LLVM_LIKELY(B.isSmall()))
0623     return A > B.getSmall();
0624   return A > B.getLarge();
0625 }
0626 LLVM_ATTRIBUTE_ALWAYS_INLINE bool operator<(int64_t A, const DynamicAPInt &B) {
0627   if (LLVM_LIKELY(B.isSmall()))
0628     return A < B.getSmall();
0629   return A < B.getLarge();
0630 }
0631 LLVM_ATTRIBUTE_ALWAYS_INLINE bool operator<=(int64_t A, const DynamicAPInt &B) {
0632   if (LLVM_LIKELY(B.isSmall()))
0633     return A <= B.getSmall();
0634   return A <= B.getLarge();
0635 }
0636 LLVM_ATTRIBUTE_ALWAYS_INLINE bool operator>=(int64_t A, const DynamicAPInt &B) {
0637   if (LLVM_LIKELY(B.isSmall()))
0638     return A >= B.getSmall();
0639   return A >= B.getLarge();
0640 }
0641 } // namespace llvm
0642
0643 #endif // LLVM_ADT_DYNAMICAPINT_H