diff --git a/libc/src/__support/common.h b/libc/src/__support/common.h --- a/libc/src/__support/common.h +++ b/libc/src/__support/common.h @@ -21,6 +21,18 @@ #define UNUSED __attribute__((unused)) #endif +#ifdef __has_attribute +#define LIBC_HAVE_ATTRIBUTE(x) __has_attribute(x) +#else +#define LIBC_HAVE_ATTRIBUTE(x) 0 +#endif + +#if LIBC_HAVE_ATTRIBUTE(aligned) || (defined(__GNUC__) && !defined(__clang__)) +#define LIBC_ATTRIBUTE_FUNC_ALIGN(bytes) __attribute__((aligned(bytes))) +#else +#define LIBC_ATTRIBUTE_FUNC_ALIGN(bytes) +#endif + #ifndef LLVM_LIBC_FUNCTION_ATTR #define LLVM_LIBC_FUNCTION_ATTR #endif diff --git a/libc/src/stdio/printf_core/parser.h b/libc/src/stdio/printf_core/parser.h --- a/libc/src/stdio/printf_core/parser.h +++ b/libc/src/stdio/printf_core/parser.h @@ -59,8 +59,7 @@ #ifndef LLVM_LIBC_PRINTF_DISABLE_INDEX_MODE Parser(const char *__restrict new_str, internal::ArgList &args) : str(new_str), args_cur(args), args_start(args) { - inline_memset(reinterpret_cast(desc_arr), 0, - DESC_ARR_LEN * sizeof(TypeDesc)); + inline_memset(desc_arr, ubyte::ZERO, sizeof(desc_arr)); } #else Parser(const char *__restrict new_str, internal::ArgList &args) diff --git a/libc/src/stdio/printf_core/writer.cpp b/libc/src/stdio/printf_core/writer.cpp --- a/libc/src/stdio/printf_core/writer.cpp +++ b/libc/src/stdio/printf_core/writer.cpp @@ -22,7 +22,7 @@ constexpr size_t BUFF_SIZE = 8; char buff[BUFF_SIZE]; int result; - inline_memset(buff, new_char, BUFF_SIZE); + inline_memset(buff, static_cast(new_char), BUFF_SIZE); while (length > BUFF_SIZE) { result = write(buff, BUFF_SIZE); if (result < 0) diff --git a/libc/src/string/bcmp.cpp b/libc/src/string/bcmp.cpp --- a/libc/src/string/bcmp.cpp +++ b/libc/src/string/bcmp.cpp @@ -7,6 +7,7 @@ //===----------------------------------------------------------------------===// #include "src/string/bcmp.h" + #include "src/__support/common.h" #include "src/string/memory_utils/bcmp_implementations.h" @@ -14,8 +15,7 @@ LLVM_LIBC_FUNCTION(int, bcmp, (const void *lhs, const void *rhs, size_t count)) { - return inline_bcmp(static_cast(lhs), - static_cast(rhs), count); + return inline_bcmp(lhs, rhs, count); } } // namespace __llvm_libc diff --git a/libc/src/string/bzero.cpp b/libc/src/string/bzero.cpp --- a/libc/src/string/bzero.cpp +++ b/libc/src/string/bzero.cpp @@ -7,13 +7,14 @@ //===----------------------------------------------------------------------===// #include "src/string/bzero.h" + #include "src/__support/common.h" #include "src/string/memory_utils/memset_implementations.h" namespace __llvm_libc { LLVM_LIBC_FUNCTION(void, bzero, (void *ptr, size_t count)) { - inline_memset(reinterpret_cast(ptr), 0, count); + inline_memset(ptr, ubyte::ZERO, count); } } // namespace __llvm_libc diff --git a/libc/src/string/memcmp.cpp b/libc/src/string/memcmp.cpp --- a/libc/src/string/memcmp.cpp +++ b/libc/src/string/memcmp.cpp @@ -7,6 +7,8 @@ //===----------------------------------------------------------------------===// #include "src/string/memcmp.h" + +#include "src/__support/common.h" #include "src/string/memory_utils/memcmp_implementations.h" #include // size_t @@ -15,8 +17,7 @@ LLVM_LIBC_FUNCTION(int, memcmp, (const void *lhs, const void *rhs, size_t count)) { - return inline_memcmp(static_cast(lhs), - static_cast(rhs), count); + return inline_memcmp(lhs, rhs, count); } } // namespace __llvm_libc diff --git a/libc/src/string/memcpy.cpp b/libc/src/string/memcpy.cpp --- a/libc/src/string/memcpy.cpp +++ b/libc/src/string/memcpy.cpp @@ -7,6 +7,7 @@ //===----------------------------------------------------------------------===// #include "src/string/memcpy.h" + #include "src/__support/common.h" #include "src/string/memory_utils/memcpy_implementations.h" @@ -15,8 +16,7 @@ LLVM_LIBC_FUNCTION(void *, memcpy, (void *__restrict dst, const void *__restrict src, size_t size)) { - inline_memcpy(reinterpret_cast(dst), - reinterpret_cast(src), size); + inline_memcpy(dst, src, size); return dst; } diff --git a/libc/src/string/memmove.cpp b/libc/src/string/memmove.cpp --- a/libc/src/string/memmove.cpp +++ b/libc/src/string/memmove.cpp @@ -9,42 +9,42 @@ #include "src/string/memmove.h" #include "src/__support/common.h" -#include "src/__support/integer_operations.h" -#include "src/string/memory_utils/elements.h" +#include "src/string/memory_utils/algorithm.h" +#include "src/string/memory_utils/backends.h" #include // size_t, ptrdiff_t namespace __llvm_libc { -static inline void inline_memmove(char *dst, const char *src, size_t count) { - using namespace __llvm_libc::scalar; +static inline void inline_memmove(DstAddr<1> dst, SrcAddr<1> src, + size_t count) { + using namespace scalar; if (count == 0) return; if (count == 1) - return move<_1>(dst, src); + return _1::move(dst, src); if (count <= 4) - return move>(dst, src, count); + return HeadTail<_2>::move(dst, src, count); if (count <= 8) - return move>(dst, src, count); + return HeadTail<_4>::move(dst, src, count); if (count <= 16) - return move>(dst, src, count); + return HeadTail<_8>::move(dst, src, count); if (count <= 32) - return move>(dst, src, count); + return HeadTail<_16>::move(dst, src, count); if (count <= 64) - return move>(dst, src, count); + return HeadTail<_32>::move(dst, src, count); if (count <= 128) - return move>(dst, src, count); + return HeadTail<_64>::move(dst, src, count); using AlignedMoveLoop = Align<_16, Arg::Src>::Then>; - if (dst < src) - return move(dst, src, count); - else if (dst > src) - return move_backward(dst, src, count); + if (dst.ptr() < src.ptr()) + return AlignedMoveLoop::move(dst, src, count); + else if (dst.ptr() > src.ptr()) + return AlignedMoveLoop::move_backward(dst, src, count); } LLVM_LIBC_FUNCTION(void *, memmove, (void *dst, const void *src, size_t count)) { - inline_memmove(reinterpret_cast(dst), - reinterpret_cast(src), count); + inline_memmove(dst, src, count); return dst; } diff --git a/libc/src/string/memory_utils/algorithm.h b/libc/src/string/memory_utils/algorithm.h new file mode 100644 --- /dev/null +++ b/libc/src/string/memory_utils/algorithm.h @@ -0,0 +1,419 @@ +//===-- Algorithms to compose sized memory operations ---------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// +// +// Higher order primitives that build upon the SizedOp facility. +// They constitute the basic blocks for composing memory functions. +// This file defines the following operations: +// - Skip +// - Tail +// - HeadTail +// - Loop +// - Align +//===----------------------------------------------------------------------===// + +#ifndef LLVM_LIBC_SRC_STRING_MEMORY_UTILS_ALGORITHM_H +#define LLVM_LIBC_SRC_STRING_MEMORY_UTILS_ALGORITHM_H + +#include "src/string/memory_utils/address.h" // Address +#include "src/string/memory_utils/utils.h" // offset_to_next_aligned + +#include // ptrdiff_t + +namespace __llvm_libc { + +// An operation that allows to skip the specified amount of bytes. +template struct Skip { + template struct Then { + template + static inline void set(DstAddrT dst, ubyte value) { + NextT::set(offsetAddr(dst), value); + } + + template + static inline uint64_t isDifferent(SrcAddrT1 src1, SrcAddrT2 src2) { + return NextT::isDifferent(offsetAddr(src1), offsetAddr(src2)); + } + + template + static inline int32_t threeWayCmp(SrcAddrT1 src1, SrcAddrT2 src2) { + return NextT::threeWayCmp(offsetAddr(src1), + offsetAddr(src2)); + } + + template + static inline int32_t threeWayCmp(SrcAddrT1 src1, SrcAddrT2 src2, + size_t runtime_size) { + return NextT::threeWayCmp(offsetAddr(src1), + offsetAddr(src2), runtime_size - Bytes); + } + }; +}; + +// Compute the address of a tail operation. +// Because of the runtime size, we loose the alignment information. +template +static auto tailAddr(AddrT addr, size_t runtime_size) { + static_assert(IsAddressType::Value); + return offsetAddrAssumeAligned<1>(addr, runtime_size - Size); +} + +// Perform the operation on the last 'Size' bytes of the buffer. +// +// e.g. with +// [1234567812345678123] +// [__XXXXXXXXXXXXXX___] +// [________XXXXXXXX___] +// +// Precondition: `runtime_size >= Size`. +template struct Tail { + static constexpr size_t SIZE = SizedOp::SIZE; + template + static inline void copy(DstAddrT dst, SrcAddrT src, size_t runtime_size) { + SizedOp::copy(tailAddr(dst, runtime_size), + tailAddr(src, runtime_size)); + } + + template + static inline void move(DstAddrT dst, SrcAddrT src, size_t runtime_size) { + SizedOp::move(tailAddr(dst, runtime_size), + tailAddr(src, runtime_size)); + } + + template + static inline void set(DstAddrT dst, ubyte value, size_t runtime_size) { + SizedOp::set(tailAddr(dst, runtime_size), value); + } + + template + static inline uint64_t isDifferent(SrcAddrT1 src1, SrcAddrT2 src2, + size_t runtime_size) { + return SizedOp::isDifferent(tailAddr(src1, runtime_size), + tailAddr(src2, runtime_size)); + } + + template + static inline int32_t threeWayCmp(SrcAddrT1 src1, SrcAddrT2 src2, + size_t runtime_size) { + return SizedOp::threeWayCmp(tailAddr(src1, runtime_size), + tailAddr(src2, runtime_size)); + } +}; + +// Perform the operation on the first and last bytes of the buffer. +// This is useful for overlapping operations. +// +// e.g. with +// [1234567812345678123] +// [__XXXXXXXXXXXXXX___] +// [__XXXXXXXX_________] +// [________XXXXXXXX___] +// +// Precondition: `runtime_size >= Size && runtime_size <= 2 x Size`. +template struct HeadTail { + template + static inline void copy(DstAddrT dst, SrcAddrT src, size_t runtime_size) { + SizedOp::copy(dst, src); + Tail::copy(dst, src, runtime_size); + } + + template + static inline void move(DstAddrT dst, SrcAddrT src, size_t runtime_size) { + static constexpr size_t SIZE = SizedOp::SIZE; + auto head = SizedOp::load(src); + auto tail = SizedOp::load(tailAddr(src, runtime_size)); + SizedOp::store(tailAddr(dst, runtime_size), tail); + SizedOp::store(dst, head); + } + + template + static inline void set(DstAddrT dst, ubyte value, size_t runtime_size) { + SizedOp::set(dst, value); + Tail::set(dst, value, runtime_size); + } + + template + static inline uint64_t isDifferent(SrcAddrT1 src1, SrcAddrT2 src2, + size_t runtime_size) { + if (const auto res = SizedOp::isDifferent(src1, src2)) + return res; + return Tail::isDifferent(src1, src2, runtime_size); + } + + template + static inline int32_t threeWayCmp(SrcAddrT1 src1, SrcAddrT2 src2, + size_t runtime_size) { + if (const auto res = SizedOp::threeWayCmp(src1, src2)) + return res; + return Tail::threeWayCmp(src1, src2, runtime_size); + } +}; + +// Simple loop ending with a Tail operation. +// +// e.g. with +// [12345678123456781234567812345678] +// [__XXXXXXXXXXXXXXXXXXXXXXXXXXXX___] +// [__XXXXXXXX_______________________] +// [__________XXXXXXXX_______________] +// [__________________XXXXXXXX_______] +// [______________________XXXXXXXX___] +// +// Precondition: +// - runtime_size >= Size +template struct Loop { + static constexpr size_t SIZE = SizedOp::SIZE; + + template + static inline void copy(DstAddrT dst, SrcAddrT src, size_t runtime_size) { + size_t offset = 0; + do { + SizedOp::copy(offsetAddrMultiplesOf(dst, offset), + offsetAddrMultiplesOf(src, offset)); + offset += SIZE; + } while (offset < runtime_size - SIZE); + Tail::copy(dst, src, runtime_size); + } + + // Move forward suitable when dst < src. We load the tail bytes before + // handling the loop. + // + // e.g. Moving two bytes + // [ | | | | |] + // [___XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX___] + // [_________________________LLLLLLLL___] + // [___LLLLLLLL_________________________] + // [_SSSSSSSS___________________________] + // [___________LLLLLLLL_________________] + // [_________SSSSSSSS___________________] + // [___________________LLLLLLLL_________] + // [_________________SSSSSSSS___________] + // [_______________________SSSSSSSS_____] + template + static inline void move(DstAddrT dst, SrcAddrT src, size_t runtime_size) { + const auto tail_value = SizedOp::load(tailAddr(src, runtime_size)); + size_t offset = 0; + do { + SizedOp::move(offsetAddrMultiplesOf(dst, offset), + offsetAddrMultiplesOf(src, offset)); + offset += SIZE; + } while (offset < runtime_size - SIZE); + SizedOp::store(tailAddr(dst, runtime_size), tail_value); + } + + // Move backward suitable when dst > src. We load the head bytes before + // handling the loop. + // + // e.g. Moving two bytes + // [ | | | | |] + // [___XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX___] + // [___LLLLLLLL_________________________] + // [_________________________LLLLLLLL___] + // [___________________________SSSSSSSS_] + // [_________________LLLLLLLL___________] + // [___________________SSSSSSSS_________] + // [_________LLLLLLLL___________________] + // [___________SSSSSSSS_________________] + // [_____SSSSSSSS_______________________] + template + static inline void move_backward(DstAddrT dst, SrcAddrT src, + size_t runtime_size) { + const auto head_value = SizedOp::load(src); + ptrdiff_t offset = runtime_size - SIZE; + do { + SizedOp::move(offsetAddrMultiplesOf(dst, offset), + offsetAddrMultiplesOf(src, offset)); + offset -= SIZE; + } while (offset >= 0); + SizedOp::store(dst, head_value); + } + + template + static inline void set(DstAddrT dst, ubyte value, size_t runtime_size) { + size_t offset = 0; + do { + SizedOp::set(offsetAddrMultiplesOf(dst, offset), value); + offset += SIZE; + } while (offset < runtime_size - SIZE); + Tail::set(dst, value, runtime_size); + } + + template + static inline uint64_t isDifferent(SrcAddrT1 src1, SrcAddrT2 src2, + size_t runtime_size) { + size_t offset = 0; + do { + if (auto res = + SizedOp::isDifferent(offsetAddrMultiplesOf(src1, offset), + offsetAddrMultiplesOf(src2, offset))) + return res; + offset += SIZE; + } while (offset < runtime_size - SIZE); + return Tail::isDifferent(src1, src2, runtime_size); + } + + template + static inline int32_t threeWayCmp(SrcAddrT1 src1, SrcAddrT2 src2, + size_t runtime_size) { + size_t offset = 0; + do { + if (auto res = + SizedOp::threeWayCmp(offsetAddrMultiplesOf(src1, offset), + offsetAddrMultiplesOf(src2, offset))) + return res; + offset += SIZE; + } while (offset < runtime_size - SIZE); + return Tail::threeWayCmp(src1, src2, runtime_size); + } +}; + +// Aligns and calls the subsequent NextT operation +// +// e.g. A 16-byte Destination Aligned 32-byte Loop Copy can be written as: +// Align<16, Arg::Dst>::Then>::copy(dst, src, runtime_size); +enum class Arg { _1, _2, Dst = _1, Src = _2, Lhs = _1, Rhs = _2 }; +template struct Align { + template struct Then { + template + static inline void copy(DstAddrT dst, SrcAddrT src, size_t runtime_size) { + SizedOp::copy(dst, src); + auto aligned = align(dst, src, runtime_size); + NextT::copy(aligned.arg1, aligned.arg2, aligned.size); + } + + // Move forward suitable when dst < src. The alignment is performed with + // an HeadTail operation of size ∈ [Alignment, 2 x Alignment]. + // + // e.g. Moving two bytes and making sure src is then aligned. + // [ | | | | ] + // [____XXXXXXXXXXXXXXXXXXXXXXXXXXXX_] + // [____LLLLLLLL_____________________] + // [___________LLLLLLLL______________] + // [_SSSSSSSS________________________] + // [________SSSSSSSS_________________] + // + // e.g. Moving two bytes and making sure dst is then aligned. + // [ | | | | ] + // [____XXXXXXXXXXXXXXXXXXXXXXXXXXXX_] + // [____LLLLLLLL_____________________] + // [______LLLLLLLL___________________] + // [_SSSSSSSS________________________] + // [___SSSSSSSS______________________] + template + static inline void move(DstAddrT dst, SrcAddrT src, size_t runtime_size) { + auto aligned_after_begin = align(dst, src, runtime_size); + // We move pointers forward by Size so we can perform HeadTail. + auto aligned = aligned_after_begin.stepForward(); + HeadTail::move(dst, src, runtime_size - aligned.size); + NextT::move(aligned.arg1, aligned.arg2, aligned.size); + } + + // Move backward suitable when dst > src. The alignment is performed with + // an HeadTail operation of size ∈ [Alignment, 2 x Alignment]. + // + // e.g. Moving two bytes backward and making sure src is then aligned. + // [ | | | | ] + // [____XXXXXXXXXXXXXXXXXXXXXXXX_____] + // [ _________________LLLLLLLL_______] + // [ ___________________LLLLLLLL_____] + // [____________________SSSSSSSS_____] + // [______________________SSSSSSSS___] + // + // e.g. Moving two bytes and making sure dst is then aligned. + // [ | | | | ] + // [____XXXXXXXXXXXXXXXXXXXXXXXX_____] + // [ _______________LLLLLLLL_________] + // [ ___________________LLLLLLLL_____] + // [__________________SSSSSSSS_______] + // [______________________SSSSSSSS___] + template + static inline void move_backward(DstAddrT dst, SrcAddrT src, + size_t runtime_size) { + const auto dst_end = offsetAddrAssumeAligned<1>(dst, runtime_size); + const auto src_end = offsetAddrAssumeAligned<1>(src, runtime_size); + auto aligned_after_end = align(dst_end, src_end, 0); + // We move pointers back by 2 x Size so we can perform HeadTail. + auto aligned = aligned_after_end.stepBack().stepBack(); + HeadTail::move(aligned.arg1, aligned.arg2, aligned.size); + NextT::move_backward(dst, src, runtime_size - aligned.size); + } + + template + static inline void set(DstAddrT dst, ubyte value, size_t runtime_size) { + SizedOp::set(dst, value); + DstAddrT _(nullptr); + auto aligned = align(dst, _, runtime_size); + NextT::set(aligned.arg1, value, aligned.size); + } + + template + static inline uint64_t isDifferent(SrcAddrT1 src1, SrcAddrT2 src2, + size_t runtime_size) { + if (const auto res = SizedOp::isDifferent(src1, src2)) + return res; + auto aligned = align(src1, src2, runtime_size); + return NextT::isDifferent(aligned.arg1, aligned.arg2, aligned.size); + } + + template + static inline int32_t threeWayCmp(SrcAddrT1 src1, SrcAddrT2 src2, + size_t runtime_size) { + if (const auto res = SizedOp::threeWayCmp(src1, src2)) + return res; + auto aligned = align(src1, src2, runtime_size); + return NextT::threeWayCmp(aligned.arg1, aligned.arg2, aligned.size); + } + }; + +private: + static constexpr size_t SIZE = SizedOp::SIZE; + static_assert(SIZE > 1); + + template struct Aligned { + Arg1AddrT arg1; + Arg2AddrT arg2; + size_t size; + + Aligned stepForward() const { + return Aligned{offsetAddrMultiplesOf(arg1, SIZE), + offsetAddrMultiplesOf(arg2, SIZE), size - SIZE}; + } + + Aligned stepBack() const { + return Aligned{offsetAddrMultiplesOf(arg1, -SIZE), + offsetAddrMultiplesOf(arg2, -SIZE), size + SIZE}; + } + }; + + template + static auto makeAligned(Arg1AddrT arg1, Arg2AddrT arg2, size_t size) { + return Aligned{arg1, arg2, size}; + } + + template + static auto align(Arg1AddrT arg1, Arg2AddrT arg2, size_t runtime_size) { + static_assert(IsAddressType::Value); + static_assert(IsAddressType::Value); + if constexpr (AlignOn == Arg::_1) { + auto offset = offset_to_next_aligned(arg1.ptr_); + return makeAligned(offsetAddrAssumeAligned(arg1, offset), + offsetAddrAssumeAligned<1>(arg2, offset), + runtime_size - offset); + } else if constexpr (AlignOn == Arg::_2) { + auto offset = offset_to_next_aligned(arg2.ptr_); + return makeAligned(offsetAddrAssumeAligned<1>(arg1, offset), + offsetAddrAssumeAligned(arg2, offset), + runtime_size - offset); + } else { + DeferredStaticAssert("AlignOn must be either Arg::_1 or Arg::_2"); + } + } +}; + +} // namespace __llvm_libc + +#endif // LLVM_LIBC_SRC_STRING_MEMORY_UTILS_ALGORITHM_H diff --git a/libc/src/string/memory_utils/bcmp_implementations.h b/libc/src/string/memory_utils/bcmp_implementations.h --- a/libc/src/string/memory_utils/bcmp_implementations.h +++ b/libc/src/string/memory_utils/bcmp_implementations.h @@ -10,50 +10,45 @@ #define LLVM_LIBC_SRC_STRING_MEMORY_UTILS_BCMP_IMPLEMENTATIONS_H #include "src/__support/architectures.h" -#include "src/__support/common.h" -#include "src/string/memory_utils/elements.h" +#include "src/string/memory_utils/algorithm.h" +#include "src/string/memory_utils/backends.h" #include // size_t namespace __llvm_libc { -// Fixed-size difference between 'lhs' and 'rhs'. -template bool differs(const char *lhs, const char *rhs) { - return !Element::equals(lhs, rhs); -} -// Runtime-size difference between 'lhs' and 'rhs'. -template -bool differs(const char *lhs, const char *rhs, size_t size) { - return !Element::equals(lhs, rhs, size); -} - -static inline int inline_bcmp(const char *lhs, const char *rhs, size_t count) { +static inline uint64_t inline_bcmp_uint64_t(SrcAddr<1> lhs, SrcAddr<1> rhs, + size_t count) { #if defined(LLVM_LIBC_ARCH_X86) - using namespace ::__llvm_libc::x86; + using namespace x86; #elif defined(LLVM_LIBC_ARCH_AARCH64) - using namespace ::__llvm_libc::aarch64; + using namespace aarch64; #else - using namespace ::__llvm_libc::scalar; + using namespace scalar; #endif if (count == 0) return 0; if (count == 1) - return differs<_1>(lhs, rhs); + return _1::isDifferent(lhs, rhs); if (count == 2) - return differs<_2>(lhs, rhs); + return _2::isDifferent(lhs, rhs); if (count == 3) - return differs<_3>(lhs, rhs); + return _3::isDifferent(lhs, rhs); if (count <= 8) - return differs>(lhs, rhs, count); + return HeadTail<_4>::isDifferent(lhs, rhs, count); if (count <= 16) - return differs>(lhs, rhs, count); + return HeadTail<_8>::isDifferent(lhs, rhs, count); if (count <= 32) - return differs>(lhs, rhs, count); + return HeadTail<_16>::isDifferent(lhs, rhs, count); if (count <= 64) - return differs>(lhs, rhs, count); + return HeadTail<_32>::isDifferent(lhs, rhs, count); if (count <= 128) - return differs>(lhs, rhs, count); - return differs::Then>>(lhs, rhs, count); + return HeadTail<_64>::isDifferent(lhs, rhs, count); + return Align<_32>::Then>::isDifferent(lhs, rhs, count); +} + +static inline int inline_bcmp(SrcAddr<1> lhs, SrcAddr<1> rhs, size_t count) { + return !!inline_bcmp_uint64_t(lhs, rhs, count); } } // namespace __llvm_libc diff --git a/libc/src/string/memory_utils/memcmp_implementations.h b/libc/src/string/memory_utils/memcmp_implementations.h --- a/libc/src/string/memory_utils/memcmp_implementations.h +++ b/libc/src/string/memory_utils/memcmp_implementations.h @@ -10,93 +10,91 @@ #define LLVM_LIBC_SRC_STRING_MEMORY_UTILS_MEMCMP_IMPLEMENTATIONS_H #include "src/__support/architectures.h" -#include "src/__support/common.h" -#include "src/string/memory_utils/elements.h" +#include "src/string/memory_utils/algorithm.h" +#include "src/string/memory_utils/backends.h" #include // size_t namespace __llvm_libc { -static inline int inline_memcmp(const char *lhs, const char *rhs, - size_t count) { +static inline int inline_memcmp(SrcAddr<1> lhs, SrcAddr<1> rhs, size_t count) { #if defined(LLVM_LIBC_ARCH_X86) ///////////////////////////////////////////////////////////////////////////// // LLVM_LIBC_ARCH_X86 ///////////////////////////////////////////////////////////////////////////// - using namespace __llvm_libc::x86; + using namespace x86; if (count == 0) return 0; if (count == 1) - return three_way_compare<_1>(lhs, rhs); + return _1::threeWayCmp(lhs, rhs); if (count == 2) - return three_way_compare<_2>(lhs, rhs); + return _2::threeWayCmp(lhs, rhs); if (count == 3) - return three_way_compare<_3>(lhs, rhs); + return _3::threeWayCmp(lhs, rhs); if (count <= 8) - return three_way_compare>(lhs, rhs, count); + return HeadTail<_4>::threeWayCmp(lhs, rhs, count); if (count <= 16) - return three_way_compare>(lhs, rhs, count); + return HeadTail<_8>::threeWayCmp(lhs, rhs, count); if (count <= 32) - return three_way_compare>(lhs, rhs, count); + return HeadTail<_16>::threeWayCmp(lhs, rhs, count); if (count <= 64) - return three_way_compare>(lhs, rhs, count); + return HeadTail<_32>::threeWayCmp(lhs, rhs, count); if (count <= 128) - return three_way_compare>(lhs, rhs, count); - return three_way_compare::Then>>(lhs, rhs, count); + return HeadTail<_64>::threeWayCmp(lhs, rhs, count); + return Align<_32>::Then>::threeWayCmp(lhs, rhs, count); #elif defined(LLVM_LIBC_ARCH_AARCH64) ///////////////////////////////////////////////////////////////////////////// // LLVM_LIBC_ARCH_AARCH64 ///////////////////////////////////////////////////////////////////////////// - using namespace ::__llvm_libc::aarch64; + using namespace aarch64; if (count == 0) // [0, 0] return 0; if (count == 1) // [1, 1] - return three_way_compare<_1>(lhs, rhs); + return _1::threeWayCmp(lhs, rhs); if (count == 2) // [2, 2] - return three_way_compare<_2>(lhs, rhs); + return _2::threeWayCmp(lhs, rhs); if (count == 3) // [3, 3] - return three_way_compare<_3>(lhs, rhs); + return _3::threeWayCmp(lhs, rhs); if (count < 8) // [4, 7] - return three_way_compare>(lhs, rhs, count); + return HeadTail<_4>::threeWayCmp(lhs, rhs, count); if (count < 16) // [8, 15] - return three_way_compare>(lhs, rhs, count); + return HeadTail<_8>::threeWayCmp(lhs, rhs, count); if (unlikely(count >= 128)) // [128, ∞] - return three_way_compare::Then>>(lhs, rhs, count); - if (!equals<_16>(lhs, rhs)) // [16, 16] - return three_way_compare<_16>(lhs, rhs); + return Align<_16>::Then>::threeWayCmp(lhs, rhs, count); + if (_16::isDifferent(lhs, rhs)) // [16, 16] + return _16::threeWayCmp(lhs, rhs); if (count < 32) // [17, 31] - return three_way_compare>(lhs, rhs, count); - if (!equals::Then<_16>>(lhs, rhs)) // [32, 32] - return three_way_compare::Then<_16>>(lhs, rhs); + return Tail<_16>::threeWayCmp(lhs, rhs, count); + if (Skip<16>::Then<_16>::isDifferent(lhs, rhs)) // [32, 32] + return Skip<16>::Then<_16>::threeWayCmp(lhs, rhs); if (count < 64) // [33, 63] - return three_way_compare>(lhs, rhs, count); + return Tail<_32>::threeWayCmp(lhs, rhs, count); // [64, 127] - return three_way_compare::Then>>(lhs, rhs, count); + return Skip<32>::Then>::threeWayCmp(lhs, rhs, count); #else ///////////////////////////////////////////////////////////////////////////// // Default ///////////////////////////////////////////////////////////////////////////// - using namespace ::__llvm_libc::scalar; - + using namespace scalar; if (count == 0) return 0; if (count == 1) - return three_way_compare<_1>(lhs, rhs); + return _1::threeWayCmp(lhs, rhs); if (count == 2) - return three_way_compare<_2>(lhs, rhs); + return _2::threeWayCmp(lhs, rhs); if (count == 3) - return three_way_compare<_3>(lhs, rhs); + return _3::threeWayCmp(lhs, rhs); if (count <= 8) - return three_way_compare>(lhs, rhs, count); + return HeadTail<_4>::threeWayCmp(lhs, rhs, count); if (count <= 16) - return three_way_compare>(lhs, rhs, count); + return HeadTail<_8>::threeWayCmp(lhs, rhs, count); if (count <= 32) - return three_way_compare>(lhs, rhs, count); + return HeadTail<_16>::threeWayCmp(lhs, rhs, count); if (count <= 64) - return three_way_compare>(lhs, rhs, count); + return HeadTail<_32>::threeWayCmp(lhs, rhs, count); if (count <= 128) - return three_way_compare>(lhs, rhs, count); - return three_way_compare::Then>>(lhs, rhs, count); + return HeadTail<_64>::threeWayCmp(lhs, rhs, count); + return Align<_32>::Then>::threeWayCmp(lhs, rhs, count); #endif } diff --git a/libc/src/string/memory_utils/memcpy_implementations.h b/libc/src/string/memory_utils/memcpy_implementations.h --- a/libc/src/string/memory_utils/memcpy_implementations.h +++ b/libc/src/string/memory_utils/memcpy_implementations.h @@ -9,10 +9,11 @@ #ifndef LLVM_LIBC_SRC_STRING_MEMORY_UTILS_MEMCPY_IMPLEMENTATIONS_H #define LLVM_LIBC_SRC_STRING_MEMORY_UTILS_MEMCPY_IMPLEMENTATIONS_H +#include "src/__support/CPP/TypeTraits.h" // cpp::ConditionalType #include "src/__support/architectures.h" -#include "src/__support/common.h" -#include "src/string/memory_utils/elements.h" -#include "src/string/memory_utils/utils.h" +#include "src/__support/common.h" // LLVM_LIBC_IS_DEFINED +#include "src/string/memory_utils/algorithm.h" +#include "src/string/memory_utils/backends.h" #include // size_t @@ -37,14 +38,11 @@ namespace __llvm_libc { -static inline void inline_memcpy(char *__restrict dst, - const char *__restrict src, size_t count) { - using namespace __llvm_libc::builtin; +static inline void inline_memcpy(DstAddr<1> dst, SrcAddr<1> src, size_t count) { #if defined(LLVM_LIBC_ARCH_X86) ///////////////////////////////////////////////////////////////////////////// // LLVM_LIBC_ARCH_X86 ///////////////////////////////////////////////////////////////////////////// - // Whether to use only rep;movsb. constexpr bool USE_ONLY_REP_MOVSB = LLVM_LIBC_IS_DEFINED(LLVM_LIBC_MEMCPY_X86_USE_ONLY_REPMOVSB); @@ -59,94 +57,91 @@ -1; #endif // LLVM_LIBC_MEMCPY_X86_USE_REPMOVSB_FROM_SIZE + using namespace x86; + // Whether target supports AVX instructions. constexpr bool HAS_AVX = LLVM_LIBC_IS_DEFINED(__AVX__); - -#if defined(__AVX__) - using LoopBlockSize = _64; -#else - using LoopBlockSize = _32; -#endif - if (USE_ONLY_REP_MOVSB) - return copy(dst, src, count); - + return repmovsb(as(dst), as(src), count); if (count == 0) return; if (count == 1) - return copy<_1>(dst, src); + return _1::copy(dst, src); if (count == 2) - return copy<_2>(dst, src); + return _2::copy(dst, src); if (count == 3) - return copy<_3>(dst, src); + return _3::copy(dst, src); if (count == 4) - return copy<_4>(dst, src); + return _4::copy(dst, src); if (count < 8) - return copy>(dst, src, count); + return HeadTail<_4>::copy(dst, src, count); if (count < 16) - return copy>(dst, src, count); + return HeadTail<_8>::copy(dst, src, count); if (count < 32) - return copy>(dst, src, count); + return HeadTail<_16>::copy(dst, src, count); if (count < 64) - return copy>(dst, src, count); + return HeadTail<_32>::copy(dst, src, count); if (count < 128) - return copy>(dst, src, count); + return HeadTail<_64>::copy(dst, src, count); if (HAS_AVX && count < 256) - return copy>(dst, src, count); + return HeadTail<_128>::copy(dst, src, count); + using LoopBlock = cpp::ConditionalType; if (count <= REP_MOVS_B_SIZE) - return copy::Then>>(dst, src, - count); - return copy(dst, src, count); + return Align<_32, Arg::Dst>::Then>::copy(dst, src, count); + return repmovsb(as(dst), as(src), count); + #elif defined(LLVM_LIBC_ARCH_AARCH64) ///////////////////////////////////////////////////////////////////////////// // LLVM_LIBC_ARCH_AARCH64 ///////////////////////////////////////////////////////////////////////////// + using namespace scalar; if (count == 0) return; if (count == 1) - return copy<_1>(dst, src); + return _1::copy(dst, src); if (count == 2) - return copy<_2>(dst, src); + return _2::copy(dst, src); if (count == 3) - return copy<_3>(dst, src); + return _3::copy(dst, src); if (count == 4) - return copy<_4>(dst, src); + return _4::copy(dst, src); if (count < 8) - return copy>(dst, src, count); + return HeadTail<_4>::copy(dst, src, count); if (count < 16) - return copy>(dst, src, count); + return HeadTail<_8>::copy(dst, src, count); if (count < 32) - return copy>(dst, src, count); + return HeadTail<_16>::copy(dst, src, count); if (count < 64) - return copy>(dst, src, count); + return HeadTail<_32>::copy(dst, src, count); if (count < 128) - return copy>(dst, src, count); - return copy::Then>>(dst, src, count); + return HeadTail<_64>::copy(dst, src, count); + return Align<_16, Arg::Src>::Then>::copy(dst, src, count); #else ///////////////////////////////////////////////////////////////////////////// // Default ///////////////////////////////////////////////////////////////////////////// + using namespace scalar; if (count == 0) return; if (count == 1) - return copy<_1>(dst, src); + return _1::copy(dst, src); if (count == 2) - return copy<_2>(dst, src); + return _2::copy(dst, src); if (count == 3) - return copy<_3>(dst, src); + return _3::copy(dst, src); if (count == 4) - return copy<_4>(dst, src); + return _4::copy(dst, src); if (count < 8) - return copy>(dst, src, count); + return HeadTail<_4>::copy(dst, src, count); if (count < 16) - return copy>(dst, src, count); + return HeadTail<_8>::copy(dst, src, count); if (count < 32) - return copy>(dst, src, count); + return HeadTail<_16>::copy(dst, src, count); if (count < 64) - return copy>(dst, src, count); + return HeadTail<_32>::copy(dst, src, count); if (count < 128) - return copy>(dst, src, count); - return copy::Then>>(dst, src, count); + return HeadTail<_64>::copy(dst, src, count); + return Align<_32, Arg::Src>::Then>::copy(dst, src, count); #endif } diff --git a/libc/src/string/memory_utils/memset_implementations.h b/libc/src/string/memory_utils/memset_implementations.h --- a/libc/src/string/memory_utils/memset_implementations.h +++ b/libc/src/string/memory_utils/memset_implementations.h @@ -10,8 +10,8 @@ #define LLVM_LIBC_SRC_STRING_MEMORY_UTILS_MEMSET_IMPLEMENTATIONS_H #include "src/__support/architectures.h" -#include "src/string/memory_utils/elements.h" -#include "src/string/memory_utils/utils.h" +#include "src/string/memory_utils/algorithm.h" +#include "src/string/memory_utils/backends.h" #include // size_t @@ -48,85 +48,86 @@ // advance. SetAlignedBlocks<64> may waste up to 63 Bytes, SetAlignedBlocks<32> // may waste up to 31 Bytes. Benchmarks showed that SetAlignedBlocks<64> was not // superior for sizes that mattered. -inline static void inline_memset(char *dst, unsigned char value, size_t count) { +inline static void inline_memset(DstAddr<1> dst, ubyte value, size_t count) { #if defined(LLVM_LIBC_ARCH_X86) ///////////////////////////////////////////////////////////////////////////// // LLVM_LIBC_ARCH_X86 ///////////////////////////////////////////////////////////////////////////// - using namespace __llvm_libc::x86; + using namespace x86; if (count == 0) return; if (count == 1) - return splat_set<_1>(dst, value); + return _1::set(dst, value); if (count == 2) - return splat_set<_2>(dst, value); + return _2::set(dst, value); if (count == 3) - return splat_set<_3>(dst, value); + return _3::set(dst, value); if (count <= 8) - return splat_set>(dst, value, count); + return HeadTail<_4>::set(dst, value, count); if (count <= 16) - return splat_set>(dst, value, count); + return HeadTail<_8>::set(dst, value, count); if (count <= 32) - return splat_set>(dst, value, count); + return HeadTail<_16>::set(dst, value, count); if (count <= 64) - return splat_set>(dst, value, count); + return HeadTail<_32>::set(dst, value, count); if (count <= 128) - return splat_set>(dst, value, count); - return splat_set::Then>>(dst, value, count); + return HeadTail<_64>::set(dst, value, count); + return Align<_32, Arg::Dst>::Then>::set(dst, value, count); #elif defined(LLVM_LIBC_ARCH_AARCH64) ///////////////////////////////////////////////////////////////////////////// // LLVM_LIBC_ARCH_AARCH64 ///////////////////////////////////////////////////////////////////////////// - using namespace __llvm_libc::aarch64_memset; + using namespace aarch64; if (count == 0) return; if (count <= 3) { - splat_set<_1>(dst, value); + _1::set(dst, value); if (count > 1) - splat_set>(dst, value, count); + Tail<_2>::set(dst, value, count); return; } if (count <= 8) - return splat_set>(dst, value, count); + return HeadTail<_4>::set(dst, value, count); if (count <= 16) - return splat_set>(dst, value, count); + return HeadTail<_8>::set(dst, value, count); if (count <= 32) - return splat_set>(dst, value, count); + return HeadTail<_16>::set(dst, value, count); if (count <= 96) { - splat_set<_32>(dst, value); + _32::set(dst, value); if (count <= 64) - return splat_set>(dst, value, count); - splat_set::Then<_32>>(dst, value); - splat_set>(dst, value, count); + return Tail<_32>::set(dst, value, count); + Skip<32>::Then<_32>::set(dst, value); + Tail<_32>::set(dst, value, count); return; } - if (count < 448 || value != 0 || !AArch64ZVA(dst, count)) - return splat_set::Then>>(dst, value, count); + if (count >= 448 && value == ubyte::ZERO && hasZva()) + return Align<_64, Arg::_1>::Then>::set(dst, ubyte::ZERO, count); + else + return Align<_16, Arg::_1>::Then>::set(dst, value, count); #else ///////////////////////////////////////////////////////////////////////////// // Default ///////////////////////////////////////////////////////////////////////////// - using namespace ::__llvm_libc::scalar; - + using namespace scalar; if (count == 0) return; if (count == 1) - return splat_set<_1>(dst, value); + return _1::set(dst, value); if (count == 2) - return splat_set<_2>(dst, value); + return _2::set(dst, value); if (count == 3) - return splat_set<_3>(dst, value); + return _3::set(dst, value); if (count <= 8) - return splat_set>(dst, value, count); + return HeadTail<_4>::set(dst, value, count); if (count <= 16) - return splat_set>(dst, value, count); + return HeadTail<_8>::set(dst, value, count); if (count <= 32) - return splat_set>(dst, value, count); + return HeadTail<_16>::set(dst, value, count); if (count <= 64) - return splat_set>(dst, value, count); + return HeadTail<_32>::set(dst, value, count); if (count <= 128) - return splat_set>(dst, value, count); - return splat_set::Then>>(dst, value, count); + return HeadTail<_64>::set(dst, value, count); + return Align<_32, Arg::Dst>::Then>::set(dst, value, count); #endif } diff --git a/libc/src/string/mempcpy.cpp b/libc/src/string/mempcpy.cpp --- a/libc/src/string/mempcpy.cpp +++ b/libc/src/string/mempcpy.cpp @@ -15,11 +15,10 @@ namespace __llvm_libc { LLVM_LIBC_FUNCTION(void *, mempcpy, - (void *__restrict dest, const void *__restrict src, + (void *__restrict dst, const void *__restrict src, size_t count)) { - char *result = reinterpret_cast(dest); - inline_memcpy(result, reinterpret_cast(src), count); - return result + count; + inline_memcpy(dst, src, count); + return reinterpret_cast(dst) + count; } } // namespace __llvm_libc diff --git a/libc/src/string/memset.cpp b/libc/src/string/memset.cpp --- a/libc/src/string/memset.cpp +++ b/libc/src/string/memset.cpp @@ -7,14 +7,14 @@ //===----------------------------------------------------------------------===// #include "src/string/memset.h" + #include "src/__support/common.h" #include "src/string/memory_utils/memset_implementations.h" namespace __llvm_libc { LLVM_LIBC_FUNCTION(void *, memset, (void *dst, int value, size_t count)) { - inline_memset(reinterpret_cast(dst), - static_cast(value), count); + inline_memset(dst, static_cast(value), count); return dst; } diff --git a/libc/src/string/stpncpy.cpp b/libc/src/string/stpncpy.cpp --- a/libc/src/string/stpncpy.cpp +++ b/libc/src/string/stpncpy.cpp @@ -7,9 +7,9 @@ //===----------------------------------------------------------------------===// #include "src/string/stpncpy.h" -#include "src/string/memory_utils/memset_implementations.h" #include "src/__support/common.h" +#include "src/string/memory_utils/memset_implementations.h" namespace __llvm_libc { @@ -22,7 +22,7 @@ dest[i] = src[i]; // When n>strlen(src), n-strlen(src) \0 are appended. if (n > i) - inline_memset(dest + i, 0, n - i); + inline_memset(dest + i, ubyte::ZERO, n - i); return dest + i; } diff --git a/libc/src/string/string_utils.h b/libc/src/string/string_utils.h --- a/libc/src/string/string_utils.h +++ b/libc/src/string/string_utils.h @@ -94,7 +94,7 @@ return len; size_t n = len < size - 1 ? len : size - 1; inline_memcpy(dst, src, n); - inline_memset(dst + n, 0, size - n); + inline_memset(dst + n, ubyte::ZERO, size - n); return len; } diff --git a/libc/test/src/string/memcmp_test.cpp b/libc/test/src/string/memcmp_test.cpp --- a/libc/test/src/string/memcmp_test.cpp +++ b/libc/test/src/string/memcmp_test.cpp @@ -46,13 +46,13 @@ reset(lhs); reset(rhs); for (size_t i = 0; i < K_MAX_SIZE; ++i) - EXPECT_EQ(__llvm_libc::memcmp(lhs, rhs, i), 0); + ASSERT_EQ(__llvm_libc::memcmp(lhs, rhs, i), 0); reset(lhs); reset(rhs); for (size_t i = 0; i < K_MAX_SIZE; ++i) { rhs[i] = 'z'; - EXPECT_LT(__llvm_libc::memcmp(lhs, rhs, K_MAX_SIZE), 0); + ASSERT_LT(__llvm_libc::memcmp(lhs, rhs, K_MAX_SIZE), 0); rhs[i] = 'a'; } } 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 @@ -4,6 +4,7 @@ libc_string_unittests SRCS address_test.cpp + algorithm_test.cpp backend_test.cpp elements_test.cpp memory_access_test.cpp diff --git a/libc/test/src/string/memory_utils/algorithm_test.cpp b/libc/test/src/string/memory_utils/algorithm_test.cpp new file mode 100644 --- /dev/null +++ b/libc/test/src/string/memory_utils/algorithm_test.cpp @@ -0,0 +1,528 @@ + +#define LLVM_LIBC_USE_BUILTIN_MEMCPY_INLINE 0 + +#include "utils/UnitTest/Test.h" +#include +#include +#include + +#include + +namespace __llvm_libc { + +struct alignas(64) Buffer : cpp::Array { + bool contains(const char *ptr) const { + return ptr >= data() && ptr < (data() + size()); + } + size_t getOffset(const char *ptr) const { return ptr - data(); } + void fill(char c) { + for (auto itr = begin(); itr != end(); ++itr) + *itr = c; + } +}; + +static Buffer buffer1; +static Buffer buffer2; +static std::ostringstream LOG; + +struct TestBackend { + static constexpr bool IS_BACKEND_TYPE = true; + + template static void log(const char *Action, const char *ptr) { + LOG << Action << "<" << sizeof(T) << "> "; + if (buffer1.contains(ptr)) + LOG << "a[" << buffer1.getOffset(ptr) << "]"; + else if (buffer2.contains(ptr)) + LOG << "b[" << buffer2.getOffset(ptr) << "]"; + LOG << "\n"; + } + + template + static T load(const T *src) { + log((AS == Aligned::YES ? "LdA" : "LdU"), + reinterpret_cast(src)); + return Scalar64BitBackend::load(src); + } + + template + static void store(T *dst, T value) { + log((AS == Aligned::YES ? "StA" : "StU"), + reinterpret_cast(dst)); + Scalar64BitBackend::store(dst, value); + } + + template static inline T splat(ubyte value) { + LOG << "Splat<" << sizeof(T) << "> " << (unsigned)value << '\n'; + return Scalar64BitBackend::splat(value); + } + + template static inline uint64_t notEquals(T v1, T v2) { + LOG << "Neq<" << sizeof(T) << ">\n"; + return Scalar64BitBackend::notEquals(v1, v2); + } + + template static inline int32_t threeWayCmp(T v1, T v2) { + LOG << "Diff<" << sizeof(T) << ">\n"; + return Scalar64BitBackend::threeWayCmp(v1, v2); + } + + template using getNextType = Scalar64BitBackend::getNextType; +}; + +struct LlvmLibcAlgorithm : public testing::Test { + void SetUp() override { + LOG = std::ostringstream(); + LOG << '\n'; + } + + void fillEqual() { + buffer1.fill('a'); + buffer2.fill('a'); + } + + void fillDifferent() { + buffer1.fill('a'); + buffer2.fill('b'); + } + + const char *getTrace() { + trace_ = LOG.str(); + return trace_.c_str(); + } + + const char *stripComments(const char *expected) { + expected_.clear(); + std::stringstream ss(expected); + std::string line; + while (std::getline(ss, line, '\n')) { + const auto pos = line.find('#'); + if (pos == std::string::npos) { + expected_ += line; + } else { + auto log = line.substr(0, pos); + while (!log.empty() && std::isspace(log.back())) + log.pop_back(); + expected_ += log; + } + expected_ += '\n'; + } + return expected_.c_str(); + } + + template SrcAddr buf1(size_t offset = 0) const { + return buffer1.data() + offset; + } + template SrcAddr buf2(size_t offset = 0) const { + return buffer2.data() + offset; + } + template DstAddr dst(size_t offset = 0) const { + return buffer1.data() + offset; + } + template SrcAddr src(size_t offset = 0) const { + return buffer2.data() + offset; + } + +private: + std::string trace_; + std::string expected_; +}; + +using _8 = SizedOp; + +/////////////////////////////////////////////////////////////////////////////// +//// Testing fixed fized forward operations +/////////////////////////////////////////////////////////////////////////////// + +TEST_F(LlvmLibcAlgorithm, copy_1) { + SizedOp::copy(dst(), src()); + EXPECT_STREQ(getTrace(), stripComments(R"( +LdU<1> b[0] +StU<1> a[0] +)")); +} + +TEST_F(LlvmLibcAlgorithm, copy_15) { + SizedOp::copy(dst(), src()); + EXPECT_STREQ(getTrace(), stripComments(R"( +LdU<8> b[0] +StU<8> a[0] +LdU<4> b[8] +StU<4> a[8] +LdU<2> b[12] +StU<2> a[12] +LdU<1> b[14] +StU<1> a[14] +)")); +} + +TEST_F(LlvmLibcAlgorithm, copy_16) { + SizedOp::copy(dst(), src()); + EXPECT_STREQ(getTrace(), stripComments(R"( +LdU<8> b[0] +StU<8> a[0] +LdU<8> b[8] +StU<8> a[8] +)")); +} + +/////////////////////////////////////////////////////////////////////////////// + +TEST_F(LlvmLibcAlgorithm, move_1) { + SizedOp::move(dst(), src()); + EXPECT_STREQ(getTrace(), stripComments(R"( +LdU<1> b[0] +StU<1> a[0] +)")); +} + +TEST_F(LlvmLibcAlgorithm, move_15) { + SizedOp::move(dst(), src()); + EXPECT_STREQ(getTrace(), stripComments(R"( +LdU<8> b[0] +LdU<4> b[8] +LdU<2> b[12] +LdU<1> b[14] +StU<1> a[14] +StU<2> a[12] +StU<4> a[8] +StU<8> a[0] +)")); +} + +TEST_F(LlvmLibcAlgorithm, move_16) { + SizedOp::move(dst(), src()); + EXPECT_STREQ(getTrace(), stripComments(R"( +LdU<8> b[0] +LdU<8> b[8] +StU<8> a[8] +StU<8> a[0] +)")); +} + +/////////////////////////////////////////////////////////////////////////////// + +TEST_F(LlvmLibcAlgorithm, set_1) { + SizedOp::set(dst(), ubyte{42}); + EXPECT_STREQ(getTrace(), stripComments(R"( +Splat<1> 42 +StU<1> a[0] +)")); +} + +TEST_F(LlvmLibcAlgorithm, set_15) { + SizedOp::set(dst(), ubyte{42}); + EXPECT_STREQ(getTrace(), stripComments(R"( +Splat<8> 42 +StU<8> a[0] +Splat<4> 42 +StU<4> a[8] +Splat<2> 42 +StU<2> a[12] +Splat<1> 42 +StU<1> a[14] +)")); +} + +TEST_F(LlvmLibcAlgorithm, set_16) { + SizedOp::set(dst(), ubyte{42}); + EXPECT_STREQ(getTrace(), stripComments(R"( +Splat<8> 42 +StU<8> a[0] +Splat<8> 42 +StU<8> a[8] +)")); +} + +/////////////////////////////////////////////////////////////////////////////// + +TEST_F(LlvmLibcAlgorithm, different_1) { + fillEqual(); + SizedOp::isDifferent(buf1(), buf2()); + EXPECT_STREQ(getTrace(), stripComments(R"( +LdU<1> a[0] +LdU<1> b[0] +Neq<1> +)")); +} + +TEST_F(LlvmLibcAlgorithm, different_15) { + fillEqual(); + SizedOp::isDifferent(buf1(), buf2()); + EXPECT_STREQ(getTrace(), stripComments(R"( +LdU<8> a[0] +LdU<8> b[0] +Neq<8> +LdU<4> a[8] +LdU<4> b[8] +Neq<4> +LdU<2> a[12] +LdU<2> b[12] +Neq<2> +LdU<1> a[14] +LdU<1> b[14] +Neq<1> +)")); +} + +TEST_F(LlvmLibcAlgorithm, different_15_no_shortcircuit) { + fillDifferent(); + SizedOp::isDifferent(buf1(), buf2()); + // If buffer compare isDifferent we continue to aggregate. + EXPECT_STREQ(getTrace(), stripComments(R"( +LdU<8> a[0] +LdU<8> b[0] +Neq<8> +LdU<4> a[8] +LdU<4> b[8] +Neq<4> +LdU<2> a[12] +LdU<2> b[12] +Neq<2> +LdU<1> a[14] +LdU<1> b[14] +Neq<1> +)")); +} + +TEST_F(LlvmLibcAlgorithm, different_16) { + fillEqual(); + SizedOp::isDifferent(buf1(), buf2()); + EXPECT_STREQ(getTrace(), stripComments(R"( +LdU<8> a[0] +LdU<8> b[0] +Neq<8> +LdU<8> a[8] +LdU<8> b[8] +Neq<8> +)")); +} + +/////////////////////////////////////////////////////////////////////////////// + +TEST_F(LlvmLibcAlgorithm, three_way_cmp_eq_1) { + fillEqual(); + SizedOp::threeWayCmp(buf1(), buf2()); + // Buffer compare equal, returning 0 and no call to Diff. + EXPECT_STREQ(getTrace(), stripComments(R"( +LdU<1> a[0] +LdU<1> b[0] +Diff<1> +)")); +} + +TEST_F(LlvmLibcAlgorithm, three_way_cmp_eq_15) { + fillEqual(); + SizedOp::threeWayCmp(buf1(), buf2()); + // Buffer compare equal, returning 0 and no call to Diff. + EXPECT_STREQ(getTrace(), stripComments(R"( +LdU<8> a[0] +LdU<8> b[0] +Diff<8> +LdU<4> a[8] +LdU<4> b[8] +Diff<4> +LdU<2> a[12] +LdU<2> b[12] +Diff<2> +LdU<1> a[14] +LdU<1> b[14] +Diff<1> +)")); +} + +TEST_F(LlvmLibcAlgorithm, three_way_cmp_neq_15_shortcircuit) { + fillDifferent(); + SizedOp::threeWayCmp(buf1(), buf2()); + // If buffer compare isDifferent we stop early. + EXPECT_STREQ(getTrace(), stripComments(R"( +LdU<8> a[0] +LdU<8> b[0] +Diff<8> +)")); +} + +TEST_F(LlvmLibcAlgorithm, three_way_cmp_eq_16) { + fillEqual(); + SizedOp::threeWayCmp(buf1(), buf2()); + // Buffer compare equal, returning 0 and no call to Diff. + EXPECT_STREQ(getTrace(), stripComments(R"( +LdU<8> a[0] +LdU<8> b[0] +Diff<8> +LdU<8> a[8] +LdU<8> b[8] +Diff<8> +)")); +} + +/////////////////////////////////////////////////////////////////////////////// +//// Testing tail operations +/////////////////////////////////////////////////////////////////////////////// + +TEST_F(LlvmLibcAlgorithm, tail_copy_8) { + Tail<_8>::copy(dst(), src(), 16); + EXPECT_STREQ(getTrace(), stripComments(R"( +LdU<8> b[8] +StU<8> a[8] +)")); +} + +TEST_F(LlvmLibcAlgorithm, tail_move_8) { + Tail<_8>::move(dst(), src(), 16); + EXPECT_STREQ(getTrace(), stripComments(R"( +LdU<8> b[8] +StU<8> a[8] +)")); +} + +TEST_F(LlvmLibcAlgorithm, tail_set_8) { + Tail<_8>::set(dst(), ubyte{42}, 16); + EXPECT_STREQ(getTrace(), stripComments(R"( +Splat<8> 42 +StU<8> a[8] +)")); +} + +TEST_F(LlvmLibcAlgorithm, tail_different_8) { + fillEqual(); + Tail<_8>::isDifferent(buf1(), buf2(), 16); + EXPECT_STREQ(getTrace(), stripComments(R"( +LdU<8> a[8] +LdU<8> b[8] +Neq<8> +)")); +} + +TEST_F(LlvmLibcAlgorithm, tail_three_way_cmp_8) { + fillEqual(); + Tail<_8>::threeWayCmp(buf1(), buf2(), 16); + EXPECT_STREQ(getTrace(), stripComments(R"( +LdU<8> a[8] +LdU<8> b[8] +Diff<8> +)")); +} + +/////////////////////////////////////////////////////////////////////////////// +//// Testing HeadTail operations +/////////////////////////////////////////////////////////////////////////////// + +TEST_F(LlvmLibcAlgorithm, head_tail_copy_8) { + HeadTail<_8>::copy(dst(), src(), 16); + EXPECT_STREQ(getTrace(), stripComments(R"( +LdU<8> b[0] +StU<8> a[0] +LdU<8> b[8] +StU<8> a[8] +)")); +} + +/////////////////////////////////////////////////////////////////////////////// +//// Testing Loop operations +/////////////////////////////////////////////////////////////////////////////// + +TEST_F(LlvmLibcAlgorithm, loop_copy_one_iteration_and_tail) { + Loop<_8>::copy(dst(), src(), 10); + EXPECT_STREQ(getTrace(), stripComments(R"( +LdU<8> b[0] +StU<8> a[0] # covers 0-7 +LdU<8> b[2] +StU<8> a[2] # covers 2-9 +)")); +} + +TEST_F(LlvmLibcAlgorithm, loop_copy_two_iteration_and_tail) { + Loop<_8>::copy(dst(), src(), 17); + EXPECT_STREQ(getTrace(), stripComments(R"( +LdU<8> b[0] +StU<8> a[0] # covers 0-7 +LdU<8> b[8] +StU<8> a[8] # covers 8-15 +LdU<8> b[9] +StU<8> a[9] # covers 9-16 +)")); +} + +TEST_F(LlvmLibcAlgorithm, loop_with_one_turn_is_inefficient_but_ok) { + Loop<_8>::copy(dst(), src(), 8); + EXPECT_STREQ(getTrace(), stripComments(R"( +LdU<8> b[0] +StU<8> a[0] # first iteration covers 0-7 +LdU<8> b[0] # tail also covers 0-7 but since Loop is supposed to be used +StU<8> a[0] # with a sufficient number of iterations the tail cost is amortised +)")); +} + +TEST_F(LlvmLibcAlgorithm, loop_with_round_number_of_turn) { + Loop<_8>::copy(dst(), src(), 24); + EXPECT_STREQ(getTrace(), stripComments(R"( +LdU<8> b[0] +StU<8> a[0] # first iteration covers 0-7 +LdU<8> b[8] +StU<8> a[8] # second iteration covers 8-15 +LdU<8> b[16] +StU<8> a[16] +)")); +} + +TEST_F(LlvmLibcAlgorithm, dst_aligned_loop) { + Loop<_8>::copy(dst<16>(), src(), 23); + EXPECT_STREQ(getTrace(), stripComments(R"( +LdU<8> b[0] +StA<8> a[0] # store is aligned on 16B +LdU<8> b[8] +StA<8> a[8] # subsequent stores are aligned +LdU<8> b[15] +StU<8> a[15] # Tail is always unaligned +)")); +} + +TEST_F(LlvmLibcAlgorithm, aligned_loop) { + Loop<_8>::copy(dst<16>(), src<8>(), 23); + EXPECT_STREQ(getTrace(), stripComments(R"( +LdA<8> b[0] # load is aligned on 8B +StA<8> a[0] # store is aligned on 16B +LdA<8> b[8] # subsequent loads are aligned +StA<8> a[8] # subsequent stores are aligned +LdU<8> b[15] # Tail is always unaligned +StU<8> a[15] # Tail is always unaligned +)")); +} + +/////////////////////////////////////////////////////////////////////////////// +//// Testing Align operations +/////////////////////////////////////////////////////////////////////////////// + +TEST_F(LlvmLibcAlgorithm, align_dst_copy_8) { + Align<_8, Arg::Dst>::Then>::copy(dst(2), src(3), 31); + EXPECT_STREQ(getTrace(), stripComments(R"( +LdU<8> b[3] +StU<8> a[2] # First store covers unaligned bytes +LdU<8> b[9] +StA<8> a[8] # First aligned store +LdU<8> b[17] +StA<8> a[16] # Subsequent stores are aligned +LdU<8> b[25] +StA<8> a[24] # Subsequent stores are aligned +LdU<8> b[26] +StU<8> a[25] # Last store covers remaining bytes +)")); +} + +TEST_F(LlvmLibcAlgorithm, align_src_copy_8) { + Align<_8, Arg::Src>::Then>::copy(dst(2), src(3), 31); + EXPECT_STREQ(getTrace(), stripComments(R"( +LdU<8> b[3] # First load covers unaligned bytes +StU<8> a[2] +LdA<8> b[8] # First aligned load +StU<8> a[7] +LdA<8> b[16] # Subsequent loads are aligned +StU<8> a[15] +LdA<8> b[24] # Subsequent loads are aligned +StU<8> a[23] +LdU<8> b[26] # Last load covers remaining bytes +StU<8> a[25] +)")); +} + +} // namespace __llvm_libc 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 @@ -783,9 +783,13 @@ cc_library( name = "string_memory_utils", hdrs = [ - "src/string/memory_utils/elements.h", - "src/string/memory_utils/elements_aarch64.h", - "src/string/memory_utils/elements_x86.h", + "src/string/memory_utils/address.h", + "src/string/memory_utils/algorithm.h", + "src/string/memory_utils/backends.h", + "src/string/memory_utils/backend_scalar.h", + "src/string/memory_utils/backend_x86.h", + "src/string/memory_utils/backend_aarch64.h", + "src/string/memory_utils/sized_op.h", "src/string/memory_utils/utils.h", ], textual_hdrs = [ @@ -797,6 +801,7 @@ deps = [ ":__support_common", ":__support_cpp_bit", + ":__support_cpp_type_traits", ":libc_root", ], )