289 lines · cpp
1//===- SlowDynamicAPInt.cpp - SlowDynamicAPInt Implementation -------------===//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-exception6//7//===----------------------------------------------------------------------===//8 9#include "llvm/ADT/SlowDynamicAPInt.h"10#include "llvm/ADT/Hashing.h"11#include "llvm/Support/Debug.h"12#include "llvm/Support/raw_ostream.h"13 14using namespace llvm;15using namespace llvm::detail;16 17SlowDynamicAPInt::SlowDynamicAPInt(int64_t Val)18 : Val(64, Val, /*isSigned=*/true) {}19SlowDynamicAPInt::SlowDynamicAPInt() : SlowDynamicAPInt(0) {}20SlowDynamicAPInt::SlowDynamicAPInt(const APInt &Val) : Val(Val) {}21SlowDynamicAPInt &SlowDynamicAPInt::operator=(int64_t Val) {22 return *this = SlowDynamicAPInt(Val);23}24SlowDynamicAPInt::operator int64_t() const { return Val.getSExtValue(); }25 26hash_code llvm::detail::hash_value(const SlowDynamicAPInt &X) {27 return hash_value(X.Val);28}29 30/// ---------------------------------------------------------------------------31/// Convenience operator overloads for int64_t.32/// ---------------------------------------------------------------------------33SlowDynamicAPInt &llvm::detail::operator+=(SlowDynamicAPInt &A, int64_t B) {34 return A += SlowDynamicAPInt(B);35}36SlowDynamicAPInt &llvm::detail::operator-=(SlowDynamicAPInt &A, int64_t B) {37 return A -= SlowDynamicAPInt(B);38}39SlowDynamicAPInt &llvm::detail::operator*=(SlowDynamicAPInt &A, int64_t B) {40 return A *= SlowDynamicAPInt(B);41}42SlowDynamicAPInt &llvm::detail::operator/=(SlowDynamicAPInt &A, int64_t B) {43 return A /= SlowDynamicAPInt(B);44}45SlowDynamicAPInt &llvm::detail::operator%=(SlowDynamicAPInt &A, int64_t B) {46 return A %= SlowDynamicAPInt(B);47}48 49bool llvm::detail::operator==(const SlowDynamicAPInt &A, int64_t B) {50 return A == SlowDynamicAPInt(B);51}52bool llvm::detail::operator!=(const SlowDynamicAPInt &A, int64_t B) {53 return A != SlowDynamicAPInt(B);54}55bool llvm::detail::operator>(const SlowDynamicAPInt &A, int64_t B) {56 return A > SlowDynamicAPInt(B);57}58bool llvm::detail::operator<(const SlowDynamicAPInt &A, int64_t B) {59 return A < SlowDynamicAPInt(B);60}61bool llvm::detail::operator<=(const SlowDynamicAPInt &A, int64_t B) {62 return A <= SlowDynamicAPInt(B);63}64bool llvm::detail::operator>=(const SlowDynamicAPInt &A, int64_t B) {65 return A >= SlowDynamicAPInt(B);66}67SlowDynamicAPInt llvm::detail::operator+(const SlowDynamicAPInt &A, int64_t B) {68 return A + SlowDynamicAPInt(B);69}70SlowDynamicAPInt llvm::detail::operator-(const SlowDynamicAPInt &A, int64_t B) {71 return A - SlowDynamicAPInt(B);72}73SlowDynamicAPInt llvm::detail::operator*(const SlowDynamicAPInt &A, int64_t B) {74 return A * SlowDynamicAPInt(B);75}76SlowDynamicAPInt llvm::detail::operator/(const SlowDynamicAPInt &A, int64_t B) {77 return A / SlowDynamicAPInt(B);78}79SlowDynamicAPInt llvm::detail::operator%(const SlowDynamicAPInt &A, int64_t B) {80 return A % SlowDynamicAPInt(B);81}82 83bool llvm::detail::operator==(int64_t A, const SlowDynamicAPInt &B) {84 return SlowDynamicAPInt(A) == B;85}86bool llvm::detail::operator!=(int64_t A, const SlowDynamicAPInt &B) {87 return SlowDynamicAPInt(A) != B;88}89bool llvm::detail::operator>(int64_t A, const SlowDynamicAPInt &B) {90 return SlowDynamicAPInt(A) > B;91}92bool llvm::detail::operator<(int64_t A, const SlowDynamicAPInt &B) {93 return SlowDynamicAPInt(A) < B;94}95bool llvm::detail::operator<=(int64_t A, const SlowDynamicAPInt &B) {96 return SlowDynamicAPInt(A) <= B;97}98bool llvm::detail::operator>=(int64_t A, const SlowDynamicAPInt &B) {99 return SlowDynamicAPInt(A) >= B;100}101SlowDynamicAPInt llvm::detail::operator+(int64_t A, const SlowDynamicAPInt &B) {102 return SlowDynamicAPInt(A) + B;103}104SlowDynamicAPInt llvm::detail::operator-(int64_t A, const SlowDynamicAPInt &B) {105 return SlowDynamicAPInt(A) - B;106}107SlowDynamicAPInt llvm::detail::operator*(int64_t A, const SlowDynamicAPInt &B) {108 return SlowDynamicAPInt(A) * B;109}110SlowDynamicAPInt llvm::detail::operator/(int64_t A, const SlowDynamicAPInt &B) {111 return SlowDynamicAPInt(A) / B;112}113SlowDynamicAPInt llvm::detail::operator%(int64_t A, const SlowDynamicAPInt &B) {114 return SlowDynamicAPInt(A) % B;115}116 117static unsigned getMaxWidth(const APInt &A, const APInt &B) {118 return std::max(A.getBitWidth(), B.getBitWidth());119}120 121/// ---------------------------------------------------------------------------122/// Comparison operators.123/// ---------------------------------------------------------------------------124 125// TODO: consider instead making APInt::compare available and using that.126bool SlowDynamicAPInt::operator==(const SlowDynamicAPInt &O) const {127 unsigned Width = getMaxWidth(Val, O.Val);128 return Val.sext(Width) == O.Val.sext(Width);129}130bool SlowDynamicAPInt::operator!=(const SlowDynamicAPInt &O) const {131 unsigned Width = getMaxWidth(Val, O.Val);132 return Val.sext(Width) != O.Val.sext(Width);133}134bool SlowDynamicAPInt::operator>(const SlowDynamicAPInt &O) const {135 unsigned Width = getMaxWidth(Val, O.Val);136 return Val.sext(Width).sgt(O.Val.sext(Width));137}138bool SlowDynamicAPInt::operator<(const SlowDynamicAPInt &O) const {139 unsigned Width = getMaxWidth(Val, O.Val);140 return Val.sext(Width).slt(O.Val.sext(Width));141}142bool SlowDynamicAPInt::operator<=(const SlowDynamicAPInt &O) const {143 unsigned Width = getMaxWidth(Val, O.Val);144 return Val.sext(Width).sle(O.Val.sext(Width));145}146bool SlowDynamicAPInt::operator>=(const SlowDynamicAPInt &O) const {147 unsigned Width = getMaxWidth(Val, O.Val);148 return Val.sext(Width).sge(O.Val.sext(Width));149}150 151/// ---------------------------------------------------------------------------152/// Arithmetic operators.153/// ---------------------------------------------------------------------------154 155/// Bring a and b to have the same width and then call op(a, b, overflow).156/// If the overflow bit becomes set, resize a and b to double the width and157/// call op(a, b, overflow), returning its result. The operation with double158/// widths should not also overflow.159APInt runOpWithExpandOnOverflow(160 const APInt &A, const APInt &B,161 function_ref<APInt(const APInt &, const APInt &, bool &Overflow)> Op) {162 bool Overflow;163 unsigned Width = getMaxWidth(A, B);164 APInt Ret = Op(A.sext(Width), B.sext(Width), Overflow);165 if (!Overflow)166 return Ret;167 168 Width *= 2;169 Ret = Op(A.sext(Width), B.sext(Width), Overflow);170 assert(!Overflow && "double width should be sufficient to avoid overflow!");171 return Ret;172}173 174SlowDynamicAPInt SlowDynamicAPInt::operator+(const SlowDynamicAPInt &O) const {175 return SlowDynamicAPInt(176 runOpWithExpandOnOverflow(Val, O.Val, std::mem_fn(&APInt::sadd_ov)));177}178SlowDynamicAPInt SlowDynamicAPInt::operator-(const SlowDynamicAPInt &O) const {179 return SlowDynamicAPInt(180 runOpWithExpandOnOverflow(Val, O.Val, std::mem_fn(&APInt::ssub_ov)));181}182SlowDynamicAPInt SlowDynamicAPInt::operator*(const SlowDynamicAPInt &O) const {183 return SlowDynamicAPInt(184 runOpWithExpandOnOverflow(Val, O.Val, std::mem_fn(&APInt::smul_ov)));185}186SlowDynamicAPInt SlowDynamicAPInt::operator/(const SlowDynamicAPInt &O) const {187 return SlowDynamicAPInt(188 runOpWithExpandOnOverflow(Val, O.Val, std::mem_fn(&APInt::sdiv_ov)));189}190SlowDynamicAPInt llvm::detail::abs(const SlowDynamicAPInt &X) {191 return X >= 0 ? X : -X;192}193SlowDynamicAPInt llvm::detail::ceilDiv(const SlowDynamicAPInt &LHS,194 const SlowDynamicAPInt &RHS) {195 if (RHS == -1)196 return -LHS;197 unsigned Width = getMaxWidth(LHS.Val, RHS.Val);198 return SlowDynamicAPInt(APIntOps::RoundingSDiv(199 LHS.Val.sext(Width), RHS.Val.sext(Width), APInt::Rounding::UP));200}201SlowDynamicAPInt llvm::detail::floorDiv(const SlowDynamicAPInt &LHS,202 const SlowDynamicAPInt &RHS) {203 if (RHS == -1)204 return -LHS;205 unsigned Width = getMaxWidth(LHS.Val, RHS.Val);206 return SlowDynamicAPInt(APIntOps::RoundingSDiv(207 LHS.Val.sext(Width), RHS.Val.sext(Width), APInt::Rounding::DOWN));208}209// The RHS is always expected to be positive, and the result210/// is always non-negative.211SlowDynamicAPInt llvm::detail::mod(const SlowDynamicAPInt &LHS,212 const SlowDynamicAPInt &RHS) {213 assert(RHS >= 1 && "mod is only supported for positive divisors!");214 return LHS % RHS < 0 ? LHS % RHS + RHS : LHS % RHS;215}216 217SlowDynamicAPInt llvm::detail::gcd(const SlowDynamicAPInt &A,218 const SlowDynamicAPInt &B) {219 assert(A >= 0 && B >= 0 && "operands must be non-negative!");220 unsigned Width = getMaxWidth(A.Val, B.Val);221 return SlowDynamicAPInt(222 APIntOps::GreatestCommonDivisor(A.Val.sext(Width), B.Val.sext(Width)));223}224 225/// Returns the least common multiple of A and B.226SlowDynamicAPInt llvm::detail::lcm(const SlowDynamicAPInt &A,227 const SlowDynamicAPInt &B) {228 SlowDynamicAPInt X = abs(A);229 SlowDynamicAPInt Y = abs(B);230 return (X * Y) / gcd(X, Y);231}232 233/// This operation cannot overflow.234SlowDynamicAPInt SlowDynamicAPInt::operator%(const SlowDynamicAPInt &O) const {235 unsigned Width = std::max(Val.getBitWidth(), O.Val.getBitWidth());236 return SlowDynamicAPInt(Val.sext(Width).srem(O.Val.sext(Width)));237}238 239SlowDynamicAPInt SlowDynamicAPInt::operator-() const {240 if (Val.isMinSignedValue()) {241 /// Overflow only occurs when the value is the minimum possible value.242 APInt Ret = Val.sext(2 * Val.getBitWidth());243 return SlowDynamicAPInt(-Ret);244 }245 return SlowDynamicAPInt(-Val);246}247 248/// ---------------------------------------------------------------------------249/// Assignment operators, preincrement, predecrement.250/// ---------------------------------------------------------------------------251SlowDynamicAPInt &SlowDynamicAPInt::operator+=(const SlowDynamicAPInt &O) {252 *this = *this + O;253 return *this;254}255SlowDynamicAPInt &SlowDynamicAPInt::operator-=(const SlowDynamicAPInt &O) {256 *this = *this - O;257 return *this;258}259SlowDynamicAPInt &SlowDynamicAPInt::operator*=(const SlowDynamicAPInt &O) {260 *this = *this * O;261 return *this;262}263SlowDynamicAPInt &SlowDynamicAPInt::operator/=(const SlowDynamicAPInt &O) {264 *this = *this / O;265 return *this;266}267SlowDynamicAPInt &SlowDynamicAPInt::operator%=(const SlowDynamicAPInt &O) {268 *this = *this % O;269 return *this;270}271SlowDynamicAPInt &SlowDynamicAPInt::operator++() {272 *this += 1;273 return *this;274}275 276SlowDynamicAPInt &SlowDynamicAPInt::operator--() {277 *this -= 1;278 return *this;279}280 281/// ---------------------------------------------------------------------------282/// Printing.283/// ---------------------------------------------------------------------------284void SlowDynamicAPInt::print(raw_ostream &OS) const { OS << Val; }285 286#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)287LLVM_DUMP_METHOD void SlowDynamicAPInt::dump() const { print(dbgs()); }288#endif289