diff --git a/libc/cmake/modules/LLVMLibCRules.cmake b/libc/cmake/modules/LLVMLibCRules.cmake --- a/libc/cmake/modules/LLVMLibCRules.cmake +++ b/libc/cmake/modules/LLVMLibCRules.cmake @@ -317,18 +317,22 @@ set(library_deps "") foreach(dep IN LISTS LIBC_UNITTEST_DEPENDS) - get_target_property(dep_type ${dep} "TARGET_TYPE") - if (dep_type) - string(COMPARE EQUAL ${dep_type} ${ENTRYPOINT_OBJ_TARGET_TYPE} dep_is_entrypoint) - if(dep_is_entrypoint) - get_target_property(obj_file ${dep} "OBJECT_FILE_RAW") - list(APPEND library_deps ${obj_file}) - continue() + # If the dep is a normal CMake library target then add it to the list of + # library_deps. + get_property(dep_type TARGET ${dep} PROPERTY "TYPE") + if (${dep_type} MATCHES "_LIBRARY$") + list(APPEND library_deps ${dep}) + else() + get_property(dep_target_type TARGET ${dep} PROPERTY "TARGET_TYPE") + if (dep_target_type) + string(COMPARE EQUAL ${dep_target_type} ${ENTRYPOINT_OBJ_TARGET_TYPE} dep_is_entrypoint) + if(dep_is_entrypoint) + get_target_property(obj_file ${dep} "OBJECT_FILE_RAW") + list(APPEND library_deps ${obj_file}) + endif() endif() endif() - # TODO: Check if the dep is a normal CMake library target. If yes, then add it - # to the list of library_deps. - endforeach(dep) + endforeach() add_executable( ${target_name} diff --git a/libc/src/string/CMakeLists.txt b/libc/src/string/CMakeLists.txt --- a/libc/src/string/CMakeLists.txt +++ b/libc/src/string/CMakeLists.txt @@ -18,3 +18,5 @@ DEPENDS string_h ) + +add_subdirectory(memory_utils) diff --git a/libc/src/string/memory_utils/CMakeLists.txt b/libc/src/string/memory_utils/CMakeLists.txt new file mode 100644 --- /dev/null +++ b/libc/src/string/memory_utils/CMakeLists.txt @@ -0,0 +1,17 @@ +add_gen_header( + cacheline_size + DEF_FILE + cacheline_size.h.def + GEN_HDR + cacheline_size.h + PARAMS + machine_cacheline_size=cacheline_size_${LIBC_TARGET_MACHINE}.h.inc + DATA_FILES + cacheline_size_${LIBC_TARGET_MACHINE}.h.inc +) + +add_header_library( + memory_utils + HDRS utils.h + DEPENDS cacheline_size +) diff --git a/libc/src/string/memory_utils/cacheline_size.h.def b/libc/src/string/memory_utils/cacheline_size.h.def new file mode 100644 --- /dev/null +++ b/libc/src/string/memory_utils/cacheline_size.h.def @@ -0,0 +1,27 @@ +//===---------------------- Cacheline Size Constant -----------------------===// +// +// 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_MEMORY_CONSTANTS_H +#define LLVM_LIBC_SRC_MEMORY_CONSTANTS_H + +// LLVM_LIBC_CACHELINE_SIZE +// +// Explicitly defines the size of the L1 cache for purposes of alignment. +// +// NOTE: this macro should be replaced with the following C++17 features, when +// those are generally available: +// +// * `std::hardware_constructive_interference_size` +// * `std::hardware_destructive_interference_size` +// +// See http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0154r1.html +// for more information. + +%%include_file(${machine_cacheline_size}) + +#endif // LLVM_LIBC_SRC_MEMORY_CONSTANTS_H diff --git a/libc/src/string/memory_utils/cacheline_size_aarch64.h.inc b/libc/src/string/memory_utils/cacheline_size_aarch64.h.inc new file mode 100644 --- /dev/null +++ b/libc/src/string/memory_utils/cacheline_size_aarch64.h.inc @@ -0,0 +1,3 @@ +// We would need to read special register ctr_el0 to find out L1 dcache size. +// This value is a good estimate based on a real aarch64 machine. +#define LLVM_LIBC_CACHELINE_SIZE 64 diff --git a/libc/src/string/memory_utils/cacheline_size_arm.h.inc b/libc/src/string/memory_utils/cacheline_size_arm.h.inc new file mode 100644 --- /dev/null +++ b/libc/src/string/memory_utils/cacheline_size_arm.h.inc @@ -0,0 +1,9 @@ +// Cache line sizes for ARM: These values are not strictly correct since +// cache line sizes depend on implementations, not architectures. There +// are even implementations with cache line sizes configurable at boot +// time. +#if defined(__ARM_ARCH_5T__) +#define LLVM_LIBC_CACHELINE_SIZE 32 +#elif defined(__ARM_ARCH_7A__) +#define LLVM_LIBC_CACHELINE_SIZE 64 +#endif diff --git a/libc/src/string/memory_utils/cacheline_size_ppc64.h.inc b/libc/src/string/memory_utils/cacheline_size_ppc64.h.inc new file mode 100644 --- /dev/null +++ b/libc/src/string/memory_utils/cacheline_size_ppc64.h.inc @@ -0,0 +1 @@ +#define LLVM_LIBC_CACHELINE_SIZE 128 diff --git a/libc/src/string/memory_utils/cacheline_size_x86.h.inc b/libc/src/string/memory_utils/cacheline_size_x86.h.inc new file mode 100644 --- /dev/null +++ b/libc/src/string/memory_utils/cacheline_size_x86.h.inc @@ -0,0 +1 @@ +#define LLVM_LIBC_CACHELINE_SIZE 64 diff --git a/libc/src/string/memory_utils/cacheline_size_x86_64.h.inc b/libc/src/string/memory_utils/cacheline_size_x86_64.h.inc new file mode 100644 --- /dev/null +++ b/libc/src/string/memory_utils/cacheline_size_x86_64.h.inc @@ -0,0 +1 @@ +#define LLVM_LIBC_CACHELINE_SIZE 64 diff --git a/libc/src/string/memory_utils/utils.h b/libc/src/string/memory_utils/utils.h new file mode 100644 --- /dev/null +++ b/libc/src/string/memory_utils/utils.h @@ -0,0 +1,60 @@ +//===---------------------------- Memory utils ----------------------------===// +// +// 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_MEMOR_UTILS_H +#define LLVM_LIBC_SRC_MEMOR_UTILS_H + +#include "src/string/memory_utils/cacheline_size.h" + +#include // size_t +#include // intptr_t / uintptr_t + +namespace __llvm_libc { + +// Return whether `value` is zero or a power of two. +static constexpr bool is_power2_or_zero(size_t value) { + return (value & (value - 1U)) == 0; +} + +// Return whether `value` is a power of two. +static constexpr bool is_power2(size_t value) { + return value && is_power2_or_zero(value); +} + +// Compile time version of log2 that handles 0. +static constexpr size_t log2(size_t value) { + return (value == 0 || value == 1) ? 0 : 1 + log2(value / 2); +} + +// Returns the first power of two preceding value or value if it is already a +// power of two (or 0 when value is 0). +static constexpr size_t le_power2(size_t value) { + return value == 0 ? value : 1ULL << log2(value); +} + +// Returns the first power of two following value or value if it is already a +// power of two (or 0 when value is 0). +static constexpr size_t ge_power2(size_t value) { + return is_power2_or_zero(value) ? value : 1ULL << (log2(value) + 1); +} + +template intptr_t offset_to_next_aligned(const void *ptr) { + static_assert(is_power2(alignment), "alignment must be a power of 2"); + // The logic is not straightforward and involves unsigned modulo arithmetic + // but the generated code is as fast as it can be. + return -reinterpret_cast(ptr) & (alignment - 1U); +} + +// Returns the offset from `ptr` to the next cache line. +static intptr_t offset_to_next_cache_line(const void *ptr) { + return offset_to_next_aligned(ptr); +} + +} // namespace __llvm_libc + +#endif // LLVM_LIBC_SRC_MEMOR_UTILS_H diff --git a/libc/test/src/string/CMakeLists.txt b/libc/test/src/string/CMakeLists.txt --- a/libc/test/src/string/CMakeLists.txt +++ b/libc/test/src/string/CMakeLists.txt @@ -1,5 +1,7 @@ add_libc_testsuite(libc_string_unittests) +add_subdirectory(memory_utils) + add_libc_unittest( strcat_test SUITE diff --git a/libc/test/src/string/memory_utils/CMakeLists.txt b/libc/test/src/string/memory_utils/CMakeLists.txt new file mode 100644 --- /dev/null +++ b/libc/test/src/string/memory_utils/CMakeLists.txt @@ -0,0 +1,10 @@ +add_libc_unittest( + utils_test + SUITE + libc_string_unittests + SRCS + utils_test.cpp + DEPENDS + memory_utils + standalone_cpp +) diff --git a/libc/test/src/string/memory_utils/utils_test.cpp b/libc/test/src/string/memory_utils/utils_test.cpp new file mode 100644 --- /dev/null +++ b/libc/test/src/string/memory_utils/utils_test.cpp @@ -0,0 +1,103 @@ +//===-------------------- Unittests for memory_utils ----------------------===// +// +// 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/string/memory_utils/utils.h" +#include "utils/CPP/ArrayRef.h" +#include "utils/UnitTest/Test.h" + +namespace __llvm_libc { + +TEST(UtilsTest, IsPowerOfTwoOrZero) { + static const cpp::ArrayRef kExpectedValues({ + 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, // 0-15 + 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // 16-31 + 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // 32-47 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // 48-63 + 1 // 64 + }); + for (size_t i = 0; i < kExpectedValues.size(); ++i) + if (kExpectedValues[i]) + EXPECT_TRUE(is_power2_or_zero(i)); + else + EXPECT_FALSE(is_power2_or_zero(i)); +} + +TEST(UtilsTest, IsPowerOfTwo) { + static const cpp::ArrayRef kExpectedValues({ + 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, // 0-15 + 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // 16-31 + 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // 32-47 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // 48-63 + 1 // 64 + }); + for (size_t i = 0; i < kExpectedValues.size(); ++i) + if (kExpectedValues[i]) + EXPECT_TRUE(is_power2(i)); + else + EXPECT_FALSE(is_power2(i)); +} + +TEST(UtilsTest, Log2) { + static const cpp::ArrayRef kExpectedValues({ + 0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, // 0-15 + 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, // 16-31 + 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, // 32-47 + 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, // 48-63 + 6 // 64 + }); + for (size_t i = 0; i < kExpectedValues.size(); ++i) + EXPECT_EQ(log2(i), kExpectedValues[i]); +} + +TEST(UtilsTest, LEPowerOf2) { + static const cpp::ArrayRef kExpectedValues({ + 0, 1, 2, 2, 4, 4, 4, 4, 8, 8, 8, 8, 8, 8, 8, 8, // 0-15 + 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, // 16-31 + 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, // 32-47 + 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, // 48-63 + 64 // 64 + }); + for (size_t i = 0; i < kExpectedValues.size(); ++i) + EXPECT_EQ(le_power2(i), kExpectedValues[i]); +} + +TEST(UtilsTest, GEPowerOf2) { + static const cpp::ArrayRef kExpectedValues({ + 0, 1, 2, 4, 4, 8, 8, 8, 8, 16, 16, 16, 16, 16, 16, 16, // 0-15 + 16, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, // 16-31 + 32, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, // 32-47 + 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, // 48-63 + 64, 128 // 64-65 + }); + for (size_t i = 0; i < kExpectedValues.size(); ++i) + EXPECT_EQ(ge_power2(i), kExpectedValues[i]); +} + +using I = intptr_t; + +// Converts an offset into a pointer. +void *forge(size_t offset) { return reinterpret_cast(offset); }; + +TEST(UtilsTest, OffsetToNextAligned) { + EXPECT_EQ(offset_to_next_aligned<16>(forge(0)), I(0)); + EXPECT_EQ(offset_to_next_aligned<16>(forge(1)), I(15)); + EXPECT_EQ(offset_to_next_aligned<16>(forge(16)), I(0)); + EXPECT_EQ(offset_to_next_aligned<16>(forge(15)), I(1)); + EXPECT_EQ(offset_to_next_aligned<32>(forge(16)), I(16)); +} + +TEST(UtilsTest, OffsetToNextCacheLine) { + EXPECT_GT(LLVM_LIBC_CACHELINE_SIZE, 0); + EXPECT_EQ(offset_to_next_cache_line(forge(0)), I(0)); + EXPECT_EQ(offset_to_next_cache_line(forge(1)), + I(LLVM_LIBC_CACHELINE_SIZE - 1)); + EXPECT_EQ(offset_to_next_cache_line(forge(LLVM_LIBC_CACHELINE_SIZE)), I(0)); + EXPECT_EQ(offset_to_next_cache_line(forge(LLVM_LIBC_CACHELINE_SIZE - 1)), + I(1)); +} +} // namespace __llvm_libc diff --git a/libc/utils/CPP/ArrayRef.h b/libc/utils/CPP/ArrayRef.h --- a/libc/utils/CPP/ArrayRef.h +++ b/libc/utils/CPP/ArrayRef.h @@ -81,7 +81,7 @@ T *data() const { return const_cast(ArrayRef::data()); } iterator begin() const { return data(); } - iterator end() const { return data() + size(); } + iterator end() const { return data() + ArrayRef::size(); } T &operator[](size_t Index) const { return data()[Index]; } };