[libc] Support constexpr uint initialization

[michaelrj]

Summary

Uint addition and subtraction normally use builtins which aren't
constexpr. This patch adds an rvalue overload version of the addition
and subtraction operation that is always constexpr.

[sivachandra]

Looks pretty good but I have some minor questions.

libc/src/__support/FPUtil/x86_64/LongDoubleBits.h

51–52

Why was this change required?

libc/src/__support/UInt.h

86

Is this required for the functionality of this change?

94

Is this required for the functionality of this change? Also, wouldn't a more correct check be *this != 0?

libc/src/__support/builtin_wrappers.h

88

Incomplete sentence?

[mikhail.ramalho]

Thanks, it fixed the problem with sub_with_borrow and add_with_carry in riscv32 for me!

The extra operators also helped with the compilation and only one extra change was required to get libc built for riscv32:

diff --git a/libc/src/__support/FPUtil/NearestIntegerOperations.h b/libc/src/__support/FPUtil/NearestIntegerOperations.h
index 06aa9484c3f7..b9332528f60c 100644
--- a/libc/src/__support/FPUtil/NearestIntegerOperations.h
+++ b/libc/src/__support/FPUtil/NearestIntegerOperations.h
@@ -133,7 +133,7 @@ LIBC_INLINE T round(T x) {
   }
 
   uint32_t trim_size = MantissaWidth<T>::VALUE - exponent;
-  bool half_bit_set = bits.get_mantissa() & (UIntType(1) << (trim_size - 1));
+  bool half_bit_set = bool(bits.get_mantissa() & (UIntType(1) << (trim_size - 1)));
   bits.set_mantissa((bits.get_mantissa() >> trim_size) << trim_size);
   T trunc_value = T(bits);

If the operators are accepted in this patch, do you mind adding this one change as well?

libc/src/__support/UInt.h

94

I did something similar to get compilation working in riscv32, but as:

constexpr explicit operator bool() const { return !is_zero(); }

I think Operator== will construct a UInt(1), while is_zero doesn't

[michaelrj]

address comments

libc/src/__support/FPUtil/x86_64/LongDoubleBits.h

51–52

This change isn't required, it's from when I was trying to move the constants away from addition and subtraction. That being said, I do think leaving this change would be good because we could remove an extra set of parentheses.

libc/src/__support/UInt.h

86

yes, because without this the casts in LongDoubleBits don't work with UInt.

A related question might be "why are there casts in LongDoubleBits?" The answer is I was testing the constant functionality by using UInt<128> instead of the builtin uint_128 on my x86_64 workstation.

libc/src/__support/FPUtil/FloatProperties.h

