Core: Test predicate segments shorter than a packet with one masked load, and OR integer packets in any() libeigen/eigen!3341
diff --git a/Eigen/src/Core/Predicator.h b/Eigen/src/Core/Predicator.h index eaba4d6..6d30226 100644 --- a/Eigen/src/Core/Predicator.h +++ b/Eigen/src/Core/Predicator.h
@@ -136,6 +136,11 @@ static EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE bool found(const Packet& m) { return predux_any(m); } + // Only the lanes set in a lane mask, as for a segment. + template <typename Packet> + static EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE bool found_in(const Packet& m, const Packet& lanes) { + return predux_any(pand(m, lanes)); + } template <typename Predicate, typename Scalar> static EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE bool test_scalar(const Predicate& pred, const Scalar& x) { return pred(x); @@ -152,6 +157,10 @@ static EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE bool found(const Packet& m) { return predux_any(pandnot(ptrue(m), m)); } + template <typename Packet> + static EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE bool found_in(const Packet& m, const Packet& lanes) { + return predux_any(pandnot(lanes, m)); + } template <typename Predicate, typename Scalar> static EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE bool test_scalar(const Predicate& pred, const Scalar& x) { return !pred(x); @@ -178,6 +187,23 @@ return x; } }; +// any_of(nonzero) on integer lanes ORs the coefficients themselves and compares the OR with zero once per block: it +// is zero exactly where every coefficient is. Floating-point lanes keep the compare per packet: their OR can be a +// signaling NaN, which a floating-point compare would flag as an invalid operation. +struct or_lane_search : predicate_search<true> { + template <typename Predicate, typename Packet> + static EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE Packet apply(const Predicate&, const Packet& x) { + return x; + } + template <typename Packet> + static EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE bool found(const Packet& m) { + return predux_any(pandnot(ptrue(m), pcmp_eq(m, pzero(m)))); + } + template <typename Packet> + static EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE bool found_in(const Packet& m, const Packet& lanes) { + return found(pand(m, lanes)); + } +}; template <bool Target, typename Predicate> struct predicate_search_for { using type = predicate_search<Target>; @@ -186,6 +212,10 @@ struct predicate_search_for<false, nonzero_predicate<Scalar>> { using type = zero_lane_search; }; +template <typename Scalar> +struct predicate_search_for<true, nonzero_predicate<Scalar>> { + using type = std::conditional_t<std::is_integral<Scalar>::value, or_lane_search, predicate_search<true>>; +}; template <> struct predicate_search_for<true, nonzero_predicate<bool>> { using type = bool_lane_search; @@ -195,6 +225,8 @@ template <typename Evaluator, bool Linear = Evaluator::LinearAccess> struct predicate_segment { using Scalar = typename Evaluator::Scalar; + static constexpr bool FixedSize = Evaluator::RowsAtCompileTime > 0 && Evaluator::ColsAtCompileTime > 0; + static constexpr bool PlainLoad = int(Evaluator::CoeffReadCost) <= int(NumTraits<Scalar>::ReadCost); const Evaluator& eval; Index length; EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE predicate_segment(const Evaluator& evaluator, Index, Index size) @@ -207,10 +239,17 @@ EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE Packet packet(Index i) const { return eval.template packet<Packet>(i); } + template <typename Packet> + EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE Packet packetSegment(Index i, Index count) const { + return eval.template packetSegment<Packet>(i, 0, count); + } }; template <typename Evaluator> struct predicate_segment<Evaluator, false> { using Scalar = typename Evaluator::Scalar; + static constexpr bool FixedSize = + (Evaluator::IsRowMajor ? Evaluator::ColsAtCompileTime : Evaluator::RowsAtCompileTime) > 0; + static constexpr bool PlainLoad = int(Evaluator::CoeffReadCost) <= int(NumTraits<Scalar>::ReadCost); const Evaluator& eval; Index outer; Index length; @@ -224,6 +263,11 @@ EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE Packet packet(Index i) const { return Evaluator::IsRowMajor ? eval.template packet<Packet>(outer, i) : eval.template packet<Packet>(i, outer); } + template <typename Packet> + EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE Packet packetSegment(Index i, Index count) const { + return Evaluator::IsRowMajor ? eval.template packetSegment<Packet>(outer, i, 0, count) + : eval.template packetSegment<Packet>(i, outer, 0, count); + } }; // Whether a predicate's scalar tests may be grouped; predicates that do not say are tested one at a time. @@ -320,6 +364,27 @@ return run(seg, pred); } }; +// first(count) is a packet whose first count lanes are all ones and whose other lanes are zero. table is one packet of +// 0xff bytes followed by one packet of zero bytes; an unaligned load that starts Size - count lanes into it reads count +// lanes of ones, then zeros. Bytes rather than Scalars, so that one table serves lanes of any width. +template <typename Packet, typename Bytes = std::make_index_sequence<2 * sizeof(Packet)>> +struct predicate_lane_table; +template <typename Packet, std::size_t... Byte> +struct predicate_lane_table<Packet, std::index_sequence<Byte...>> { + using Scalar = typename unpacket_traits<Packet>::type; + static constexpr Index Size = unpacket_traits<Packet>::size; + // Aligned to the packet, so that every load start is aligned to its Scalar. + alignas(sizeof(Packet)) static constexpr unsigned char table[2 * sizeof(Packet)] = { + (Byte < sizeof(Packet) ? 0xff : 0)...}; + static EIGEN_STRONG_INLINE Packet first(Index count) { + return ploadu<Packet>(reinterpret_cast<const Scalar*>(table + (Size - count) * sizeof(Scalar))); + } +}; +#if EIGEN_COMP_CXXVER < 17 +template <typename Packet, std::size_t... Byte> +alignas(sizeof(Packet)) constexpr unsigned char predicate_lane_table<Packet, std::index_sequence<Byte...>>::table[]; +#endif + template <typename Search, typename Packet> struct predicate_search_segment<Search, Packet, true> { // One helper per packet, taking its operands by reference and returning the mask by value: if the early inliner @@ -351,6 +416,8 @@ i = 3 * PacketSize; } if (EIGEN_PREDICT_TRUE(i == size)) return false; + } else if (has_packet_segment<Packet>::value && Segment::PlainLoad && (Segment::FixedSize || size >= 4)) { + return run_partial(seg, pred, bool_constant<has_packet_segment<Packet>::value>()); } else if (size < 4 && predicate_groups_scalars<Predicate>::value) { // Shorter than one packet and than a group of four: only these sizes reach this check. return predicate_search_upto3<Search>(seg, 0, pred); @@ -358,6 +425,22 @@ return predicate_search_tail<Search>(seg, i, pred); } + // A segment shorter than one packet, of a compile-time length or of at least four coefficients: one masked load, + // with the lanes past the segment masked off. Shorter runtime lengths keep their scalar tests, which are faster than + // building the masks; a compile-time length folds them. Only for a segment that loads its coefficients + // (Segment::PlainLoad): an expression computes on the zeros past the segment too, and 0 / 0 there would raise + // FE_INVALID, which the scalar tests of the same coefficients do not. + template <typename Segment, typename Predicate> + static EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE bool run_partial(const Segment& seg, Predicate pred, std::true_type) { + const Index size = seg.size(); + return Search::found_in(Search::apply(pred, seg.template packetSegment<Packet>(0, size)), + predicate_lane_table<Packet>::first(size)); + } + template <typename Segment, typename Predicate> + static EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE bool run_partial(const Segment& seg, Predicate pred, std::false_type) { + return predicate_search_tail<Search>(seg, 0, pred); + } + template <int Block, typename Segment, typename Predicate> static EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE bool run_blocks(const Segment& seg, Predicate pred) { const Index size = seg.size();
diff --git a/Eigen/src/Core/Visitor.h b/Eigen/src/Core/Visitor.h index 0fb61c9..71bc2ff 100644 --- a/Eigen/src/Core/Visitor.h +++ b/Eigen/src/Core/Visitor.h
@@ -339,12 +339,20 @@ EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE Packet packet(Index row, Index col) const { return m_evaluator.template packet<Alignment, Packet>(row, col); } + template <typename Packet> + EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE Packet packetSegment(Index row, Index col, Index begin, Index count) const { + return m_evaluator.template packetSegment<Unaligned, Packet>(row, col, begin, count); + } // linear access EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE CoeffReturnType coeff(Index index) const { return m_evaluator.coeff(index); } template <typename Packet, int Alignment = XprAlignment> EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE Packet packet(Index index) const { return m_evaluator.template packet<Alignment, Packet>(index); } + template <typename Packet> + EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE Packet packetSegment(Index index, Index begin, Index count) const { + return m_evaluator.template packetSegment<Unaligned, Packet>(index, begin, count); + } protected: Evaluator m_evaluator;
diff --git a/test/visitor.cpp b/test/visitor.cpp index 3c0153f..595c4c5 100644 --- a/test/visitor.cpp +++ b/test/visitor.cpp
@@ -10,6 +10,8 @@ #include "main.h" +#include <cfenv> + template <typename MatrixType> void matrixVisitor_impl(MatrixType& m) { typedef typename MatrixType::Scalar Scalar; @@ -390,6 +392,66 @@ VERIFY_IS_EQUAL(matrix.any(), count != 0); } +template <typename VectorType> +void checkFuzzyPredicates(VectorType&, std::false_type) {} + +template <typename VectorType> +void checkFuzzyPredicates(VectorType& v, std::true_type) { + using Scalar = typename VectorType::Scalar; + for (Index k = -1; k < v.size(); ++k) { + v.setConstant(Scalar(2)); + if (k >= 0) v(k) = Scalar(3); + VERIFY_IS_EQUAL(v.isApproxToConstant(Scalar(2)), k < 0); + v.setZero(); + if (k >= 0) v(k) = Scalar(1); + VERIFY_IS_EQUAL(v.isZero(), k < 0); + v.setOnes(); + if (k >= 0) v(k) = Scalar(NumTraits<typename NumTraits<Scalar>::Real>::infinity()); + VERIFY_IS_EQUAL(v.allFinite(), k < 0); + } +} + +// The deciding coefficient at each position of a vector, which for sizes below a packet reaches the masked segment +// load where the target has one. +template <typename VectorType> +void checkPredicatesAtEachPosition(VectorType& v) { + using Scalar = typename VectorType::Scalar; + for (int value = 0; value <= 1; ++value) { + for (Index k = -1; k < v.size(); ++k) { + v.setConstant(Scalar(value)); + if (k >= 0) v(k) = Scalar(!value); + checkBooleanVisitors(v); + } + } + checkFuzzyPredicates(v, internal::bool_constant<!NumTraits<Scalar>::IsInteger>()); +} + +template <typename Scalar, int Size> +void checkFixedPartialPacket() { + Array<Scalar, Size, 1> v; + checkPredicatesAtEachPosition(v); +} + +template <typename Scalar, int... Sizes> +void checkFixedPartialPackets(std::integer_sequence<int, Sizes...>) { + int unused[] = {0, (checkFixedPartialPacket<Scalar, Sizes + 1>(), 0)...}; + EIGEN_UNUSED_VARIABLE(unused); +} + +// Every runtime size up to two packets, aligned and not, and fixed sizes up to seven. +template <typename Scalar> +void checkPartialPackets() { + constexpr Index PacketSize = internal::packet_traits<Scalar>::size; + std::vector<Scalar> data(2 * PacketSize + 3); + for (Index size = 0; size <= 2 * PacketSize + 1; ++size) { + Array<Scalar, Dynamic, 1> v(size); + checkPredicatesAtEachPosition(v); + Map<Array<Scalar, Dynamic, 1>, Unaligned> unaligned(data.data() + 1, size); + checkPredicatesAtEachPosition(unaligned); + } + checkFixedPartialPackets<Scalar>(std::make_integer_sequence<int, 7>()); +} + template <typename Scalar, int Options> void checkBooleanVisitorTraversal() { constexpr int PacketSize = internal::packet_traits<Scalar>::size; @@ -423,6 +485,65 @@ checkBooleanVisitors(fixed); } +template <typename ArrayType> +EIGEN_DONT_INLINE bool anyOfArray(const ArrayType& a) { + return a.any(); +} + +// any() ORs whole integer packets before testing them, but not floating-point ones: the OR of two finite coefficients +// can be a signaling NaN, which a floating-point comparison would flag as an invalid operation. +template <typename Scalar> +void checkAnyRaisesNoInvalid() { + using Bits = typename numext::get_integer_by_size<sizeof(Scalar)>::unsigned_type; + constexpr Index PacketSize = internal::packet_traits<Scalar>::size; + // The successor of 1 and 2: their OR has an all-ones exponent and only the lowest mantissa bit set, a signaling NaN. + const Bits one = numext::bit_cast<Bits>(Scalar(1)) | Bits(1), two = numext::bit_cast<Bits>(Scalar(2)); + for (Index size : {2 * PacketSize, 3 * PacketSize, 8 * PacketSize, 9 * PacketSize + 3}) { + Array<Scalar, Dynamic, 1> a(size); + for (Index i = 0; i < size; ++i) a(i) = numext::bit_cast<Scalar>((i / PacketSize) % 2 ? one : two); +#if defined(FE_ALL_EXCEPT) && defined(FE_INVALID) + std::feclearexcept(FE_ALL_EXCEPT); + VERIFY(anyOfArray(a)); + VERIFY_IS_EQUAL(std::fetestexcept(FE_INVALID) & FE_INVALID, 0); +#else + VERIFY(anyOfArray(a)); +#endif + } +} + +template <typename ArrayType> +EIGEN_DONT_INLINE bool quotientAllFinite(const ArrayType& a, const ArrayType& b) { + return (a / b).allFinite(); +} +template <typename ArrayType> +EIGEN_DONT_INLINE bool quotientIsZero(const ArrayType& a, const ArrayType& b) { + return (a / b).matrix().isZero(); +} + +template <typename ArrayType> +void checkQuotientRaisesNoInvalid(const ArrayType& a, const ArrayType& b) { +#if defined(FE_ALL_EXCEPT) && defined(FE_INVALID) + std::feclearexcept(FE_ALL_EXCEPT); + VERIFY(quotientAllFinite(a, b)); + VERIFY(!quotientIsZero(a, b) || a.size() == 0); + VERIFY_IS_EQUAL(std::fetestexcept(FE_INVALID) & FE_INVALID, 0); +#else + VERIFY(quotientAllFinite(a, b)); + VERIFY(!quotientIsZero(a, b) || a.size() == 0); +#endif +} + +// A segment shorter than a packet is tested with one masked load only where the expression loads its coefficients: +// a quotient would also divide the zeros past the segment, 0 / 0, and flag an invalid operation that the scalar tests +// of the same coefficients do not. +template <typename Scalar> +void checkPartialPacketsRaiseNoInvalid() { + constexpr Index PacketSize = internal::packet_traits<Scalar>::size; + for (Index size = 0; size <= 2 * PacketSize + 1; ++size) + checkQuotientRaisesNoInvalid<Array<Scalar, Dynamic, 1>>(Array<Scalar, Dynamic, 1>::Constant(size, Scalar(1)), + Array<Scalar, Dynamic, 1>::Constant(size, Scalar(2))); +} + template <bool Vectorize = false> struct CountVisitorReads { Index* reads; @@ -671,8 +792,10 @@ CALL_SUBTEST_14((checkBooleanVisitorTraversal<bool, ColMajor>())); CALL_SUBTEST_14((checkBooleanVisitorTraversal<bool, RowMajor>())); CALL_SUBTEST_14((checkBooleanVisitorTraversal<float, ColMajor>())); + CALL_SUBTEST_14((checkBooleanVisitorTraversal<float, RowMajor>())); CALL_SUBTEST_14((checkBooleanVisitorTraversal<double, RowMajor>())); CALL_SUBTEST_14((checkBooleanVisitorTraversal<int, ColMajor>())); + CALL_SUBTEST_14((checkBooleanVisitorTraversal<int, RowMajor>())); CALL_SUBTEST_14((checkBooleanVisitorTraversal<int64_t, RowMajor>())); CALL_SUBTEST_14((checkBooleanVisitorTraversal<Eigen::half, ColMajor>())); CALL_SUBTEST_14((checkBooleanVisitorTraversal<std::complex<float>, RowMajor>())); @@ -684,4 +807,15 @@ CALL_SUBTEST_14((checkVisitorShortCircuit<RowMajor, true>())); CALL_SUBTEST_15(checkFindCoeffWithoutPacketCmp<ColMajor>()); CALL_SUBTEST_15(checkFindCoeffWithoutPacketCmp<RowMajor>()); + CALL_SUBTEST_16(checkAnyRaisesNoInvalid<float>()); + CALL_SUBTEST_16(checkAnyRaisesNoInvalid<double>()); + CALL_SUBTEST_16(checkPartialPacketsRaiseNoInvalid<float>()); + CALL_SUBTEST_16(checkPartialPacketsRaiseNoInvalid<double>()); + CALL_SUBTEST_17(checkPartialPackets<float>()); + CALL_SUBTEST_17(checkPartialPackets<double>()); + CALL_SUBTEST_17(checkPartialPackets<int>()); + CALL_SUBTEST_17(checkPartialPackets<int64_t>()); + CALL_SUBTEST_17(checkPartialPackets<Eigen::half>()); + CALL_SUBTEST_17(checkPartialPackets<std::complex<float>>()); + CALL_SUBTEST_17(checkPartialPackets<std::complex<double>>()); }