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 <__utility/integer_sequence.h>
19#include <cstdint>
20
21#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
22# pragma GCC system_header
23#endif
24
25_LIBCPP_PUSH_MACROS
26#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 1
31#else
32# define _LIBCPP_HAS_ALGORITHM_VECTOR_UTILS 0
33#endif
34
35#if _LIBCPP_HAS_ALGORITHM_VECTOR_UTILS && !defined(__OPTIMIZE_SIZE__)
36# define _LIBCPP_VECTORIZE_ALGORITHMS 1
37#else
38# define _LIBCPP_VECTORIZE_ALGORITHMS 0
39#endif
40
41#if _LIBCPP_HAS_ALGORITHM_VECTOR_UTILS
42
43_LIBCPP_BEGIN_NAMESPACE_STD
44
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 performance
74// in mixed simd/non-simd workloads and don't provide any performance improvement for currently vectorized algorithms
75// 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# else
86template <class _Tp>
87inline constexpr size_t __native_vector_size = 1;
88# endif
89
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 rest
118_LIBCPP_DIAGNOSTIC_PUSH
119_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 __val
129template <class _VecT>
130[[__nodiscard__]] _LIBCPP_ALWAYS_INLINE _LIBCPP_HIDE_FROM_ABI _VecT
131__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_POP
137
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/PR85876
158 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# else
163 return std::min<size_t>(
164 _Np, std::__countr_zero(__builtin_bit_cast(_MaskT, __builtin_convertvector(__vec, __mask_vec))));
165# endif
166 };
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_STD
188
189#endif // _LIBCPP_HAS_ALGORITHM_VECTOR_UTILS
190
191_LIBCPP_POP_MACROS
192
193#endif // _LIBCPP___ALGORITHM_SIMD_UTILS_H
194