[APInt] Add helpers for rounding u/sdivs.

[sanjoy]

llvm/include/llvm/ADT/APInt.h

2160 ↗

(On Diff #152519)

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 ↗

(On Diff #152519)

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 ↗

(On Diff #152519)

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 ↗

(On Diff #152519)

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 ↗

(On Diff #152519)

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 ↗

(On Diff #152762)

Nit: rounding

[timshen]

Updated comments.

[timshen]

llvm/include/llvm/ADT/APInt.h

2160 ↗

(On Diff #152519)

Done. Added rounding guarantee to udiv and sdiv.

llvm/lib/Support/APInt.cpp

2680 ↗

(On Diff #152762)

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

[lebedev.ri]

llvm/trunk/unittests/ADT/APIntTest.cpp

2299

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

2307

This always asserts.

llvm/trunk/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.
#endif
   /// Rotate right by rotateAmt.
   APInt rotr(const APInt &rotateAmt) const;
 
   /// Unsigned division operation.
   ///
   /// Perform an unsigned divide operation on this APInt by RHS. Both this and
   /// RHS are treated as unsigned quantities for purposes of this division.
   ///
-  /// \returns a new APInt value containing the division result
+  /// \returns a new APInt value containing the division result, rounded towards
+  /// zero.
   APInt udiv(const APInt &RHS) const;
   APInt udiv(uint64_t RHS) const;
 
   /// Signed division function for APInt.
   ///
   /// Signed divide this APInt by APInt RHS.
+  ///
+  /// The result is rounded towards zero.
   APInt sdiv(const APInt &RHS) const;
   APInt sdiv(int64_t RHS) const;
 
   /// Unsigned remainder operation.
   ///
   /// Perform an unsigned remainder operation on this APInt with RHS being the
   /// divisor. Both this and RHS are treated as unsigned quantities for purposes
   /// of this operation. Note that this is a true remainder operation and not a

 
 /// 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/trunk/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;
 }
+
+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;
+  }
+  }
+}
+
+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/trunk/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