Eigen  5.0.1-dev+master
 
Loading...
Searching...
No Matches
Redux.h
1// This file is part of Eigen, a lightweight C++ template library
2// for linear algebra.
3//
4// Copyright (C) 2008 Gael Guennebaud <gael.guennebaud@inria.fr>
5// Copyright (C) 2006-2008 Benoit Jacob <jacob.benoit.1@gmail.com>
6//
7// This Source Code Form is subject to the terms of the Mozilla
8// Public License v. 2.0. If a copy of the MPL was not distributed
9// with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
10// SPDX-License-Identifier: MPL-2.0
11
12#ifndef EIGEN_REDUX_H
13#define EIGEN_REDUX_H
14
15// IWYU pragma: private
16#include "./InternalHeaderCheck.h"
17
18namespace Eigen {
19
20namespace internal {
21
22// TODO
23// * implement other kind of vectorization
24// * factorize code
25
26/***************************************************************************
27 * Part 1 : the logic deciding a strategy for vectorization and unrolling
28 ***************************************************************************/
29
30// Bounds used only to exclude unreachable reduction paths. Combining expression
31// storage bounds instead would change PlainObject types and can create oversized inline storage.
32template <typename Xpr>
33struct redux_max_size {
34 static constexpr int Rows = Xpr::MaxRowsAtCompileTime;
35 static constexpr int Cols = Xpr::MaxColsAtCompileTime;
36 static constexpr int Size = Xpr::MaxSizeAtCompileTime;
37};
38
39template <typename Op, typename Lhs, typename Rhs>
40struct redux_max_size<CwiseBinaryOp<Op, Lhs, Rhs>> {
41 using Left = redux_max_size<remove_all_t<Lhs>>;
42 using Right = redux_max_size<remove_all_t<Rhs>>;
43 static constexpr int Rows = min_size_prefer_fixed(Left::Rows, Right::Rows);
44 static constexpr int Cols = min_size_prefer_fixed(Left::Cols, Right::Cols);
45 static constexpr int Size =
46 min_size_prefer_fixed(min_size_prefer_fixed(Left::Size, Right::Size), size_at_compile_time(Rows, Cols));
47};
48
49template <typename Op, typename Arg>
50struct redux_max_size<CwiseUnaryOp<Op, Arg>> : redux_max_size<remove_all_t<Arg>> {};
51
52template <typename Arg>
53struct redux_max_size<ArrayWrapper<Arg>> : redux_max_size<remove_all_t<Arg>> {};
54
55template <typename Arg>
56struct redux_max_size<MatrixWrapper<Arg>> : redux_max_size<remove_all_t<Arg>> {};
57
58template <typename Op, typename Arg1, typename Arg2, typename Arg3>
59struct redux_max_size<CwiseTernaryOp<Op, Arg1, Arg2, Arg3>> {
60 using First = redux_max_size<remove_all_t<Arg1>>;
61 using Second = redux_max_size<remove_all_t<Arg2>>;
62 using Third = redux_max_size<remove_all_t<Arg3>>;
63 static constexpr int Rows = min_size_prefer_fixed(First::Rows, min_size_prefer_fixed(Second::Rows, Third::Rows));
64 static constexpr int Cols = min_size_prefer_fixed(First::Cols, min_size_prefer_fixed(Second::Cols, Third::Cols));
65 static constexpr int Size =
66 min_size_prefer_fixed(min_size_prefer_fixed(First::Size, min_size_prefer_fixed(Second::Size, Third::Size)),
67 size_at_compile_time(Rows, Cols));
68};
69
70template <typename Func, typename Evaluator>
71struct redux_traits {
72 public:
73 using PacketType = typename find_best_packet<typename Evaluator::Scalar, Evaluator::SizeAtCompileTime>::type;
74 enum {
75 PacketSize = unpacket_traits<PacketType>::size,
76 InnerMaxSize = int(Evaluator::IsRowMajor) ? Evaluator::MaxColsAtCompileTime : Evaluator::MaxRowsAtCompileTime,
77 OuterMaxSize = int(Evaluator::IsRowMajor) ? Evaluator::MaxRowsAtCompileTime : Evaluator::MaxColsAtCompileTime,
78 SliceVectorizedWork = int(InnerMaxSize) == Dynamic ? Dynamic
79 : int(OuterMaxSize) == Dynamic ? (int(InnerMaxSize) >= int(PacketSize) ? Dynamic : 0)
80 : (int(InnerMaxSize) / int(PacketSize)) * int(OuterMaxSize)
81 };
82
83 enum {
84 MayLinearize = (int(Evaluator::Flags) & LinearAccessBit),
85 MightVectorize = (int(Evaluator::Flags) & ActualPacketAccessBit) && (functor_traits<Func>::PacketAccess),
86 MayLinearVectorize = bool(MightVectorize) && bool(MayLinearize),
87 MaySliceVectorize = bool(MightVectorize) && (int(SliceVectorizedWork) == Dynamic || int(SliceVectorizedWork) >= 3)
88 };
89
90 public:
91 enum {
92 Traversal = int(MayLinearVectorize) ? int(LinearVectorizedTraversal)
93 : int(MaySliceVectorize) ? int(SliceVectorizedTraversal)
94 : int(MayLinearize) ? int(LinearTraversal)
95 : int(DefaultTraversal)
96 };
97
98 public:
99 enum {
100 Cost = Evaluator::SizeAtCompileTime == Dynamic
101 ? HugeCost
102 : int(Evaluator::SizeAtCompileTime) * int(Evaluator::CoeffReadCost) +
103 (Evaluator::SizeAtCompileTime - 1) * functor_traits<Func>::Cost,
104 UnrollingLimit = EIGEN_UNROLLING_LIMIT * (int(Traversal) == int(DefaultTraversal) ? 1 : int(PacketSize))
105 };
106
107 public:
108 // UnrollingLimit grows with the packet size and by default reaches HugeCost from 91 scalars per packet on, so the
109 // Cost of a runtime size alone does not rule out unrolling it.
110 static constexpr int Unrolling =
111 (Evaluator::SizeAtCompileTime != Dynamic && Cost <= UnrollingLimit) ? CompleteUnrolling : NoUnrolling;
112
113#ifdef EIGEN_DEBUG_ASSIGN
114 static void debug() {
115 std::cerr << "Xpr: " << typeid(typename Evaluator::XprType).name() << std::endl;
116 std::cerr.setf(std::ios::hex, std::ios::basefield);
117 EIGEN_DEBUG_VAR(Evaluator::Flags)
118 std::cerr.unsetf(std::ios::hex);
119 EIGEN_DEBUG_VAR(InnerMaxSize)
120 EIGEN_DEBUG_VAR(OuterMaxSize)
121 EIGEN_DEBUG_VAR(SliceVectorizedWork)
122 EIGEN_DEBUG_VAR(PacketSize)
123 EIGEN_DEBUG_VAR(MightVectorize)
124 EIGEN_DEBUG_VAR(MayLinearVectorize)
125 EIGEN_DEBUG_VAR(MaySliceVectorize)
126 std::cerr << "Traversal"
127 << " = " << Traversal << " (" << demangle_traversal(Traversal) << ")" << std::endl;
128 EIGEN_DEBUG_VAR(UnrollingLimit)
129 std::cerr << "Unrolling"
130 << " = " << Unrolling << " (" << demangle_unrolling(Unrolling) << ")" << std::endl;
131 std::cerr << std::endl;
132 }
133#endif
134};
135
136/***************************************************************************
137 * Part 2 : unrollers
138 ***************************************************************************/
139
140/*** no vectorization ***/
141
142template <typename Func, typename Evaluator, Index Start, Index Length>
143struct redux_novec_unroller {
144 static constexpr Index HalfLength = Length / 2;
145
146 using Scalar = typename Evaluator::Scalar;
147
148 EIGEN_DEVICE_FUNC static constexpr EIGEN_STRONG_INLINE Scalar run(const Evaluator& eval, const Func& func) {
149 return func(redux_novec_unroller<Func, Evaluator, Start, HalfLength>::run(eval, func),
150 redux_novec_unroller<Func, Evaluator, Start + HalfLength, Length - HalfLength>::run(eval, func));
151 }
152};
153
154template <typename Func, typename Evaluator, Index Start>
155struct redux_novec_unroller<Func, Evaluator, Start, 1> {
156 static constexpr Index outer = Start / Evaluator::InnerSizeAtCompileTime;
157 static constexpr Index inner = Start % Evaluator::InnerSizeAtCompileTime;
158
159 using Scalar = typename Evaluator::Scalar;
160
161 EIGEN_DEVICE_FUNC static constexpr EIGEN_STRONG_INLINE Scalar run(const Evaluator& eval, const Func&) {
162 return eval.coeffByOuterInner(outer, inner);
163 }
164};
165
166// This is actually dead code and will never be called. It is required
167// to prevent false warnings regarding failed inlining though
168// for 0 length run() will never be called at all.
169template <typename Func, typename Evaluator, Index Start>
170struct redux_novec_unroller<Func, Evaluator, Start, 0> {
171 using Scalar = typename Evaluator::Scalar;
172 EIGEN_DEVICE_FUNC static constexpr EIGEN_STRONG_INLINE Scalar run(const Evaluator&, const Func&) { return Scalar(); }
173};
174
175template <typename Func, typename Evaluator, Index Start, Index Length>
176struct redux_novec_linear_unroller {
177 static constexpr Index HalfLength = Length / 2;
178
179 using Scalar = typename Evaluator::Scalar;
180
181 EIGEN_DEVICE_FUNC static constexpr EIGEN_STRONG_INLINE Scalar run(const Evaluator& eval, const Func& func) {
182 return func(redux_novec_linear_unroller<Func, Evaluator, Start, HalfLength>::run(eval, func),
183 redux_novec_linear_unroller<Func, Evaluator, Start + HalfLength, Length - HalfLength>::run(eval, func));
184 }
185};
186
187template <typename Func, typename Evaluator, Index Start>
188struct redux_novec_linear_unroller<Func, Evaluator, Start, 1> {
189 using Scalar = typename Evaluator::Scalar;
190
191 EIGEN_DEVICE_FUNC static constexpr EIGEN_STRONG_INLINE Scalar run(const Evaluator& eval, const Func&) {
192 return eval.coeff(Start);
193 }
194};
195
196// This is actually dead code and will never be called. It is required
197// to prevent false warnings regarding failed inlining though
198// for 0 length run() will never be called at all.
199template <typename Func, typename Evaluator, Index Start>
200struct redux_novec_linear_unroller<Func, Evaluator, Start, 0> {
201 using Scalar = typename Evaluator::Scalar;
202 EIGEN_DEVICE_FUNC static constexpr EIGEN_STRONG_INLINE Scalar run(const Evaluator&, const Func&) { return Scalar(); }
203};
204
205/*** vectorization ***/
206
207template <typename Func, typename Evaluator, Index Start, Index Length>
208struct redux_vec_unroller {
209 template <typename PacketType>
210 EIGEN_DEVICE_FUNC static EIGEN_STRONG_INLINE PacketType run(const Evaluator& eval, const Func& func) {
211 constexpr Index HalfLength = Length / 2;
212
213 return func.packetOp(
214 redux_vec_unroller<Func, Evaluator, Start, HalfLength>::template run<PacketType>(eval, func),
215 redux_vec_unroller<Func, Evaluator, Start + HalfLength, Length - HalfLength>::template run<PacketType>(eval,
216 func));
217 }
218};
219
220template <typename Func, typename Evaluator, Index Start>
221struct redux_vec_unroller<Func, Evaluator, Start, 1> {
222 template <typename PacketType>
223 EIGEN_DEVICE_FUNC static EIGEN_STRONG_INLINE PacketType run(const Evaluator& eval, const Func&) {
224 constexpr Index PacketSize = unpacket_traits<PacketType>::size;
225 constexpr Index index = Start * PacketSize;
226 constexpr Index outer = index / int(Evaluator::InnerSizeAtCompileTime);
227 constexpr Index inner = index % int(Evaluator::InnerSizeAtCompileTime);
228 constexpr int alignment = Evaluator::Alignment;
229
230 return eval.template packetByOuterInner<alignment, PacketType>(outer, inner);
231 }
232};
233
234template <typename Func, typename Evaluator, Index Start, Index Length>
235struct redux_vec_linear_unroller {
236 template <typename PacketType>
237 EIGEN_DEVICE_FUNC static EIGEN_STRONG_INLINE PacketType run(const Evaluator& eval, const Func& func) {
238 constexpr Index HalfLength = Length / 2;
239
240 return func.packetOp(
241 redux_vec_linear_unroller<Func, Evaluator, Start, HalfLength>::template run<PacketType>(eval, func),
242 redux_vec_linear_unroller<Func, Evaluator, Start + HalfLength, Length - HalfLength>::template run<PacketType>(
243 eval, func));
244 }
245};
246
247template <typename Func, typename Evaluator, Index Start>
248struct redux_vec_linear_unroller<Func, Evaluator, Start, 1> {
249 template <typename PacketType>
250 EIGEN_DEVICE_FUNC static EIGEN_STRONG_INLINE PacketType run(const Evaluator& eval, const Func&) {
251 constexpr Index PacketSize = unpacket_traits<PacketType>::size;
252 constexpr Index index = (Start * PacketSize);
253 constexpr int alignment = Evaluator::Alignment;
254 return eval.template packet<alignment, PacketType>(index);
255 }
256};
257
258/***************************************************************************
259 * Part 3 : implementation of all cases
260 ***************************************************************************/
261
262template <typename Func, typename Evaluator, int Traversal = redux_traits<Func, Evaluator>::Traversal,
263 int Unrolling = redux_traits<Func, Evaluator>::Unrolling>
264struct redux_impl;
265
266// Cutoffs below which the plain serial loop beats the wider unrolled bodies, measured on x86-64
267// with GCC 13 and Clang 18. The linear path serves both contiguous data (vectorizes, profits
268// from ~24) and strided data (loads dominate, profits only from ~64); 32 is where neither side
269// loses measurably.
270constexpr Index kReduxCommutativeCutoff = 32; // independent accumulators, linear traversal
271constexpr Index kReduxCommutativeInnerCutoff = 16; // independent accumulators, outer/inner traversal
272// GCC auto-vectorizes the ordered tree through a shuffle network whose setup only amortizes on
273// long runs; Clang keeps it scalar, where the shorter dependency chain pays from small sizes.
274constexpr Index kReduxOrderedTreeCutoff = EIGEN_COMP_GNUC_STRICT ? 192 : 16;
275
276template <typename Func, typename Evaluator>
277struct redux_impl<Func, Evaluator, DefaultTraversal, NoUnrolling> {
278 using Scalar = typename Evaluator::Scalar;
279
280 template <typename XprType>
281 EIGEN_DEVICE_FUNC static EIGEN_STRONG_INLINE Scalar run(const Evaluator& eval, const Func& func, const XprType& xpr) {
282 EIGEN_INTERNAL_ASSERT_NONEMPTY(xpr);
283 const Index innerSize = xpr.innerSize();
284 const Index outerSize = xpr.outerSize();
285 using Bounds = redux_max_size<XprType>;
286 constexpr int MaxInnerSize = XprType::IsVectorAtCompileTime ? Bounds::Size
287 : XprType::IsRowMajor ? Bounds::Cols
288 : Bounds::Rows;
289 EIGEN_IF_CONSTEXPR (functor_is_commutative<Func>::value) {
290 EIGEN_IF_CONSTEXPR (MaxInnerSize == Dynamic || MaxInnerSize >= kReduxCommutativeInnerCutoff) {
291 if (innerSize >= kReduxCommutativeInnerCutoff) return runCommutative(eval, func, innerSize, outerSize);
292 }
293 } else {
294 EIGEN_IF_CONSTEXPR (MaxInnerSize == Dynamic || MaxInnerSize >= kReduxOrderedTreeCutoff) {
295 if (innerSize >= kReduxOrderedTreeCutoff) return runOrderedTree(eval, func, innerSize, outerSize);
296 }
297 }
298 Scalar res = eval.coeffByOuterInner(0, 0);
299 for (Index j = 1; j < innerSize; ++j) res = func(res, eval.coeffByOuterInner(0, j));
300 for (Index i = 1; i < outerSize; ++i)
301 for (Index j = 0; j < innerSize; ++j) res = func(res, eval.coeffByOuterInner(i, j));
302 return res;
303 }
304
305 // Commutativity lets coefficients split across eight independent accumulators: the dependency
306 // chain drops to size/8 and each stride-8 stream vectorizes without cross-lane shuffles. The
307 // accumulators persist across outer slices; only the ragged inner tail of each slice joins a0.
308 EIGEN_DEVICE_FUNC static EIGEN_STRONG_INLINE Scalar runCommutative(const Evaluator& eval, const Func& func,
309 Index innerSize, Index outerSize) {
310 Scalar a0 = eval.coeffByOuterInner(0, 0), a1 = eval.coeffByOuterInner(0, 1);
311 Scalar a2 = eval.coeffByOuterInner(0, 2), a3 = eval.coeffByOuterInner(0, 3);
312 Scalar a4 = eval.coeffByOuterInner(0, 4), a5 = eval.coeffByOuterInner(0, 5);
313 Scalar a6 = eval.coeffByOuterInner(0, 6), a7 = eval.coeffByOuterInner(0, 7);
314 const Index unrolledEnd = innerSize - innerSize % 8;
315 for (Index i = 0; i < outerSize; ++i) {
316 Index j = (i == 0) ? 8 : 0;
317 for (; j < unrolledEnd; j += 8) {
318 a0 = func(a0, eval.coeffByOuterInner(i, j + 0));
319 a1 = func(a1, eval.coeffByOuterInner(i, j + 1));
320 a2 = func(a2, eval.coeffByOuterInner(i, j + 2));
321 a3 = func(a3, eval.coeffByOuterInner(i, j + 3));
322 a4 = func(a4, eval.coeffByOuterInner(i, j + 4));
323 a5 = func(a5, eval.coeffByOuterInner(i, j + 5));
324 a6 = func(a6, eval.coeffByOuterInner(i, j + 6));
325 a7 = func(a7, eval.coeffByOuterInner(i, j + 7));
326 }
327 for (; j < innerSize; ++j) a0 = func(a0, eval.coeffByOuterInner(i, j));
328 }
329 return func(func(func(a0, a1), func(a2, a3)), func(func(a4, a5), func(a6, a7)));
330 }
331
332 // Associativity alone: contiguous groups of four combine in traversal order through a pairwise
333 // tree, shortening the dependency chain to size/4 without reordering any operands.
334 EIGEN_DEVICE_FUNC static EIGEN_STRONG_INLINE Scalar runOrderedTree(const Evaluator& eval, const Func& func,
335 Index innerSize, Index outerSize) {
336 const Index unrolledEnd = innerSize - innerSize % 4;
337 Scalar res = reduce4(eval, func, 0, 0);
338 for (Index i = 0; i < outerSize; ++i) {
339 Index j = (i == 0) ? 4 : 0;
340 for (; j < unrolledEnd; j += 4) res = func(res, reduce4(eval, func, i, j));
341 for (; j < innerSize; ++j) res = func(res, eval.coeffByOuterInner(i, j));
342 }
343 return res;
344 }
345
346 EIGEN_DEVICE_FUNC static EIGEN_STRONG_INLINE Scalar reduce4(const Evaluator& eval, const Func& func, Index outer,
347 Index inner) {
348 return func(func(eval.coeffByOuterInner(outer, inner + 0), eval.coeffByOuterInner(outer, inner + 1)),
349 func(eval.coeffByOuterInner(outer, inner + 2), eval.coeffByOuterInner(outer, inner + 3)));
350 }
351};
352
353template <typename Func, typename Evaluator>
354struct redux_impl<Func, Evaluator, LinearTraversal, NoUnrolling> {
355 using Scalar = typename Evaluator::Scalar;
356
357 template <typename XprType>
358 EIGEN_DEVICE_FUNC static EIGEN_STRONG_INLINE Scalar run(const Evaluator& eval, const Func& func, const XprType& xpr) {
359 const Index size = xpr.size();
360 EIGEN_INTERNAL_ASSERT_NONEMPTY_SIZE(xpr, size);
361 // Do not generate wide reduction bodies for bounded expressions that cannot
362 // reach their cutoff (GCC can otherwise diagnose their unreachable loads).
363 EIGEN_IF_CONSTEXPR (functor_is_commutative<Func>::value) {
364 EIGEN_IF_CONSTEXPR (redux_max_size<XprType>::Size == Dynamic ||
365 redux_max_size<XprType>::Size >= kReduxCommutativeCutoff) {
366 if (size >= kReduxCommutativeCutoff) return runCommutative(eval, func, size);
367 }
368 } else {
369 EIGEN_IF_CONSTEXPR (redux_max_size<XprType>::Size == Dynamic ||
370 redux_max_size<XprType>::Size >= kReduxOrderedTreeCutoff) {
371 if (size >= kReduxOrderedTreeCutoff) return runOrderedTree(eval, func, size);
372 }
373 }
374 Scalar res = eval.coeff(0);
375 for (Index k = 1; k < size; ++k) res = func(res, eval.coeff(k));
376 return res;
377 }
378
379 // Commutativity lets coefficients split across eight independent accumulators: the dependency
380 // chain drops to size/8 and each stride-8 stream vectorizes without cross-lane shuffles.
381 EIGEN_DEVICE_FUNC static EIGEN_STRONG_INLINE Scalar runCommutative(const Evaluator& eval, const Func& func,
382 Index size) {
383 Scalar a0 = eval.coeff(0), a1 = eval.coeff(1), a2 = eval.coeff(2), a3 = eval.coeff(3);
384 Scalar a4 = eval.coeff(4), a5 = eval.coeff(5), a6 = eval.coeff(6), a7 = eval.coeff(7);
385 const Index unrolledEnd = size - size % 8;
386 Index k = 8;
387 for (; k < unrolledEnd; k += 8) {
388 a0 = func(a0, eval.coeff(k + 0));
389 a1 = func(a1, eval.coeff(k + 1));
390 a2 = func(a2, eval.coeff(k + 2));
391 a3 = func(a3, eval.coeff(k + 3));
392 a4 = func(a4, eval.coeff(k + 4));
393 a5 = func(a5, eval.coeff(k + 5));
394 a6 = func(a6, eval.coeff(k + 6));
395 a7 = func(a7, eval.coeff(k + 7));
396 }
397 Scalar res = func(func(func(a0, a1), func(a2, a3)), func(func(a4, a5), func(a6, a7)));
398 for (; k < size; ++k) res = func(res, eval.coeff(k));
399 return res;
400 }
401
402 // Associativity alone: contiguous groups of four combine in traversal order through a pairwise
403 // tree, shortening the dependency chain to size/4 without reordering any operands.
404 EIGEN_DEVICE_FUNC static EIGEN_STRONG_INLINE Scalar runOrderedTree(const Evaluator& eval, const Func& func,
405 Index size) {
406 Scalar res = func(func(eval.coeff(0), eval.coeff(1)), func(eval.coeff(2), eval.coeff(3)));
407 const Index unrolledEnd = size - size % 4;
408 Index k = 4;
409 for (; k < unrolledEnd; k += 4) {
410 res = func(res, func(func(eval.coeff(k), eval.coeff(k + 1)), func(eval.coeff(k + 2), eval.coeff(k + 3))));
411 }
412 for (; k < size; ++k) res = func(res, eval.coeff(k));
413 return res;
414 }
415};
416
417template <typename Func, typename Evaluator>
418struct redux_impl<Func, Evaluator, DefaultTraversal, CompleteUnrolling>
419 : redux_novec_unroller<Func, Evaluator, 0, Evaluator::SizeAtCompileTime> {
420 using Base = redux_novec_unroller<Func, Evaluator, 0, Evaluator::SizeAtCompileTime>;
421 using Scalar = typename Evaluator::Scalar;
422 template <typename XprType>
423 EIGEN_DEVICE_FUNC static EIGEN_STRONG_INLINE Scalar run(const Evaluator& eval, const Func& func,
424 const XprType& /*xpr*/) {
425 return Base::run(eval, func);
426 }
428
429template <typename Func, typename Evaluator>
430struct redux_impl<Func, Evaluator, LinearTraversal, CompleteUnrolling>
431 : redux_novec_linear_unroller<Func, Evaluator, 0, Evaluator::SizeAtCompileTime> {
432 using Base = redux_novec_linear_unroller<Func, Evaluator, 0, Evaluator::SizeAtCompileTime>;
433 using Scalar = typename Evaluator::Scalar;
434 template <typename XprType>
435 EIGEN_DEVICE_FUNC static EIGEN_STRONG_INLINE Scalar run(const Evaluator& eval, const Func& func,
436 const XprType& /*xpr*/) {
437 return Base::run(eval, func);
438 }
439};
440
441template <typename Func, typename Evaluator>
442struct redux_impl<Func, Evaluator, LinearVectorizedTraversal, NoUnrolling> {
443 using Scalar = typename Evaluator::Scalar;
444 using PacketScalar = typename redux_traits<Func, Evaluator>::PacketType;
445
446 template <typename XprType>
447 static Scalar run(const Evaluator& eval, const Func& func, const XprType& xpr) {
448 const Index size = xpr.size();
449
450 constexpr Index packetSize = redux_traits<Func, Evaluator>::PacketSize;
451 constexpr int packetAlignment = unpacket_traits<PacketScalar>::alignment;
452 constexpr int alignment0 =
453 (bool(Evaluator::Flags & DirectAccessBit) && bool(packet_traits<Scalar>::AlignedOnScalar))
454 ? int(packetAlignment)
455 : int(Unaligned);
456 constexpr int alignment = plain_enum_max(alignment0, Evaluator::Alignment);
457 const Index alignedStart = internal::first_aligned<alignment>(xpr);
458 const Index alignedSize4 = numext::round_down(size - alignedStart, 4 * packetSize);
459 const Index alignedSize = numext::round_down(size - alignedStart, packetSize);
460 const Index alignedEnd4 = alignedStart + alignedSize4;
461 const Index alignedEnd = alignedStart + alignedSize;
462 Scalar res;
463 constexpr Index maxSize = redux_max_size<XprType>::Size;
464 EIGEN_IF_CONSTEXPR (maxSize == Dynamic || maxSize >= packetSize) {
465 if (alignedSize) {
466 PacketScalar packet_res0 = eval.template packet<alignment, PacketScalar>(alignedStart);
467 EIGEN_IF_CONSTEXPR (maxSize == Dynamic || maxSize >= 4 * packetSize) {
468 if (alignedSize4) // four independent accumulators keep the loop off the packetOp latency chain
469 {
470 PacketScalar packet_res1 = eval.template packet<alignment, PacketScalar>(alignedStart + packetSize);
471 PacketScalar packet_res2 = eval.template packet<alignment, PacketScalar>(alignedStart + 2 * packetSize);
472 PacketScalar packet_res3 = eval.template packet<alignment, PacketScalar>(alignedStart + 3 * packetSize);
473 for (Index index = alignedStart + 4 * packetSize; index < alignedEnd4; index += 4 * packetSize) {
474 packet_res0 = func.packetOp(packet_res0, eval.template packet<alignment, PacketScalar>(index));
475 packet_res1 =
476 func.packetOp(packet_res1, eval.template packet<alignment, PacketScalar>(index + packetSize));
477 packet_res2 =
478 func.packetOp(packet_res2, eval.template packet<alignment, PacketScalar>(index + 2 * packetSize));
479 packet_res3 =
480 func.packetOp(packet_res3, eval.template packet<alignment, PacketScalar>(index + 3 * packetSize));
481 }
482
483 // The one to three leftover packets go into accumulators that are still independent, so they
484 // cost a packetOp each rather than extending the merge below.
485 const Index remSize = alignedSize - alignedSize4;
486 if (remSize >= packetSize) {
487 packet_res0 = func.packetOp(packet_res0, eval.template packet<alignment, PacketScalar>(alignedEnd4));
488 if (remSize >= 2 * packetSize) {
489 packet_res1 =
490 func.packetOp(packet_res1, eval.template packet<alignment, PacketScalar>(alignedEnd4 + packetSize));
491 if (remSize == 3 * packetSize)
492 packet_res2 = func.packetOp(
493 packet_res2, eval.template packet<alignment, PacketScalar>(alignedEnd4 + 2 * packetSize));
494 }
495 }
496
497 // Merge as (res0 + res1) + (res2 + res3): two packetOp latencies deep instead of three.
498 packet_res0 = func.packetOp(packet_res0, packet_res1);
499 packet_res2 = func.packetOp(packet_res2, packet_res3);
500 packet_res0 = func.packetOp(packet_res0, packet_res2);
501 }
502 }
503 EIGEN_IF_CONSTEXPR (maxSize == Dynamic || maxSize >= 2 * packetSize) {
504 if (!alignedSize4 && alignedSize > packetSize) {
505 // Two or three packets: straight-line, with none of the trip-count setup a loop would need.
506 packet_res0 =
507 func.packetOp(packet_res0, eval.template packet<alignment, PacketScalar>(alignedStart + packetSize));
508 EIGEN_IF_CONSTEXPR (maxSize == Dynamic || maxSize >= 3 * packetSize) {
509 if (alignedSize > 2 * packetSize)
510 packet_res0 = func.packetOp(
511 packet_res0, eval.template packet<alignment, PacketScalar>(alignedStart + 2 * packetSize));
512 }
513 }
514 }
515 res = func.predux(packet_res0);
516
517 for (Index index = 0; index < alignedStart; ++index) res = func(res, eval.coeff(index));
518
519 for (Index index = alignedEnd; index < size; ++index) res = func(res, eval.coeff(index));
520 return res;
521 }
522 }
523 // Too small to vectorize anything.
524 res = eval.coeff(0);
525 for (Index index = 1; index < size; ++index) res = func(res, eval.coeff(index));
526 return res;
527 }
528};
529
530// NOTE: for SliceVectorizedTraversal we simply bypass unrolling
531template <typename Func, typename Evaluator, int Unrolling>
532struct redux_impl<Func, Evaluator, SliceVectorizedTraversal, Unrolling> {
533 using Scalar = typename Evaluator::Scalar;
534 using PacketType = typename redux_traits<Func, Evaluator>::PacketType;
535
536 static constexpr Index PacketSize = redux_traits<Func, Evaluator>::PacketSize;
537
538 EIGEN_DEVICE_FUNC static EIGEN_STRONG_INLINE PacketType packetAt(const Evaluator& eval, Index j, Index i) {
539 return eval.template packetByOuterInner<Unaligned, PacketType>(j, i);
540 }
541
542 template <typename XprType>
543 EIGEN_DEVICE_FUNC static Scalar run(const Evaluator& eval, const Func& func, const XprType& xpr) {
544 EIGEN_INTERNAL_ASSERT_NONEMPTY(xpr);
545 const Index innerSize = xpr.innerSize();
546 const Index outerSize = xpr.outerSize();
547 const Index packetedInnerSize = numext::round_down(innerSize, PacketSize);
548 const Index quadInnerSize = numext::round_down(innerSize, 4 * PacketSize);
549 Scalar res;
550 if (packetedInnerSize) {
551 // A single accumulator leaves one packetOp latency between consecutive iterations, so carry
552 // four of them across the whole (j, i) traversal and merge them once.
553 PacketType packet_res0 = packetAt(eval, 0, 0);
554 if (quadInnerSize) {
555 // Four packets or more per panel: each accumulator takes one packet of every group of four.
556 PacketType packet_res1 = packetAt(eval, 0, PacketSize);
557 PacketType packet_res2 = packetAt(eval, 0, 2 * PacketSize);
558 PacketType packet_res3 = packetAt(eval, 0, 3 * PacketSize);
559 // Every panel has the same number of packets left over, so this is loop-invariant and the
560 // branches on it do not wait on the packet loop below.
561 const Index remSize = packetedInnerSize - quadInnerSize;
562 for (Index j = 0; j < outerSize; ++j) {
563 for (Index i = (j == 0) ? 4 * PacketSize : 0; i < quadInnerSize; i += 4 * PacketSize) {
564 packet_res0 = func.packetOp(packet_res0, packetAt(eval, j, i));
565 packet_res1 = func.packetOp(packet_res1, packetAt(eval, j, i + PacketSize));
566 packet_res2 = func.packetOp(packet_res2, packetAt(eval, j, i + 2 * PacketSize));
567 packet_res3 = func.packetOp(packet_res3, packetAt(eval, j, i + 3 * PacketSize));
568 }
569 // This panel's one to three leftover packets, into accumulators that are still
570 // independent of each other.
571 if (remSize >= PacketSize) {
572 packet_res0 = func.packetOp(packet_res0, packetAt(eval, j, quadInnerSize));
573 if (remSize >= 2 * PacketSize) {
574 packet_res1 = func.packetOp(packet_res1, packetAt(eval, j, quadInnerSize + PacketSize));
575 if (remSize == 3 * PacketSize)
576 packet_res2 = func.packetOp(packet_res2, packetAt(eval, j, quadInnerSize + 2 * PacketSize));
577 }
578 }
579 }
580 // Merge as (res0 + res1) + (res2 + res3): two packetOp latencies deep instead of three.
581 packet_res0 = func.packetOp(packet_res0, packet_res1);
582 packet_res2 = func.packetOp(packet_res2, packet_res3);
583 packet_res0 = func.packetOp(packet_res0, packet_res2);
584 } else if (outerSize >= 4) {
585 // Panels of one to three packets cannot supply four independent packets, so the
586 // independence comes from the outer dimension: each accumulator takes its own panel.
587 PacketType packet_res1 = packetAt(eval, 1, 0);
588 PacketType packet_res2 = packetAt(eval, 2, 0);
589 PacketType packet_res3 = packetAt(eval, 3, 0);
590 for (Index i = PacketSize; i < packetedInnerSize; i += PacketSize) {
591 packet_res0 = func.packetOp(packet_res0, packetAt(eval, 0, i));
592 packet_res1 = func.packetOp(packet_res1, packetAt(eval, 1, i));
593 packet_res2 = func.packetOp(packet_res2, packetAt(eval, 2, i));
594 packet_res3 = func.packetOp(packet_res3, packetAt(eval, 3, i));
595 }
596 // Both loops take their bounds from quadOuterSize rather than sharing j: for a fixed outer size, GCC 10
597 // otherwise emits -Waggressive-loop-optimizations for the tail loop, which never runs.
598 const Index quadOuterSize = numext::round_down(outerSize, 4);
599 for (Index j = 4; j < quadOuterSize; j += 4)
600 for (Index i = 0; i < packetedInnerSize; i += PacketSize) {
601 packet_res0 = func.packetOp(packet_res0, packetAt(eval, j, i));
602 packet_res1 = func.packetOp(packet_res1, packetAt(eval, j + 1, i));
603 packet_res2 = func.packetOp(packet_res2, packetAt(eval, j + 2, i));
604 packet_res3 = func.packetOp(packet_res3, packetAt(eval, j + 3, i));
605 }
606 for (Index j = quadOuterSize; j < outerSize; ++j)
607 for (Index i = 0; i < packetedInnerSize; i += PacketSize)
608 packet_res0 = func.packetOp(packet_res0, packetAt(eval, j, i));
609
610 packet_res0 = func.packetOp(packet_res0, packet_res1);
611 packet_res2 = func.packetOp(packet_res2, packet_res3);
612 packet_res0 = func.packetOp(packet_res0, packet_res2);
613 } else {
614 // Fewer than four narrow panels: at most nine packets in total, not worth a merge.
615 for (Index j = 0; j < outerSize; ++j)
616 for (Index i = (j == 0 ? PacketSize : 0); i < packetedInnerSize; i += PacketSize)
617 packet_res0 = func.packetOp(packet_res0, packetAt(eval, j, i));
618 }
619
620 res = func.predux(packet_res0);
621 for (Index j = 0; j < outerSize; ++j)
622 for (Index i = packetedInnerSize; i < innerSize; ++i) res = func(res, eval.coeffByOuterInner(j, i));
623 } else // too small to vectorize anything.
624 // since this is dynamic-size hence inefficient anyway for such small sizes, don't try to optimize.
625 {
626 res = redux_impl<Func, Evaluator, DefaultTraversal, NoUnrolling>::run(eval, func, xpr);
627 }
628
629 return res;
630 }
631};
632
633template <typename Func, typename Evaluator>
634struct redux_impl<Func, Evaluator, LinearVectorizedTraversal, CompleteUnrolling> {
635 using Scalar = typename Evaluator::Scalar;
636
637 using PacketType = typename redux_traits<Func, Evaluator>::PacketType;
638 static constexpr Index PacketSize = redux_traits<Func, Evaluator>::PacketSize;
639 static constexpr Index Size = Evaluator::SizeAtCompileTime;
640 static constexpr Index VectorizedSize = (int(Size) / int(PacketSize)) * int(PacketSize);
641
642 template <typename XprType>
643 EIGEN_DEVICE_FUNC static EIGEN_STRONG_INLINE Scalar run(const Evaluator& eval, const Func& func, const XprType& xpr) {
644 EIGEN_ONLY_USED_FOR_DEBUG(xpr);
645 EIGEN_INTERNAL_ASSERT_NONEMPTY(xpr);
646 if (VectorizedSize > 0) {
647 Scalar res = func.predux(
648 redux_vec_linear_unroller<Func, Evaluator, 0, Size / PacketSize>::template run<PacketType>(eval, func));
649 if (VectorizedSize != Size)
650 res = func(
651 res, redux_novec_linear_unroller<Func, Evaluator, VectorizedSize, Size - VectorizedSize>::run(eval, func));
652 return res;
653 } else {
654 return redux_novec_linear_unroller<Func, Evaluator, 0, Size>::run(eval, func);
655 }
656 }
657};
658
659// evaluator adaptor
660template <typename XprType_>
661class redux_evaluator : public internal::evaluator<const XprType_> {
662 using Base = internal::evaluator<const XprType_>;
663
664 public:
665 using XprType = XprType_;
666 EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE explicit redux_evaluator(const XprType& xpr) : Base(xpr) {}
667
668 using Scalar = typename XprType::Scalar;
669 using CoeffReturnType = typename XprType::CoeffReturnType;
670 using PacketScalar = typename XprType::PacketScalar;
671
672 enum {
673 MaxRowsAtCompileTime = XprType::MaxRowsAtCompileTime,
674 MaxColsAtCompileTime = XprType::MaxColsAtCompileTime,
675 // TODO: we should not remove DirectAccessBit and rather find an elegant way to query the alignment offset at
676 // runtime from the evaluator
677 Flags = Base::Flags & ~DirectAccessBit,
678 IsRowMajor = XprType::IsRowMajor,
679 SizeAtCompileTime = XprType::SizeAtCompileTime,
680 InnerSizeAtCompileTime = XprType::InnerSizeAtCompileTime
681 };
682
683 EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE CoeffReturnType coeffByOuterInner(Index outer, Index inner) const {
684 return Base::coeff(IsRowMajor ? outer : inner, IsRowMajor ? inner : outer);
685 }
686
687 template <int LoadMode, typename PacketType>
688 EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE PacketType packetByOuterInner(Index outer, Index inner) const {
689 return Base::template packet<LoadMode, PacketType>(IsRowMajor ? outer : inner, IsRowMajor ? inner : outer);
690 }
691
692 template <int LoadMode, typename PacketType>
693 EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE PacketType packetSegmentByOuterInner(Index outer, Index inner, Index begin,
694 Index count) const {
695 return Base::template packetSegment<LoadMode, PacketType>(IsRowMajor ? outer : inner, IsRowMajor ? inner : outer,
696 begin, count);
697 }
698};
699
700// A reduction over an expression whose inner stride is not statically 1 (e.g. a dynamic-inner-stride
701// Map/Ref, or a row of a dynamic matrix) falls back to a scalar traversal, because the evaluator
702// drops PacketAccessBit when the inner stride is unknown at compile time. Yet such expressions are
703// very often contiguous at runtime. This trait flags the cases where it is worth checking at runtime
704// whether the data is contiguous and, if so, reducing it as a contiguous vector to recover full
705// vectorization. We only bother when the expression has direct access, the functor and scalar are
706// vectorizable, and the inner stride is not already statically 1 (otherwise it is handled directly).
707template <typename Func, typename Evaluator>
708struct redux_has_runtime_unit_stride_path {
709 using XprType = typename Evaluator::XprType;
710 using Scalar = typename Evaluator::Scalar;
711 static constexpr bool value = bool(traits<XprType>::Flags & DirectAccessBit) &&
712 bool(functor_traits<Func>::PacketAccess) && bool(packet_traits<Scalar>::Vectorizable) &&
713 (int(inner_stride_at_compile_time<XprType>::value) != 1);
714};
715
716template <typename Func, typename Evaluator, typename XprType,
717 bool = redux_has_runtime_unit_stride_path<Func, Evaluator>::value>
718struct redux_dispatch {
719 static EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE typename Evaluator::Scalar run(const Evaluator& thisEval,
720 const Func& func, const XprType& xpr) {
721 return redux_impl<Func, Evaluator>::run(thisEval, func, xpr);
722 }
723};
724
725// Runtime contiguity fast path: when the inner stride is 1 and the data is fully packed
726// (a single inner panel, or no gap between inner panels), reduce the underlying buffer as a
727// contiguous vector. The reduction is over all coefficients with an associative functor, so
728// reducing in storage order yields the same result (up to the usual floating-point reassociation
729// already inherent to vectorized reductions).
730template <typename Func, typename Evaluator, typename XprType>
731struct redux_dispatch<Func, Evaluator, XprType, true> {
732 using Scalar = typename Evaluator::Scalar;
733 static EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE Scalar run(const Evaluator& thisEval, const Func& func,
734 const XprType& xpr) {
735 if (xpr.innerStride() == 1 && (xpr.outerSize() == 1 || xpr.outerStride() == xpr.innerSize())) {
736 using PlainVector = Matrix<Scalar, Dynamic, 1>;
737 using MapType = Map<const PlainVector, Evaluator::Alignment>;
738 MapType contiguous(xpr.data(), xpr.size());
739 redux_evaluator<MapType> mapEval(contiguous);
740 return redux_impl<Func, redux_evaluator<MapType>>::run(mapEval, func, contiguous);
741 }
742 return redux_impl<Func, Evaluator>::run(thisEval, func, xpr);
743 }
744};
745
746// Convert identity to Scalar only for empty inputs; otherwise reduce without inserting it.
747// Tag dispatch avoids instantiating redux for statically empty inputs or converting an unused identity in C++14.
748// TODO(C++17): replace tag dispatch with if constexpr.
749template <typename Derived, typename Func, typename Identity>
750EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE typename Derived::Scalar redux_with_identity_impl(const DenseBase<Derived>&,
751 const Func&,
752 Identity&& identity,
753 true_type) {
754 return typename Derived::Scalar(std::forward<Identity>(identity));
755}
756
757// Compare against 0 rather than Dynamic: non-inline constexpr Dynamic has internal linkage in C++14,
758// which keeps Clang header modules from merging template redeclarations across textual inclusions.
759template <typename Derived, typename Func, typename Identity,
760 std::enable_if_t<(Derived::SizeAtCompileTime < 0), int> = 0>
761EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE typename Derived::Scalar redux_with_identity_impl(const DenseBase<Derived>& xpr,
762 const Func& func,
763 Identity&& identity,
764 false_type) {
765 if (xpr.size() == 0) return typename Derived::Scalar(std::forward<Identity>(identity));
766 return xpr.derived().redux(func);
767}
768
769template <typename Derived, typename Func, typename Identity,
770 std::enable_if_t<(Derived::SizeAtCompileTime >= 0), int> = 0>
771EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE typename Derived::Scalar redux_with_identity_impl(const DenseBase<Derived>& xpr,
772 const Func& func, Identity&&,
773 false_type) {
774 return xpr.derived().redux(func);
775}
776
777template <typename Derived, typename Func, typename Identity>
778EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE typename Derived::Scalar redux_with_identity(const DenseBase<Derived>& xpr,
779 const Func& func,
780 Identity&& identity) {
781 return redux_with_identity_impl(xpr, func, std::forward<Identity>(identity),
782 bool_constant<Derived::MaxSizeAtCompileTime == 0>());
783}
784
785} // end namespace internal
786
787/***************************************************************************
788 * Part 4 : public API
789 ***************************************************************************/
790
803template <typename Derived>
804template <typename Func>
805EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE typename internal::traits<Derived>::Scalar DenseBase<Derived>::redux(
806 const Func& func) const {
807 EIGEN_INTERNAL_ASSERT_NONEMPTY(*this);
808
809 using ThisEvaluator = typename internal::redux_evaluator<Derived>;
810 ThisEvaluator thisEval(derived());
811
812 // The initial expression is passed to the reducer as an additional argument instead of
813 // passing it as a member of redux_evaluator. redux_dispatch additionally takes a runtime
814 // contiguity fast path for expressions that lose compile-time vectorization to a dynamic
815 // inner stride but are contiguous at runtime (see redux_dispatch).
816 return internal::redux_dispatch<Func, ThisEvaluator, Derived>::run(thisEval, func, derived());
817}
818
826template <typename Derived>
827template <int NaNPropagation>
828EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE typename internal::traits<Derived>::Scalar DenseBase<Derived>::minCoeff() const {
829 return derived().redux(Eigen::internal::scalar_min_op<Scalar, Scalar, NaNPropagation>());
830}
831
839template <typename Derived>
840template <int NaNPropagation>
841EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE typename internal::traits<Derived>::Scalar DenseBase<Derived>::maxCoeff() const {
842 return derived().redux(Eigen::internal::scalar_max_op<Scalar, Scalar, NaNPropagation>());
843}
844
851template <typename Derived>
852EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE typename internal::traits<Derived>::Scalar DenseBase<Derived>::sum() const {
853 return internal::redux_with_identity(*this, internal::scalar_sum_op<Scalar, Scalar>(), 0);
854}
855
860template <typename Derived>
861EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE typename internal::traits<Derived>::Scalar DenseBase<Derived>::mean() const {
862#ifdef __INTEL_COMPILER
863#pragma warning push
864#pragma warning(disable : 2259)
865#endif
866 return Scalar(derived().redux(Eigen::internal::scalar_sum_op<Scalar, Scalar>())) / Scalar(this->size());
867#ifdef __INTEL_COMPILER
868#pragma warning pop
869#endif
870}
871
879template <typename Derived>
880EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE typename internal::traits<Derived>::Scalar DenseBase<Derived>::prod() const {
881 return internal::redux_with_identity(*this, internal::scalar_product_op<Scalar>(), 1);
882}
883
890template <typename Derived>
891EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE typename internal::traits<Derived>::Scalar MatrixBase<Derived>::trace() const {
892 return derived().diagonal().sum();
893}
894
895} // end namespace Eigen
896
897#endif // EIGEN_REDUX_H
internal::traits< Derived >::Scalar minCoeff() const
Definition Redux.h:828
Scalar mean() const
Definition Redux.h:861
internal::traits< Derived >::Scalar maxCoeff() const
Definition Redux.h:841
EvalReturnType eval() const
Definition DenseBase.h:389
typename internal::traits< ArrayWrapper< ExpressionType > >::Scalar Scalar
Definition DenseBase.h:63
Scalar sum() const
Definition Redux.h:852
Scalar prod() const
Definition Redux.h:880
Scalar trace() const
Definition Redux.h:891
constexpr unsigned int ActualPacketAccessBit
Definition Constants.h:109
constexpr unsigned int LinearAccessBit
Definition Constants.h:134