194 lines · c
1//===----------------------------------------------------------------------===//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 _LIBCPP___ALGORITHM_SIMD_UTILS_H10#define _LIBCPP___ALGORITHM_SIMD_UTILS_H11 12#include <__algorithm/min.h>13#include <__bit/bit_cast.h>14#include <__bit/countl.h>15#include <__bit/countr.h>16#include <__config>17#include <__cstddef/size_t.h>18#include <__utility/integer_sequence.h>19#include <cstdint>20 21#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)22# pragma GCC system_header23#endif24 25_LIBCPP_PUSH_MACROS26#include <__undef_macros>27 28// TODO: Find out how altivec changes things and allow vectorizations there too.29#if _LIBCPP_STD_VER >= 14 && defined(_LIBCPP_COMPILER_CLANG_BASED) && !defined(__ALTIVEC__)30# define _LIBCPP_HAS_ALGORITHM_VECTOR_UTILS 131#else32# define _LIBCPP_HAS_ALGORITHM_VECTOR_UTILS 033#endif34 35#if _LIBCPP_HAS_ALGORITHM_VECTOR_UTILS && !defined(__OPTIMIZE_SIZE__)36# define _LIBCPP_VECTORIZE_ALGORITHMS 137#else38# define _LIBCPP_VECTORIZE_ALGORITHMS 039#endif40 41#if _LIBCPP_HAS_ALGORITHM_VECTOR_UTILS42 43_LIBCPP_BEGIN_NAMESPACE_STD44 45template <class _Tp>46inline constexpr bool __can_map_to_integer_v =47 sizeof(_Tp) == alignof(_Tp) && (sizeof(_Tp) == 1 || sizeof(_Tp) == 2 || sizeof(_Tp) == 4 || sizeof(_Tp) == 8);48 49template <size_t _TypeSize>50struct __get_as_integer_type_impl;51 52template <>53struct __get_as_integer_type_impl<1> {54 using type _LIBCPP_NODEBUG = uint8_t;55};56 57template <>58struct __get_as_integer_type_impl<2> {59 using type _LIBCPP_NODEBUG = uint16_t;60};61template <>62struct __get_as_integer_type_impl<4> {63 using type _LIBCPP_NODEBUG = uint32_t;64};65template <>66struct __get_as_integer_type_impl<8> {67 using type _LIBCPP_NODEBUG = uint64_t;68};69 70template <class _Tp>71using __get_as_integer_type_t _LIBCPP_NODEBUG = typename __get_as_integer_type_impl<sizeof(_Tp)>::type;72 73// This isn't specialized for 64 byte vectors on purpose. They have the potential to significantly reduce performance74// in mixed simd/non-simd workloads and don't provide any performance improvement for currently vectorized algorithms75// as far as benchmarks are concerned.76# if defined(__AVX__) || defined(__MVS__)77template <class _Tp>78inline constexpr size_t __native_vector_size = 32 / sizeof(_Tp);79# elif defined(__SSE__) || defined(__ARM_NEON)80template <class _Tp>81inline constexpr size_t __native_vector_size = 16 / sizeof(_Tp);82# elif defined(__MMX__)83template <class _Tp>84inline constexpr size_t __native_vector_size = 8 / sizeof(_Tp);85# else86template <class _Tp>87inline constexpr size_t __native_vector_size = 1;88# endif89 90template <class _ArithmeticT, size_t _Np>91using __simd_vector __attribute__((__ext_vector_type__(_Np))) _LIBCPP_NODEBUG = _ArithmeticT;92 93template <class _VecT>94inline constexpr size_t __simd_vector_size_v = []<bool _False = false>() -> size_t {95 static_assert(_False, "Not a vector!");96}();97 98template <class _Tp, size_t _Np>99inline constexpr size_t __simd_vector_size_v<__simd_vector<_Tp, _Np>> = _Np;100 101template <class _Tp, size_t _Np>102_LIBCPP_HIDE_FROM_ABI _Tp __simd_vector_underlying_type_impl(__simd_vector<_Tp, _Np>) {103 return _Tp{};104}105 106template <class _VecT>107using __simd_vector_underlying_type_t _LIBCPP_NODEBUG = decltype(std::__simd_vector_underlying_type_impl(_VecT{}));108 109// This isn't inlined without always_inline when loading chars.110template <class _VecT, class _Iter>111[[__nodiscard__]] _LIBCPP_ALWAYS_INLINE _LIBCPP_HIDE_FROM_ABI _VecT __load_vector(_Iter __iter) noexcept {112 return [=]<size_t... _Indices>(index_sequence<_Indices...>) _LIBCPP_ALWAYS_INLINE noexcept {113 return _VecT{__iter[_Indices]...};114 }(make_index_sequence<__simd_vector_size_v<_VecT>>{});115}116 117// Load the first _Np elements, zero the rest118_LIBCPP_DIAGNOSTIC_PUSH119_LIBCPP_CLANG_DIAGNOSTIC_IGNORED("-Wpsabi")120template <class _VecT, size_t _Np, class _Iter>121[[__nodiscard__]] _LIBCPP_ALWAYS_INLINE _LIBCPP_HIDE_FROM_ABI _VecT __partial_load(_Iter __iter) noexcept {122 return [=]<size_t... _LoadIndices, size_t... _ZeroIndices>(123 index_sequence<_LoadIndices...>, index_sequence<_ZeroIndices...>) _LIBCPP_ALWAYS_INLINE noexcept {124 return _VecT{__iter[_LoadIndices]..., ((void)_ZeroIndices, 0)...};125 }(make_index_sequence<_Np>{}, make_index_sequence<__simd_vector_size_v<_VecT> - _Np>{});126}127 128// Create a vector where every elements is __val129template <class _VecT>130[[__nodiscard__]] _LIBCPP_ALWAYS_INLINE _LIBCPP_HIDE_FROM_ABI _VecT131__broadcast(__simd_vector_underlying_type_t<_VecT> __val) {132 return [&]<std::size_t... _Indices>(index_sequence<_Indices...>) {133 return _VecT{((void)_Indices, __val)...};134 }(make_index_sequence<__simd_vector_size_v<_VecT>>());135}136_LIBCPP_DIAGNOSTIC_POP137 138template <class _Tp, size_t _Np>139[[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI bool __any_of(__simd_vector<_Tp, _Np> __vec) noexcept {140 return __builtin_reduce_or(__builtin_convertvector(__vec, __simd_vector<bool, _Np>));141}142 143template <class _Tp, size_t _Np>144[[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI bool __all_of(__simd_vector<_Tp, _Np> __vec) noexcept {145 return __builtin_reduce_and(__builtin_convertvector(__vec, __simd_vector<bool, _Np>));146}147 148template <class _Tp, size_t _Np>149[[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI bool __none_of(__simd_vector<_Tp, _Np> __vec) noexcept {150 return !__builtin_reduce_or(__builtin_convertvector(__vec, __simd_vector<bool, _Np>));151}152 153template <class _Tp, size_t _Np>154[[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI size_t __find_first_set(__simd_vector<_Tp, _Np> __vec) noexcept {155 using __mask_vec = __simd_vector<bool, _Np>;156 157 // This has MSan disabled du to https://llvm.org/PR85876158 auto __impl = [&]<class _MaskT>(_MaskT) _LIBCPP_NO_SANITIZE("memory") noexcept {159# if defined(_LIBCPP_BIG_ENDIAN)160 return std::min<size_t>(161 _Np, std::__countl_zero(__builtin_bit_cast(_MaskT, __builtin_convertvector(__vec, __mask_vec))));162# else163 return std::min<size_t>(164 _Np, std::__countr_zero(__builtin_bit_cast(_MaskT, __builtin_convertvector(__vec, __mask_vec))));165# endif166 };167 168 if constexpr (sizeof(__mask_vec) == sizeof(uint8_t)) {169 return __impl(uint8_t{});170 } else if constexpr (sizeof(__mask_vec) == sizeof(uint16_t)) {171 return __impl(uint16_t{});172 } else if constexpr (sizeof(__mask_vec) == sizeof(uint32_t)) {173 return __impl(uint32_t{});174 } else if constexpr (sizeof(__mask_vec) == sizeof(uint64_t)) {175 return __impl(uint64_t{});176 } else {177 static_assert(sizeof(__mask_vec) == 0, "unexpected required size for mask integer type");178 return 0;179 }180}181 182template <class _Tp, size_t _Np>183[[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI size_t __find_first_not_set(__simd_vector<_Tp, _Np> __vec) noexcept {184 return std::__find_first_set(~__vec);185}186 187_LIBCPP_END_NAMESPACE_STD188 189#endif // _LIBCPP_HAS_ALGORITHM_VECTOR_UTILS190 191_LIBCPP_POP_MACROS192 193#endif // _LIBCPP___ALGORITHM_SIMD_UTILS_H194