template <> struct FloatProperties<long double> {
 
   static constexpr BitsType SIGN_MASK =
       BitsType(1) << (EXPONENT_WIDTH + MANTISSA_WIDTH + 1);
   static constexpr BitsType EXPONENT_MASK =
       ((BitsType(1) << EXPONENT_WIDTH) - 1) << (MANTISSA_WIDTH + 1);
   static constexpr uint32_t EXPONENT_BIAS = 16383;
 
   static constexpr BitsType EXP_MANT_MASK =
-      MANTISSA_MASK + EXPLICIT_BIT_MASK + EXPONENT_MASK;
+      MANTISSA_MASK | EXPLICIT_BIT_MASK | EXPONENT_MASK;
   static_assert(EXP_MANT_MASK == (~SIGN_MASK & FULL_WIDTH_MASK),
                 "Exponent and mantissa masks are not as expected.");
 
   // If a number x is a NAN, then it is a quiet NAN if:
   //   QuietNaNMask & bits(x) != 0
   // Else, it is a signalling NAN.
   static constexpr BitsType QUIET_NAN_MASK = BitsType(1)
                                              << (MANTISSA_WIDTH - 1);
template <> struct FloatProperties<long double> {
   static constexpr uint32_t MANTISSA_WIDTH = 112;
   static constexpr uint32_t EXPONENT_WIDTH = 15;
   static constexpr BitsType MANTISSA_MASK = (BitsType(1) << MANTISSA_WIDTH) - 1;
   static constexpr BitsType SIGN_MASK = BitsType(1)
                                         << (EXPONENT_WIDTH + MANTISSA_WIDTH);
   static constexpr BitsType EXPONENT_MASK = ~(SIGN_MASK | MANTISSA_MASK);
   static constexpr uint32_t EXPONENT_BIAS = 16383;
 
-  static constexpr BitsType EXP_MANT_MASK = MANTISSA_MASK + EXPONENT_MASK;
+  static constexpr BitsType EXP_MANT_MASK = MANTISSA_MASK | EXPONENT_MASK;
   static_assert(EXP_MANT_MASK == ~SIGN_MASK,
                 "Exponent and mantissa masks are not as expected.");
 
   // If a number x is a NAN, then it is a quiet NAN if:
   //   QuietNaNMask & bits(x) != 0
   // Else, it is a signalling NAN.
   static constexpr BitsType QUIET_NAN_MASK = BitsType(1)
                                              << (MANTISSA_WIDTH - 1);

libc/src/__support/FPUtil/NearestIntegerOperations.h

if (exponent <= -2) {
     // Absolute value of x is less than 0.5.
     if (is_neg)
       return T(-0.0);
     else
       return T(0.0);
   }
 
   uint32_t trim_size = MantissaWidth<T>::VALUE - exponent;
-  bool half_bit_set = bits.get_mantissa() & (UIntType(1) << (trim_size - 1));
+  bool half_bit_set =
+      bool(bits.get_mantissa() & (UIntType(1) << (trim_size - 1)));
   bits.set_mantissa((bits.get_mantissa() >> trim_size) << trim_size);
   T trunc_value = T(bits);
 
   // If x is already an integer, return it.
   if (trunc_value == x)
     return x;
 
   if (!half_bit_set) {

libc/src/__support/FPUtil/x86_64/LongDoubleBits.h

 #include <stdint.h>
 
 namespace __llvm_libc {
 namespace fputil {
 
 template <unsigned Width> struct Padding;
 
 // i386 padding.
-template <> struct Padding<4> { static constexpr unsigned VALUE = 16; };
+template <> struct Padding<4> {
+  static constexpr unsigned VALUE = 16;
+};
 
 // x86_64 padding.
-template <> struct Padding<8> { static constexpr unsigned VALUE = 48; };
+template <> struct Padding<8> {
+  static constexpr unsigned VALUE = 48;
+};
 
 template <> struct FPBits<long double> {
   using UIntType = UInt128;
 
   static constexpr int EXPONENT_BIAS = 0x3FFF;
   static constexpr int MAX_EXPONENT = 0x7FFF;
   static constexpr UIntType MIN_SUBNORMAL = UIntType(1);
   // Subnormal numbers include the implicit bit in x86 long double formats.
   static constexpr UIntType MAX_SUBNORMAL =
       (UIntType(1) << (MantissaWidth<long double>::VALUE)) - 1;
   static constexpr UIntType MIN_NORMAL =
       (UIntType(3) << MantissaWidth<long double>::VALUE);
   static constexpr UIntType MAX_NORMAL =
-      ((UIntType(MAX_EXPONENT) - 1)
-       << (MantissaWidth<long double>::VALUE + 1)) |
+      (UIntType(MAX_EXPONENT - 1) << (MantissaWidth<long double>::VALUE + 1)) |
       (UIntType(1) << MantissaWidth<long double>::VALUE) | MAX_SUBNORMAL;
 
   using FloatProp = FloatProperties<long double>;
 
   UIntType bits;
 
   LIBC_INLINE void set_mantissa(UIntType mantVal) {
     mantVal &= (FloatProp::MANTISSA_MASK);
template <> struct FPBits<long double> {
   }
 
   LIBC_INLINE void set_implicit_bit(bool implicitVal) {
     bits &= ~(UIntType(1) << FloatProp::MANTISSA_WIDTH);
     bits |= (UIntType(implicitVal) << FloatProp::MANTISSA_WIDTH);
   }
 
   LIBC_INLINE bool get_implicit_bit() const {
-    return ((bits & (UIntType(1) << FloatProp::MANTISSA_WIDTH)) >>
+    return bool((bits & (UIntType(1) << FloatProp::MANTISSA_WIDTH)) >>
                 FloatProp::MANTISSA_WIDTH);
   }
 
   LIBC_INLINE void set_sign(bool signVal) {
     bits &= ~(FloatProp::SIGN_MASK);
     UIntType sign1 = UIntType(signVal) << (FloatProp::BIT_WIDTH - 1);
     bits |= sign1;
   }
 
   LIBC_INLINE bool get_sign() const {
-    return ((bits & FloatProp::SIGN_MASK) >> (FloatProp::BIT_WIDTH - 1));
+    return bool((bits & FloatProp::SIGN_MASK) >> (FloatProp::BIT_WIDTH - 1));
   }
 
   FPBits() : bits(0) {}
 
   template <typename XType,
             cpp::enable_if_t<cpp::is_same_v<long double, XType>, int> = 0>
   explicit FPBits(XType x) : bits(cpp::bit_cast<UIntType>(x)) {
     // bits starts uninitialized, and setting it to a long double only

libc/src/__support/UInt.h

template <size_t Bits> struct UInt {
   }
 
   constexpr explicit operator uint64_t() const { return val[0]; }
 
   constexpr explicit operator uint32_t() const {
     return uint32_t(uint64_t(*this));
   }
 
+  constexpr explicit operator uint16_t() const {
+    return uint16_t(uint64_t(*this));
+  }
+
   constexpr explicit operator uint8_t() const {
     return uint8_t(uint64_t(*this));
   }
 
+  constexpr explicit operator bool() const { return !is_zero(); }
+
   UInt<Bits> &operator=(const UInt<Bits> &other) = default;
 
   constexpr bool is_zero() const {
     for (size_t i = 0; i < WORDCOUNT; ++i) {
       if (val[i] != 0)
         return false;
     }
     return true;
   }
 
   // Add x to this number and store the result in this number.
   // Returns the carry value produced by the addition operation.
   constexpr uint64_t add(const UInt<Bits> &x) {
     SumCarry<uint64_t> s{0, 0};
     for (size_t i = 0; i < WORDCOUNT; ++i) {
       s = add_with_carry(val[i], x.val[i], s.carry);
       val[i] = s.sum;
     }
     return s.carry;
   }
 
-  constexpr UInt<Bits> operator+(const UInt<Bits> &other) const {
+  UInt<Bits> operator+(const UInt<Bits> &other) const {
     UInt<Bits> result;
     SumCarry<uint64_t> s{0, 0};
     for (size_t i = 0; i < WORDCOUNT; ++i) {
       s = add_with_carry(val[i], other.val[i], s.carry);
       result.val[i] = s.sum;
     }
     return result;
   }
 
+  // This will only apply when initializing a variable from constant values, so
+  // it will always use the constexpr version of add_with_carry.
+  constexpr UInt<Bits> operator+(UInt<Bits> &&other) const {
+    UInt<Bits> result;
+    SumCarry<uint64_t> s{0, 0};
+    for (size_t i = 0; i < WORDCOUNT; ++i) {
+      s = add_with_carry_const(val[i], other.val[i], s.carry);
+      result.val[i] = s.sum;
+    }
+    return result;
+  }
+
   constexpr UInt<Bits> &operator+=(const UInt<Bits> &other) {
     add(other); // Returned carry value is ignored.
     return *this;
   }
 
   // Subtract x to this number and store the result in this number.
   // Returns the carry value produced by the subtraction operation.
   constexpr uint64_t sub(const UInt<Bits> &x) {
     DiffBorrow<uint64_t> d{0, 0};
     for (size_t i = 0; i < WORDCOUNT; ++i) {
       d = sub_with_borrow(val[i], x.val[i], d.borrow);
       val[i] = d.diff;
     }
     return d.borrow;
   }
 
-  constexpr UInt<Bits> operator-(const UInt<Bits> &other) const {
+  UInt<Bits> operator-(const UInt<Bits> &other) const {
     UInt<Bits> result;
     DiffBorrow<uint64_t> d{0, 0};
     for (size_t i = 0; i < WORDCOUNT; ++i) {
       d = sub_with_borrow(val[i], other.val[i], d.borrow);
       result.val[i] = d.diff;
     }
     return result;
   }
 
+  constexpr UInt<Bits> operator-(UInt<Bits> &&other) const {
+    UInt<Bits> result;
+    DiffBorrow<uint64_t> d{0, 0};
+    for (size_t i = 0; i < WORDCOUNT; ++i) {
+      d = sub_with_borrow_const(val[i], other.val[i], d.borrow);
+      result.val[i] = d.diff;
+    }
+    return result;
+  }
+
   constexpr UInt<Bits> &operator-=(const UInt<Bits> &other) {
     // TODO(lntue): Set overflow flag / errno when carry is true.
     sub(other);
     return *this;
   }
 
   // Multiply this number with x and store the result in this number. It is
   // implemented using the long multiplication algorithm by splitting the

libc/src/__support/builtin_wrappers.h

 //===--Convenient template for builtins -------------------------*- C++ -*-===//
 //             (Count Lead Zeroes) and (Count Trailing Zeros)
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_LIBC_SRC_SUPPORT_BUILTIN_WRAPPERS_H
 #define LLVM_LIBC_SRC_SUPPORT_BUILTIN_WRAPPERS_H
 
 #include "named_pair.h"
 #include "src/__support/CPP/type_traits.h"
-#include "src/__support/macros/attributes.h"          // LIBC_INLINE
-#include "src/__support/macros/config.h"              // LIBC_HAS_BUILTIN
+#include "src/__support/macros/attributes.h" // LIBC_INLINE
+#include "src/__support/macros/config.h"     // LIBC_HAS_BUILTIN
 
 namespace __llvm_libc {
 
 // The following overloads are matched based on what is accepted by
 // __builtin_clz/ctz* rather than using the exactly-sized aliases from stdint.h.
 // This way, we can avoid making any assumptions about integer sizes and let the
 // compiler match for us.
 namespace __internal {

 
 template <typename T> LIBC_INLINE int unsafe_clz(T val) {
   return __internal::clz(val);
 }
 
 // Add with carry
 DEFINE_NAMED_PAIR_TEMPLATE(SumCarry, sum, carry);
 
+// This version is always valid for constexpr.
 template <typename T>
 LIBC_INLINE constexpr cpp::enable_if_t<
     cpp::is_integral_v<T> && cpp::is_unsigned_v<T>, SumCarry<T>>
-add_with_carry(T a, T b, T carry_in) {
+add_with_carry_const(T a, T b, T carry_in) {
   T tmp = a + carry_in;
   T sum = b + tmp;
-  T carry_out = (sum < b) || (tmp < a);
+  T carry_out = (sum < b) + (tmp < a);
   return {sum, carry_out};
 }
 
+// This version is not always valid for constepxr because it's overriden below
+// if builtins are available.
+template <typename T>
+LIBC_INLINE cpp::enable_if_t<cpp::is_integral_v<T> && cpp::is_unsigned_v<T>,
+                             SumCarry<T>>
+add_with_carry(T a, T b, T carry_in) {
+  return add_with_carry_const<T>(a, b, carry_in);
+}
+
 #if LIBC_HAS_BUILTIN(__builtin_addc)
 // https://clang.llvm.org/docs/LanguageExtensions.html#multiprecision-arithmetic-builtins
 
 template <>
 LIBC_INLINE SumCarry<unsigned char>
 add_with_carry<unsigned char>(unsigned char a, unsigned char b,
                               unsigned char carry_in) {
   SumCarry<unsigned char> result{0, 0};
add_with_carry<unsigned long long>(unsigned long long a, unsigned long long b,
   return result;
 }
 
 #endif // LIBC_HAS_BUILTIN(__builtin_addc)
 
 // Subtract with borrow
 DEFINE_NAMED_PAIR_TEMPLATE(DiffBorrow, diff, borrow);
 
+// This version is always valid for constexpr.
 template <typename T>
 LIBC_INLINE constexpr cpp::enable_if_t<
     cpp::is_integral_v<T> && cpp::is_unsigned_v<T>, DiffBorrow<T>>
-sub_with_borrow(T a, T b, T borrow_in) {
+sub_with_borrow_const(T a, T b, T borrow_in) {
   T tmp = a - b;
   T diff = tmp - borrow_in;
-  T borrow_out = (diff > tmp) || (tmp > a);
+  T borrow_out = (diff > tmp) + (tmp > a);
   return {diff, borrow_out};
 }
 
+// This version is not always valid for constepxr because it's overriden below
+// if builtins are available.
+template <typename T>
+LIBC_INLINE cpp::enable_if_t<cpp::is_integral_v<T> && cpp::is_unsigned_v<T>,
+                             DiffBorrow<T>>
+sub_with_borrow(T a, T b, T borrow_in) {
+  return sub_with_borrow_const<T>(a, b, borrow_in);
+}
+
 #if LIBC_HAS_BUILTIN(__builtin_subc)
 // https://clang.llvm.org/docs/LanguageExtensions.html#multiprecision-arithmetic-builtins
 
 template <>
 LIBC_INLINE DiffBorrow<unsigned char>
 sub_with_borrow<unsigned char>(unsigned char a, unsigned char b,
                                unsigned char borrow_in) {
   DiffBorrow<unsigned char> result{0, 0};

libc/test/src/__support/uint_test.cpp

#define TEST_QUICK_MUL_HI(Bits, Error)                                         \
   } while (0)
 
 TEST(LlvmLibcUIntClassTest, QuickMulHiTests) {
   TEST_QUICK_MUL_HI(128, 1);
   TEST_QUICK_MUL_HI(192, 2);
   TEST_QUICK_MUL_HI(256, 3);
   TEST_QUICK_MUL_HI(512, 7);
 }
+
+TEST(LlvmLibcUIntClassTest, ConstexprInitTests) {
+  constexpr LL_UInt128 add = LL_UInt128(1) + LL_UInt128(2);
+  ASSERT_EQ(add, LL_UInt128(3));
+  constexpr LL_UInt128 sub = LL_UInt128(5) - LL_UInt128(4);
+  ASSERT_EQ(sub, LL_UInt128(1));
+}