[APInt] Add support for dividing or remainder by a uint64_t or int64_t.

Summary:
This patch adds udiv/sdiv/urem/srem/udivrem/sdivrem methods that can divide by a uint64_t. This makes division consistent with all the other arithmetic operations.

This modifies the interface of the divide helper method to work on raw arrays instead of APInts. This way we can pass the uint64_t in for the RHS without wrapping it in an APInt. This required moving all the Quotient and Remainder allocation handling up to the callers. For udiv/urem this was as simple as just creating the Quotient/Remainder with the right size when they were declared. For udivrem we have to rely on reallocate not changing the contents of the variable LHS or RHS is aliased with the Quotient or Remainder APInts. We also have to zero the upper bits of Remainder and Quotient that divide doesn't write to if lhsWords/rhsWords is smaller than the width.

I've update the toString method to use the new udivrem.

Reviewers: hans, dblaikie, RKSimon

Reviewed By: RKSimon

Subscribers: llvm-commits

Differential Revision: https://reviews.llvm.org/D33310

llvm-svn: 303431

1 files changed, 58 insertions, 0 deletions

diff --git a/llvm/unittests/ADT/APIntTest.cpp b/llvm/unittests/ADT/APIntTest.cpp
index 5594955e7ba..05fad386064 100644
--- a/llvm/unittests/ADT/APIntTest.cpp
+++ b/llvm/unittests/ADT/APIntTest.cpp
@@ -1002,6 +1002,64 @@ TEST(APIntTest, divrem_big7) {
           {224, "80000000800000010000000f", 16});
 }
 
+void testDiv(APInt a, uint64_t b, APInt c) {
+  auto p = a * b + c;
+
+  APInt q;
+  uint64_t r;
+  // Unsigned division will only work if our original number wasn't negative.
+  if (!a.isNegative()) {
+    q = p.udiv(b);
+    r = p.urem(b);
+    EXPECT_EQ(a, q);
+    EXPECT_EQ(c, r);
+    APInt::udivrem(p, b, q, r);
+    EXPECT_EQ(a, q);
+    EXPECT_EQ(c, r);
+  }
+  q = p.sdiv(b);
+  r = p.srem(b);
+  EXPECT_EQ(a, q);
+  if (c.isNegative())
+    EXPECT_EQ(-c, -r); // Need to negate so the uint64_t compare will work.
+  else
+    EXPECT_EQ(c, r);
+  int64_t sr;
+  APInt::sdivrem(p, b, q, sr);
+  EXPECT_EQ(a, q);
+  if (c.isNegative())
+    EXPECT_EQ(-c, -sr); // Need to negate so the uint64_t compare will work.
+  else
+    EXPECT_EQ(c, sr);
+}
+
+TEST(APIntTest, divremuint) {
+  // Single word APInt
+  testDiv(APInt{64, 9},
+          2,
+          APInt{64, 1});
+
+  // Single word negative APInt
+  testDiv(-APInt{64, 9},
+          2,
+          -APInt{64, 1});
+
+  // Multiword dividend with only one significant word.
+  testDiv(APInt{256, 9},
+          2,
+          APInt{256, 1});
+
+  // Negative dividend.
+  testDiv(-APInt{256, 9},
+          2,
+          -APInt{256, 1});
+
+  // Multiword dividend
+  testDiv(APInt{1024, 19}.shl(811),
+          4356013, // one word
+          APInt{1024, 1});
+}
+
 TEST(APIntTest, fromString) {
   EXPECT_EQ(APInt(32, 0), APInt(32,   "0", 2));
   EXPECT_EQ(APInt(32, 1), APInt(32,   "1", 2));