[libc] Add sub_with_borrow to builtin_wrapper.h

[lntue]

Summary

Add sub_with_borrow to builtin_wrapper.h to be used in UInt.

[sivachandra]

libc/src/__support/builtin_wrappers.h

137

Why not use number_pair for the return value?

[lntue]

libc/src/__support/builtin_wrappers.h

137

Since these are kind of built-in wrappers, I want to kind of preserve how the builtins are defined. Also the number_pair for subtraction is actually a bit odd, since then the carry/borrow/high part is actually of negative sign, while the result/low part is of positive sign.

[lntue]

Add DEFINE_NAMED_PAIR_TEMPLATE and update return values for builtins wrappers.

[sivachandra]

Thanks for cleaning up other places also.

libc/src/__support/CMakeLists.txt

 add_subdirectory(CPP)
 
 add_header_library(
   blockstore
   HDRS
     blockstore.h
 )
 
 add_header_library(
+  named_pair
+  HDRS
+    named_pair.h
+)
+
+add_header_library(
   builtin_wrappers
   HDRS
     builtin_wrappers.h
   DEPENDS
+    .named_pair
     libc.src.__support.CPP.type_traits
 )
 
 add_header_library(
   common
   HDRS
     architectures.h
     common.h
DEPENDS
     libc.src.__support.CPP.array
 )
 
 add_header_library(
   number_pair
   HDRS
     number_pair.h
   DEPENDS
+    .named_pair
     libc.src.__support.CPP.type_traits
 )
 
 add_header_library(
   integer_utils
   HDRS
     integer_utils.h
   DEPENDS

libc/src/__support/UInt.h

template <size_t Bits> struct UInt {
   }
 
   // Add x to this number and store the result in this number.
   // Returns the carry value produced by the addition operation.
   // To prevent overflow from intermediate results, we use the following
   // property of unsigned integers:
   //   x + (~x) = 2^(sizeof(x)) - 1.
   constexpr uint64_t add(const UInt<Bits> &x) {
-    uint64_t carry_in = 0;
-    uint64_t carry_out = 0;
+    SumCarry<uint64_t> s{0, 0};
     for (size_t i = 0; i < WordCount; ++i) {
-      val[i] = add_with_carry(val[i], x.val[i], carry_in, carry_out);
-      carry_in = carry_out;
+      s = add_with_carry(val[i], x.val[i], s.carry);
+      val[i] = s.sum;
     }
-    return carry_out;
+    return s.carry;
   }
 
   constexpr UInt<Bits> operator+(const UInt<Bits> &other) const {
     UInt<Bits> result;
-    uint64_t carry_in = 0;
-    uint64_t carry_out = 0;
+    SumCarry<uint64_t> s{0, 0};
     for (size_t i = 0; i < WordCount; ++i) {
-      result.val[i] = add_with_carry(val[i], other.val[i], carry_in, carry_out);
-      carry_in = carry_out;
+      s = add_with_carry(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;
   }

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"
 
 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.
template <typename T> static inline int safe_clz(T val) {
   return __internal::correct_zero(val, __internal::clz(val));
 }
 
 template <typename T> static inline int unsafe_clz(T val) {
   return __internal::clz(val);
 }
 
 // Add with carry
+DEFINE_NAMED_PAIR_TEMPLATE(SumCarry, sum, carry);
+
 template <typename T>
 inline constexpr cpp::enable_if_t<
-    cpp::is_integral_v<T> && cpp::is_unsigned_v<T>, T>
-add_with_carry(T a, T b, T carry_in, T &carry_out) {
+    cpp::is_integral_v<T> && cpp::is_unsigned_v<T>, SumCarry<T>>
+add_with_carry(T a, T b, T carry_in) {
   T tmp = a + carry_in;
   T sum = b + tmp;
-  carry_out = (sum < b) || (tmp < a);
-  return sum;
+  T carry_out = (sum < b) || (tmp < a);
+  return {sum, carry_out};
 }
 
 #if __has_builtin(__builtin_addc)
 // https://clang.llvm.org/docs/LanguageExtensions.html#multiprecision-arithmetic-builtins
 
 template <>
-inline unsigned char add_with_carry<unsigned char>(unsigned char a,
-                                                   unsigned char b,
-                                                   unsigned char carry_in,
-                                                   unsigned char &carry_out) {
-  return __builtin_addcb(a, b, carry_in, &carry_out);
+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};
+  result.sum = __builtin_addcb(a, b, carry_in, &result.carry);
+  return result;
 }
 
 template <>
-inline unsigned short
+inline SumCarry<unsigned short>
 add_with_carry<unsigned short>(unsigned short a, unsigned short b,
-                               unsigned short carry_in,
-                               unsigned short &carry_out) {
-  return __builtin_addcs(a, b, carry_in, &carry_out);
+                               unsigned short carry_in) {
+  SumCarry<unsigned short> result{0, 0};
+  result.sum = __builtin_addcs(a, b, carry_in, &result.carry);
+  return result;
 }
 
 template <>
-inline unsigned int add_with_carry<unsigned int>(unsigned int a, unsigned int b,
-                                                 unsigned int carry_in,
-                                                 unsigned int &carry_out) {
-  return __builtin_addc(a, b, carry_in, &carry_out);
+inline SumCarry<unsigned int>
+add_with_carry<unsigned int>(unsigned int a, unsigned int b,
+                             unsigned int carry_in) {
+  SumCarry<unsigned int> result{0, 0};
+  result.sum = __builtin_addc(a, b, carry_in, &result.carry);
+  return result;
 }
 
 template <>
-inline unsigned long add_with_carry<unsigned long>(unsigned long a,
-                                                   unsigned long b,
-                                                   unsigned long carry_in,
-                                                   unsigned long &carry_out) {
-  return __builtin_addcl(a, b, carry_in, &carry_out);
+inline SumCarry<unsigned long>
+add_with_carry<unsigned long>(unsigned long a, unsigned long b,
+                              unsigned long carry_in) {
+  SumCarry<unsigned long> result{0, 0};
+  result.sum = __builtin_addcl(a, b, carry_in, &result.carry);
+  return result;
 }
 
 template <>
-inline unsigned long long
+inline SumCarry<unsigned long long>
 add_with_carry<unsigned long long>(unsigned long long a, unsigned long long b,
-                                   unsigned long long carry_in,
-                                   unsigned long long &carry_out) {
-  return __builtin_addcll(a, b, carry_in, &carry_out);
+                                   unsigned long long carry_in) {
+  SumCarry<unsigned long long> result{0, 0};
+  result.sum = __builtin_addcll(a, b, carry_in, &result.carry);
+  return result;
 }
+
 #endif // __has_builtin(__builtin_addc)
 
+// Subtract with borrow
+DEFINE_NAMED_PAIR_TEMPLATE(DiffBorrow, diff, borrow);
+
+template <typename T>
+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) {
+  T tmp = a - b;
+  T diff = tmp - borrow_in;
+  T borrow_out = (diff > tmp) || (tmp > a);
+  return {diff, borrow_out};
+}
+
+#if __has_builtin(__builtin_subc)
+// https://clang.llvm.org/docs/LanguageExtensions.html#multiprecision-arithmetic-builtins
+
+template <>
+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};
+  result.diff = __builtin_subcb(a, b, borrow_in, &result.borrow);
+  return result;
+}
+
+template <>
+inline DiffBorrow<unsigned short>
+sub_with_borrow<unsigned short>(unsigned short a, unsigned short b,
+                                unsigned short borrow_in) {
+  DiffBorrow<unsigned short> result{0, 0};
+  result.diff = __builtin_subcs(a, b, borrow_in, &result.borrow);
+  return result;
+}
+
+template <>
+inline DiffBorrow<unsigned int>
+sub_with_borrow<unsigned int>(unsigned int a, unsigned int b,
+                              unsigned int borrow_in) {
+  DiffBorrow<unsigned int> result{0, 0};
+  result.diff = __builtin_subc(a, b, borrow_in, &result.borrow);
+  return result;
+}
+
+template <>
+inline DiffBorrow<unsigned long>
+sub_with_borrow<unsigned long>(unsigned long a, unsigned long b,
+                               unsigned long borrow_in) {
+  DiffBorrow<unsigned long> result{0, 0};
+  result.diff = __builtin_subcl(a, b, borrow_in, &result.borrow);
+  return result;
+}
+
+template <>
+inline DiffBorrow<unsigned long long>
+sub_with_borrow<unsigned long long>(unsigned long long a, unsigned long long b,
+                                    unsigned long long borrow_in) {
+  DiffBorrow<unsigned long long> result{0, 0};
+  result.diff = __builtin_subcll(a, b, borrow_in, &result.borrow);
+  return result;
+}
+
+#endif // __has_builtin(__builtin_subc)
+
 } // namespace __llvm_libc
 
 #endif // LLVM_LIBC_SRC_SUPPORT_BUILTIN_WRAPPERS_H

libc/src/__support/integer_utils.h

#else
   NumberPair<uint64_t> pb = split(b);
   NumberPair<uint64_t> prod;
 
   prod.lo = pa.lo * pb.lo;                           // exact
   prod.hi = pa.hi * pb.hi;                           // exact
   NumberPair<uint64_t> lo_hi = split(pa.lo * pb.hi); // exact
   NumberPair<uint64_t> hi_lo = split(pa.hi * pb.lo); // exact
 
-  uint64_t carry_in = 0;
-  uint64_t carry_out = 0;
-  uint64_t carry_unused = 0;
-  prod.lo = add_with_carry(prod.lo, lo_hi.lo << 32, carry_in, carry_out);
-  prod.hi = add_with_carry(prod.hi, lo_hi.hi, carry_out, carry_unused);
-  prod.lo = add_with_carry(prod.lo, hi_lo.lo << 32, carry_in, carry_out);
-  prod.hi = add_with_carry(prod.hi, hi_lo.hi, carry_out, carry_unused);
+  auto r1 = add_with_carry(prod.lo, lo_hi.lo << 32, uint64_t(0));
+  prod.lo = r1.sum;
+  prod.hi = add_with_carry(prod.hi, lo_hi.hi, r1.carry).sum;
+
+  auto r2 = add_with_carry(prod.lo, hi_lo.lo << 32, uint64_t(0));
+  prod.lo = r2.sum;
+  prod.hi = add_with_carry(prod.hi, hi_lo.hi, r2.carry).sum;
 
   return prod;
 #endif // __SIZEOF_INT128__
 }
 
 } // namespace __llvm_libc
 
 #endif // LLVM_LIBC_SRC_SUPPORT_INTEGER_UTILS_H

