llvm/lib/Support/SlowDynamicAPInt.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-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()); }