diff --git a/libc/src/string/memory_utils/CMakeLists.txt b/libc/src/string/memory_utils/CMakeLists.txt --- a/libc/src/string/memory_utils/CMakeLists.txt +++ b/libc/src/string/memory_utils/CMakeLists.txt @@ -2,6 +2,7 @@ memory_utils HDRS utils.h + elements.h memcpy_utils.h memset_utils.h ) diff --git a/libc/src/string/memory_utils/elements.h b/libc/src/string/memory_utils/elements.h new file mode 100644 --- /dev/null +++ b/libc/src/string/memory_utils/elements.h @@ -0,0 +1,407 @@ +//===-- Elementary operations to compose memory primitives ----------------===// +// +// 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_STRING_MEMORY_UTILS_ELEMENTS_H +#define LLVM_LIBC_SRC_STRING_MEMORY_UTILS_ELEMENTS_H + +#include // size_t +#include // uint8_t, uint16_t, uint32_t, uint64_t + +#include "src/__support/endian.h" +#include "src/string/memory_utils/utils.h" + +namespace __llvm_libc { + +// Fixed-size Elementary Operations +// -------------------------------- +// We define abstract elementary operations acting on fixed chunks of memory. +// These are low level building blocks that are meant to be assembled to compose +// higher order abstractions. + +// Copies 'Element::kSize' bytes from 'src' to 'dst'. +template +void Copy(char *__restrict dst, const char *__restrict src) { + Element::Copy(dst, src); +} + +// Checks whether the 'Element::kSize' first bytes of 'lhs' and 'rhs' compare +// equal. +template bool Equals(const char *lhs, const char *rhs) { + return Element::Equals(lhs, rhs); +} + +// Computes the three-way comparison of the 'Element::kSize' first bytes +// between 'lhs' and 'rhs'. +template +int ThreeWayCompare(const char *lhs, const char *rhs) { + return Element::ThreeWayCompare(lhs, rhs); +} + +// Sets the 'Element::kSize' first bytes of 'dst' to 'value'. +template +void SplatSet(char *dst, const unsigned char value) { + Element::SplatSet(dst, value); +} + +// Fixed-size Scalar Operations +// ---------------------------- + +// The Scalar type makes use of simple sized integers. +template struct Scalar { + static constexpr size_t kSize = sizeof(T); + + static void Copy(char *__restrict dst, const char *__restrict src) { + Store(dst, Load(src)); + } + + static bool Equals(const char *lhs, const char *rhs) { + return Load(lhs) == Load(rhs); + } + + static int ThreeWayCompare(const char *lhs, const char *rhs) { + return ScalarThreeWayCompare(Load(lhs), Load(rhs)); + } + + static void SplatSet(char *dst, const unsigned char value) { + Store(dst, GetSplattedValue(value)); + } + +private: + static T Load(const char *ptr) { + T value; + __builtin_memcpy_inline(&value, ptr, kSize); + return value; + } + static void Store(char *ptr, T value) { + __builtin_memcpy_inline(ptr, &value, kSize); + } + static T GetSplattedValue(const unsigned char value) { + return T(~0) / T(0xFF) * T(value); + } + static int ScalarThreeWayCompare(T a, T b); +}; + +template <> +inline int Scalar::ScalarThreeWayCompare(uint8_t a, uint8_t b) { + const int16_t la = Endian::ToBigEndian(a); + const int16_t lb = Endian::ToBigEndian(b); + return la - lb; +} +template <> +inline int Scalar::ScalarThreeWayCompare(uint16_t a, uint16_t b) { + const int32_t la = Endian::ToBigEndian(a); + const int32_t lb = Endian::ToBigEndian(b); + return la - lb; +} +template <> +inline int Scalar::ScalarThreeWayCompare(uint32_t a, uint32_t b) { + const int64_t la = Endian::ToBigEndian(a); + const int64_t lb = Endian::ToBigEndian(b); + const int64_t diff = la - lb; + return diff ? (diff < 0 ? -1 : 1) : 0; +} +template <> +inline int Scalar::ScalarThreeWayCompare(uint64_t a, uint64_t b) { + const __int128_t la = Endian::ToBigEndian(a); + const __int128_t lb = Endian::ToBigEndian(b); + const __int128_t diff = la - lb; + return diff ? (diff < 0 ? -1 : 1) : 0; +} + +using UINT8 = Scalar; // 1 Byte +using UINT16 = Scalar; // 2 Bytes +using UINT32 = Scalar; // 4 Bytes +using UINT64 = Scalar; // 8 Bytes + +// Fixed-size Higher-Order Operations +// ---------------------------------- +// - Repeated: Repeat the operation several times in a row. +// - Chained: Chain the operation of several types. + +// Repeat the operation several times in a row. +template struct Repeated { + static constexpr size_t kSize = ElementCount * Element::kSize; + + static void Copy(char *__restrict dst, const char *__restrict src) { + for (size_t i = 0; i < ElementCount; ++i) { + const size_t offset = i * Element::kSize; + Element::Copy(dst + offset, src + offset); + } + } + + static bool Equals(const char *lhs, const char *rhs) { + for (size_t i = 0; i < ElementCount; ++i) { + const size_t offset = i * Element::kSize; + if (!Element::Equals(lhs + offset, rhs + offset)) + return false; + } + return true; + } + + static int ThreeWayCompare(const char *lhs, const char *rhs) { + for (size_t i = 0; i < ElementCount; ++i) { + const size_t offset = i * Element::kSize; + // We make the assumption that 'Equals' si cheaper than 'ThreeWayCompare'. + if (Element::Equals(lhs + offset, rhs + offset)) + continue; + return Element::ThreeWayCompare(lhs + offset, rhs + offset); + } + return 0; + } + + static void SplatSet(char *dst, const unsigned char value) { + for (size_t i = 0; i < ElementCount; ++i) { + const size_t offset = i * Element::kSize; + Element::SplatSet(dst + offset, value); + } + } +}; + +// Chain the operation of several types. +// For instance, to handle a 3 bytes operation, one can use: +// Chained::Operation(); +template struct Chained; + +template struct Chained { + static constexpr size_t kSize = Head::kSize + Chained::kSize; + + static void Copy(char *__restrict dst, const char *__restrict src) { + Chained::Copy(dst + Head::kSize, src + Head::kSize); + __llvm_libc::Copy(dst, src); + } + + static bool Equals(const char *lhs, const char *rhs) { + if (!__llvm_libc::Equals(lhs, rhs)) + return false; + return Chained::Equals(lhs + Head::kSize, rhs + Head::kSize); + } + + static int ThreeWayCompare(const char *lhs, const char *rhs) { + if (__llvm_libc::Equals(lhs, rhs)) + return Chained::ThreeWayCompare(lhs + Head::kSize, + rhs + Head::kSize); + return __llvm_libc::ThreeWayCompare(lhs, rhs); + } + + static void SplatSet(char *dst, const unsigned char value) { + Chained::SplatSet(dst + Head::kSize, value); + __llvm_libc::SplatSet(dst, value); + } +}; + +template <> struct Chained<> { + static constexpr size_t kSize = 0; + static void Copy(char *__restrict dst, const char *__restrict src) {} + static bool Equals(const char *lhs, const char *rhs) { return true; } + static int ThreeWayCompare(const char *lhs, const char *rhs) { return 0; } + static void SplatSet(char *dst, const unsigned char value) {} +}; + +// Runtime-size Elementary Operations +// ---------------------------------- +// We define abstract elementary operations acting on chunks of memory. +// These are low level building blocks that are meant to be assembled to compose +// higher order abstractions. + +// Copies 'Element::kSize' bytes from 'src' to 'dst'. +template +void Copy(char *__restrict dst, const char *__restrict src, size_t size) { + Element::Copy(dst, src, size); +} + +// Checks whether the 'Element::kSize' first bytes of 'lhs' and 'rhs' compare +// equal. +template +bool Equals(const char *lhs, const char *rhs, size_t size) { + return Element::Equals(lhs, rhs, size); +} + +// Computes the three-way comparison of the 'Element::kSize' first bytes +// between 'lhs' and 'rhs'. +template +int ThreeWayCompare(const char *lhs, const char *rhs, size_t size) { + return Element::ThreeWayCompare(lhs, rhs, size); +} + +// Sets the 'Element::kSize' first bytes of 'dst' to 'value'. +template +void SplatSet(char *dst, const unsigned char value, size_t size) { + Element::SplatSet(dst, value, size); +} + +// Runtime-size Higher-Order Operations +// ------------------------------------ +// - Tail: Perform the operation on the last 'T::kSize' bytes of the buffer. +// - HeadTail: Perform the operation on the first and last 'T::kSize' bytes +// of the buffer. +// - Loop: Perform a loop of fixed-sized operations. + +// Perform the operation on the last 'T::kSize' bytes of the buffer. +// +// e.g. with +// [1234567812345678123] +// [__XXXXXXXXXXXXXX___] +// [________XXXXXXXX___] +// +// Precondition: `size >= T::kSize`. +template struct Tail { + static void Copy(char *__restrict dst, const char *__restrict src, + size_t size) { + return T::Copy(dst + offset(size), src + offset(size)); + } + + static bool Equals(const char *lhs, const char *rhs, size_t size) { + return T::Equals(lhs + offset(size), rhs + offset(size)); + } + + static int ThreeWayCompare(const char *lhs, const char *rhs, size_t size) { + return T::ThreeWayCompare(lhs + offset(size), rhs + offset(size)); + } + + static void SplatSet(char *dst, const unsigned char value, size_t size) { + return T::SplatSet(dst + offset(size), value); + } + + static size_t offset(size_t size) { return size - T::kSize; } +}; + +// Perform the operation on the first and last 'T::kSize' bytes of the buffer. +// This is useful for overlapping operations. +// +// e.g. with +// [1234567812345678123] +// [__XXXXXXXXXXXXXX___] +// [__XXXXXXXX_________] +// [________XXXXXXXX___] +// +// Precondition: `size >= T::kSize && size <= 2 x T::kSize`. +template struct HeadTail { + static void Copy(char *__restrict dst, const char *__restrict src, + size_t size) { + T::Copy(dst, src); + Tail::Copy(dst, src, size); + } + + static bool Equals(const char *lhs, const char *rhs, size_t size) { + if (!T::Equals(lhs, rhs)) + return false; + return Tail::Equals(lhs, rhs, size); + } + + static int ThreeWayCompare(const char *lhs, const char *rhs, size_t size) { + if (const int result = T::ThreeWayCompare(lhs, rhs)) + return result; + return Tail::ThreeWayCompare(lhs, rhs, size); + } + + static void SplatSet(char *dst, const unsigned char value, size_t size) { + T::SplatSet(dst, value); + Tail::SplatSet(dst, value, size); + } +}; + +// Simple loop ending with a Tail operation. +// +// e.g. with +// [12345678123456781234567812345678] +// [__XXXXXXXXXXXXXXXXXXXXXXXXXXXX___] +// [__XXXXXXXX_______________________] +// [__________XXXXXXXX_______________] +// [__________________XXXXXXXX_______] +// [______________________XXXXXXXX___] +// +// Precondition: +// - size >= T::kSize +template struct Loop { + static void Copy(char *__restrict dst, const char *__restrict src, + size_t size) { + for (size_t offset = 0; offset < size - T::kSize; offset += T::kSize) + T::Copy(dst + offset, src + offset); + Tail::Copy(dst, src, size); + } + + static bool Equals(const char *lhs, const char *rhs, size_t size) { + for (size_t offset = 0; offset < size - T::kSize; offset += T::kSize) + if (!T::Equals(lhs + offset, rhs + offset)) + return false; + return Tail::Equals(lhs, rhs, size); + } + + static int ThreeWayCompare(const char *lhs, const char *rhs, size_t size) { + for (size_t offset = 0; offset < size - T::kSize; offset += T::kSize) + if (const int result = T::ThreeWayCompare(lhs + offset, rhs + offset)) + return result; + return Tail::ThreeWayCompare(lhs, rhs, size); + } + + static void SplatSet(char *dst, const unsigned char value, size_t size) { + for (size_t offset = 0; offset < size - T::kSize; offset += T::kSize) + T::SplatSet(dst + offset, value); + Tail::SplatSet(dst, value, size); + } +}; + +// Same as 'Loop' but starts with a first operation to align underlying buffers. +// +// e.g. with +// [12345678123456781234567812345678] +// [__XXXXXXXXXXXXXXXXXXXXXXXXXXXX___] +// [__XXXX___________________________] +// [_____XXXXXXXX____________________] +// [_____________XXXXXXXX____________] +// [_____________________XXXXXXXX____] +// [______________________XXXXXXXX___] +// +// Precondition: +// - size >= T::kSize +// - AlignmentT::kSize >= 1 +template +struct AlignedLoop { +private: + static_assert(AlignmentT::kSize > 1, "Alignment must be more than 1"); + static_assert(is_power2(AlignmentT::kSize), "Alignment must be a power of 2"); + + static intptr_t offset_from_last_aligned(const void *a, const void *b) { + return ::__llvm_libc::offset_from_last_aligned( + AlignOnFirstPointer ? a : b); + } + +public: + static void Copy(char *__restrict dst, const char *__restrict src, + size_t size) { + AlignmentT::Copy(dst, src); + const size_t ofla = offset_from_last_aligned(dst, src); + Loop::Copy(dst + ofla, src + ofla, size - ofla); + } + + static bool Equals(const char *lhs, const char *rhs, size_t size) { + if (!AlignmentT::Equals(lhs, rhs)) + return false; + const size_t ofla = offset_from_last_aligned(lhs, rhs); + return Loop::Equals(lhs + ofla, rhs + ofla, size - ofla); + } + + static int ThreeWayCompare(const char *lhs, const char *rhs, size_t size) { + if (const int result = AlignmentT::ThreeWayCompare(lhs, rhs)) + return result; + const size_t ofla = offset_from_last_aligned(lhs, rhs); + return Loop::ThreeWayCompare(lhs + ofla, rhs + ofla, size - ofla); + } + + static void SplatSet(char *dst, const unsigned char value, size_t size) { + AlignmentT::SplatSet(dst, value); + const size_t ofla = offset_from_last_aligned(dst, dst); + Loop::SplatSet(dst + ofla, value, size - ofla); + } +}; + +} // namespace __llvm_libc + +#include + +#endif // LLVM_LIBC_SRC_STRING_MEMORY_UTILS_ELEMENTS_H diff --git a/libc/src/string/memory_utils/elements_x86.h b/libc/src/string/memory_utils/elements_x86.h new file mode 100644 --- /dev/null +++ b/libc/src/string/memory_utils/elements_x86.h @@ -0,0 +1,122 @@ +//===-- Elementary operations for x86 -------------------------------------===// +// +// 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_STRING_MEMORY_UTILS_ELEMENTS_X86_H +#define LLVM_LIBC_SRC_STRING_MEMORY_UTILS_ELEMENTS_X86_H + +#include // size_t +#include // uint8_t, uint16_t, uint32_t, uint64_t + +#ifdef __SSE2__ +#include +#endif // __SSE2__ + +// Fixed-size Vector Operations +// ---------------------------- + +namespace __llvm_libc { +namespace x86 { + +#ifdef __SSE2__ +template struct Vector : public Base { + static void Copy(char *dst, const char *src) { + Base::Store(dst, Base::Load(src)); + } + + static bool Equals(const char *a, const char *b) { + return Base::NotEqualMask(Base::Load(a), Base::Load(b)) == 0; + } + + static int ThreeWayCompare(const char *a, const char *b) { + const auto mask = Base::NotEqualMask(Base::Load(a), Base::Load(b)); + if (!mask) + return 0; + return CharDiff(a, b, mask); + } + + static void SplatSet(char *dst, const unsigned char value) { + Base::Store(dst, Base::GetSplattedValue(value)); + } + + static int CharDiff(const char *a, const char *b, uint64_t mask) { + const size_t diff_index = __builtin_ctzl(mask); + const int ca = (unsigned char)a[diff_index]; + const int cb = (unsigned char)b[diff_index]; + return ca - cb; + } +}; + +struct M128 { + static constexpr size_t kSize = 16; + using T = char __attribute__((__vector_size__(kSize))); + static uint16_t mask(T value) { return _mm_movemask_epi8(value); } + static uint16_t NotEqualMask(T a, T b) { return mask(a != b); } + static T Load(const char *ptr) { + return _mm_loadu_si128(reinterpret_cast<__m128i_u const *>(ptr)); + } + static void Store(char *ptr, T value) { + return _mm_storeu_si128(reinterpret_cast<__m128i_u *>(ptr), value); + } + static T GetSplattedValue(const char v) { + const T splatted = {v, v, v, v, v, v, v, v, v, v, v, v, v, v, v, v}; + return splatted; + } +}; + +using Vector128 = Vector; // 16 Bytes + +#ifdef __AVX2__ +struct M256 { + static constexpr size_t kSize = 32; + using T = char __attribute__((__vector_size__(kSize))); + static uint32_t mask(T value) { return _mm256_movemask_epi8(value); } + static uint32_t NotEqualMask(T a, T b) { return mask(a != b); } + static T Load(const char *ptr) { + return _mm256_loadu_si256(reinterpret_cast<__m256i const *>(ptr)); + } + static void Store(char *ptr, T value) { + return _mm256_storeu_si256(reinterpret_cast<__m256i *>(ptr), value); + } + static T GetSplattedValue(const char v) { + const T splatted = {v, v, v, v, v, v, v, v, v, v, v, v, v, v, v, v, + v, v, v, v, v, v, v, v, v, v, v, v, v, v, v, v}; + return splatted; + } +}; + +using Vector256 = Vector; // 32 Bytes + +#if defined(__AVX512F__) and defined(__AVX512BW__) +struct M512 { + static constexpr size_t kSize = 64; + using T = char __attribute__((__vector_size__(kSize))); + static uint64_t NotEqualMask(T a, T b) { + return _mm512_cmpneq_epi8_mask(a, b); + } + static T Load(const char *ptr) { return _mm512_loadu_epi8(ptr); } + static void Store(char *ptr, T value) { + return _mm512_storeu_epi8(ptr, value); + } + static T GetSplattedValue(const char v) { + const T splatted = {v, v, v, v, v, v, v, v, v, v, v, v, v, v, v, v, + v, v, v, v, v, v, v, v, v, v, v, v, v, v, v, v, + v, v, v, v, v, v, v, v, v, v, v, v, v, v, v, v, + v, v, v, v, v, v, v, v, v, v, v, v, v, v, v, v}; + return splatted; + } +}; +using Vector512 = Vector; + +#endif // defined(__AVX512F__) and defined(__AVX512BW__) +#endif // __AVX2__ +#endif // __SSE2__ + +} // namespace x86 +} // namespace __llvm_libc + +#endif // LLVM_LIBC_SRC_STRING_MEMORY_UTILS_ELEMENTS_X86_H diff --git a/libc/test/src/string/memory_utils/CMakeLists.txt b/libc/test/src/string/memory_utils/CMakeLists.txt --- a/libc/test/src/string/memory_utils/CMakeLists.txt +++ b/libc/test/src/string/memory_utils/CMakeLists.txt @@ -3,11 +3,15 @@ SUITE libc_string_unittests SRCS + elements_test.cpp + memory_access_test.cpp utils_test.cpp memcpy_utils_test.cpp DEPENDS libc.src.string.memory_utils.memory_utils libc.utils.CPP.standalone_cpp + COMPILE_OPTIONS + -march=native ) target_compile_definitions( diff --git a/libc/test/src/string/memory_utils/elements_test.cpp b/libc/test/src/string/memory_utils/elements_test.cpp new file mode 100644 --- /dev/null +++ b/libc/test/src/string/memory_utils/elements_test.cpp @@ -0,0 +1,107 @@ +//===-- 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/elements.h" +#include "utils/CPP/Array.h" +#include "utils/UnitTest/Test.h" +#include + +namespace __llvm_libc { + +// Registering Types +using FixedSizeTypes = testing::TypeList< +#ifdef __SSE2__ + x86::Vector128, // + Repeated, // + Repeated, // + Repeated, // + Repeated, // +#endif // __SSE2__ +#ifdef __AVX2__ + x86::Vector256, // + Repeated, // + Repeated, // + Repeated, // +#endif // __AVX2__ +#if defined(__AVX512F__) and defined(__AVX512BW__) + x86::Vector512, // + Repeated, // + Repeated, // +#endif // defined(__AVX512F__) and defined(__AVX512BW__) + UINT8, // + UINT16, // + UINT32, // + UINT64, // + Repeated, // + Repeated, // + Repeated, // + Repeated, // + Repeated, // + Chained, // + Chained>; + +char GetRandomChar() { + static constexpr const uint64_t a = 1103515245; + static constexpr const uint64_t c = 12345; + static constexpr const uint64_t m = 1ULL << 31; + static uint64_t seed = 123456789; + seed = (a * seed + c) % m; + return seed; +} + +template using Buffer = cpp::Array; +template Buffer GetRandomBuffer() { + Buffer buffer; + for (auto ¤t : buffer) + current = GetRandomChar(); + return buffer; +} + +TYPED_TEST(LlvmLibcMemoryElements, Copy, FixedSizeTypes) { + Buffer Dst; + const auto buffer = GetRandomBuffer(); + Copy(Dst.data(), buffer.data()); + for (size_t i = 0; i < ParamType::kSize; ++i) + EXPECT_EQ(Dst[i], buffer[i]); +} + +TYPED_TEST(LlvmLibcMemoryElements, Equals, FixedSizeTypes) { + const auto buffer = GetRandomBuffer(); + EXPECT_TRUE(Equals(buffer.data(), buffer.data())); +} + +TYPED_TEST(LlvmLibcMemoryElements, ThreeWayCompare, FixedSizeTypes) { + Buffer initial; + for (auto &c : initial) + c = 5; + + // Testing equality + EXPECT_EQ(ThreeWayCompare(initial.data(), initial.data()), 0); + + // Testing all mismatching positions + for (size_t i = 0; i < ParamType::kSize; ++i) { + auto copy = initial; + ++copy[i]; // Copy is now lexicographycally greated than initial + const auto *less = initial.data(); + const auto *greater = copy.data(); + EXPECT_LT(ThreeWayCompare(less, greater), 0); + EXPECT_GT(ThreeWayCompare(greater, less), 0); + } +} + +TYPED_TEST(LlvmLibcMemoryElements, Splat, FixedSizeTypes) { + Buffer Dst; + const cpp::Array values = {char(0x00), char(0x7F), char(0xFF)}; + for (char value : values) { + SplatSet(Dst.data(), value); + for (size_t i = 0; i < ParamType::kSize; ++i) + EXPECT_EQ(Dst[i], value); + } +} + +} // namespace __llvm_libc diff --git a/libc/test/src/string/memory_utils/memory_access_test.cpp b/libc/test/src/string/memory_utils/memory_access_test.cpp new file mode 100644 --- /dev/null +++ b/libc/test/src/string/memory_utils/memory_access_test.cpp @@ -0,0 +1,232 @@ +//===-- 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 +// +//===----------------------------------------------------------------------===// + +#define LLVM_LIBC_UNITTEST_OBSERVE 1 + +#include "src/string/memory_utils/elements.h" +#include "utils/CPP/Array.h" +#include "utils/CPP/ArrayRef.h" +#include "utils/UnitTest/Test.h" + +#include +#include + +namespace __llvm_libc { + +static constexpr const size_t kMaxBuffer = 32; + +struct BufferAccess : cpp::Array { + BufferAccess() { Reset(); } + void Reset() { + for (auto &value : *this) + value = '0'; + this->operator[](kMaxBuffer) = '\0'; + } + void Touch(ptrdiff_t offset, size_t size) { + if (offset < 0) + return; + for (size_t i = 0; i < size; ++i) + ++(*this)[offset + i]; + } + operator const char *() const { return this->data(); } +}; + +struct Buffer { + ptrdiff_t Offset(const char *ptr) const { + const bool contained = ptr >= data.begin() && ptr < data.end(); + return contained ? ptr - data.begin() : -1; + } + void Reset() { + reads.Reset(); + writes.Reset(); + } + cpp::Array data; + BufferAccess __attribute__((aligned(64))) reads; + BufferAccess __attribute__((aligned(64))) writes; +}; + +struct MemoryAccessObserver { + void ObserveRead(const char *ptr, size_t size) { + Buffer1.reads.Touch(Buffer1.Offset(ptr), size); + Buffer2.reads.Touch(Buffer2.Offset(ptr), size); + } + + void ObserveWrite(const char *ptr, size_t size) { + Buffer1.writes.Touch(Buffer1.Offset(ptr), size); + Buffer2.writes.Touch(Buffer2.Offset(ptr), size); + } + + void Reset() { + Buffer1.Reset(); + Buffer2.Reset(); + } + + Buffer Buffer1; + Buffer Buffer2; +}; + +MemoryAccessObserver Observer; + +template struct TestingElement { + static constexpr size_t kSize = Size; + + static void Copy(char *__restrict dst, const char *__restrict src) { + Observer.ObserveRead(src, kSize); + Observer.ObserveWrite(dst, kSize); + } + + static bool Equals(const char *lhs, const char *rhs) { + Observer.ObserveRead(lhs, kSize); + Observer.ObserveRead(rhs, kSize); + return true; + } + + static int ThreeWayCompare(const char *lhs, const char *rhs) { + Observer.ObserveRead(lhs, kSize); + Observer.ObserveRead(rhs, kSize); + return 0; + } + + static void SplatSet(char *dst, const unsigned char value) { + Observer.ObserveWrite(dst, kSize); + } +}; + +using Types = testing::TypeList< + TestingElement<1>, // 1 Byte + TestingElement<2>, // 2 Bytes + TestingElement<4>, // 4 Bytes + Repeated, 3>, // 6 Bytes + Chained, TestingElement<2>, TestingElement<1>> // 7 Bytes + >; + +struct LlvmLibcTestAccessBase : public testing::Test { + + template + void checkOperations(const BufferAccess &expected) { + static const BufferAccess untouched; + + Observer.Reset(); + HigherOrder::Copy(dst_ptr() + Offset, src_ptr() + Offset, Size); + ASSERT_STREQ(src().writes, untouched); + ASSERT_STREQ(dst().reads, untouched); + ASSERT_STREQ(src().reads, expected); + ASSERT_STREQ(dst().writes, expected); + Observer.Reset(); + HigherOrder::Equals(lhs_ptr() + Offset, rhs_ptr() + Offset, Size); + ASSERT_STREQ(lhs().writes, untouched); + ASSERT_STREQ(rhs().writes, untouched); + ASSERT_STREQ(lhs().reads, expected); + ASSERT_STREQ(rhs().reads, expected); + Observer.Reset(); + HigherOrder::ThreeWayCompare(lhs_ptr() + Offset, rhs_ptr() + Offset, Size); + ASSERT_STREQ(lhs().writes, untouched); + ASSERT_STREQ(rhs().writes, untouched); + ASSERT_STREQ(lhs().reads, expected); + ASSERT_STREQ(rhs().reads, expected); + Observer.Reset(); + HigherOrder::SplatSet(dst_ptr() + Offset, 5, Size); + ASSERT_STREQ(src().reads, untouched); + ASSERT_STREQ(src().writes, untouched); + ASSERT_STREQ(dst().reads, untouched); + ASSERT_STREQ(dst().writes, expected); + } + + void checkMaxAccess(const BufferAccess &expected, int max) { + for (size_t i = 0; i < kMaxBuffer; ++i) { + int value = (int)expected[i] - '0'; + if (value < 0 || value > max) { + printf("expected no more than %d access, was '%s'\n", max, + (const char *)expected); + ASSERT_LE(value, max); + } + } + } + +private: + const Buffer &lhs() const { return Observer.Buffer1; } + const Buffer &rhs() const { return Observer.Buffer2; } + const Buffer &src() const { return Observer.Buffer2; } + const Buffer &dst() const { return Observer.Buffer1; } + Buffer &dst() { return Observer.Buffer1; } + + char *dst_ptr() { return dst().data.begin(); } + const char *src_ptr() { return src().data.begin(); } + const char *lhs_ptr() { return lhs().data.begin(); } + const char *rhs_ptr() { return rhs().data.begin(); } +}; + +template +struct LlvmLibcTestAccessTail : public LlvmLibcTestAccessBase { + + void TearDown() override { + static constexpr size_t Size = 10; + + BufferAccess expected; + expected.Touch(Size - ParamType::kSize, ParamType::kSize); + + checkMaxAccess(expected, 1); + checkOperations, Size>(expected); + } +}; +TYPED_TEST_F(LlvmLibcTestAccessTail, Operations, Types) {} + +template +struct LlvmLibcTestAccessHeadTail : public LlvmLibcTestAccessBase { + void TearDown() override { + static constexpr size_t Size = 10; + + BufferAccess expected; + expected.Touch(0, ParamType::kSize); + expected.Touch(Size - ParamType::kSize, ParamType::kSize); + + checkMaxAccess(expected, 2); + checkOperations, Size>(expected); + } +}; +TYPED_TEST_F(LlvmLibcTestAccessHeadTail, Operations, Types) {} + +template +struct LlvmLibcTestAccessLoop : public LlvmLibcTestAccessBase { + void TearDown() override { + static constexpr size_t Size = 20; + + BufferAccess expected; + for (size_t i = 0; i < Size - ParamType::kSize; i += ParamType::kSize) + expected.Touch(i, ParamType::kSize); + expected.Touch(Size - ParamType::kSize, ParamType::kSize); + + checkMaxAccess(expected, 2); + checkOperations, Size>(expected); + } +}; +TYPED_TEST_F(LlvmLibcTestAccessLoop, Operations, Types) {} + +template +struct LlvmLibcTestAccessAlignedLoop : public LlvmLibcTestAccessBase { + void TearDown() override { + static constexpr size_t Size = 10; + static constexpr size_t Offset = 2; + static constexpr size_t Alignment = 4; + using AlignmentT = TestingElement; + + BufferAccess expected; + expected.Touch(Offset, AlignmentT::kSize); + for (size_t i = AlignmentT::kSize; i < Offset + Size - ParamType::kSize; + i += ParamType::kSize) + expected.Touch(i, ParamType::kSize); + expected.Touch(Offset + Size - ParamType::kSize, ParamType::kSize); + + checkMaxAccess(expected, 3); + checkOperations, Size, Offset>( + expected); + } +}; +TYPED_TEST_F(LlvmLibcTestAccessAlignedLoop, Operations, Types) {} + +} // namespace __llvm_libc