diff --git a/libc/src/__support/CMakeLists.txt b/libc/src/__support/CMakeLists.txt --- a/libc/src/__support/CMakeLists.txt +++ b/libc/src/__support/CMakeLists.txt @@ -6,11 +6,18 @@ 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 ) @@ -111,6 +118,7 @@ HDRS number_pair.h DEPENDS + .named_pair libc.src.__support.CPP.type_traits ) diff --git a/libc/src/__support/UInt.h b/libc/src/__support/UInt.h --- a/libc/src/__support/UInt.h +++ b/libc/src/__support/UInt.h @@ -101,22 +101,20 @@ // property of unsigned integers: // x + (~x) = 2^(sizeof(x)) - 1. constexpr uint64_t add(const UInt &x) { - uint64_t carry_in = 0; - uint64_t carry_out = 0; + SumCarry 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 operator+(const UInt &other) const { UInt result; - uint64_t carry_in = 0; - uint64_t carry_out = 0; + SumCarry 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; } diff --git a/libc/src/__support/builtin_wrappers.h b/libc/src/__support/builtin_wrappers.h --- a/libc/src/__support/builtin_wrappers.h +++ b/libc/src/__support/builtin_wrappers.h @@ -10,6 +10,7 @@ #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 { @@ -67,59 +68,131 @@ } // Add with carry +DEFINE_NAMED_PAIR_TEMPLATE(SumCarry, sum, carry); + template inline constexpr cpp::enable_if_t< - cpp::is_integral_v && cpp::is_unsigned_v, T> -add_with_carry(T a, T b, T carry_in, T &carry_out) { + cpp::is_integral_v && cpp::is_unsigned_v, SumCarry> +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 a, - unsigned char b, - unsigned char carry_in, - unsigned char &carry_out) { - return __builtin_addcb(a, b, carry_in, &carry_out); +inline SumCarry +add_with_carry(unsigned char a, unsigned char b, + unsigned char carry_in) { + SumCarry result{0, 0}; + result.sum = __builtin_addcb(a, b, carry_in, &result.carry); + return result; } template <> -inline unsigned short +inline SumCarry add_with_carry(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 result{0, 0}; + result.sum = __builtin_addcs(a, b, carry_in, &result.carry); + return result; } template <> -inline unsigned int add_with_carry(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 +add_with_carry(unsigned int a, unsigned int b, + unsigned int carry_in) { + SumCarry result{0, 0}; + result.sum = __builtin_addc(a, b, carry_in, &result.carry); + return result; } template <> -inline unsigned long add_with_carry(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 +add_with_carry(unsigned long a, unsigned long b, + unsigned long carry_in) { + SumCarry result{0, 0}; + result.sum = __builtin_addcl(a, b, carry_in, &result.carry); + return result; } template <> -inline unsigned long long +inline SumCarry add_with_carry(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 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 +inline constexpr cpp::enable_if_t< + cpp::is_integral_v && cpp::is_unsigned_v, DiffBorrow> +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 +sub_with_borrow(unsigned char a, unsigned char b, + unsigned char borrow_in) { + DiffBorrow result{0, 0}; + result.diff = __builtin_subcb(a, b, borrow_in, &result.borrow); + return result; +} + +template <> +inline DiffBorrow +sub_with_borrow(unsigned short a, unsigned short b, + unsigned short borrow_in) { + DiffBorrow result{0, 0}; + result.diff = __builtin_subcs(a, b, borrow_in, &result.borrow); + return result; +} + +template <> +inline DiffBorrow +sub_with_borrow(unsigned int a, unsigned int b, + unsigned int borrow_in) { + DiffBorrow result{0, 0}; + result.diff = __builtin_subc(a, b, borrow_in, &result.borrow); + return result; +} + +template <> +inline DiffBorrow +sub_with_borrow(unsigned long a, unsigned long b, + unsigned long borrow_in) { + DiffBorrow result{0, 0}; + result.diff = __builtin_subcl(a, b, borrow_in, &result.borrow); + return result; +} + +template <> +inline DiffBorrow +sub_with_borrow(unsigned long long a, unsigned long long b, + unsigned long long borrow_in) { + DiffBorrow 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 diff --git a/libc/src/__support/integer_utils.h b/libc/src/__support/integer_utils.h --- a/libc/src/__support/integer_utils.h +++ b/libc/src/__support/integer_utils.h @@ -46,13 +46,13 @@ NumberPair lo_hi = split(pa.lo * pb.hi); // exact NumberPair 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__ diff --git a/libc/src/__support/named_pair.h b/libc/src/__support/named_pair.h new file mode 100644 --- /dev/null +++ b/libc/src/__support/named_pair.h @@ -0,0 +1,18 @@ +//===-- 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 struct Name { \ + T1 FirstField; \ + T2 SecondField; \ + } + +#endif // LLVM_LIBC_SRC_SUPPORT_NAMED_PAIR_H diff --git a/libc/src/__support/number_pair.h b/libc/src/__support/number_pair.h --- a/libc/src/__support/number_pair.h +++ b/libc/src/__support/number_pair.h @@ -10,15 +10,13 @@ #define LLVM_LIBC_SRC_SUPPORT_NUMBER_PAIR_H #include "CPP/type_traits.h" +#include "named_pair.h" #include namespace __llvm_libc { -template struct NumberPair { - T lo; - T hi; -}; +DEFINE_NAMED_PAIR_TEMPLATE(NumberPair, lo, hi); using DoubleDouble = NumberPair; diff --git a/utils/bazel/llvm-project-overlay/libc/BUILD.bazel b/utils/bazel/llvm-project-overlay/libc/BUILD.bazel --- a/utils/bazel/llvm-project-overlay/libc/BUILD.bazel +++ b/utils/bazel/llvm-project-overlay/libc/BUILD.bazel @@ -161,6 +161,7 @@ hdrs = ["src/__support/number_pair.h"], deps = [ "__support_cpp_type_traits", + "__support_named_pair", ":libc_root", ], ) @@ -230,11 +231,18 @@ ], ) +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", ], )