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 <__cstddef/size_t.h> 18 #include <__type_traits/is_arithmetic.h> 19 #include <__type_traits/is_same.h> 20 #include <__utility/integer_sequence.h> 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) && !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 [[__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 <size_t _Np> 120 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI bool __all_of(__simd_vector<bool, _Np> __vec) noexcept { 121 return __builtin_reduce_and(__vec); 122 } 123 124 template <class _Tp, size_t _Np> 125 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI auto __as_mask(__simd_vector<_Tp, _Np> __vec) noexcept { 126 static_assert(!is_same<_Tp, bool>::value, "vector type should not be a bool!"); 127 return __builtin_convertvector(__vec, __simd_vector<bool, _Np>); 128 } 129 130 // This uses __builtin_convertvector around the __builtin_shufflevector to work around #107981. 131 template <size_t _Np> 132 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI __simd_vector<bool, 8> 133 __extend_vector(__simd_vector<bool, _Np> __vec) noexcept { 134 using _VecT = __simd_vector<bool, _Np>; 135 if constexpr (_Np == 4) { 136 return __builtin_convertvector( 137 __builtin_shufflevector(__vec, _VecT{}, 0, 1, 2, 3, 4, 5, 6, 7), __simd_vector<bool, 8>); 138 } else if constexpr (_Np == 2) { 139 return std::__extend_vector( 140 __builtin_convertvector(__builtin_shufflevector(__vec, _VecT{}, 0, 1, 2, 3), __simd_vector<bool, 4>)); 141 } else if constexpr (_Np == 1) { 142 return std::__extend_vector( 143 __builtin_convertvector(__builtin_shufflevector(__vec, _VecT{}, 0, 1), __simd_vector<bool, 2>)); 144 } else { 145 static_assert(sizeof(_VecT) == 0, "Unexpected vector size"); 146 } 147 } 148 149 template <size_t _Np> 150 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI auto __to_int_mask(__simd_vector<bool, _Np> __vec) { 151 if constexpr (_Np < 8) { 152 return std::__bit_cast<uint8_t>(std::__extend_vector(__vec)); 153 } else if constexpr (_Np == 8) { 154 return std::__bit_cast<uint8_t>(__vec); 155 } else if constexpr (_Np == 16) { 156 return std::__bit_cast<uint16_t>(__vec); 157 } else if constexpr (_Np == 32) { 158 return std::__bit_cast<uint32_t>(__vec); 159 } else if constexpr (_Np == 64) { 160 return std::__bit_cast<uint64_t>(__vec); 161 } else { 162 static_assert(sizeof(__simd_vector<bool, _Np>) == 0, "Unexpected vector size"); 163 return 0; 164 } 165 } 166 167 template <size_t _Np> 168 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI size_t __find_first_set(__simd_vector<bool, _Np> __vec) noexcept { 169 # if defined(_LIBCPP_BIG_ENDIAN) 170 return std::min<size_t>(_Np, std::__countl_zero(std::__to_int_mask(__vec))); 171 # else 172 return std::min<size_t>(_Np, std::__countr_zero(std::__to_int_mask(__vec))); 173 # endif 174 } 175 176 template <size_t _Np> 177 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI size_t __find_first_not_set(__simd_vector<bool, _Np> __vec) noexcept { 178 return std::__find_first_set(~__vec); 179 } 180 181 _LIBCPP_END_NAMESPACE_STD 182 183 #endif // _LIBCPP_HAS_ALGORITHM_VECTOR_UTILS 184 185 _LIBCPP_POP_MACROS 186 187 #endif // _LIBCPP___ALGORITHM_SIMD_UTILS_H 188