[APInt] Add helpers for rounding u/sdivs.

[sanjoy]

llvm/include/llvm/ADT/APInt.h

2160

Nit: rounding

Did you consider implementing these in sdiv and udiv and passing in a defaulted Rounded parameter? That seems a bit cleaner to me.

Otherwise can you please add comments on sdiv and udiv about their rounding behavior?

llvm/lib/Support/APInt.cpp

2686

I'm wondering if this can be simplified. Is this logic correct:

Q, R = sdivrem(A, B);
if (R == 0) { return Q; }
if (Q < 0) { return RoundDown ? Q-1:Q; }
return RoundDown ? Q:Q-1;

the logic being that if R != 0 then the quotient is "off by one" depending on its sign.

[timshen]

Updated comments.

[timshen]

llvm/include/llvm/ADT/APInt.h

2160

Did you consider implementing these in sdiv and udiv and passing in a defaulted Rounded parameter? That seems a bit cleaner to me.

I thought about it, but it seems bad to just add complexity to the current APInt API, especially when we didn't find more usage.

APIntOps, on the other hand, are considered by me a set of helpers built on the top of APInt, therefore not adding API complexity to APInt itself.

Otherwise can you please add comments on sdiv and udiv about their rounding behavior?

I'm not sure if the behavior is intentionally not promised to the user, or just undocumented.

llvm/lib/Support/APInt.cpp

2686

I'm not sure, as the divisor maybe positive or negative. I found it difficult to prove.

Notice that the current algorithm is easy to prove, as it doesn't care whether sdiv rounds towards zero, or down, or up (I changed the comment to make that clear). As long as Quo * B + Rem = A holds, this algorithm is correct.

[sanjoy]

lgtm

llvm/include/llvm/ADT/APInt.h

2160

APIntOps, on the other hand, are considered by me a set of helpers built on the top of APInt, therefore not adding API complexity to APInt itself.

SGTM

I'm not sure if the behavior is intentionally not promised to the user, or just undocumented.

But you're relying on it right, when the users requests TOWARDS_ZERO?

llvm/lib/Support/APInt.cpp

2680

Nit: rounding

[timshen]

Updated comments.

[timshen]

llvm/include/llvm/ADT/APInt.h

2160

Done. Added rounding guarantee to udiv and sdiv.

llvm/lib/Support/APInt.cpp

2680

Removed. Those should be decl comments, not def comments.

[lebedev.ri]

llvm/trunk/unittests/ADT/APIntTest.cpp

2299 ↗

(On Diff #152807)

This doesn't do what you think it does..
In reality this inner loop simply never runs.

2307 ↗

(On Diff #152807)

This always asserts.

llvm/include/llvm/ADT/APInt.h

public:
   /// This enum is used to hold the constants we needed for APInt.
   enum : unsigned {
     /// Byte size of a word.
     APINT_WORD_SIZE = sizeof(WordType),
     /// Bits in a word.
     APINT_BITS_PER_WORD = APINT_WORD_SIZE * CHAR_BIT
   };
 
+  enum class Rounding {
+    DOWN,
+    TOWARD_ZERO,
+    UP,
+  };
+
   static const WordType WORD_MAX = ~WordType(0);
 
 private:
   /// This union is used to store the integer value. When the
   /// integer bit-width <= 64, it uses VAL, otherwise it uses pVal.
   union {
     uint64_t VAL;   ///< Used to store the <= 64 bits integer value.
     uint64_t *pVal; ///< Used to store the >64 bits integer value.

 
 /// Converts a float value into a APInt.
 ///
 /// Converts a float value into an APInt value.
 inline APInt RoundFloatToAPInt(float Float, unsigned width) {
   return RoundDoubleToAPInt(double(Float), width);
 }
 
+/// Return A unsign-divided by B, rounded by the given rounding mode.
+APInt RoundingUDiv(const APInt &A, const APInt &B, APInt::Rounding RM);
+
+/// Return A sign-divided by B, rounded by the given rounding mode.
+APInt RoundingSDiv(const APInt &A, const APInt &B, APInt::Rounding RM);
+
 } // End of APIntOps namespace
 
 // See friend declaration above. This additional declaration is required in
 // order to compile LLVM with IBM xlC compiler.
 hash_code hash_value(const APInt &Arg);
 } // End of llvm namespace
 
 #endif

llvm/lib/Support/APInt.cpp

void APInt::tcSetLeastSignificantBits(WordType *dst, unsigned parts,
   }
 
   if (bits)
     dst[i++] = ~(WordType) 0 >> (APINT_BITS_PER_WORD - bits);
 
   while (i < parts)
     dst[i++] = 0;
 }
