341 lines · c
1//===-- x86 implementation of memory function building blocks -------------===//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// This file provides x86 specific building blocks to compose memory functions.10//11//===----------------------------------------------------------------------===//12#ifndef LLVM_LIBC_SRC_STRING_MEMORY_UTILS_OP_X86_H13#define LLVM_LIBC_SRC_STRING_MEMORY_UTILS_OP_X86_H14 15#include "src/__support/macros/attributes.h" // LIBC_INLINE16#include "src/__support/macros/config.h" // LIBC_NAMESPACE_DECL17#include "src/__support/macros/properties/architectures.h"18#include "src/__support/macros/properties/compiler.h"19 20#if defined(LIBC_TARGET_ARCH_IS_X86)21 22#include "src/__support/common.h"23#include "src/string/memory_utils/op_builtin.h"24#include "src/string/memory_utils/op_generic.h"25 26#if defined(__AVX512BW__) || defined(__AVX512F__) || defined(__AVX2__) || \27 defined(__SSE2__)28#include <immintrin.h>29#endif30 31// Define fake functions to prevent the compiler from failing on undefined32// functions in case the CPU extension is not present.33#if !defined(__AVX512BW__) && (defined(_MSC_VER) || defined(__SCE__))34#undef _mm512_cmpneq_epi8_mask35#define _mm512_cmpneq_epi8_mask(A, B) 036#endif37#if !defined(__AVX2__) && (defined(_MSC_VER) || defined(__SCE__))38#undef _mm256_movemask_epi839#define _mm256_movemask_epi8(A) 040#endif41#if !defined(__SSE2__) && (defined(_MSC_VER) || defined(__SCE__))42#undef _mm_movemask_epi843#define _mm_movemask_epi8(A) 044#endif45 46namespace LIBC_NAMESPACE_DECL {47namespace x86 {48 49// A set of constants to check compile time features.50LIBC_INLINE_VAR constexpr bool K_SSE2 = LLVM_LIBC_IS_DEFINED(__SSE2__);51LIBC_INLINE_VAR constexpr bool K_SSE41 = LLVM_LIBC_IS_DEFINED(__SSE4_1__);52LIBC_INLINE_VAR constexpr bool K_AVX = LLVM_LIBC_IS_DEFINED(__AVX__);53LIBC_INLINE_VAR constexpr bool K_AVX2 = LLVM_LIBC_IS_DEFINED(__AVX2__);54LIBC_INLINE_VAR constexpr bool K_AVX512_F = LLVM_LIBC_IS_DEFINED(__AVX512F__);55LIBC_INLINE_VAR constexpr bool K_AVX512_BW = LLVM_LIBC_IS_DEFINED(__AVX512BW__);56 57///////////////////////////////////////////////////////////////////////////////58// Memcpy repmovsb implementation59struct Memcpy {60 LIBC_INLINE static void repmovsb(void *dst, const void *src, size_t count) {61#ifdef LIBC_COMPILER_IS_MSVC62 __movsb(static_cast<unsigned char *>(dst),63 static_cast<const unsigned char *>(src), count);64#else65 asm volatile("rep movsb" : "+D"(dst), "+S"(src), "+c"(count) : : "memory");66#endif // LIBC_COMPILER_IS_MSVC67 }68};69 70} // namespace x8671} // namespace LIBC_NAMESPACE_DECL72 73namespace LIBC_NAMESPACE_DECL {74namespace generic {75 76///////////////////////////////////////////////////////////////////////////////77// Specializations for uint16_t78template <> struct cmp_is_expensive<uint16_t> : public cpp::false_type {};79template <> LIBC_INLINE bool eq<uint16_t>(CPtr p1, CPtr p2, size_t offset) {80 return load<uint16_t>(p1, offset) == load<uint16_t>(p2, offset);81}82template <>83LIBC_INLINE uint32_t neq<uint16_t>(CPtr p1, CPtr p2, size_t offset) {84 return load<uint16_t>(p1, offset) ^ load<uint16_t>(p2, offset);85}86template <>87LIBC_INLINE MemcmpReturnType cmp<uint16_t>(CPtr p1, CPtr p2, size_t offset) {88 return static_cast<int32_t>(load_be<uint16_t>(p1, offset)) -89 static_cast<int32_t>(load_be<uint16_t>(p2, offset));90}91template <>92LIBC_INLINE MemcmpReturnType cmp_neq<uint16_t>(CPtr p1, CPtr p2, size_t offset);93 94///////////////////////////////////////////////////////////////////////////////95// Specializations for uint32_t96template <> struct cmp_is_expensive<uint32_t> : public cpp::false_type {};97template <> LIBC_INLINE bool eq<uint32_t>(CPtr p1, CPtr p2, size_t offset) {98 return load<uint32_t>(p1, offset) == load<uint32_t>(p2, offset);99}100template <>101LIBC_INLINE uint32_t neq<uint32_t>(CPtr p1, CPtr p2, size_t offset) {102 return load<uint32_t>(p1, offset) ^ load<uint32_t>(p2, offset);103}104template <>105LIBC_INLINE MemcmpReturnType cmp<uint32_t>(CPtr p1, CPtr p2, size_t offset) {106 const auto a = load_be<uint32_t>(p1, offset);107 const auto b = load_be<uint32_t>(p2, offset);108 return cmp_uint32_t(a, b);109}110template <>111LIBC_INLINE MemcmpReturnType cmp_neq<uint32_t>(CPtr p1, CPtr p2, size_t offset);112 113///////////////////////////////////////////////////////////////////////////////114// Specializations for uint64_t115template <> struct cmp_is_expensive<uint64_t> : public cpp::true_type {};116template <> LIBC_INLINE bool eq<uint64_t>(CPtr p1, CPtr p2, size_t offset) {117 return load<uint64_t>(p1, offset) == load<uint64_t>(p2, offset);118}119template <>120LIBC_INLINE uint32_t neq<uint64_t>(CPtr p1, CPtr p2, size_t offset) {121 return !eq<uint64_t>(p1, p2, offset);122}123template <>124LIBC_INLINE MemcmpReturnType cmp<uint64_t>(CPtr p1, CPtr p2, size_t offset);125template <>126LIBC_INLINE MemcmpReturnType cmp_neq<uint64_t>(CPtr p1, CPtr p2,127 size_t offset) {128 const auto a = load_be<uint64_t>(p1, offset);129 const auto b = load_be<uint64_t>(p2, offset);130 return cmp_neq_uint64_t(a, b);131}132 133// SIMD types are defined with attributes. e.g., '__m128i' is defined as134// long long __attribute__((__vector_size__(16), __aligned__(16)))135// When we use these SIMD types in template specialization GCC complains:136// "ignoring attributes on template argument ‘__m128i’ [-Wignored-attributes]"137// Therefore, we disable this warning in this file.138#ifndef LIBC_COMPILER_IS_MSVC139#pragma GCC diagnostic push140#pragma GCC diagnostic ignored "-Wignored-attributes"141#endif // !LIBC_COMPILER_IS_MSVC142 143///////////////////////////////////////////////////////////////////////////////144// Specializations for __m128i145#if defined(__SSE4_1__)146template <> struct is_vector<__m128i> : cpp::true_type {};147template <> struct cmp_is_expensive<__m128i> : cpp::true_type {};148LIBC_INLINE __m128i bytewise_max(__m128i a, __m128i b) {149 return _mm_max_epu8(a, b);150}151LIBC_INLINE __m128i bytewise_reverse(__m128i value) {152 return _mm_shuffle_epi8(value, _mm_set_epi8(0, 1, 2, 3, 4, 5, 6, 7, //153 8, 9, 10, 11, 12, 13, 14, 15));154}155LIBC_INLINE uint16_t big_endian_cmp_mask(__m128i max, __m128i value) {156 return static_cast<uint16_t>(157 _mm_movemask_epi8(bytewise_reverse(_mm_cmpeq_epi8(max, value))));158}159template <> LIBC_INLINE bool eq<__m128i>(CPtr p1, CPtr p2, size_t offset) {160 const auto a = load<__m128i>(p1, offset);161 const auto b = load<__m128i>(p2, offset);162 const auto xored = _mm_xor_si128(a, b);163 return _mm_testz_si128(xored, xored) == 1; // 1 iff xored == 0164}165template <> LIBC_INLINE uint32_t neq<__m128i>(CPtr p1, CPtr p2, size_t offset) {166 const auto a = load<__m128i>(p1, offset);167 const auto b = load<__m128i>(p2, offset);168 const auto xored = _mm_xor_si128(a, b);169 return _mm_testz_si128(xored, xored) == 0; // 0 iff xored != 0170}171template <>172LIBC_INLINE MemcmpReturnType cmp_neq<__m128i>(CPtr p1, CPtr p2, size_t offset) {173 const auto a = load<__m128i>(p1, offset);174 const auto b = load<__m128i>(p2, offset);175 const auto vmax = bytewise_max(a, b);176 const auto le = big_endian_cmp_mask(vmax, b);177 const auto ge = big_endian_cmp_mask(vmax, a);178 static_assert(cpp::is_same_v<cpp::remove_cv_t<decltype(le)>, uint16_t>);179 return static_cast<int32_t>(ge) - static_cast<int32_t>(le);180}181#endif // __SSE4_1__182 183///////////////////////////////////////////////////////////////////////////////184// Specializations for __m256i185#if defined(__AVX__)186template <> struct is_vector<__m256i> : cpp::true_type {};187template <> struct cmp_is_expensive<__m256i> : cpp::true_type {};188template <> LIBC_INLINE bool eq<__m256i>(CPtr p1, CPtr p2, size_t offset) {189 const auto a = load<__m256i>(p1, offset);190 const auto b = load<__m256i>(p2, offset);191 const auto xored = _mm256_castps_si256(192 _mm256_xor_ps(_mm256_castsi256_ps(a), _mm256_castsi256_ps(b)));193 return _mm256_testz_si256(xored, xored) == 1; // 1 iff xored == 0194}195template <> LIBC_INLINE uint32_t neq<__m256i>(CPtr p1, CPtr p2, size_t offset) {196 const auto a = load<__m256i>(p1, offset);197 const auto b = load<__m256i>(p2, offset);198 const auto xored = _mm256_castps_si256(199 _mm256_xor_ps(_mm256_castsi256_ps(a), _mm256_castsi256_ps(b)));200 return _mm256_testz_si256(xored, xored) == 0; // 0 iff xored != 0201}202#endif // __AVX__203 204#if defined(__AVX2__)205LIBC_INLINE __m256i bytewise_max(__m256i a, __m256i b) {206 return _mm256_max_epu8(a, b);207}208LIBC_INLINE uint32_t big_endian_cmp_mask(__m256i max, __m256i value) {209 // Bytewise comparison of 'max' and 'value'.210 const __m256i little_endian_byte_mask = _mm256_cmpeq_epi8(max, value);211 // Because x86 is little endian, bytes in the vector must be reversed before212 // using movemask.213#if defined(__AVX512VBMI__) && defined(__AVX512VL__)214 // When AVX512BMI is available we can completely reverse the vector through215 // VPERMB __m256i _mm256_permutexvar_epi8( __m256i idx, __m256i a);216 const __m256i big_endian_byte_mask =217 _mm256_permutexvar_epi8(_mm256_set_epi8(0, 1, 2, 3, 4, 5, 6, 7, //218 8, 9, 10, 11, 12, 13, 14, 15, //219 16, 17, 18, 19, 20, 21, 22, 23, //220 24, 25, 26, 27, 28, 29, 30, 31),221 little_endian_byte_mask);222 // And turn the byte vector mask into an 'uint32_t' for direct scalar223 // comparison.224 return _mm256_movemask_epi8(big_endian_byte_mask);225#else226 // We can't byte-reverse '__m256i' in a single instruction with AVX2.227 // '_mm256_shuffle_epi8' can only shuffle within each 16-byte lane228 // leading to:229 // ymm = ymm[15,14,13,12,11,10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0,230 // 31,30,29,28,27,26,25,24,23,22,21,20,19,18,17,16]231 // So we first shuffle each 16-byte lane leading to half-reversed vector mask.232 const __m256i half_reversed = _mm256_shuffle_epi8(233 little_endian_byte_mask, _mm256_set_epi8(0, 1, 2, 3, 4, 5, 6, 7, //234 8, 9, 10, 11, 12, 13, 14, 15, //235 0, 1, 2, 3, 4, 5, 6, 7, //236 8, 9, 10, 11, 12, 13, 14, 15));237 // Then we turn the vector into an uint32_t.238 const uint32_t half_reversed_scalar = _mm256_movemask_epi8(half_reversed);239 // And swap the lower and upper parts. This is optimized into a single `rorx`240 // instruction.241 return (half_reversed_scalar << 16) | (half_reversed_scalar >> 16);242#endif243}244template <>245LIBC_INLINE MemcmpReturnType cmp_neq<__m256i>(CPtr p1, CPtr p2, size_t offset) {246 const auto a = load<__m256i>(p1, offset);247 const auto b = load<__m256i>(p2, offset);248 const auto vmax = bytewise_max(a, b);249 const auto le = big_endian_cmp_mask(vmax, b);250 const auto ge = big_endian_cmp_mask(vmax, a);251 static_assert(cpp::is_same_v<cpp::remove_cv_t<decltype(le)>, uint32_t>);252 return cmp_neq_uint64_t(ge, le);253}254#endif // __AVX2__255 256///////////////////////////////////////////////////////////////////////////////257// Specializations for __m512i258#if defined(__AVX512BW__)259template <> struct is_vector<__m512i> : cpp::true_type {};260template <> struct cmp_is_expensive<__m512i> : cpp::true_type {};261LIBC_INLINE __m512i bytewise_max(__m512i a, __m512i b) {262 return _mm512_max_epu8(a, b);263}264LIBC_INLINE uint64_t big_endian_cmp_mask(__m512i max, __m512i value) {265 // The AVX512BMI version is disabled due to bad codegen.266 // https://github.com/llvm/llvm-project/issues/77459267 // https://github.com/llvm/llvm-project/pull/77081268 // TODO: Re-enable when clang version meets the fixed version.269#if false && defined(__AVX512VBMI__)270 // When AVX512BMI is available we can completely reverse the vector through271 // VPERMB __m512i _mm512_permutexvar_epi8( __m512i idx, __m512i a);272 const auto indices = _mm512_set_epi8(0, 1, 2, 3, 4, 5, 6, 7, //273 8, 9, 10, 11, 12, 13, 14, 15, //274 16, 17, 18, 19, 20, 21, 22, 23, //275 24, 25, 26, 27, 28, 29, 30, 31, //276 32, 33, 34, 35, 36, 37, 38, 39, //277 40, 41, 42, 43, 44, 45, 46, 47, //278 48, 49, 50, 51, 52, 53, 54, 55, //279 56, 57, 58, 59, 60, 61, 62, 63);280 // Then we compute the mask for equal bytes.281 return _mm512_cmpeq_epi8_mask(_mm512_permutexvar_epi8(indices, max), //282 _mm512_permutexvar_epi8(indices, value));283#else284 // We can't byte-reverse '__m512i' in a single instruction with __AVX512BW__.285 // '_mm512_shuffle_epi8' can only shuffle within each 16-byte lane.286 // So we only reverse groups of 8 bytes, these groups are necessarily within a287 // 16-byte lane.288 // zmm = | 16 bytes | 16 bytes | 16 bytes | 16 bytes |289 // zmm = | <8> | <8> | <8> | <8> | <8> | <8> | <8> | <8> |290 const __m512i indices = _mm512_set_epi8(8, 9, 10, 11, 12, 13, 14, 15, //291 0, 1, 2, 3, 4, 5, 6, 7, //292 8, 9, 10, 11, 12, 13, 14, 15, //293 0, 1, 2, 3, 4, 5, 6, 7, //294 8, 9, 10, 11, 12, 13, 14, 15, //295 0, 1, 2, 3, 4, 5, 6, 7, //296 8, 9, 10, 11, 12, 13, 14, 15, //297 0, 1, 2, 3, 4, 5, 6, 7);298 // Then we compute the mask for equal bytes. In this mask the bits of each299 // byte are already reversed but the byte themselves should be reversed, this300 // is done by using a bswap instruction.301 return __builtin_bswap64(302 _mm512_cmpeq_epi8_mask(_mm512_shuffle_epi8(max, indices), //303 _mm512_shuffle_epi8(value, indices)));304 305#endif306}307template <> LIBC_INLINE bool eq<__m512i>(CPtr p1, CPtr p2, size_t offset) {308 const auto a = load<__m512i>(p1, offset);309 const auto b = load<__m512i>(p2, offset);310 return _mm512_cmpneq_epi8_mask(a, b) == 0;311}312template <> LIBC_INLINE uint32_t neq<__m512i>(CPtr p1, CPtr p2, size_t offset) {313 const auto a = load<__m512i>(p1, offset);314 const auto b = load<__m512i>(p2, offset);315 const uint64_t xored = _mm512_cmpneq_epi8_mask(a, b);316 return static_cast<uint32_t>(xored >> 32) |317 static_cast<uint32_t>(xored & 0xFFFFFFFF);318}319template <>320LIBC_INLINE MemcmpReturnType cmp_neq<__m512i>(CPtr p1, CPtr p2, size_t offset) {321 const auto a = load<__m512i>(p1, offset);322 const auto b = load<__m512i>(p2, offset);323 const auto vmax = bytewise_max(a, b);324 const auto le = big_endian_cmp_mask(vmax, b);325 const auto ge = big_endian_cmp_mask(vmax, a);326 static_assert(cpp::is_same_v<cpp::remove_cv_t<decltype(le)>, uint64_t>);327 return cmp_neq_uint64_t(ge, le);328}329#endif // __AVX512BW__330 331#ifndef LIBC_COMPILER_IS_MSVC332#pragma GCC diagnostic pop333#endif // !LIBC_COMPILER_IS_MSVC334 335} // namespace generic336} // namespace LIBC_NAMESPACE_DECL337 338#endif // LIBC_TARGET_ARCH_IS_X86339 340#endif // LLVM_LIBC_SRC_STRING_MEMORY_UTILS_OP_X86_H341