Intel xvec
Experimental C++ simd class library
Loading...
Searching...
No Matches
reduce.hpp
1//===----------------------------------------------------------------------===//
2//
3// Copyright (C) 2021 Intel Corporation
4//
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#pragma once
10
11#include <xvec/detail/config.hpp>
12
13#include <bit> // std::bit_ceil
14#include <cstddef>
15#include <cstdint> // std::uint64_t
16#include <limits> // std::numeric_limits
17
18namespace _XVEC_NAMESPACE::simd
19{
20
21namespace detail
22{
23inline auto minBinaryOperator = [](auto lhs, auto rhs) { using std::min; return min(lhs, rhs); };
24inline auto maxBinaryOperator = [](auto lhs, auto rhs) { using std::max; return max(lhs, rhs); };
25
26template<typename _Op, typename _Tp>
28 requires (const _Op binary_op, const vec<_Tp, 1> v) {{ binary_op(v, v) } -> std::same_as<vec<_Tp, 1>>; };
29
30template<typename _Op, typename _Tp>
31constexpr auto choose_identity_element() {
32 if constexpr (std::same_as<_Op, std::plus<>>)
33 return _Tp();
34 else if constexpr (std::same_as<_Op, std::multiplies<>>)
35 return _Tp(1);
36 else if constexpr (std::same_as<_Op, std::bit_and<>>)
37 return _Tp(~_Tp());
38 else if constexpr (std::same_as<_Op, std::bit_or<>>)
39 return _Tp();
40 else if constexpr (std::same_as<_Op, std::bit_xor<>>)
41 return _Tp();
42 else
43 static_assert(dependent_false<_Op>, "Unsupported binary reduction operator");
44}
45
52template<simd_size_type _Size, typename _Tp, typename _Abi, binary_reduction_fn<_Tp> _BinaryFn>
53inline _Tp reduce_helper(const basic_vec<_Tp, _Abi>& v, _BinaryFn binop) {
54
55 if constexpr (_Size == 1)
56 return v[0];
57 else
58 {
59 // Split the complete incoming simd into two pieces: one a power-of-2 and
60 // the other the remainder, where both are at least as big as the smallest
61 // register. It is better to handle anything small as a complete register,
62 // rather than extracting and inserting sub-register pieces in the final
63 // stages of the reduction.
64 constexpr int halfSize = std::bit_ceil((std::uint64_t)_Size) / 2;
65 constexpr auto opSize = std::max(register_size<_Tp, 1>, halfSize);
66
67 const auto lower = permute<opSize>(v, perm_uninitResize);
68 const auto upper = permute<opSize>(drop<halfSize>(v), perm_uninitResize);
69
70 auto r = binop(lower, upper);
71
72 // If the upper and lower are different sizes, because the incoming value
73 // was not divisible by 2, then mask off the unwanted elements and copy the
74 // originals through.
75 constexpr auto remainderSize = _Size - halfSize;
76 if constexpr (halfSize != remainderSize)
77 {
78 const auto remainderMask = mask<_Tp, opSize>::__mask_from_count(remainderSize);
79 r = select(remainderMask, r, lower);
80 }
81
82 return reduce_helper<halfSize>(r, binop);
83 }
84}
85
86} // End namespace detail
87
95
104template<vec_type _V, detail::binary_reduction_fn<typename _V::value_type> _BinaryFn = std::plus<>>
105constexpr typename _V::value_type reduce(const _V& v, _BinaryFn binop = {})
106 { return detail::reduce_helper<_V::size()>(v, binop); }
107
117template<typename _Tp, typename _Abi, detail::binary_reduction_fn<_Tp> _BinaryFn = std::plus<>>
118constexpr _Tp reduce(const basic_vec<_Tp, _Abi>& v,
119 const typename basic_vec<_Tp, _Abi>::mask_type& m,
120 _BinaryFn binop = {},
121 std::type_identity_t<_Tp> identity_element = detail::choose_identity_element<_BinaryFn, _Tp>())
122 { return detail::reduce_helper<_Abi::num_elements>(select(m, v, identity_element), binop); }
123
130template<detail::vectorizable _Tp,
131 detail::binary_reduction_fn<_Tp> _BinaryFn = std::plus<>>
132constexpr _Tp reduce(const _Tp& v, [[maybe_unused]] _BinaryFn binop = {}) noexcept
133 { return v; }
134
143template<detail::vectorizable _Tp,
144 detail::binary_reduction_fn<_Tp> _BinaryFn = std::plus<>>
145constexpr _Tp reduce(
146 const _Tp& v, std::same_as<bool> auto m, [[maybe_unused]] _BinaryFn binop = {},
147 std::type_identity_t<_Tp> identity_element =
148 detail::choose_identity_element<_BinaryFn, _Tp>()) noexcept
149 { return m ? v : identity_element; }
150
155template<vec_type _V> requires requires (_V x) { min(x, x); }
156constexpr typename _V::value_type reduce_min(const _V& v) noexcept
157 { return reduce(v, detail::minBinaryOperator); }
158
162template<vec_type _V> requires requires (_V x) { reduce_min(x); }
163constexpr typename _V::value_type
164reduce_min(const _V& v, const typename _V::mask_type& m) noexcept
165{
166 // Note that it is more efficient to replace unused elements with the max
167 // value as that eliminates any need to do masking during the reduction.
168 // For types with an infinity, max() is smaller than +inf, so use +inf
169 // instead and only return max() when no element is selected.
170 if constexpr (std::numeric_limits<typename _V::value_type>::has_infinity)
171 {
172 if (none_of(m))
173 return std::numeric_limits<typename _V::value_type>::max();
174 return reduce_min(select(m, v, std::numeric_limits<_V>::infinity()));
175 }
176 else
177 {
178 const auto r = select(m, v, std::numeric_limits<_V>::max());
179 return reduce_min(r);
180 }
181}
182
186template<vec_type _V> requires requires (_V x) { max(x, x); }
187constexpr typename _V::value_type reduce_max(const _V& v) noexcept { return reduce(v, detail::maxBinaryOperator); }
188
192template<vec_type _V> requires requires (_V x) { reduce_max(x); }
193constexpr typename _V::value_type
194reduce_max(const _V& v, const typename _V::mask_type& m) noexcept
195{
196 // Note that it is more efficient to replace unused elements with the lowest
197 // value as that eliminates any need to do masking during the reduction.
198 // For types with an infinity, lowest() is larger than -inf, so use -inf
199 // instead and only return lowest() when no element is selected.
200 if constexpr (std::numeric_limits<typename _V::value_type>::has_infinity)
201 {
202 if (none_of(m))
203 return std::numeric_limits<typename _V::value_type>::lowest();
204 return reduce_max(select(m, v, -std::numeric_limits<_V>::infinity()));
205 }
206 else
207 {
208 const auto r = select(m, v, std::numeric_limits<_V>::lowest());
209 return reduce_max(r);
210 }
211}
212
217template<detail::vectorizable _Tp> requires std::totally_ordered<_Tp>
218constexpr _Tp reduce_min(const _Tp& v) noexcept { return v; }
219
225template<detail::vectorizable _Tp> requires std::totally_ordered<_Tp>
226constexpr _Tp reduce_min(const _Tp& v, std::same_as<bool> auto m) noexcept
227 { return m ? v : std::numeric_limits<_Tp>::max(); }
228
233template<detail::vectorizable _Tp> requires std::totally_ordered<_Tp>
234constexpr _Tp reduce_max(const _Tp& v) noexcept { return v; }
235
241template<detail::vectorizable _Tp> requires std::totally_ordered<_Tp>
242constexpr _Tp reduce_max(const _Tp& v, std::same_as<bool> auto m) noexcept
243 { return m ? v : std::numeric_limits<_Tp>::lowest(); }
244
246
247} // namespace _XVEC_NAMESPACE::simd
static constexpr basic_mask __mask_from_count(simd_size_type _n)
Definition mask.hpp:223
Vector of elements sharing an element type and ABI.
Definition simd:161
basic_mask< sizeof(_Tp), _Abi > mask_type
Definition simd:184
constexpr _Vp min(const _Vp &lhs, const _Vp &rhs) noexcept
Compute the smaller of each respective vec element from the two input arguments.
Definition std_algorithm.hpp:34
constexpr _Vp max(const _Vp &lhs, const _Vp &rhs) noexcept
Compute the larger of each respective vec element from the two input arguments.
Definition std_algorithm.hpp:48
constexpr auto select(const _M &m, const _T &if_true, const _U &if_false) noexcept -> decltype(simd_select_impl(m, if_true, if_false))
Select between corresponding elements according to a mask.
Definition std_algorithm.hpp:88
constexpr bool none_of(const mask_type auto &mask) noexcept
Return true if no mask element is true.
Definition mask.hpp:489
basic_vec< _Tp, simd_fixed_size_abi< _Np > > vec
Definition core.hpp:379
constexpr _V::value_type reduce(const _V &v, _BinaryFn binop={})
Apply a reduction operation across all elements of the basic_vec value to reduce them to a single sca...
Definition reduce.hpp:105
constexpr _V::value_type reduce_max(const _V &v) noexcept
Return the maximum vector element.
Definition reduce.hpp:187
constexpr _V::value_type reduce_min(const _V &v) noexcept
Return the minimum vector element.
Definition reduce.hpp:156
constexpr auto drop(const vec_or_mask_type auto &in)
Discard the first _Np elements of the input, returning the remainder.
Definition named_permute.hpp:240
constexpr basic_vec< _Tp, _AbiIp > permute(VENDOR tag, const basic_vec< _Tp, _AbiTp > &v, const basic_vec< _Ip, _AbiIp > &indexes)
Definition permute.hpp:276
constexpr bool dependent_false
Definition utilities.hpp:103
_Tp reduce_helper(const basic_vec< _Tp, _Abi > &v, _BinaryFn binop)
Definition reduce.hpp:53