Fix modules build with different technique to suppress Knuth debugging

[t.p.northover]

Summary

Currently we use #pragma push_macro(LLVM_DEBUG) to fiddle with the LLVM_DEBUG macro so that we can silence debugging the Knuth division algorithm unless it's actually desired. Unfortunately this is incompatible with enabling modules while building LLVM (via LLVM_ENABLE_MODULES=ON) because the macro then has incompatible definitions in a single translation unit.

This patch changes the Knuth division function to use a special KNUTH_DEBUG throughout, which can be #defined to LLVM_DEBUG if debug output is desired. A default implementation doing nothing is provided locally (rather than in include/llvm/Support/Debug.h).

[kristina]

This looks great, currently unable to build without manually fixing it as we do modular builds. I don't think those backslashes are within 80 col limit but otherwise LGTM.

(Looking closely seems that it's Phabricator rendering them oddly, excuse the previous remark)

[kristina]

I don't have commit access but this fixes modular builds and is essentially NFC, so I don't think it needs any further review and is ready to land as-is. The whitespace comment was wrong since just seems to be a Phabricator quirk.

[teemperor]

We could also land the original version of the patch that introduced this. It didn't contain the push/pop_macro and wouldn't change the functionality to people actually using KNUTH_DEBUG. https://reviews.llvm.org/D40404?id=124114 But I'm fine with both.

Unfortunately this is incompatible with enabling modules while building LLVM (via LLVM_ENABLE_MODULES=ON) because the macro then has incompatible definitions in a single translation unit.

I don't think that's what's going on here. The problem is that the first use of LLVM_DEBUG is from inside the push_macro pragma. But we don't update the LLVM_DEBUG IdentifierInfo with the data from the modules before pushing it, which means we just push the undefined identifier on the stack which later will be popped and used for the rest of the translation unit. This would be fixed by D33004 or by just manually updating the identifier from the push_macro code through calling updateOutOfDateIdentifier.

Thanks for fixing this! LGTM, but if possible update the explanation in the commit message.

[kristina]

Personal style preference but I think #define DEBUG_KNUTH(X) do {} while(false) on one line would be better as well instead of splitting it across three lines as well. It's how a lot of them are defined in headers in libLLVMSupport.

[kristina]

The original version (the one you linked for D40404 without push/pop) does indeed look better, I haven't reviewed or tested it, but it seems others have so I'd say go for that one. Would probably be the best approach since it's truly NFC as it's basically just reverting push/pop for more traditional #define + #undef while leaving most of their original commits intact. Though personally I don't really mind which, sooner I can replace a local patch to APInt with one from upstream the better before it snowballs into a merge conflict but I think reverting is better than applying "fix" patches in situations like this.

[kristina]

Superseded by 3rd revision of D40404. Closing.

[t.p.northover]

Thanks for the comments. I've committed basically the original version of the D40404 (modulo DEBUG -> LLVM_DEBUG renaming) as r339009.

lib/Support/APInt.cpp

static void KnuthDiv(uint32_t *u, uint32_t *v, uint32_t *q, uint32_t* r,
   assert(q && "Must provide quotient");
   assert(u != v && u != q && v != q && "Must use different memory");
   assert(n>1 && "n must be > 1");
 
   // b denotes the base of the number system. In our case b is 2^32.
   const uint64_t b = uint64_t(1) << 32;
 
 // The DEBUG macros here tend to be spam in the debug output if you're not
-// debugging this code. Disable them unless KNUTH_DEBUG is defined.
-#pragma push_macro("LLVM_DEBUG")
+// debugging this code. Enable them by defining KNUTH_DEBUG to LLVM_DEBUG.
 #ifndef KNUTH_DEBUG
-#undef LLVM_DEBUG
-#define LLVM_DEBUG(X)                                                          \
+#define KNUTH_DEBUG(X)                                                         \
   do {                                                                         \
   } while (false)
 #endif
 
-  LLVM_DEBUG(dbgs() << "KnuthDiv: m=" << m << " n=" << n << '\n');
-  LLVM_DEBUG(dbgs() << "KnuthDiv: original:");
-  LLVM_DEBUG(for (int i = m + n; i >= 0; i--) dbgs() << " " << u[i]);
-  LLVM_DEBUG(dbgs() << " by");
-  LLVM_DEBUG(for (int i = n; i > 0; i--) dbgs() << " " << v[i - 1]);
-  LLVM_DEBUG(dbgs() << '\n');
+  KNUTH_DEBUG(dbgs() << "KnuthDiv: m=" << m << " n=" << n << '\n');
+  KNUTH_DEBUG(dbgs() << "KnuthDiv: original:");
+  KNUTH_DEBUG(for (int i = m + n; i >= 0; i--) dbgs() << " " << u[i]);
+  KNUTH_DEBUG(dbgs() << " by");
+  KNUTH_DEBUG(for (int i = n; i > 0; i--) dbgs() << " " << v[i - 1]);
+  KNUTH_DEBUG(dbgs() << '\n');
   // 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.
if (shift) {
     for (unsigned i = 0; i < n; ++i) {
       uint32_t v_tmp = v[i] >> (32 - shift);
       v[i] = (v[i] << shift) | v_carry;
       v_carry = v_tmp;
     }
   }
   u[m+n] = u_carry;
 
-  LLVM_DEBUG(dbgs() << "KnuthDiv:   normal:");
-  LLVM_DEBUG(for (int i = m + n; i >= 0; i--) dbgs() << " " << u[i]);
-  LLVM_DEBUG(dbgs() << " by");
-  LLVM_DEBUG(for (int i = n; i > 0; i--) dbgs() << " " << v[i - 1]);
-  LLVM_DEBUG(dbgs() << '\n');
+  KNUTH_DEBUG(dbgs() << "KnuthDiv:   normal:");
+  KNUTH_DEBUG(for (int i = m + n; i >= 0; i--) dbgs() << " " << u[i]);
+  KNUTH_DEBUG(dbgs() << " by");
+  KNUTH_DEBUG(for (int i = n; i > 0; i--) dbgs() << " " << v[i - 1]);
+  KNUTH_DEBUG(dbgs() << '\n');
 
   // D2. [Initialize j.]  Set j to m. This is the loop counter over the places.
   int j = m;
   do {
-    LLVM_DEBUG(dbgs() << "KnuthDiv: quotient digit #" << j << '\n');
+    KNUTH_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')
     // Now test if qp == b or qp*v[n-2] > b*rp + u[j+n-2]; if so, decrease
     // qp by 1, increase rp by v[n-1], and repeat this test if rp < b. The test
     // on v[n-2] determines at high speed most of the cases in which the trial
     // value qp is one too large, and it eliminates all cases where qp is two
     // too large.
     uint64_t dividend = Make_64(u[j+n], u[j+n-1]);
-    LLVM_DEBUG(dbgs() << "KnuthDiv: dividend == " << dividend << '\n');
+    KNUTH_DEBUG(dbgs() << "KnuthDiv: dividend == " << dividend << '\n');
     uint64_t qp = dividend / v[n-1];
     uint64_t rp = dividend % v[n-1];
     if (qp == b || qp*v[n-2] > b*rp + u[j+n-2]) {
       qp--;
       rp += v[n-1];
       if (rp < b && (qp == b || qp*v[n-2] > b*rp + u[j+n-2]))
         qp--;
     }
-    LLVM_DEBUG(dbgs() << "KnuthDiv: qp == " << qp << ", rp == " << rp << '\n');
+    KNUTH_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.
     int64_t borrow = 0;
     for (unsigned i = 0; i < n; ++i) {
       uint64_t p = uint64_t(qp) * uint64_t(v[i]);
       int64_t subres = int64_t(u[j+i]) - borrow - Lo_32(p);
       u[j+i] = Lo_32(subres);
       borrow = Hi_32(p) - Hi_32(subres);
-      LLVM_DEBUG(dbgs() << "KnuthDiv: u[j+i] = " << u[j + i]
+      KNUTH_DEBUG(dbgs() << "KnuthDiv: u[j+i] = " << u[j + i]
                         << ", borrow = " << borrow << '\n');
     }
     bool isNeg = u[j+n] < borrow;
     u[j+n] -= Lo_32(borrow);
 
-    LLVM_DEBUG(dbgs() << "KnuthDiv: after subtraction:");
-    LLVM_DEBUG(for (int i = m + n; i >= 0; i--) dbgs() << " " << u[i]);
-    LLVM_DEBUG(dbgs() << '\n');
+    KNUTH_DEBUG(dbgs() << "KnuthDiv: after subtraction:");
+    KNUTH_DEBUG(for (int i = m + n; i >= 0; i--) dbgs() << " " << u[i]);
+    KNUTH_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] = Lo_32(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++) {
         uint32_t 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;
     }
-    LLVM_DEBUG(dbgs() << "KnuthDiv: after correction:");
-    LLVM_DEBUG(for (int i = m + n; i >= 0; i--) dbgs() << " " << u[i]);
-    LLVM_DEBUG(dbgs() << "\nKnuthDiv: digit result = " << q[j] << '\n');
+    KNUTH_DEBUG(dbgs() << "KnuthDiv: after correction:");
+    KNUTH_DEBUG(for (int i = m + n; i >= 0; i--) dbgs() << " " << u[i]);
+    KNUTH_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);
 
-  LLVM_DEBUG(dbgs() << "KnuthDiv: quotient:");
-  LLVM_DEBUG(for (int i = m; i >= 0; i--) dbgs() << " " << q[i]);
-  LLVM_DEBUG(dbgs() << '\n');
+  KNUTH_DEBUG(dbgs() << "KnuthDiv: quotient:");
+  KNUTH_DEBUG(for (int i = m; i >= 0; i--) dbgs() << " " << q[i]);
+  KNUTH_DEBUG(dbgs() << '\n');
 
   // D8. [Unnormalize]. Now q[...] is the desired quotient, and the desired
   // remainder may be obtained by dividing u[...] by d. If r is non-null we
   // compute the remainder (urem uses this).
   if (r) {
     // The value d is expressed by the "shift" value above since we avoided
     // multiplication by d by using a shift left. So, all we have to do is
     // shift right here.
     if (shift) {
       uint32_t carry = 0;
-      LLVM_DEBUG(dbgs() << "KnuthDiv: remainder:");
+      KNUTH_DEBUG(dbgs() << "KnuthDiv: remainder:");
       for (int i = n-1; i >= 0; i--) {
         r[i] = (u[i] >> shift) | carry;
         carry = u[i] << (32 - shift);
-        LLVM_DEBUG(dbgs() << " " << r[i]);
+        KNUTH_DEBUG(dbgs() << " " << r[i]);
       }
     } else {
       for (int i = n-1; i >= 0; i--) {
         r[i] = u[i];
-        LLVM_DEBUG(dbgs() << " " << r[i]);
+        KNUTH_DEBUG(dbgs() << " " << r[i]);
       }
     }
-    LLVM_DEBUG(dbgs() << '\n');
+    KNUTH_DEBUG(dbgs() << '\n');
   }
-  LLVM_DEBUG(dbgs() << '\n');
-
-#pragma pop_macro("LLVM_DEBUG")
+  KNUTH_DEBUG(dbgs() << '\n');
 }
 
 void APInt::divide(const WordType *LHS, unsigned lhsWords, const WordType *RHS,
                    unsigned rhsWords, WordType *Quotient, WordType *Remainder) {
   assert(lhsWords >= rhsWords && "Fractional result");
 
   // First, compose the values into an array of 32-bit words instead of
   // 64-bit words. This is a necessity of both the "short division" algorithm