libc/src/__support/named_pair.h

+//===-- Utilities for pairs of numbers. -------------------------*- C++ -*-===//
+//
+// 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_NAMED_PAIR_H
+#define LLVM_LIBC_SRC_SUPPORT_NAMED_PAIR_H
+
+#define DEFINE_NAMED_PAIR_TEMPLATE(Name, FirstField, SecondField)              \
+  template <typename T1, typename T2 = T1> struct Name {                       \
+    T1 FirstField;                                                             \
+    T2 SecondField;                                                            \
+  }
+
+#endif // LLVM_LIBC_SRC_SUPPORT_NAMED_PAIR_H

libc/src/__support/number_pair.h

 //===-- Utilities for pairs of numbers. -------------------------*- C++ -*-===//
 //
 // 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_NUMBER_PAIR_H
 #define LLVM_LIBC_SRC_SUPPORT_NUMBER_PAIR_H
 
 #include "CPP/type_traits.h"
+#include "named_pair.h"
 
 #include <stddef.h>
 
 namespace __llvm_libc {
 
-template <typename T> struct NumberPair {
-  T lo;
-  T hi;
-};
+DEFINE_NAMED_PAIR_TEMPLATE(NumberPair, lo, hi);
 
 using DoubleDouble = NumberPair<double>;
 
 template <typename T>
 cpp::enable_if_t<cpp::is_integral_v<T> && cpp::is_unsigned_v<T>, NumberPair<T>>
 split(T a) {
   constexpr size_t HALF_BIT_WIDTH = sizeof(T) * 4;
   constexpr T LOWER_HALF_MASK = (T(1) << HALF_BIT_WIDTH) - T(1);

utils/bazel/llvm-project-overlay/libc/BUILD.bazel

cc_library(
     ],
 )
 
 cc_library(
     name = "__support_number_pair",
     hdrs = ["src/__support/number_pair.h"],
     deps = [
         "__support_cpp_type_traits",
+        "__support_named_pair",
         ":libc_root",
     ],
 )
 
 cc_library(
     name = "__support_integer_utils",
     hdrs = ["src/__support/integer_utils.h"],
     deps = [
cc_library(
     deps = [
         ":__support_cpp_type_traits",
         ":__support_fputil_fp_bits",
         ":libc_root",
     ],
 )
 
 cc_library(
+    name = "__support_named_pair",
+    hdrs = ["src/__support/named_pair.h"],
+    deps = [":libc_root"],
+)
+
+cc_library(
     name = "__support_builtin_wrappers",
     hdrs = ["src/__support/builtin_wrappers.h"],
     deps = [
         ":__support_cpp_type_traits",
+        ":__support_named_pair",
         ":libc_root",
     ],
 )
 
 cc_library(
     name = "__support_fputil_division_and_remainder_operations",
     hdrs = ["src/__support/FPUtil/DivisionAndRemainderOperations.h"],
     deps = [