Fix APInt division algorithm

[chfast]

Summary

APInt uses Knuth's D algorithm for long division. In rare cases the implementation applied a transformation that was not needed.

[chfast]

Ping!

[yaron.keren]

Minor nitpicks, LGTM.

lib/Support/APInt.cpp

1510

Could b be LLVM_CONSTEXPR ?

1583

The parenthesis around the shift make the expression more readable, even if not required.

You flipped the | arguments so they would consistent with the usual u[j+n], u[j+n-1]...u[j] representation?

1786

I'd remove the FIXME and explain that *currently* this is a dead case since all callers in APInt calls either test for divide() with lhswords == rhswords == 1 or proivde the a small radix before calling divide() but it is worth keeping this code alive for correctness in case some new code does call divide() with lhswords == rhswords == 1.

[chfast]

lib/Support/APInt.cpp

1510

Probably. I'm not used to constexpr because Visual Studio still does not support it.

1583

I flipped arguments because I like high word being on the left. You shift left to make space for a low word.

1786

Ok, I will change that. I'm just a bit worried that this code cannot be reached with unittests.

[chfast]

Applied suggestions by yaron.keren.

Can you submit the patch for me?

[yaron.keren]

Sure, committed revision 233312.

lib/Support/APInt.cpp

 /// from "Art of Computer Programming, Volume 2", section 4.3.1, p. 272. The
 /// variables here have the same names as in the algorithm. Comments explain
 /// the algorithm and any deviation from it.
 static void KnuthDiv(unsigned *u, unsigned *v, unsigned *q, unsigned* r,
                      unsigned m, unsigned n) {
   assert(u && "Must provide dividend");
   assert(v && "Must provide divisor");
   assert(q && "Must provide quotient");
-  assert(u != v && u != q && v != q && "Must us different memory");
+  assert(u != v && u != q && v != q && "Must use different memory");
   assert(n>1 && "n must be > 1");
 
-  // Knuth uses the value b as the base of the number system. In our case b
-  // is 2^31 so we just set it to -1u.
-  uint64_t b = uint64_t(1) << 32;
+  // b denotes the base of the number system. In our case b is 2^32.
+  LLVM_CONSTEXPR uint64_t b = uint64_t(1) << 32;
 
-#if 0
   DEBUG(dbgs() << "KnuthDiv: m=" << m << " n=" << n << '\n');
   DEBUG(dbgs() << "KnuthDiv: original:");
   DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
   DEBUG(dbgs() << " by");
   DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]);
   DEBUG(dbgs() << '\n');
-#endif
   // D1. [Normalize.] Set d = b / (v[n-1] + 1) and multiply all the digits of
   // u and v by d. Note that we have taken Knuth's advice here to use a power
   // of 2 value for d such that d * v[n-1] >= b/2 (b is the base). A power of
   // 2 allows us to shift instead of multiply and it is easy to determine the
   // shift amount from the leading zeros.  We are basically normalizing the u
   // and v so that its high bits are shifted to the top of v's range without
   // overflow. Note that this can require an extra word in u so that u must
   // be of length m+n+1.
   unsigned shift = countLeadingZeros(v[n-1]);
   unsigned v_carry = 0;
   unsigned u_carry = 0;
   if (shift) {
     for (unsigned i = 0; i < m+n; ++i) {
       unsigned u_tmp = u[i] >> (32 - shift);
       u[i] = (u[i] << shift) | u_carry;
       u_carry = u_tmp;
     }
     for (unsigned i = 0; i < n; ++i) {
       unsigned v_tmp = v[i] >> (32 - shift);
       v[i] = (v[i] << shift) | v_carry;
       v_carry = v_tmp;
     }
   }
   u[m+n] = u_carry;
-#if 0
+
   DEBUG(dbgs() << "KnuthDiv:   normal:");
   DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
   DEBUG(dbgs() << " by");
   DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]);
   DEBUG(dbgs() << '\n');
