op_generic.h | Explore in Territory

//===-- Generic implementation of memory function building blocks ---------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file provides generic C++ building blocks.
// Depending on the requested size, the block operation uses unsigned integral
// types, vector types or an array of the type with the maximum size.
//
// The maximum size is passed as a template argument. For instance, on x86
// platforms that only supports integral types the maximum size would be 8
// (corresponding to uint64_t). On this platform if we request the size 32, this
// would be treated as a cpp::array<uint64_t, 4>.
//
// On the other hand, if the platform is x86 with support for AVX the maximum
// size is 32 and the operation can be handled with a single native operation.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_LIBC_SRC_STRING_MEMORY_UTILS_OP_GENERIC_H
#define LLVM_LIBC_SRC_STRING_MEMORY_UTILS_OP_GENERIC_H

#include "src/__support/CPP/array.h"
#include "src/__support/CPP/type_traits.h"
#include "src/__support/common.h"
#include "src/__support/endian.h"
#include "src/__support/macros/config.h"
#include "src/__support/macros/optimization.h"
#include "src/__support/macros/properties/types.h" // LIBC_TYPES_HAS_INT64
#include "src/string/memory_utils/op_builtin.h"
#include "src/string/memory_utils/utils.h"

#include <stdint.h>

static_assert …;

namespace LIBC_NAMESPACE_DECL {
// Compiler types using the vector attributes.
generic_v128 __attribute__((__vector_size__(16)));
generic_v256 __attribute__((__vector_size__(32)));
generic_v512 __attribute__((__vector_size__(64)));
} // namespace LIBC_NAMESPACE_DECL

