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-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #ifndef _LIBCPP___ALGORITHM_SIMD_UTILS_H 10 #define _LIBCPP___ALGORITHM_SIMD_UTILS_H 11 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 <__type_traits/is_arithmetic.h> 18 #include <__type_traits/is_same.h> 19 #include <__utility/integer_sequence.h> 20 #include <cstddef> 21 #include <cstdint> 22 23 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 24 # pragma GCC system_header 25 #endif 26 27 _LIBCPP_PUSH_MACROS 28 #include <__undef_macros> 29 30 // TODO: Find out how altivec changes things and allow vectorizations there too. 31 #if _LIBCPP_STD_VER >= 14 && (defined(_LIBCPP_CLANG_VER) && _LIBCPP_CLANG_VER >= 1500) && !defined(__ALTIVEC__) 32 # define _LIBCPP_HAS_ALGORITHM_VECTOR_UTILS 1 33 #else 34 # define _LIBCPP_HAS_ALGORITHM_VECTOR_UTILS 0 35 #endif 36 37 #if _LIBCPP_HAS_ALGORITHM_VECTOR_UTILS && !defined(__OPTIMIZE_SIZE__) 38 # define _LIBCPP_VECTORIZE_ALGORITHMS 1 39 #else 40 # define _LIBCPP_VECTORIZE_ALGORITHMS 0 41 #endif 42 43 #if _LIBCPP_HAS_ALGORITHM_VECTOR_UTILS 44 45 _LIBCPP_BEGIN_NAMESPACE_STD 46 47 template <class _Tp> 48 inline constexpr bool __can_map_to_integer_v = 49 sizeof(_Tp) == alignof(_Tp) && (sizeof(_Tp) == 1 || sizeof(_Tp) == 2 || sizeof(_Tp) == 4 || sizeof(_Tp) == 8); 50 51 template <size_t _TypeSize> 52 struct __get_as_integer_type_impl; 53 54 template <> 55 struct __get_as_integer_type_impl<1> { 56 using type = uint8_t; 57 }; 58 59 template <> 60 struct __get_as_integer_type_impl<2> { 61 using type = uint16_t; 62 }; 63 template <> 64 struct __get_as_integer_type_impl<4> { 65 using type = uint32_t; 66 }; 67 template <> 68 struct __get_as_integer_type_impl<8> { 69 using type = uint64_t; 70 }; 71 72 template <class _Tp> 73 using __get_as_integer_type_t = typename __get_as_integer_type_impl<sizeof(_Tp)>::type; 74 75 // This isn't specialized for 64 byte vectors on purpose. They have the potential to significantly reduce performance 76 // in mixed simd/non-simd workloads and don't provide any performance improvement for currently vectorized algorithms 77 // as far as benchmarks are concerned. 78 # if defined(__AVX__) || defined(__MVS__) 79 template <class _Tp> 80 inline constexpr size_t __native_vector_size = 32 / sizeof(_Tp); 81 # elif defined(__SSE__) || defined(__ARM_NEON__) 82 template <class _Tp> 83 inline constexpr size_t __native_vector_size = 16 / sizeof(_Tp); 84 # elif defined(__MMX__) 85 template <class _Tp> 86 inline constexpr size_t __native_vector_size = 8 / sizeof(_Tp); 87 # else 88 template <class _Tp> 89 inline constexpr size_t __native_vector_size = 1; 90 # endif 91 92 template <class _ArithmeticT, size_t _Np> 93 using __simd_vector __attribute__((__ext_vector_type__(_Np))) = _ArithmeticT; 94 95 template <class _VecT> 96 inline constexpr size_t __simd_vector_size_v = []<bool _False = false>() -> size_t { 97 static_assert(_False, "Not a vector!"); 98 }(); 99 100 template <class _Tp, size_t _Np> 101 inline constexpr size_t __simd_vector_size_v<__simd_vector<_Tp, _Np>> = _Np; 102 103 template <class _Tp, size_t _Np> 104 _LIBCPP_HIDE_FROM_ABI _Tp __simd_vector_underlying_type_impl(__simd_vector<_Tp, _Np>) { 105 return _Tp{}; 106 } 107 108 template <class _VecT> 109 using __simd_vector_underlying_type_t = decltype(std::__simd_vector_underlying_type_impl(_VecT{})); 110 111 // This isn't inlined without always_inline when loading chars. 112 template <class _VecT, class _Iter> 113 _LIBCPP_NODISCARD _LIBCPP_ALWAYS_INLINE _LIBCPP_HIDE_FROM_ABI _VecT __load_vector(_Iter __iter) noexcept { 114 return [=]<size_t... _Indices>(index_sequence<_Indices...>) _LIBCPP_ALWAYS_INLINE noexcept { 115 return _VecT{__iter[_Indices]...}; 116 }(make_index_sequence<__simd_vector_size_v<_VecT>>{}); 117 } 118 119 template <class _Tp, size_t _Np> 120 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI bool __all_of(__simd_vector<_Tp, _Np> __vec) noexcept { 121 return __builtin_reduce_and(__builtin_convertvector(__vec, __simd_vector<bool, _Np>)); 122 } 123 124 template <class _Tp, size_t _Np> 125 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI size_t __find_first_set(__simd_vector<_Tp, _Np> __vec) noexcept { 126 using __mask_vec = __simd_vector<bool, _Np>; 127 128 // This has MSan disabled du to https://github.com/llvm/llvm-project/issues/85876 129 auto __impl = [&]<class _MaskT>(_MaskT) _LIBCPP_NO_SANITIZE("memory") noexcept { 130 # if defined(_LIBCPP_BIG_ENDIAN) 131 return std::min<size_t>( 132 _Np, std::__countl_zero(__builtin_bit_cast(_MaskT, __builtin_convertvector(__vec, __mask_vec)))); 133 # else 134 return std::min<size_t>( 135 _Np, std::__countr_zero(__builtin_bit_cast(_MaskT, __builtin_convertvector(__vec, __mask_vec)))); 136 # endif 137 }; 138 139 if constexpr (sizeof(__mask_vec) == sizeof(uint8_t)) { 140 return __impl(uint8_t{}); 141 } else if constexpr (sizeof(__mask_vec) == sizeof(uint16_t)) { 142 return __impl(uint16_t{}); 143 } else if constexpr (sizeof(__mask_vec) == sizeof(uint32_t)) { 144 return __impl(uint32_t{}); 145 } else if constexpr (sizeof(__mask_vec) == sizeof(uint64_t)) { 146 return __impl(uint64_t{}); 147 } else { 148 static_assert(sizeof(__mask_vec) == 0, "unexpected required size for mask integer type"); 149 return 0; 150 } 151 } 152 153 template <class _Tp, size_t _Np> 154 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI size_t __find_first_not_set(__simd_vector<_Tp, _Np> __vec) noexcept { 155 return std::__find_first_set(~__vec); 156 } 157 158 _LIBCPP_END_NAMESPACE_STD 159 160 #endif // _LIBCPP_HAS_ALGORITHM_VECTOR_UTILS 161 162 _LIBCPP_POP_MACROS 163 164 #endif // _LIBCPP___ALGORITHM_SIMD_UTILS_H 165