362 lines · c
1//===-- Memory utils --------------------------------------------*- C++ -*-===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef LLVM_LIBC_SRC_STRING_MEMORY_UTILS_UTILS_H10#define LLVM_LIBC_SRC_STRING_MEMORY_UTILS_UTILS_H11 12#include "hdr/stdint_proxy.h" // intptr_t / uintptr_t / INT32_MAX / INT32_MIN13#include "src/__support/CPP/bit.h"14#include "src/__support/CPP/cstddef.h"15#include "src/__support/CPP/type_traits.h"16#include "src/__support/endian_internal.h"17#include "src/__support/macros/attributes.h" // LIBC_INLINE18#include "src/__support/macros/config.h" // LIBC_NAMESPACE_DECL19#include "src/__support/macros/properties/architectures.h"20#include "src/__support/macros/properties/compiler.h"21 22#include <stddef.h> // size_t23 24namespace LIBC_NAMESPACE_DECL {25 26// Returns the number of bytes to substract from ptr to get to the previous27// multiple of alignment. If ptr is already aligned returns 0.28template <size_t alignment>29LIBC_INLINE uintptr_t distance_to_align_down(const void *ptr) {30 static_assert(cpp::has_single_bit(alignment),31 "alignment must be a power of 2");32 return reinterpret_cast<uintptr_t>(ptr) & (alignment - 1U);33}34 35// Returns the number of bytes to add to ptr to get to the next multiple of36// alignment. If ptr is already aligned returns 0.37template <size_t alignment>38LIBC_INLINE uintptr_t distance_to_align_up(const void *ptr) {39 static_assert(cpp::has_single_bit(alignment),40 "alignment must be a power of 2");41 // The logic is not straightforward and involves unsigned modulo arithmetic42 // but the generated code is as fast as it can be.43 return -reinterpret_cast<uintptr_t>(ptr) & (alignment - 1U);44}45 46// Returns the number of bytes to add to ptr to get to the next multiple of47// alignment. If ptr is already aligned returns alignment.48template <size_t alignment>49LIBC_INLINE uintptr_t distance_to_next_aligned(const void *ptr) {50 return alignment - distance_to_align_down<alignment>(ptr);51}52 53// Returns the same pointer but notifies the compiler that it is aligned.54template <size_t alignment, typename T> LIBC_INLINE T *assume_aligned(T *ptr) {55 return reinterpret_cast<T *>(__builtin_assume_aligned(ptr, alignment));56}57 58// Returns true iff memory regions [p1, p1 + size] and [p2, p2 + size] are59// disjoint.60LIBC_INLINE bool is_disjoint(const void *p1, const void *p2, size_t size) {61 const ptrdiff_t sdiff =62 static_cast<const char *>(p1) - static_cast<const char *>(p2);63 // We use bit_cast to make sure that we don't run into accidental integer64 // promotion. Notably the unary minus operator goes through integer promotion65 // at the expression level. We assume arithmetic to be two's complement (i.e.,66 // bit_cast has the same behavior as a regular signed to unsigned cast).67 static_assert(-1 == ~0, "not 2's complement");68 const size_t udiff = cpp::bit_cast<size_t>(sdiff);69 // Integer promition would be caught here.70 const size_t neg_udiff = cpp::bit_cast<size_t>(-sdiff);71 // This is expected to compile a conditional move.72 return sdiff >= 0 ? size <= udiff : size <= neg_udiff;73}74 75#if __has_builtin(__builtin_memcpy_inline)76#define LLVM_LIBC_HAS_BUILTIN_MEMCPY_INLINE77#endif78 79#if __has_builtin(__builtin_memset_inline)80#define LLVM_LIBC_HAS_BUILTIN_MEMSET_INLINE81#endif82 83// Performs a constant count copy.84template <size_t Size>85LIBC_INLINE void memcpy_inline(void *__restrict dst,86 const void *__restrict src) {87#ifdef LLVM_LIBC_HAS_BUILTIN_MEMCPY_INLINE88 __builtin_memcpy_inline(dst, src, Size);89#else90 // In memory functions `memcpy_inline` is instantiated several times with91 // different value of the Size parameter. This doesn't play well with GCC's92 // Value Range Analysis that wrongly detects out of bounds accesses. We93 // disable these warnings for the purpose of this function.94#ifndef LIBC_COMPILER_IS_MSVC95#pragma GCC diagnostic push96#pragma GCC diagnostic ignored "-Warray-bounds"97#pragma GCC diagnostic ignored "-Wstringop-overread"98#pragma GCC diagnostic ignored "-Wstringop-overflow"99#endif // !LIBC_COMPILER_IS_MSVC100 for (size_t i = 0; i < Size; ++i)101 static_cast<char *>(dst)[i] = static_cast<const char *>(src)[i];102#ifndef LIBC_COMPILER_IS_MSVC103#pragma GCC diagnostic pop104#endif // !LIBC_COMPILER_IS_MSVC105#endif106}107 108using Ptr = cpp::byte *; // Pointer to raw data.109using CPtr = const cpp::byte *; // Pointer to const raw data.110 111// This type makes sure that we don't accidentally promote an integral type to112// another one. It is only constructible from the exact T type.113template <typename T> struct StrictIntegralType {114 static_assert(cpp::is_integral_v<T>);115 116 // Can only be constructed from a T.117 template <typename U, cpp::enable_if_t<cpp::is_same_v<U, T>, bool> = 0>118 LIBC_INLINE StrictIntegralType(U value) : value(value) {}119 120 // Allows using the type in an if statement.121 LIBC_INLINE explicit operator bool() const { return value; }122 123 // If type is unsigned (bcmp) we allow bitwise OR operations.124 LIBC_INLINE StrictIntegralType125 operator|(const StrictIntegralType &Rhs) const {126 static_assert(!cpp::is_signed_v<T>);127 return value | Rhs.value;128 }129 130 // For interation with the C API we allow explicit conversion back to the131 // `int` type.132 LIBC_INLINE explicit operator int() const {133 // bit_cast makes sure that T and int have the same size.134 return cpp::bit_cast<int>(value);135 }136 137 // Helper to get the zero value.138 LIBC_INLINE static constexpr StrictIntegralType zero() { return {T(0)}; }139 LIBC_INLINE static constexpr StrictIntegralType nonzero() { return {T(1)}; }140 141private:142 T value;143};144 145using MemcmpReturnType = StrictIntegralType<int32_t>;146using BcmpReturnType = StrictIntegralType<uint32_t>;147 148// This implements the semantic of 'memcmp' returning a negative value when 'a'149// is less than 'b', '0' when 'a' equals 'b' and a positive number otherwise.150LIBC_INLINE MemcmpReturnType cmp_uint32_t(uint32_t a, uint32_t b) {151 // We perform the difference as an int64_t.152 const int64_t diff = static_cast<int64_t>(a) - static_cast<int64_t>(b);153 // For the int64_t to int32_t conversion we want the following properties:154 // - int32_t[31:31] == 1 iff diff < 0155 // - int32_t[31:0] == 0 iff diff == 0156 157 // We also observe that:158 // - When diff < 0: diff[63:32] == 0xffffffff and diff[31:0] != 0159 // - When diff > 0: diff[63:32] == 0 and diff[31:0] != 0160 // - When diff == 0: diff[63:32] == 0 and diff[31:0] == 0161 // - https://godbolt.org/z/8W7qWP6e5162 // - This implies that we can only look at diff[32:32] for determining the163 // sign bit for the returned int32_t.164 165 // So, we do the following:166 // - int32_t[31:31] = diff[32:32]167 // - int32_t[30:0] = diff[31:0] == 0 ? 0 : non-0.168 169 // And, we can achieve the above by the expression below. We could have also170 // used (diff64 >> 1) | (diff64 & 0x1) but (diff64 & 0xFFFF) is faster than171 // (diff64 & 0x1). https://godbolt.org/z/j3b569rW1172 return static_cast<int32_t>((diff >> 1) | (diff & 0xFFFF));173}174 175// Returns a negative value if 'a' is less than 'b' and a positive value176// otherwise. This implements the semantic of 'memcmp' when we know that 'a' and177// 'b' differ.178LIBC_INLINE MemcmpReturnType cmp_neq_uint64_t(uint64_t a, uint64_t b) {179#if defined(LIBC_TARGET_ARCH_IS_X86)180 // On x86, the best strategy would be to use 'INT32_MAX' and 'INT32_MIN' for181 // positive and negative value respectively as they are one value apart:182 // xor eax, eax <- free183 // cmp rdi, rsi <- serializing184 // adc eax, 2147483647 <- serializing185 186 // Unfortunately we found instances of client code that negate the result of187 // 'memcmp' to reverse ordering. Because signed integers are not symmetric188 // (e.g., int8_t ∈ [-128, 127]) returning 'INT_MIN' would break such code as189 // `-INT_MIN` is not representable as an int32_t.190 191 // As a consequence, we use 5 and -5 which is still OK nice in terms of192 // latency.193 // cmp rdi, rsi <- serializing194 // mov ecx, -5 <- can be done in parallel195 // mov eax, 5 <- can be done in parallel196 // cmovb eax, ecx <- serializing197 static constexpr int32_t POSITIVE = 5;198 static constexpr int32_t NEGATIVE = -5;199#else200 // On RISC-V we simply use '1' and '-1' as it leads to branchless code.201 // On ARMv8, both strategies lead to the same performance.202 static constexpr int32_t POSITIVE = 1;203 static constexpr int32_t NEGATIVE = -1;204#endif205 static_assert(POSITIVE > 0);206 static_assert(NEGATIVE < 0);207 return a < b ? NEGATIVE : POSITIVE;208}209 210// Loads bytes from memory (possibly unaligned) and materializes them as211// type.212template <typename T> LIBC_INLINE T load(CPtr ptr) {213 T out;214 memcpy_inline<sizeof(T)>(&out, ptr);215 return out;216}217 218// Stores a value of type T in memory (possibly unaligned).219template <typename T> LIBC_INLINE void store(Ptr ptr, T value) {220 memcpy_inline<sizeof(T)>(ptr, &value);221}222 223// On architectures that do not allow for unaligned access we perform several224// aligned accesses and recombine them through shifts and logicals operations.225// For instance, if we know that the pointer is 2-byte aligned we can decompose226// a 64-bit operation into four 16-bit operations.227 228// Loads a 'ValueType' by decomposing it into several loads that are assumed to229// be aligned.230// e.g. load_aligned<uint32_t, uint16_t, uint16_t>(ptr);231template <typename ValueType, typename T, typename... TS>232LIBC_INLINE ValueType load_aligned(CPtr src) {233 static_assert(sizeof(ValueType) >= (sizeof(T) + ... + sizeof(TS)));234 const ValueType value = load<T>(assume_aligned<sizeof(T)>(src));235 if constexpr (sizeof...(TS) > 0) {236 constexpr size_t SHIFT = sizeof(T) * 8;237 const ValueType next = load_aligned<ValueType, TS...>(src + sizeof(T));238 if constexpr (Endian::IS_LITTLE)239 return value | (next << SHIFT);240 else if constexpr (Endian::IS_BIG)241 return (value << SHIFT) | next;242 else243 static_assert(cpp::always_false<T>, "Invalid endianness");244 } else {245 return value;246 }247}248 249// Alias for loading a 'uint32_t'.250template <typename T, typename... TS>251LIBC_INLINE auto load32_aligned(CPtr src, size_t offset) {252 static_assert((sizeof(T) + ... + sizeof(TS)) == sizeof(uint32_t));253 return load_aligned<uint32_t, T, TS...>(src + offset);254}255 256// Alias for loading a 'uint64_t'.257template <typename T, typename... TS>258LIBC_INLINE auto load64_aligned(CPtr src, size_t offset) {259 static_assert((sizeof(T) + ... + sizeof(TS)) == sizeof(uint64_t));260 return load_aligned<uint64_t, T, TS...>(src + offset);261}262 263// Stores a 'ValueType' by decomposing it into several stores that are assumed264// to be aligned.265// e.g. store_aligned<uint32_t, uint16_t, uint16_t>(value, ptr);266template <typename ValueType, typename T, typename... TS>267LIBC_INLINE void store_aligned(ValueType value, Ptr dst) {268 static_assert(sizeof(ValueType) >= (sizeof(T) + ... + sizeof(TS)));269 constexpr size_t SHIFT = sizeof(T) * 8;270 if constexpr (Endian::IS_LITTLE) {271 store<T>(assume_aligned<sizeof(T)>(dst), T(value & T(~0)));272 if constexpr (sizeof...(TS) > 0)273 store_aligned<ValueType, TS...>(value >> SHIFT, dst + sizeof(T));274 } else if constexpr (Endian::IS_BIG) {275 constexpr size_t OFFSET = (0 + ... + sizeof(TS));276 store<T>(assume_aligned<sizeof(T)>(dst + OFFSET), value & ~T(0));277 if constexpr (sizeof...(TS) > 0)278 store_aligned<ValueType, TS...>(value >> SHIFT, dst);279 } else {280 static_assert(cpp::always_false<T>, "Invalid endianness");281 }282}283 284// Alias for storing a 'uint32_t'.285template <typename T, typename... TS>286LIBC_INLINE void store32_aligned(uint32_t value, Ptr dst, size_t offset) {287 static_assert((sizeof(T) + ... + sizeof(TS)) == sizeof(uint32_t));288 store_aligned<uint32_t, T, TS...>(value, dst + offset);289}290 291// Alias for storing a 'uint64_t'.292template <typename T, typename... TS>293LIBC_INLINE void store64_aligned(uint64_t value, Ptr dst, size_t offset) {294 static_assert((sizeof(T) + ... + sizeof(TS)) == sizeof(uint64_t));295 store_aligned<uint64_t, T, TS...>(value, dst + offset);296}297 298// Advances the pointers p1 and p2 by offset bytes and decrease count by the299// same amount.300template <typename T1, typename T2>301LIBC_INLINE void adjust(ptrdiff_t offset, T1 *__restrict &p1,302 T2 *__restrict &p2, size_t &count) {303 p1 += offset;304 p2 += offset;305 count -= static_cast<size_t>(offset);306}307 308// Advances p1 and p2 so p1 gets aligned to the next SIZE bytes boundary309// and decrease count by the same amount.310// We make sure the compiler knows about the adjusted pointer alignment.311template <size_t SIZE, typename T1, typename T2>312void align_p1_to_next_boundary(T1 *__restrict &p1, T2 *__restrict &p2,313 size_t &count) {314 adjust(static_cast<ptrdiff_t>(distance_to_next_aligned<SIZE>(p1)), p1, p2,315 count);316 p1 = assume_aligned<SIZE>(p1);317}318 319// Same as align_p1_to_next_boundary above but with a single pointer instead.320template <size_t SIZE, typename T>321LIBC_INLINE void align_to_next_boundary(T *&p1, size_t &count) {322 const T *dummy = p1;323 align_p1_to_next_boundary<SIZE>(p1, dummy, count);324}325 326// An enum class that discriminates between the first and second pointer.327enum class Arg { P1, P2, Dst = P1, Src = P2 };328 329// Same as align_p1_to_next_boundary but allows for aligning p2 instead of p1.330// Precondition: &p1 != &p2331template <size_t SIZE, Arg AlignOn, typename T1, typename T2>332LIBC_INLINE void align_to_next_boundary(T1 *__restrict &p1, T2 *__restrict &p2,333 size_t &count) {334 if constexpr (AlignOn == Arg::P1)335 align_p1_to_next_boundary<SIZE>(p1, p2, count);336 else if constexpr (AlignOn == Arg::P2)337 align_p1_to_next_boundary<SIZE>(p2, p1, count); // swapping p1 and p2.338 else339 static_assert(cpp::always_false<T1>,340 "AlignOn must be either Arg::P1 or Arg::P2");341}342 343template <size_t SIZE> struct AlignHelper {344 LIBC_INLINE AlignHelper(CPtr ptr)345 : offset(distance_to_next_aligned<SIZE>(ptr)) {}346 347 LIBC_INLINE bool not_aligned() const { return offset != SIZE; }348 uintptr_t offset;349};350 351LIBC_INLINE void prefetch_for_write(CPtr dst) {352 __builtin_prefetch(dst, /*write*/ 1, /*max locality*/ 3);353}354 355LIBC_INLINE void prefetch_to_local_cache(CPtr dst) {356 __builtin_prefetch(dst, /*read*/ 0, /*max locality*/ 3);357}358 359} // namespace LIBC_NAMESPACE_DECL360 361#endif // LLVM_LIBC_SRC_STRING_MEMORY_UTILS_UTILS_H362