[libc] Add Size Saving for String To Float

[michaelrj]

Summary

String to float uses the Eisel-Lemire algorithm for better performance
in most cases, however this requires a very large table. Some
configurations, such as embedded devices, don't care about speed as much
as code size. This patch adds a flag to disable the Eisel-Lemire
algorithm as well as other code size savings for string to float.

[michaelrj]

The flag name is TBD, I picked LIBC_SIZE because it would be obvious what it was being used for, but it doesn't seem like a good long-term solution.

[tschuett]

In D130584#3680135, @michaelrj wrote:

The flag name is TBD, I picked LIBC_SIZE because it would be obvious what it was being used for, but it doesn't seem like a good long-term solution.

Could I have instead a custom entrypoints.txt file with an adapted symbols list for my embedded target? Then I can mix and match..

[sivachandra]

In src/stdlib maybe, add a README.md which describes the new knob this patch is adding.

libc/src/__support/str_to_float.h

81

Use a more specific flag name. Also, instead of excluding large blocks of code, move this to a separate header file and conditionally include it.

592–613

Can this block be moved in to a function by itself and invoked conditionally?

libc/test/src/__support/str_to_float_test.cpp

17

Instead of conditional exclusion, move them to a more focused test.

[michaelrj]

Similar commit landed in https://reviews.llvm.org/D136495

libc/src/__support/str_to_float.h

 
 #if defined(SPECIAL_X86_LONG_DOUBLE)
 template <>
 inline void set_implicit_bit<long double>(fputil::FPBits<long double> &result) {
   result.set_implicit_bit(result.get_unbiased_exponent() != 0);
 }
 #endif
 
+#ifndef LIBC_SIZE
+
 // This Eisel-Lemire implementation is based on the algorithm described in the
 // paper Number Parsing at a Gigabyte per Second, Software: Practice and
 // Experience 51 (8), 2021 (https://arxiv.org/abs/2101.11408), as well as the
 // description by Nigel Tao
 // (https://nigeltao.github.io/blog/2020/eisel-lemire.html) and the golang
 // implementation, also by Nigel Tao
 // (https://github.com/golang/go/blob/release-branch.go1.16/src/strconv/eisel_lemire.go#L25)
 // for some optimizations as well as handling 32 bit floats.
if (exp10 < DETAILED_POWERS_OF_TEN_MIN_EXP_10 ||
       exp10 > DETAILED_POWERS_OF_TEN_MAX_EXP_10) {
     return false;
   }
 
   // Normalization
   uint32_t clz = leading_zeroes<BitsType>(mantissa);
   mantissa <<= clz;
 
-  uint32_t exp2 = static_cast<uint32_t>(exp10_to_exp2(exp10)) + BITS_IN_MANTISSA +
-                  fputil::FloatProperties<T>::EXPONENT_BIAS - clz;
+  uint32_t exp2 = static_cast<uint32_t>(exp10_to_exp2(exp10)) +
+                  BITS_IN_MANTISSA + fputil::FloatProperties<T>::EXPONENT_BIAS -
+                  clz;
 
   // Multiplication
   const uint64_t *power_of_ten =
       DETAILED_POWERS_OF_TEN[exp10 - DETAILED_POWERS_OF_TEN_MIN_EXP_10];
 
   UInt128 first_approx =
       static_cast<UInt128>(mantissa) * static_cast<UInt128>(power_of_ten[1]);
 
if ((high64(second_approx) & halfway_constant) == halfway_constant &&
       return false;
     }
     final_approx = second_approx;
   } else {
     final_approx = first_approx;
   }
 
   // Shifting to 54 bits for doubles and 25 bits for floats
