-
Notifications
You must be signed in to change notification settings - Fork 13.6k
[wip][libc] Implemented fixed point divifx functions in llvm-libc #138238
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
base: main
Are you sure you want to change the base?
Conversation
@llvm/pr-subscribers-libc Author: Abhinav Kumar (kr-2003) ChangesCurrently work in progressFixing #129124 Full diff: https://github.com/llvm/llvm-project/pull/138238.diff 9 Files Affected:
diff --git a/libc/config/darwin/arm/entrypoints.txt b/libc/config/darwin/arm/entrypoints.txt
index 70c888aec064c..1759da59a7e5a 100644
--- a/libc/config/darwin/arm/entrypoints.txt
+++ b/libc/config/darwin/arm/entrypoints.txt
@@ -581,6 +581,7 @@ if(LIBC_COMPILER_HAS_FIXED_POINT)
libc.src.stdfix.abslk
libc.src.stdfix.abslr
libc.src.stdfix.absr
+ libc.src.stdfix.divir
libc.src.stdfix.exphk
libc.src.stdfix.expk
libc.src.stdfix.roundhk
diff --git a/libc/include/stdfix.yaml b/libc/include/stdfix.yaml
index 5b385124eb63d..16d7650884e3c 100644
--- a/libc/include/stdfix.yaml
+++ b/libc/include/stdfix.yaml
@@ -238,6 +238,14 @@ functions:
arguments:
- type: unsigned long accum
guard: LIBC_COMPILER_HAS_FIXED_POINT
+ - name: divir
+ standards:
+ - stdc_ext
+ return_type: int
+ arguments:
+ - type: int
+ - type: fract
+ guard: LIBC_COMPILER_HAS_FIXED_POINT
- name: idivr
standards:
- stdc_ext
diff --git a/libc/src/__support/fixed_point/divifx.h b/libc/src/__support/fixed_point/divifx.h
new file mode 100644
index 0000000000000..af715612c327d
--- /dev/null
+++ b/libc/src/__support/fixed_point/divifx.h
@@ -0,0 +1,132 @@
+//===-- Division of integers by fixed-point 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
+//
+//===----------------------------------------------------------------------===//
+//
+// This file provides implementations for functions that divide a standard
+// integer type by a fixed-point type, returning a standard integer type result.
+// This corresponds to the divi<fx> family (e.g., divir, divik) described
+// in ISO/IEC TR 18037:2008 Annex C.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_LIBC_SRC___SUPPORT_FIXEDPOINT_INT_DIV_FX_H
+#define LLVM_LIBC_SRC___SUPPORT_FIXEDPOINT_INT_DIV_FX_H
+
+#include "include/llvm-libc-macros/stdfix-macros.h" // Fixed-point types
+#include "src/__support/CPP/bit.h" // bit_cast
+#include "src/__support/CPP/limits.h" // numeric_limits (optional)
+#include "src/__support/CPP/type_traits.h" // conditional_t, is_same_v
+#include "src/__support/macros/attributes.h" // LIBC_INLINE
+#include "src/__support/macros/config.h" // LIBC_NAMESPACE_DECL, LIBC_COMPILER_HAS_FIXED_POINT
+#include "src/__support/macros/optimization.h" // LIBC_UNLIKELY
+
+#include "fx_rep.h" // FXRep for type info (FRACTION_LEN, StorageType)
+
+// Only define contents if the compiler supports fixed-point types
+#ifdef LIBC_COMPILER_HAS_FIXED_POINT
+
+// Check for 128-bit integer support needed for high precision intermediates
+#if defined(__SIZEOF_INT128__)
+#define LIBC_INTERNAL_HAS_INT128
+using int128_t = __int128_t;
+using uint128_t = __uint128_t;
+#endif
+
+namespace LIBC_NAMESPACE_DECL {
+namespace fixed_point {
+namespace internal {
+
+// --- Helper type traits for selecting intermediate calculation types ---
+
+template <typename IntType, int FractionalBits>
+using SelectDivIntermediateSigned =
+ cpp::conditional_t<
+ (sizeof(IntType) * 8 - 1 + FractionalBits <= 64), int64_t,
+#ifdef LIBC_INTERNAL_HAS_INT128
+ cpp::conditional_t<(sizeof(IntType) * 8 - 1 + FractionalBits <= 128),
+ int128_t,
+ void>
+#else
+ void
+#endif
+ >;
+
+template <typename IntType, int FractionalBits>
+using SelectDivIntermediateUnsigned = cpp::conditional_t<
+ (sizeof(IntType) * 8 - 1 + FractionalBits <= 64), uint64_t,
+#ifdef LIBC_INTERNAL_HAS_INT128
+ cpp::conditional_t<(sizeof(IntType) * 8 - 1 + FractionalBits <= 128),
+ uint128_t, void>
+#else
+ void
+#endif
+ >;
+
+// --- Core implementation template ---
+
+
+template <typename IntType, typename FxType>
+LIBC_INLINE IntType divifx_impl(IntType i, FxType fx) {
+ // Get metadata about the fixed-point type using FXRep helper
+ using FX = FXRep<FxType>;
+ using StorageType = typename FX::StorageType;
+ constexpr int F = FX::FRACTION_LEN; // Number of fractional bits
+ constexpr bool FxIsSigned = FX::SIGN_LEN; // Is the fx type signed?
+
+ // Extract the raw integer bits from the fixed-point divisor
+ StorageType raw_fx = cpp::bit_cast<StorageType>(fx);
+
+ volatile StorageType check_raw_fx = raw_fx;
+ if (LIBC_UNLIKELY(check_raw_fx == 0)) {
+
+ }
+
+ // Select appropriately sized intermediate types for the calculation
+ using IntermediateSigned = SelectDivIntermediateSigned<IntType, F>;
+ using IntermediateUnsigned = SelectDivIntermediateUnsigned<IntType, F>;
+
+ // Compile-time check: ensure a wide enough type was found.
+ static_assert(!cpp::is_same_v<IntermediateSigned, void>,
+ "Calculation requires intermediate precision exceeding "
+ "available types (int64_t or __int128_t).");
+
+ // Calculate the numerator: (i << F)
+ // Use the signed intermediate type for the numerator.
+ IntermediateSigned num = static_cast<IntermediateSigned>(i) << F;
+
+ // Perform the division: num / raw_fx
+ IntermediateSigned intermediate_result;
+ if constexpr (FxIsSigned) {
+ IntermediateSigned den = static_cast<IntermediateSigned>(raw_fx);
+ intermediate_result = num / den;
+ } else {
+ IntermediateUnsigned den = static_cast<IntermediateUnsigned>(raw_fx);
+ intermediate_result = num / den;
+ }
+
+ return static_cast<IntType>(intermediate_result);
+}
+
+} // namespace internal
+
+//===----------------------------------------------------------------------===//
+// Public API: divi<fx> functions
+//===----------------------------------------------------------------------===//
+
+// --- Signed Fract Types ---
+
+/** Divides int by fract, returns int. */
+LIBC_INLINE int divir(int i, fract f) {
+ return internal::divifx_impl<int, fract>(i, f);
+}
+
+} // namespace fixed_point
+} // namespace LIBC_NAMESPACE_DECL
+
+#endif // LIBC_COMPILER_HAS_FIXED_POINT
+
+#endif // LLVM_LIBC_SRC___SUPPORT_FIXEDPOINT_INT_DIV_FX_H
diff --git a/libc/src/stdfix/CMakeLists.txt b/libc/src/stdfix/CMakeLists.txt
index 843111e3f80b1..926035199c958 100644
--- a/libc/src/stdfix/CMakeLists.txt
+++ b/libc/src/stdfix/CMakeLists.txt
@@ -26,6 +26,20 @@ foreach(suffix IN ITEMS uhr ur ulr uhk uk)
)
endforeach()
+foreach(suffix IN ITEMS r)
+ add_entrypoint_object(
+ divi${suffix}
+ HDRS
+ divi${suffix}.h
+ SRCS
+ divi${suffix}.cpp
+ COMPILE_OPTIONS
+ ${libc_opt_high_flag}
+ DEPENDS
+ libc.src.__support.fixed_point.fx_bits
+ )
+endforeach()
+
foreach(suffix IN ITEMS hr r lr hk k lk uhr ur ulr uhk uk ulk)
add_entrypoint_object(
round${suffix}
diff --git a/libc/src/stdfix/divir.cpp b/libc/src/stdfix/divir.cpp
new file mode 100644
index 0000000000000..a952f9fba492f
--- /dev/null
+++ b/libc/src/stdfix/divir.cpp
@@ -0,0 +1,13 @@
+#include "divir.h"
+#include "src/__support/common.h"
+#include "src/__support/fixed_point/divifx.h" // divifx_impl
+#include "src/__support/fixed_point/fx_bits.h"
+#include "src/__support/macros/config.h" // LIBC_NAMESPACE_DECL
+
+namespace LIBC_NAMESPACE_DECL {
+
+LLVM_LIBC_FUNCTION(int, divir, (int i, fract f)) {
+ return fixed_point::divir(i, f);
+}
+
+} // namespace LIBC_NAMESPACE_DECL
diff --git a/libc/src/stdfix/divir.h b/libc/src/stdfix/divir.h
new file mode 100644
index 0000000000000..ef803160ff1b5
--- /dev/null
+++ b/libc/src/stdfix/divir.h
@@ -0,0 +1,21 @@
+//===-- Implementation header for divir function ----------------*- 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_STDFIX_DIVIR_H
+#define LLVM_LIBC_SRC_STDFIX_DIVIR_H
+
+#include "include/llvm-libc-macros/stdfix-macros.h" // Provides 'fract' type
+#include "src/__support/macros/config.h" // LIBC_NAMESPACE_DECL
+
+namespace LIBC_NAMESPACE_DECL {
+
+int divir(int i, fract f);
+
+} // namespace LIBC_NAMESPACE_DECL
+
+#endif // LLVM_LIBC_SRC_STDFIX_DIVIR_H
diff --git a/libc/test/src/stdfix/CMakeLists.txt b/libc/test/src/stdfix/CMakeLists.txt
index e2b4bc1805f7c..d2449b628e87f 100644
--- a/libc/test/src/stdfix/CMakeLists.txt
+++ b/libc/test/src/stdfix/CMakeLists.txt
@@ -43,6 +43,23 @@ foreach(suffix IN ITEMS uhr ur ulr uhk uk)
)
endforeach()
+foreach(suffix IN ITEMS r)
+ add_libc_test(
+ divi${suffix}_test
+ SUITE
+ libc-stdfix-tests
+ HDRS
+ DiviFxTest.h
+ SRCS
+ divi${suffix}_test.cpp
+ COMPILE_OPTIONS
+ ${libc_opt_high_flag}
+ DEPENDS
+ libc.src.stdfix.divi${suffix}
+ libc.src.__support.fixed_point.fx_bits
+ )
+endforeach()
+
foreach(suffix IN ITEMS hr r lr hk k lk uhr ur ulr uhk uk ulk)
add_libc_test(
round${suffix}_test
diff --git a/libc/test/src/stdfix/DiviFxTest.h b/libc/test/src/stdfix/DiviFxTest.h
new file mode 100644
index 0000000000000..1ee2a5e7b2b48
--- /dev/null
+++ b/libc/test/src/stdfix/DiviFxTest.h
@@ -0,0 +1,40 @@
+//===-- Utility class to test bitsfx functions ------------------*- 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
+//
+//===----------------------------------------------------------------------===//
+
+#include "test/UnitTest/Test.h"
+
+#include "src/__support/fixed_point/fx_rep.h"
+#include "src/__support/fixed_point/divifx.h"
+
+template <typename T, typename XType>
+class DiviFxTest : public LIBC_NAMESPACE::testing::Test {
+
+ using FXRep = LIBC_NAMESPACE::fixed_point::FXRep<T>;
+ static constexpr T zero = FXRep::ZERO();
+ static constexpr T max = FXRep::MAX();
+ static constexpr T min = FXRep::MIN();
+ static constexpr T one_half = FXRep::ONE_HALF();
+ static constexpr T one_fourth = FXRep::ONE_FOURTH();
+ static constexpr T eps = FXRep::EPS();
+
+public:
+ typedef XType (*DiviFxFunc)(int, T);
+
+ void testSpecialNumbers(DiviFxFunc func) {
+ EXPECT_EQ(static_cast<XType>(200), func(100, one_half));
+ EXPECT_EQ(static_cast<XType>(400), func(100, one_fourth));
+ // std::cout << one_half << " " << one_fourth << std::endl;
+ }
+};
+
+#define LIST_DIVIFX_TESTS(Name, T, XType, func) \
+ using LlvmLibcDivifx##Name##Test = DiviFxTest<T, XType>; \
+ TEST_F(LlvmLibcDivifx##Name##Test, SpecialNumbers) { \
+ testSpecialNumbers(&func); \
+ } \
+ static_assert(true, "Require semicolon.")
diff --git a/libc/test/src/stdfix/divir_test.cpp b/libc/test/src/stdfix/divir_test.cpp
new file mode 100644
index 0000000000000..1fbd0f24852f5
--- /dev/null
+++ b/libc/test/src/stdfix/divir_test.cpp
@@ -0,0 +1,13 @@
+//===-- Unittests for divir -------------------------------------------===//
+//
+// 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 "DiviFxTest.h"
+
+#include "src/stdfix/divir.h"
+
+LIST_DIVIFX_TESTS(r, fract, int, LIBC_NAMESPACE::divir);
|
✅ With the latest revision this PR passed the C/C++ code formatter. |
@PiJoules For now I have tried implementing |
Casting up then shifting before an integral division I think is a good general approach. Rather than unconditionally using a 128-bit int I think it would be instead better to cast just to an appropriate storage of a higher rank. Perhaps you can add something to |
Currently work in progress
Fixing #129124