Substantially optimize APFloat::toString() by doing a single large divide to

cut the significand down to the desired precision *before* entering the
core divmod loop.  Makes the overall algorithm logarithmic in the exponent.

There's still a lot of room for improvement here, but this gets the
performance back down to acceptable-for-diagnostics levels, even for
long doubles.
negligible, even on long doubles.

llvm-svn: 92130

1 files changed, 37 insertions, 0 deletions

diff --git a/llvm/lib/Support/APFloat.cpp b/llvm/lib/Support/APFloat.cpp
index 4426a361c06..5f748a2c24c 100644
--- a/llvm/lib/Support/APFloat.cpp
+++ b/llvm/lib/Support/APFloat.cpp
@@ -3223,6 +3223,41 @@ namespace {
     append(Buffer, N, Str);
   }
 
+  /// Removes data from the given significand until it is no more
+  /// precise than is required for the desired precision.
+  void AdjustToPrecision(APInt &significand,
+                         int &exp, unsigned FormatPrecision) {
+    unsigned bits = significand.getActiveBits();
+
+    // 196/59 is a very slight overestimate of lg_2(10).
+    unsigned bitsRequired = (FormatPrecision * 196 + 58) / 59;
+
+    if (bits <= bitsRequired) return;
+
+    unsigned tensRemovable = (bits - bitsRequired) * 59 / 196;
+    if (!tensRemovable) return;
+
+    exp += tensRemovable;
+
+    APInt divisor(significand.getBitWidth(), 1);
+    APInt powten(significand.getBitWidth(), 10);
+    while (true) {
+      if (tensRemovable & 1)
+        divisor *= powten;
+      tensRemovable >>= 1;
+      if (!tensRemovable) break;
+      powten *= powten;
+    }
+
+    significand = significand.udiv(divisor);
+
+    // Truncate the significand down to its active bit count, but
+    // don't try to drop below 32.
+    unsigned newPrecision = std::min(32U, significand.getActiveBits());
+    significand.trunc(newPrecision);
+  }
+
+
   void AdjustToPrecision(SmallVectorImpl<char> &buffer,
                          int &exp, unsigned FormatPrecision) {
     unsigned N = buffer.size();
@@ -3343,6 +3378,8 @@ void APFloat::toString(SmallVectorImpl<char> &Str,
     }
   }
 
+  AdjustToPrecision(significand, exp, FormatPrecision);
+
   llvm::SmallVector<char, 256> buffer;
 
   // Fill the buffer.