-  BitsType msb = static_cast<BitsType>(high64(final_approx) >> (BITS_IN_MANTISSA - 1));
-  BitsType final_mantissa = static_cast<BitsType>(high64(final_approx) >>
+  BitsType msb =
+      static_cast<BitsType>(high64(final_approx) >> (BITS_IN_MANTISSA - 1));
+  BitsType final_mantissa =
+      static_cast<BitsType>(high64(final_approx) >>
                             (msb + BITS_IN_MANTISSA -
                              (fputil::FloatProperties<T>::MANTISSA_WIDTH + 3)));
   exp2 -= static_cast<uint32_t>(1 ^ msb); // same as !msb
 
   // Half-way ambiguity
   if (low64(final_approx) == 0 &&
       (high64(final_approx) & halfway_constant) == 0 &&
       (final_mantissa & 3) == 1) {
if (exp10 < DETAILED_POWERS_OF_TEN_MIN_EXP_10 ||
       exp10 > DETAILED_POWERS_OF_TEN_MAX_EXP_10) {
     return false;
   }
 
   // Normalization
   uint32_t clz = leading_zeroes<BitsType>(mantissa);
   mantissa <<= clz;
 
-  uint32_t exp2 = static_cast<uint32_t>(exp10_to_exp2(exp10)) + BITS_IN_MANTISSA +
+  uint32_t exp2 = static_cast<uint32_t>(exp10_to_exp2(exp10)) +
+                  BITS_IN_MANTISSA +
                   fputil::FloatProperties<long double>::EXPONENT_BIAS - clz;
 
   // Multiplication
   const uint64_t *power_of_ten =
       DETAILED_POWERS_OF_TEN[exp10 - DETAILED_POWERS_OF_TEN_MIN_EXP_10];
 
   // Since the input mantissa is more than 64 bits, we have to multiply with the
   // full 128 bits of the power of ten to get an approximation with the same
inline bool eisel_lemire<long double>(
   }
 
   *outputMantissa = final_mantissa;
   *outputExp2 = exp2;
   return true;
 }
 #endif
 
+#endif // LIBC_SIZE
+
 // The nth item in POWERS_OF_TWO represents the greatest power of two less than
 // 10^n. This tells us how much we can safely shift without overshooting.
 constexpr uint8_t POWERS_OF_TWO[19] = {
     0, 3, 6, 9, 13, 16, 19, 23, 26, 29, 33, 36, 39, 43, 46, 49, 53, 56, 59,
 };
 constexpr int32_t NUM_POWERS_OF_TWO =
     sizeof(POWERS_OF_TWO) / sizeof(POWERS_OF_TWO[0]);
 
simple_decimal_conversion(const char *__restrict numStart,
   if (exp2 == 0) {
     errno = ERANGE;
   }
 
   *outputMantissa = final_mantissa;
   *outputExp2 = exp2;
 }
 
+#ifndef LIBC_SIZE
 // This class is used for templating the constants for Clinger's Fast Path,
 // described as a method of approximation in
 // Clinger WD. How to Read Floating Point Numbers Accurately. SIGPLAN Not 1990
 // Jun;25(6):92–101. https://doi.org/10.1145/93548.93557.
 // As well as the additions by Gay that extend the useful range by the number of
 // exact digits stored by the float type, described in
 // Gay DM, Correctly rounded binary-decimal and decimal-binary conversions;
 // 1990. AT&T Bell Laboratories Numerical Analysis Manuscript 90-10.
if (exp10 > 0) {
     }
     result = fputil::FPBits<T>(float_mantissa /
                                ClingerConsts<T>::POWERS_OF_TEN_ARRAY[-exp10]);
   }
   *outputMantissa = result.get_mantissa();
   *outputExp2 = result.get_unbiased_exponent();
   return true;
 }
+#endif // LIBC_SIZE
 
 // Takes a mantissa and base 10 exponent and converts it into its closest
 // floating point type T equivalient. First we try the Eisel-Lemire algorithm,
 // then if that fails then we fall back to a more accurate algorithm for
 // accuracy. The resulting mantissa and exponent are placed in outputMantissa
 // and outputExp2.
 template <class T>
 static inline void
if (exp10 < 0 &&
                                fputil::FloatProperties<T>::MANTISSA_WIDTH) /
               2) {
     *outputMantissa = 0;
     *outputExp2 = 0;
     errno = ERANGE;
     return;
   }
 
+#ifndef LIBC_SIZE
   if (!truncated) {
     if (clinger_fast_path<T>(mantissa, exp10, outputMantissa, outputExp2)) {
       return;
     }
   }
 
   // Try Eisel-Lemire
   if (eisel_lemire<T>(mantissa, exp10, outputMantissa, outputExp2)) {
     if (!truncated) {
       return;
     }
     // If the mantissa is truncated, then the result may be off by the LSB, so
     // check if rounding the mantissa up changes the result. If not, then it's
     // safe, else use the fallback.
     typename fputil::FPBits<T>::UIntType first_mantissa = *outputMantissa;
     uint32_t first_exp2 = *outputExp2;
     if (eisel_lemire<T>(mantissa + 1, exp10, outputMantissa, outputExp2)) {
       if (*outputMantissa == first_mantissa && *outputExp2 == first_exp2) {
         return;
       }
     }
   }
+#endif // LIBC_SIZE
 
   simple_decimal_conversion<T>(numStart, outputMantissa, outputExp2);
 
   return;
 }
 
 // Takes a mantissa and base 2 exponent and converts it into its closest
 // floating point type T equivalient. Since the exponent is already in the right

