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