+
+/// Return A unsign-divided by B, rounded by the given roundining mode.
+APInt llvm::APIntOps::RoundingUDiv(const APInt &A, const APInt &B,
+                                   APInt::Rounding RM) {
+  // Currently udivrem always rounds down.
+  switch (RM) {
+  case APInt::Rounding::DOWN:
+  case APInt::Rounding::TOWARD_ZERO:
+    return A.udiv(B);
+  case APInt::Rounding::UP: {
+    APInt Quo, Rem;
+    APInt::udivrem(A, B, Quo, Rem);
+    if (Rem == 0)
+      return Quo;
+    return Quo + 1;
+  }
+  }
+}
+
+/// Return A sign-divided by B, rounded by the given roundining mode.
+APInt llvm::APIntOps::RoundingSDiv(const APInt &A, const APInt &B,
+                                   APInt::Rounding RM) {
+  switch (RM) {
+  case APInt::Rounding::DOWN:
+  case APInt::Rounding::UP: {
+    APInt Quo, Rem;
+    APInt::sdivrem(A, B, Quo, Rem);
+    if (Rem == 0)
+      return Quo;
+    // This algorithm deals with arbitrary rounding mode used by sdivrem.
+    // We want to check whether the non-integer part of the mathematical value
+    // is negative or not. If the non-integer part is negative, we need to round
+    // down from Quo; otherwise, if it's positive or 0, we return Quo, as it's
+    // already rounded down.
+    if (RM == APInt::Rounding::DOWN) {
+      if (Rem.isNegative() != B.isNegative())
+        return Quo - 1;
+      return Quo;
+    }
+    if (Rem.isNegative() != B.isNegative())
+      return Quo;
+    return Quo + 1;
+  }
+  // Currently sdiv rounds twards zero.
+  case APInt::Rounding::TOWARD_ZERO:
+    return A.sdiv(B);
+  }
+}

llvm/unittests/ADT/APIntTest.cpp

TEST(APIntTest, multiply) {
 
   APInt i96 = APInt::getOneBitSet(96, 64);
   i96 *= ~0ULL;
   EXPECT_EQ(32U, i96.countLeadingOnes());
   EXPECT_EQ(32U, i96.countPopulation());
   EXPECT_EQ(64U, i96.countTrailingZeros());
 }
 
+TEST(APIntTest, RoundingUDiv) {
+  for (uint64_t Ai = 1; Ai <= 255; Ai++) {
+    APInt A(8, Ai);
+    APInt Zero(8, 0);
+    EXPECT_EQ(0, APIntOps::RoundingUDiv(Zero, A, APInt::Rounding::UP));
+    EXPECT_EQ(0, APIntOps::RoundingUDiv(Zero, A, APInt::Rounding::DOWN));
+    EXPECT_EQ(0, APIntOps::RoundingUDiv(Zero, A, APInt::Rounding::TOWARD_ZERO));
+
+    for (uint64_t Bi = 1; Bi <= 255; Bi++) {
+      APInt B(8, Bi);
+      {
+        APInt Quo = APIntOps::RoundingUDiv(A, B, APInt::Rounding::UP);
+        auto Prod = Quo.zext(16) * B.zext(16);
+        EXPECT_TRUE(Prod.uge(Ai));
+        if (Prod.ugt(Ai)) {
+          EXPECT_TRUE(((Quo - 1).zext(16) * B.zext(16)).ult(Ai));
+        }
+      }
+      {
+        APInt Quo = A.udiv(B);
+        EXPECT_EQ(Quo, APIntOps::RoundingUDiv(A, B, APInt::Rounding::TOWARD_ZERO));
+        EXPECT_EQ(Quo, APIntOps::RoundingUDiv(A, B, APInt::Rounding::DOWN));
+      }
+    }
+  }
+}
+
+TEST(APIntTest, RoundingSDiv) {
+  for (int64_t Ai = -128; Ai <= 127; Ai++) {
+    APInt A(8, Ai);
+
+    if (Ai != 0) {
+      APInt Zero(8, 0);
+      EXPECT_EQ(0, APIntOps::RoundingSDiv(Zero, A, APInt::Rounding::UP));
+      EXPECT_EQ(0, APIntOps::RoundingSDiv(Zero, A, APInt::Rounding::DOWN));
+      EXPECT_EQ(0, APIntOps::RoundingSDiv(Zero, A, APInt::Rounding::TOWARD_ZERO));
+    }
+
+    for (uint64_t Bi = -128; Bi <= 127; Bi++) {
+      if (Bi == 0)
+        continue;
+
+      APInt B(8, Bi);
+      {
+        APInt Quo = APIntOps::RoundingSDiv(A, B, APInt::Rounding::UP);
+        auto Prod = Quo.sext(16) * B.sext(16);
+        EXPECT_TRUE(Prod.uge(A));
+        if (Prod.ugt(A)) {
+          EXPECT_TRUE(((Quo - 1).sext(16) * B.sext(16)).ult(A));
+        }
+      }
+      {
+        APInt Quo = APIntOps::RoundingSDiv(A, B, APInt::Rounding::DOWN);
+        auto Prod = Quo.sext(16) * B.sext(16);
+        EXPECT_TRUE(Prod.ule(A));
+        if (Prod.ult(A)) {
+          EXPECT_TRUE(((Quo + 1).sext(16) * B.sext(16)).ugt(A));
+        }
+      }
+      {
+        APInt Quo = A.sdiv(B);
+        EXPECT_EQ(Quo, APIntOps::RoundingSDiv(A, B, APInt::Rounding::TOWARD_ZERO));
+      }
+    }
+  }
+}
+
 } // end anonymous namespace