v1/__algorithm/simd_utils.h

0001 //===----------------------------------------------------------------------===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008
0009 #ifndef _LIBCPP___ALGORITHM_SIMD_UTILS_H
0010 #define _LIBCPP___ALGORITHM_SIMD_UTILS_H
0011
0012 #include <__algorithm/min.h>
0013 #include <__bit/bit_cast.h>
0014 #include <__bit/countl.h>
0015 #include <__bit/countr.h>
0016 #include <__config>
0017 #include <__cstddef/size_t.h>
0018 #include <__type_traits/is_arithmetic.h>
0019 #include <__type_traits/is_same.h>
0020 #include <__utility/integer_sequence.h>
0021 #include <cstdint>
0022
0023 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
0024 #  pragma GCC system_header
0025 #endif
0026
0027 _LIBCPP_PUSH_MACROS
0028 #include <__undef_macros>
0029
0030 // TODO: Find out how altivec changes things and allow vectorizations there too.
0031 #if _LIBCPP_STD_VER >= 14 && defined(_LIBCPP_CLANG_VER) && !defined(__ALTIVEC__)
0032 #  define _LIBCPP_HAS_ALGORITHM_VECTOR_UTILS 1
0033 #else
0034 #  define _LIBCPP_HAS_ALGORITHM_VECTOR_UTILS 0
0035 #endif
0036
0037 #if _LIBCPP_HAS_ALGORITHM_VECTOR_UTILS && !defined(__OPTIMIZE_SIZE__)
0038 #  define _LIBCPP_VECTORIZE_ALGORITHMS 1
0039 #else
0040 #  define _LIBCPP_VECTORIZE_ALGORITHMS 0
0041 #endif
0042
0043 #if _LIBCPP_HAS_ALGORITHM_VECTOR_UTILS
0044
0045 _LIBCPP_BEGIN_NAMESPACE_STD
0046
0047 template <class _Tp>
0048 inline constexpr bool __can_map_to_integer_v =
0049     sizeof(_Tp) == alignof(_Tp) && (sizeof(_Tp) == 1 || sizeof(_Tp) == 2 || sizeof(_Tp) == 4 || sizeof(_Tp) == 8);
0050
0051 template <size_t _TypeSize>
0052 struct __get_as_integer_type_impl;
0053
0054 template <>
0055 struct __get_as_integer_type_impl<1> {
0056   using type = uint8_t;
0057 };
0058
0059 template <>
0060 struct __get_as_integer_type_impl<2> {
0061   using type = uint16_t;
0062 };
0063 template <>
0064 struct __get_as_integer_type_impl<4> {
0065   using type = uint32_t;
0066 };
0067 template <>
0068 struct __get_as_integer_type_impl<8> {
0069   using type = uint64_t;
0070 };
0071
0072 template <class _Tp>
0073 using __get_as_integer_type_t _LIBCPP_NODEBUG = typename __get_as_integer_type_impl<sizeof(_Tp)>::type;
0074
0075 // This isn't specialized for 64 byte vectors on purpose. They have the potential to significantly reduce performance
0076 // in mixed simd/non-simd workloads and don't provide any performance improvement for currently vectorized algorithms
0077 // as far as benchmarks are concerned.
0078 #  if defined(__AVX__) || defined(__MVS__)
0079 template <class _Tp>
0080 inline constexpr size_t __native_vector_size = 32 / sizeof(_Tp);
0081 #  elif defined(__SSE__) || defined(__ARM_NEON__)
0082 template <class _Tp>
0083 inline constexpr size_t __native_vector_size = 16 / sizeof(_Tp);
0084 #  elif defined(__MMX__)
0085 template <class _Tp>
0086 inline constexpr size_t __native_vector_size = 8 / sizeof(_Tp);
0087 #  else
0088 template <class _Tp>
0089 inline constexpr size_t __native_vector_size = 1;
0090 #  endif
0091
0092 template <class _ArithmeticT, size_t _Np>
0093 using __simd_vector __attribute__((__ext_vector_type__(_Np))) _LIBCPP_NODEBUG = _ArithmeticT;
0094
0095 template <class _VecT>
0096 inline constexpr size_t __simd_vector_size_v = []<bool _False = false>() -> size_t {
0097   static_assert(_False, "Not a vector!");
0098 }();
0099
0100 template <class _Tp, size_t _Np>
0101 inline constexpr size_t __simd_vector_size_v<__simd_vector<_Tp, _Np>> = _Np;
0102
0103 template <class _Tp, size_t _Np>
0104 _LIBCPP_HIDE_FROM_ABI _Tp __simd_vector_underlying_type_impl(__simd_vector<_Tp, _Np>) {
0105   return _Tp{};
0106 }
0107
0108 template <class _VecT>
0109 using __simd_vector_underlying_type_t _LIBCPP_NODEBUG = decltype(std::__simd_vector_underlying_type_impl(_VecT{}));
0110
0111 // This isn't inlined without always_inline when loading chars.
0112 template <class _VecT, class _Iter>
0113 [[__nodiscard__]] _LIBCPP_ALWAYS_INLINE _LIBCPP_HIDE_FROM_ABI _VecT __load_vector(_Iter __iter) noexcept {
0114   return [=]<size_t... _Indices>(index_sequence<_Indices...>) _LIBCPP_ALWAYS_INLINE noexcept {
0115     return _VecT{__iter[_Indices]...};
0116   }(make_index_sequence<__simd_vector_size_v<_VecT>>{});
0117 }
0118
0119 template <class _Tp, size_t _Np>
0120 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI bool __all_of(__simd_vector<_Tp, _Np> __vec) noexcept {
0121   return __builtin_reduce_and(__builtin_convertvector(__vec, __simd_vector<bool, _Np>));
0122 }
0123
0124 template <class _Tp, size_t _Np>
0125 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI size_t __find_first_set(__simd_vector<_Tp, _Np> __vec) noexcept {
0126   using __mask_vec = __simd_vector<bool, _Np>;
0127
0128   // This has MSan disabled du to https://github.com/llvm/llvm-project/issues/85876
0129   auto __impl = [&]<class _MaskT>(_MaskT) _LIBCPP_NO_SANITIZE("memory") noexcept {
0130 #  if defined(_LIBCPP_BIG_ENDIAN)
0131     return std::min<size_t>(
0132         _Np, std::__countl_zero(__builtin_bit_cast(_MaskT, __builtin_convertvector(__vec, __mask_vec))));
0133 #  else
0134     return std::min<size_t>(
0135         _Np, std::__countr_zero(__builtin_bit_cast(_MaskT, __builtin_convertvector(__vec, __mask_vec))));
0136 #  endif
0137   };
0138
0139   if constexpr (sizeof(__mask_vec) == sizeof(uint8_t)) {
0140     return __impl(uint8_t{});
0141   } else if constexpr (sizeof(__mask_vec) == sizeof(uint16_t)) {
0142     return __impl(uint16_t{});
0143   } else if constexpr (sizeof(__mask_vec) == sizeof(uint32_t)) {
0144     return __impl(uint32_t{});
0145   } else if constexpr (sizeof(__mask_vec) == sizeof(uint64_t)) {
0146     return __impl(uint64_t{});
0147   } else {
0148     static_assert(sizeof(__mask_vec) == 0, "unexpected required size for mask integer type");
0149     return 0;
0150   }
0151 }
0152
0153 template <class _Tp, size_t _Np>
0154 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI size_t __find_first_not_set(__simd_vector<_Tp, _Np> __vec) noexcept {
0155   return std::__find_first_set(~__vec);
0156 }
0157
0158 _LIBCPP_END_NAMESPACE_STD
0159
0160 #endif // _LIBCPP_HAS_ALGORITHM_VECTOR_UTILS
0161
0162 _LIBCPP_POP_MACROS
0163
0164 #endif // _LIBCPP___ALGORITHM_SIMD_UTILS_H