-#endif
 
   // D2. [Initialize j.]  Set j to m. This is the loop counter over the places.
   int j = m;
   do {
     DEBUG(dbgs() << "KnuthDiv: quotient digit #" << j << '\n');
     // D3. [Calculate q'.].
     //     Set qp = (u[j+n]*b + u[j+n-1]) / v[n-1]. (qp=qprime=q')
     //     Set rp = (u[j+n]*b + u[j+n-1]) % v[n-1]. (rp=rprime=r')
if (qp == b || qp*v[n-2] > b*rp + u[j+n-2]) {
         qp--;
     }
     DEBUG(dbgs() << "KnuthDiv: qp == " << qp << ", rp == " << rp << '\n');
 
     // D4. [Multiply and subtract.] Replace (u[j+n]u[j+n-1]...u[j]) with
     // (u[j+n]u[j+n-1]..u[j]) - qp * (v[n-1]...v[1]v[0]). This computation
     // consists of a simple multiplication by a one-place number, combined with
     // a subtraction.
+    // The digits (u[j+n]...u[j]) should be kept positive; if the result of
+    // this step is actually negative, (u[j+n]...u[j]) should be left as the
+    // true value plus b**(n+1), namely as the b's complement of
+    // the true value, and a "borrow" to the left should be remembered.
     bool isNeg = false;
     for (unsigned i = 0; i < n; ++i) {
-      uint64_t u_tmp = uint64_t(u[j+i]) | (uint64_t(u[j+i+1]) << 32);
+      uint64_t u_tmp = (uint64_t(u[j+i+1]) << 32) | uint64_t(u[j+i]);
       uint64_t subtrahend = uint64_t(qp) * uint64_t(v[i]);
       bool borrow = subtrahend > u_tmp;
-      DEBUG(dbgs() << "KnuthDiv: u_tmp == " << u_tmp
-                   << ", subtrahend == " << subtrahend
+      DEBUG(dbgs() << "KnuthDiv: u_tmp = " << u_tmp
+                   << ", subtrahend = " << subtrahend
                    << ", borrow = " << borrow << '\n');
 
       uint64_t result = u_tmp - subtrahend;
       unsigned k = j + i;
-      u[k++] = (unsigned)(result & (b-1)); // subtract low word
-      u[k++] = (unsigned)(result >> 32);   // subtract high word
-      while (borrow && k <= m+n) { // deal with borrow to the left
+      u[k++] = (unsigned)result;         // subtraction low word
+      u[k++] = (unsigned)(result >> 32); // subtraction high word
+      while (borrow && k <= m+n) {       // deal with borrow to the left
         borrow = u[k] == 0;
         u[k]--;
         k++;
       }
       isNeg |= borrow;
-      DEBUG(dbgs() << "KnuthDiv: u[j+i] == " << u[j+i] << ",  u[j+i+1] == " <<
-                    u[j+i+1] << '\n');
+      DEBUG(dbgs() << "KnuthDiv: u[j+i] = " << u[j+i] 
+                   << ", u[j+i+1] = " << u[j+i+1] << '\n');
     }
     DEBUG(dbgs() << "KnuthDiv: after subtraction:");
     DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
     DEBUG(dbgs() << '\n');
-    // The digits (u[j+n]...u[j]) should be kept positive; if the result of
-    // this step is actually negative, (u[j+n]...u[j]) should be left as the
-    // true value plus b**(n+1), namely as the b's complement of
-    // the true value, and a "borrow" to the left should be remembered.
-    //
-    if (isNeg) {
-      bool carry = true;  // true because b's complement is "complement + 1"
-      for (unsigned i = 0; i <= m+n; ++i) {
-        u[i] = ~u[i] + carry; // b's complement
-        carry = carry && u[i] == 0;
-      }
-    }
-    DEBUG(dbgs() << "KnuthDiv: after complement:");
-    DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
-    DEBUG(dbgs() << '\n');
 
     // D5. [Test remainder.] Set q[j] = qp. If the result of step D4 was
     // negative, go to step D6; otherwise go on to step D7.
     q[j] = (unsigned)qp;
     if (isNeg) {
       // D6. [Add back]. The probability that this step is necessary is very
       // small, on the order of only 2/b. Make sure that test data accounts for
       // this possibility. Decrease q[j] by 1
       q[j]--;
       // and add (0v[n-1]...v[1]v[0]) to (u[j+n]u[j+n-1]...u[j+1]u[j]).
       // A carry will occur to the left of u[j+n], and it should be ignored
       // since it cancels with the borrow that occurred in D4.
       bool carry = false;
       for (unsigned i = 0; i < n; i++) {
         unsigned limit = std::min(u[j+i],v[i]);
         u[j+i] += v[i] + carry;
         carry = u[j+i] < limit || (carry && u[j+i] == limit);
       }
       u[j+n] += carry;
     }
     DEBUG(dbgs() << "KnuthDiv: after correction:");
-    DEBUG(for (int i = m+n; i >=0; i--) dbgs() <<" " << u[i]);
+    DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
     DEBUG(dbgs() << "\nKnuthDiv: digit result = " << q[j] << '\n');
 
   // D7. [Loop on j.]  Decrease j by one. Now if j >= 0, go back to D3.
   } while (--j >= 0);
 
   DEBUG(dbgs() << "KnuthDiv: quotient:");
   DEBUG(for (int i = m; i >=0; i--) dbgs() <<" " << q[i]);
   DEBUG(dbgs() << '\n');
if (r) {
     } else {
       for (int i = n-1; i >= 0; i--) {
         r[i] = u[i];
         DEBUG(dbgs() << " " << r[i]);
       }
     }
     DEBUG(dbgs() << '\n');
   }
-#if 0
   DEBUG(dbgs() << '\n');
-#endif
 }
 
 void APInt::divide(const APInt LHS, unsigned lhsWords,
                    const APInt &RHS, unsigned rhsWords,
                    APInt *Quotient, APInt *Remainder)
 {
   assert(lhsWords >= rhsWords && "Fractional result");
 
if (Quotient->BitWidth != LHS.BitWidth) {
       Quotient->BitWidth = LHS.BitWidth;
       if (!Quotient->isSingleWord())
         Quotient->pVal = getClearedMemory(Quotient->getNumWords());
     } else
       Quotient->clearAllBits();
 
     // The quotient is in Q. Reconstitute the quotient into Quotient's low
     // order words.
+    // This case is currently dead as all users of divide() handle trivial cases
+    // earlier.
     if (lhsWords == 1) {
       uint64_t tmp =
         uint64_t(Q[0]) | (uint64_t(Q[1]) << (APINT_BITS_PER_WORD / 2));
       if (Quotient->isSingleWord())
         Quotient->VAL = tmp;
       else
         Quotient->pVal[0] = tmp;
     } else {
       assert(!Quotient->isSingleWord() && "Quotient APInt not large enough");

unittests/ADT/APIntTest.cpp

TEST(APIntTest, i1) {
   EXPECT_EQ(-four, q);
   EXPECT_EQ(one, r);
   APInt::sdivrem(-nine, -two, q, r);
   EXPECT_EQ(four, q);
   EXPECT_EQ(-one, r);
   }
 }
 
+TEST(APIntTest, divrem_big1) {
+  // Tests KnuthDiv rare step D6
+  APInt a{256, "1ffffffffffffffff", 16};
+  APInt b{256, "1ffffffffffffffff", 16};
+  APInt c{256, 0};
+
+  auto p = a * b + c;
+  auto q = p.udiv(a);
+  auto r = p.urem(a);
+  EXPECT_EQ(q, b);
+  EXPECT_EQ(r, c);
+  APInt::udivrem(p, a, q, r);
+  EXPECT_EQ(q, b);
+  EXPECT_EQ(r, c);
+  q = p.udiv(b);
+  r = p.urem(b);
+  EXPECT_EQ(q, a);
+  EXPECT_EQ(r, c);
+  APInt::udivrem(p, b, q, r);
+  EXPECT_EQ(q, a);
+  EXPECT_EQ(r, c);
+  q = p.sdiv(a);
+  r = p.srem(a);
+  EXPECT_EQ(q, b);
+  EXPECT_EQ(r, c);
+  APInt::sdivrem(p, a, q, r);
+  EXPECT_EQ(q, b);
+  EXPECT_EQ(r, c);
+  q = p.sdiv(b);
+  r = p.srem(b);
+  EXPECT_EQ(q, a);
+  EXPECT_EQ(r, c);
+  APInt::sdivrem(p, b, q, r);
+  EXPECT_EQ(q, a);
+  EXPECT_EQ(r, c);
+}
+
+TEST(APIntTest, divrem_big2) {
+  // Tests KnuthDiv rare step D6
+  APInt a{1024,           "111111ffffffffffffffff"
+                "ffffffffffffffffffffffffffffffff"
+                "fffffffffffffffffffffffffffffccf"
+                "ffffffffffffffffffffffffffffff00", 16};
+  APInt b{1024,                       "112233ceff"
+                "cecece000000ffffffffffffffffffff"
+                "ffffffffffffffffffffffffffffffff"
+                "ffffffffffffffffffffffffffffffff"
+                "ffffffffffffffffffffffffffffff33", 16};
+  APInt c{1024, 7919};
+
+  auto p = a * b + c;
+  auto q = p.udiv(a);
+  auto r = p.urem(a);
+  EXPECT_EQ(q, b);
+  EXPECT_EQ(r, c);
+  APInt::udivrem(p, a, q, r);
+  EXPECT_EQ(q, b);
+  EXPECT_EQ(r, c);
+  q = p.udiv(b);
+  r = p.urem(b);
+  EXPECT_EQ(q, a);
+  EXPECT_EQ(r, c);
+  APInt::udivrem(p, b, q, r);
+  EXPECT_EQ(q, a);
+  EXPECT_EQ(r, c);
+  q = p.sdiv(a);
+  r = p.srem(a);
+  EXPECT_EQ(q, b);
+  EXPECT_EQ(r, c);
+  APInt::sdivrem(p, a, q, r);
+  EXPECT_EQ(q, b);
+  EXPECT_EQ(r, c);
+  q = p.sdiv(b);
+  r = p.srem(b);
+  EXPECT_EQ(q, a);
+  EXPECT_EQ(r, c);
+  APInt::sdivrem(p, b, q, r);
+  EXPECT_EQ(q, a);
+  EXPECT_EQ(r, c);
+}
+
+TEST(APIntTest, divrem_big3) {
+  // Tests KnuthDiv case without shift
+  APInt a{256, "ffffffffffffff0000000", 16};
+  APInt b{256, "80000001ffffffffffffffff", 16};
+  APInt c{256, 4219};
+
+  auto p = a * b + c;
+  auto q = p.udiv(a);
+  auto r = p.urem(a);
+  EXPECT_EQ(q, b);
+  EXPECT_EQ(r, c);
+  APInt::udivrem(p, a, q, r);
+  EXPECT_EQ(q, b);
+  EXPECT_EQ(r, c);
+  q = p.udiv(b);
+  r = p.urem(b);
+  EXPECT_EQ(q, a);
+  EXPECT_EQ(r, c);
+  APInt::udivrem(p, b, q, r);
+  EXPECT_EQ(q, a);
+  EXPECT_EQ(r, c);
+  q = p.sdiv(a);
+  r = p.srem(a);
+  EXPECT_EQ(q, b);
+  EXPECT_EQ(r, c);
+  APInt::sdivrem(p, a, q, r);
+  EXPECT_EQ(q, b);
+  EXPECT_EQ(r, c);
+  q = p.sdiv(b);
+  r = p.srem(b);
+  EXPECT_EQ(q, a);
+  EXPECT_EQ(r, c);
+  APInt::sdivrem(p, b, q, r);
+  EXPECT_EQ(q, a);
+  EXPECT_EQ(r, c);
+}
+
+TEST(APIntTest, divrem_big4) {
+  // Tests heap allocation in divide() enfoced by huge numbers
+  auto a = APInt{4096, 1}.shl(2000);
+  auto b = APInt{4096, 5}.shl(2001);
+  auto c = APInt{4096, 4219*13};
+
+  auto p = a * b + c;
+  auto q = p.udiv(a);
+  auto r = p.urem(a);
+  EXPECT_EQ(q, b);
+  EXPECT_EQ(r, c);
+  q = APInt{1024, 0}; // test non-single word APInt conversion in divide()
+  r = APInt{1024, 0};
+  APInt::udivrem(p, a, q, r);
+  EXPECT_EQ(q, b);
+  EXPECT_EQ(r, c);
+  q = p.udiv(b);
+  r = p.urem(b);
+  EXPECT_EQ(q, a);
+  EXPECT_EQ(r, c);
+  q = APInt{1024, 0};
+  r = APInt{1024, 0};
+  APInt::udivrem(p, b, q, r);
+  EXPECT_EQ(q, a);
+  EXPECT_EQ(r, c);
+  q = p.sdiv(a);
+  r = p.srem(a);
+  EXPECT_EQ(q, b);
+  EXPECT_EQ(r, c);
+  q = APInt{1024, 0};
+  r = APInt{1024, 0};
+  APInt::sdivrem(p, a, q, r);
+  EXPECT_EQ(q, b);
+  EXPECT_EQ(r, c);
+  q = p.sdiv(b);
+  r = p.srem(b);
+  EXPECT_EQ(q, a);
+  EXPECT_EQ(r, c);
+  q = APInt{1024, 0};
+  r = APInt{1024, 0};
+  APInt::sdivrem(p, b, q, r);
+  EXPECT_EQ(q, a);
+  EXPECT_EQ(r, c);
+}
+
+TEST(APIntTest, divrem_big5) {
+  // Tests one word divisor case of divide()
+  auto a = APInt{1024, 19}.shl(811);
+  auto b = APInt{1024, 4356013}; // one word
+  auto c = APInt{1024, 1};
+
+  auto p = a * b + c;
+  auto q = p.udiv(a);
+  auto r = p.urem(a);
+  EXPECT_EQ(q, b);
+  EXPECT_EQ(r, c);
+  APInt::udivrem(p, a, q, r);
+  EXPECT_EQ(q, b);
+  EXPECT_EQ(r, c);
+  q = p.udiv(b);
+  r = p.urem(b);
+  EXPECT_EQ(q, a);
+  EXPECT_EQ(r, c);
+  APInt::udivrem(p, b, q, r);
+  EXPECT_EQ(q, a);
+  EXPECT_EQ(r, c);
+  q = p.sdiv(a);
+  r = p.srem(a);
+  EXPECT_EQ(q, b);
+  EXPECT_EQ(r, c);
+  APInt::sdivrem(p, a, q, r);
+  EXPECT_EQ(q, b);
+  EXPECT_EQ(r, c);
+  q = p.sdiv(b);
+  r = p.srem(b);
+  EXPECT_EQ(q, a);
+  EXPECT_EQ(r, c);
+  APInt::sdivrem(p, b, q, r);
+  EXPECT_EQ(q, a);
+  EXPECT_EQ(r, c);
+}
+
 TEST(APIntTest, fromString) {
   EXPECT_EQ(APInt(32, 0), APInt(32,   "0", 2));
   EXPECT_EQ(APInt(32, 1), APInt(32,   "1", 2));
   EXPECT_EQ(APInt(32, 2), APInt(32,  "10", 2));
   EXPECT_EQ(APInt(32, 3), APInt(32,  "11", 2));
   EXPECT_EQ(APInt(32, 4), APInt(32, "100", 2));
 
   EXPECT_EQ(APInt(32, 0), APInt(32,   "+0", 2));