libc/test/src/__support/str_to_float_test.cpp

 //===-- Unittests for str_to_float ----------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "src/__support/CPP/UInt128.h"
 #include "src/__support/FPUtil/FPBits.h"
 #include "src/__support/str_to_float.h"
 
 #include "utils/UnitTest/Test.h"
 
 class LlvmLibcStrToFloatTest : public __llvm_libc::testing::Test {
 public:
+#ifndef LIBC_SIZE
   template <class T>
   void clinger_fast_path_test(
       const typename __llvm_libc::fputil::FPBits<T>::UIntType inputMantissa,
       const int32_t inputExp10,
       const typename __llvm_libc::fputil::FPBits<T>::UIntType
           expectedOutputMantissa,
       const uint32_t expectedOutputExp2) {
     typename __llvm_libc::fputil::FPBits<T>::UIntType actual_output_mantissa =
void eisel_lemire_test(
     uint32_t actual_output_exp2 = 0;
 
     ASSERT_TRUE(__llvm_libc::internal::eisel_lemire<T>(
         inputMantissa, inputExp10, &actual_output_mantissa,
         &actual_output_exp2));
     EXPECT_EQ(actual_output_mantissa, expectedOutputMantissa);
     EXPECT_EQ(actual_output_exp2, expectedOutputExp2);
   }
-
+#endif // LIBC_SIZE
   template <class T>
   void simple_decimal_conversion_test(
       const char *__restrict numStart,
       const typename __llvm_libc::fputil::FPBits<T>::UIntType
           expectedOutputMantissa,
       const uint32_t expectedOutputExp2, const int expectedErrno = 0) {
     typename __llvm_libc::fputil::FPBits<T>::UIntType actual_output_mantissa =
         0;
TEST(LlvmLibcStrToFloatTest, LeadingZeroes) {
   for (; num_of_zeroes < 32; test_num32 <<= 1, num_of_zeroes--) {
     EXPECT_EQ(__llvm_libc::internal::leading_zeroes<uint32_t>(test_num32),
               num_of_zeroes);
   }
 
   EXPECT_EQ(__llvm_libc::internal::leading_zeroes<uint32_t>(0xffffffff), 0u);
 }
 
+#ifndef LIBC_SIZE
 TEST_F(LlvmLibcStrToFloatTest, ClingerFastPathFloat64Simple) {
   clinger_fast_path_test<double>(123, 0, 0xEC00000000000, 1029);
   clinger_fast_path_test<double>(1234567890123456, 1, 0x5ee2a2eb5a5c0, 1076);
   clinger_fast_path_test<double>(1234567890, -10, 0xf9add3739635f, 1019);
 }
 
 TEST_F(LlvmLibcStrToFloatTest, ClingerFastPathFloat64ExtendedExp) {
   clinger_fast_path_test<double>(1, 30, 0x93e5939a08cea, 1122);
TEST_F(LlvmLibcStrToFloatTest, EiselLemireFallbackStates) {
   // from both of its closest floating point approximations
   // (12345678901234548736 and 12345678901234550784)
   ASSERT_FALSE(__llvm_libc::internal::eisel_lemire<double>(
       12345678901234549760u, 0, &double_output_mantissa, &output_exp2));
 
   ASSERT_FALSE(__llvm_libc::internal::eisel_lemire<float>(
       20040229, 0, &float_output_mantissa, &output_exp2));
 }
+#endif // LIBC_SIZE
 
 TEST_F(LlvmLibcStrToFloatTest, SimpleDecimalConversion64BasicWholeNumbers) {
   simple_decimal_conversion_test<double>("123456789012345678900",
                                          0x1AC53A7E04BCDA, 1089);
   simple_decimal_conversion_test<double>("123", 0x1EC00000000000, 1029);
   simple_decimal_conversion_test<double>("12345678901234549760",
                                          0x156A95319D63D8, 1086);
 }
TEST(LlvmLibcStrToFloatTest, SimpleDecimalConversionExtraTypes) {
   errno = 0;
   __llvm_libc::internal::simple_decimal_conversion<double>(
       "123456789012345678900", &double_output_mantissa, &output_exp2);
   EXPECT_EQ(double_output_mantissa, uint64_t(0x1AC53A7E04BCDA));
   EXPECT_EQ(output_exp2, uint32_t(1089));
   EXPECT_EQ(errno, 0);
 }
 
+#ifndef LIBC_SIZE
+
 #if defined(LONG_DOUBLE_IS_DOUBLE)
 TEST_F(LlvmLibcStrToFloatTest, EiselLemireFloat64AsLongDouble) {
   eisel_lemire_test<long double>(123, 0, 0x1EC00000000000, 1029);
 }
 #elif defined(SPECIAL_X86_LONG_DOUBLE)
 TEST_F(LlvmLibcStrToFloatTest, EiselLemireFloat80Simple) {
   eisel_lemire_test<long double>(123, 0, 0xf600000000000000, 16389);
   eisel_lemire_test<long double>(12345678901234568192u, 0, 0xab54a98ceb1f0c00,
TEST_F(LlvmLibcStrToFloatTest, EiselLemireFloat128Fallback) {
   uint32_t outputExp2 = 0;
   UInt128 quadOutputMantissa = 0;
 
   ASSERT_FALSE(__llvm_libc::internal::eisel_lemire<long double>(
       (UInt128(0x5ce0e9a56015fec5) << 64) + UInt128(0xaadfa328ae39b333), 1,
       &quadOutputMantissa, &outputExp2));
 }
 #endif
+#endif // LIBC_SIZE