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-exception 6 // 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 14 using namespace llvm; 15 using namespace detail; 16 17 SlowDynamicAPInt::SlowDynamicAPInt(int64_t Val) 18 : Val(64, Val, /*isSigned=*/true) {} 19 SlowDynamicAPInt::SlowDynamicAPInt() : SlowDynamicAPInt(0) {} 20 SlowDynamicAPInt::SlowDynamicAPInt(const APInt &Val) : Val(Val) {} 21 SlowDynamicAPInt &SlowDynamicAPInt::operator=(int64_t Val) { 22 return *this = SlowDynamicAPInt(Val); 23 } 24 SlowDynamicAPInt::operator int64_t() const { return Val.getSExtValue(); } 25 26 hash_code detail::hash_value(const SlowDynamicAPInt &X) { 27 return hash_value(X.Val); 28 } 29 30 /// --------------------------------------------------------------------------- 31 /// Convenience operator overloads for int64_t. 32 /// --------------------------------------------------------------------------- 33 SlowDynamicAPInt &detail::operator+=(SlowDynamicAPInt &A, int64_t B) { 34 return A += SlowDynamicAPInt(B); 35 } 36 SlowDynamicAPInt &detail::operator-=(SlowDynamicAPInt &A, int64_t B) { 37 return A -= SlowDynamicAPInt(B); 38 } 39 SlowDynamicAPInt &detail::operator*=(SlowDynamicAPInt &A, int64_t B) { 40 return A *= SlowDynamicAPInt(B); 41 } 42 SlowDynamicAPInt &detail::operator/=(SlowDynamicAPInt &A, int64_t B) { 43 return A /= SlowDynamicAPInt(B); 44 } 45 SlowDynamicAPInt &detail::operator%=(SlowDynamicAPInt &A, int64_t B) { 46 return A %= SlowDynamicAPInt(B); 47 } 48 49 bool detail::operator==(const SlowDynamicAPInt &A, int64_t B) { 50 return A == SlowDynamicAPInt(B); 51 } 52 bool detail::operator!=(const SlowDynamicAPInt &A, int64_t B) { 53 return A != SlowDynamicAPInt(B); 54 } 55 bool detail::operator>(const SlowDynamicAPInt &A, int64_t B) { 56 return A > SlowDynamicAPInt(B); 57 } 58 bool detail::operator<(const SlowDynamicAPInt &A, int64_t B) { 59 return A < SlowDynamicAPInt(B); 60 } 61 bool detail::operator<=(const SlowDynamicAPInt &A, int64_t B) { 62 return A <= SlowDynamicAPInt(B); 63 } 64 bool detail::operator>=(const SlowDynamicAPInt &A, int64_t B) { 65 return A >= SlowDynamicAPInt(B); 66 } 67 SlowDynamicAPInt detail::operator+(const SlowDynamicAPInt &A, int64_t B) { 68 return A + SlowDynamicAPInt(B); 69 } 70 SlowDynamicAPInt detail::operator-(const SlowDynamicAPInt &A, int64_t B) { 71 return A - SlowDynamicAPInt(B); 72 } 73 SlowDynamicAPInt detail::operator*(const SlowDynamicAPInt &A, int64_t B) { 74 return A * SlowDynamicAPInt(B); 75 } 76 SlowDynamicAPInt detail::operator/(const SlowDynamicAPInt &A, int64_t B) { 77 return A / SlowDynamicAPInt(B); 78 } 79 SlowDynamicAPInt detail::operator%(const SlowDynamicAPInt &A, int64_t B) { 80 return A % SlowDynamicAPInt(B); 81 } 82 83 bool detail::operator==(int64_t A, const SlowDynamicAPInt &B) { 84 return SlowDynamicAPInt(A) == B; 85 } 86 bool detail::operator!=(int64_t A, const SlowDynamicAPInt &B) { 87 return SlowDynamicAPInt(A) != B; 88 } 89 bool detail::operator>(int64_t A, const SlowDynamicAPInt &B) { 90 return SlowDynamicAPInt(A) > B; 91 } 92 bool detail::operator<(int64_t A, const SlowDynamicAPInt &B) { 93 return SlowDynamicAPInt(A) < B; 94 } 95 bool detail::operator<=(int64_t A, const SlowDynamicAPInt &B) { 96 return SlowDynamicAPInt(A) <= B; 97 } 98 bool detail::operator>=(int64_t A, const SlowDynamicAPInt &B) { 99 return SlowDynamicAPInt(A) >= B; 100 } 101 SlowDynamicAPInt detail::operator+(int64_t A, const SlowDynamicAPInt &B) { 102 return SlowDynamicAPInt(A) + B; 103 } 104 SlowDynamicAPInt detail::operator-(int64_t A, const SlowDynamicAPInt &B) { 105 return SlowDynamicAPInt(A) - B; 106 } 107 SlowDynamicAPInt detail::operator*(int64_t A, const SlowDynamicAPInt &B) { 108 return SlowDynamicAPInt(A) * B; 109 } 110 SlowDynamicAPInt detail::operator/(int64_t A, const SlowDynamicAPInt &B) { 111 return SlowDynamicAPInt(A) / B; 112 } 113 SlowDynamicAPInt detail::operator%(int64_t A, const SlowDynamicAPInt &B) { 114 return SlowDynamicAPInt(A) % B; 115 } 116 117 static 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. 126 bool SlowDynamicAPInt::operator==(const SlowDynamicAPInt &O) const { 127 unsigned Width = getMaxWidth(Val, O.Val); 128 return Val.sext(Width) == O.Val.sext(Width); 129 } 130 bool SlowDynamicAPInt::operator!=(const SlowDynamicAPInt &O) const { 131 unsigned Width = getMaxWidth(Val, O.Val); 132 return Val.sext(Width) != O.Val.sext(Width); 133 } 134 bool SlowDynamicAPInt::operator>(const SlowDynamicAPInt &O) const { 135 unsigned Width = getMaxWidth(Val, O.Val); 136 return Val.sext(Width).sgt(O.Val.sext(Width)); 137 } 138 bool SlowDynamicAPInt::operator<(const SlowDynamicAPInt &O) const { 139 unsigned Width = getMaxWidth(Val, O.Val); 140 return Val.sext(Width).slt(O.Val.sext(Width)); 141 } 142 bool SlowDynamicAPInt::operator<=(const SlowDynamicAPInt &O) const { 143 unsigned Width = getMaxWidth(Val, O.Val); 144 return Val.sext(Width).sle(O.Val.sext(Width)); 145 } 146 bool 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 and 157 /// call op(a, b, overflow), returning its result. The operation with double 158 /// widths should not also overflow. 159 APInt 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 174 SlowDynamicAPInt SlowDynamicAPInt::operator+(const SlowDynamicAPInt &O) const { 175 return SlowDynamicAPInt( 176 runOpWithExpandOnOverflow(Val, O.Val, std::mem_fn(&APInt::sadd_ov))); 177 } 178 SlowDynamicAPInt SlowDynamicAPInt::operator-(const SlowDynamicAPInt &O) const { 179 return SlowDynamicAPInt( 180 runOpWithExpandOnOverflow(Val, O.Val, std::mem_fn(&APInt::ssub_ov))); 181 } 182 SlowDynamicAPInt SlowDynamicAPInt::operator*(const SlowDynamicAPInt &O) const { 183 return SlowDynamicAPInt( 184 runOpWithExpandOnOverflow(Val, O.Val, std::mem_fn(&APInt::smul_ov))); 185 } 186 SlowDynamicAPInt SlowDynamicAPInt::operator/(const SlowDynamicAPInt &O) const { 187 return SlowDynamicAPInt( 188 runOpWithExpandOnOverflow(Val, O.Val, std::mem_fn(&APInt::sdiv_ov))); 189 } 190 SlowDynamicAPInt detail::abs(const SlowDynamicAPInt &X) { 191 return X >= 0 ? X : -X; 192 } 193 SlowDynamicAPInt 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 } 201 SlowDynamicAPInt 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 result 210 /// is always non-negative. 211 SlowDynamicAPInt 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 217 SlowDynamicAPInt 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. 226 SlowDynamicAPInt 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. 234 SlowDynamicAPInt 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 239 SlowDynamicAPInt 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 /// --------------------------------------------------------------------------- 251 SlowDynamicAPInt &SlowDynamicAPInt::operator+=(const SlowDynamicAPInt &O) { 252 *this = *this + O; 253 return *this; 254 } 255 SlowDynamicAPInt &SlowDynamicAPInt::operator-=(const SlowDynamicAPInt &O) { 256 *this = *this - O; 257 return *this; 258 } 259 SlowDynamicAPInt &SlowDynamicAPInt::operator*=(const SlowDynamicAPInt &O) { 260 *this = *this * O; 261 return *this; 262 } 263 SlowDynamicAPInt &SlowDynamicAPInt::operator/=(const SlowDynamicAPInt &O) { 264 *this = *this / O; 265 return *this; 266 } 267 SlowDynamicAPInt &SlowDynamicAPInt::operator%=(const SlowDynamicAPInt &O) { 268 *this = *this % O; 269 return *this; 270 } 271 SlowDynamicAPInt &SlowDynamicAPInt::operator++() { 272 *this += 1; 273 return *this; 274 } 275 276 SlowDynamicAPInt &SlowDynamicAPInt::operator--() { 277 *this -= 1; 278 return *this; 279 } 280 281 /// --------------------------------------------------------------------------- 282 /// Printing. 283 /// --------------------------------------------------------------------------- 284 void SlowDynamicAPInt::print(raw_ostream &OS) const { OS << Val; } 285 286 void SlowDynamicAPInt::dump() const { print(dbgs()); } 287