namespace LIBC_NAMESPACE_DECL {
namespace generic {

// We accept three types of values as elements for generic operations:
// - scalar : unsigned integral types,
// - vector : compiler types using the vector attributes or platform builtins,
// - array  : a cpp::array<T, N> where T is itself either a scalar or a vector.
// The following traits help discriminate between these cases.

template <typename T> struct is_scalar : cpp::false_type { … };
template <> struct is_scalar<uint8_t> : cpp::true_type { … };
template <> struct is_scalar<uint16_t> : cpp::true_type { … };
template <> struct is_scalar<uint32_t> : cpp::true_type { … };
#ifdef LIBC_TYPES_HAS_INT64
template <> struct is_scalar<uint64_t> : cpp::true_type { … };
#endif // LIBC_TYPES_HAS_INT64
// Meant to match std::numeric_limits interface.
// NOLINTNEXTLINE(readability-identifier-naming)
is_scalar_v;

template <typename T> struct is_vector : cpp::false_type { … };
template <> struct is_vector<generic_v128> : cpp::true_type { … };
template <> struct is_vector<generic_v256> : cpp::true_type { … };
template <> struct is_vector<generic_v512> : cpp::true_type { … };
// Meant to match std::numeric_limits interface.
// NOLINTNEXTLINE(readability-identifier-naming)
is_vector_v;

template <class T> struct is_array : cpp::false_type { … };
is_array<cpp::array<T, N>>;
// Meant to match std::numeric_limits interface.
// NOLINTNEXTLINE(readability-identifier-naming)
is_array_v;

// Meant to match std::numeric_limits interface.
// NOLINTBEGIN(readability-identifier-naming)
is_element_type_v;
// NOLINTEND(readability-identifier-naming)

// Helper struct to retrieve the number of elements of an array.
template <class T> struct array_size { … };
array_size<cpp::array<T, N>>;
// Meant to match std::numeric_limits interface.
// NOLINTNEXTLINE(readability-identifier-naming)
array_size_v;

// Generic operations for the above type categories.

template <typename T> T load(CPtr src) { … }

template <typename T> void store(Ptr dst, T value) { … }

template <typename T> T splat(uint8_t value) { … }

///////////////////////////////////////////////////////////////////////////////
// Memset
///////////////////////////////////////////////////////////////////////////////

template <typename T> struct Memset { … };

template <typename T, typename... TS> struct MemsetSequence { … };

///////////////////////////////////////////////////////////////////////////////
// Memmove
///////////////////////////////////////////////////////////////////////////////

template <typename T> struct Memmove { … };

///////////////////////////////////////////////////////////////////////////////
// Low level operations for Bcmp and Memcmp that operate on memory locations.
///////////////////////////////////////////////////////////////////////////////

// Same as load above but with an offset to the pointer.
// Making the offset explicit hints the compiler to use relevant addressing mode
// consistently.
template <typename T> LIBC_INLINE T load(CPtr ptr, size_t offset) { … }

// Same as above but also makes sure the loaded value is in big endian format.
// This is useful when implementing lexicograhic comparisons as big endian
// scalar comparison directly maps to lexicographic byte comparisons.
template <typename T> LIBC_INLINE T load_be(CPtr ptr, size_t offset) { … }

// Equality: returns true iff values at locations (p1 + offset) and (p2 +
// offset) compare equal.
template <typename T> LIBC_INLINE bool eq(CPtr p1, CPtr p2, size_t offset);

// Not equals: returns non-zero iff values at locations (p1 + offset) and (p2 +
// offset) differ.
template <typename T> LIBC_INLINE uint32_t neq(CPtr p1, CPtr p2, size_t offset);

// Lexicographic comparison:
// - returns 0 iff values at locations (p1 + offset) and (p2 + offset) compare
//   equal.
// - returns a negative value if value at location (p1 + offset) is
//   lexicographically less than value at (p2 + offset).
// - returns a positive value if value at location (p1 + offset) is
//   lexicographically greater than value at (p2 + offset).
template <typename T>
LIBC_INLINE MemcmpReturnType cmp(CPtr p1, CPtr p2, size_t offset);

// Lexicographic comparison of non-equal values:
// - returns a negative value if value at location (p1 + offset) is
//   lexicographically less than value at (p2 + offset).
// - returns a positive value if value at location (p1 + offset) is
//   lexicographically greater than value at (p2 + offset).
template <typename T>
LIBC_INLINE MemcmpReturnType cmp_neq(CPtr p1, CPtr p2, size_t offset);

///////////////////////////////////////////////////////////////////////////////
// Memcmp implementation
//
// When building memcmp, not all types are considered equals.
//
// For instance, the lexicographic comparison of two uint8_t can be implemented
// as a simple subtraction, but for wider operations the logic can be much more
// involving, especially on little endian platforms.
//
// For such wider types it is a good strategy to test for equality first and
// only do the expensive lexicographic comparison if necessary.
//
// Decomposing the algorithm like this for wider types allows us to have
// efficient implementation of higher order functions like 'head_tail' or
// 'loop_and_tail'.
///////////////////////////////////////////////////////////////////////////////

// Type traits to decide whether we can use 'cmp' directly or if we need to
// split the computation.
template <typename T> struct cmp_is_expensive;

template <typename T> struct Memcmp { … };

template <typename T, typename... TS> struct MemcmpSequence { … };

///////////////////////////////////////////////////////////////////////////////
// Bcmp
///////////////////////////////////////////////////////////////////////////////
template <typename T> struct Bcmp { … };

template <typename T, typename... TS> struct BcmpSequence { … };

///////////////////////////////////////////////////////////////////////////////
// Specializations for uint8_t
template <> struct cmp_is_expensive<uint8_t> : public cpp::false_type { … };
template <> LIBC_INLINE bool eq<uint8_t>(CPtr p1, CPtr p2, size_t offset) { … }
template <> LIBC_INLINE uint32_t neq<uint8_t>(CPtr p1, CPtr p2, size_t offset) { … }
template <>
LIBC_INLINE MemcmpReturnType cmp<uint8_t>(CPtr p1, CPtr p2, size_t offset) { … }
template <>
LIBC_INLINE MemcmpReturnType cmp_neq<uint8_t>(CPtr p1, CPtr p2, size_t offset);

} // namespace generic
} // namespace LIBC_NAMESPACE_DECL

#endif // LLVM_LIBC_SRC_STRING_MEMORY_UTILS_OP_GENERIC_H
llvm/libc/src/string/memory_utils/op_generic.h
