1 // -*- C++ -*- 2 //===-- scan.pass.cpp -----------------------------------------------------===// 3 // 4 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 5 // See https://llvm.org/LICENSE.txt for license information. 6 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 7 // 8 //===----------------------------------------------------------------------===// 9 10 #include "support/pstl_test_config.h" 11 12 #include <execution> 13 #include <numeric> 14 15 #include "support/utils.h" 16 17 using namespace TestUtils; 18 19 // We provide the no execution policy versions of the exclusive_scan and inclusive_scan due checking correctness result of the versions with execution policies. 20 //TODO: to add a macro for availability of ver implementations 21 template <class InputIterator, class OutputIterator, class T> 22 OutputIterator 23 exclusive_scan_serial(InputIterator first, InputIterator last, OutputIterator result, T init) 24 { 25 for (; first != last; ++first, ++result) 26 { 27 *result = init; 28 init = init + *first; 29 } 30 return result; 31 } 32 33 template <class InputIterator, class OutputIterator, class T, class BinaryOperation> 34 OutputIterator 35 exclusive_scan_serial(InputIterator first, InputIterator last, OutputIterator result, T init, BinaryOperation binary_op) 36 { 37 for (; first != last; ++first, ++result) 38 { 39 *result = init; 40 init = binary_op(init, *first); 41 } 42 return result; 43 } 44 45 // Note: N4582 is missing the ", class T". Issue was reported 2016-Apr-11 to [email protected] 46 template <class InputIterator, class OutputIterator, class BinaryOperation, class T> 47 OutputIterator 48 inclusive_scan_serial(InputIterator first, InputIterator last, OutputIterator result, BinaryOperation binary_op, T init) 49 { 50 for (; first != last; ++first, ++result) 51 { 52 init = binary_op(init, *first); 53 *result = init; 54 } 55 return result; 56 } 57 58 template <class InputIterator, class OutputIterator, class BinaryOperation> 59 OutputIterator 60 inclusive_scan_serial(InputIterator first, InputIterator last, OutputIterator result, BinaryOperation binary_op) 61 { 62 if (first != last) 63 { 64 auto tmp = *first; 65 *result = tmp; 66 return inclusive_scan_serial(++first, last, ++result, binary_op, tmp); 67 } 68 else 69 { 70 return result; 71 } 72 } 73 74 template <class InputIterator, class OutputIterator> 75 OutputIterator 76 inclusive_scan_serial(InputIterator first, InputIterator last, OutputIterator result) 77 { 78 typedef typename std::iterator_traits<InputIterator>::value_type input_type; 79 return inclusive_scan_serial(first, last, result, std::plus<input_type>()); 80 } 81 82 // Most of the framework required for testing inclusive and exclusive scan is identical, 83 // so the tests for both are in this file. Which is being tested is controlled by the global 84 // flag inclusive, which is set to each alternative by main(). 85 static bool inclusive; 86 87 template <typename Iterator, typename Size, typename T> 88 void 89 check_and_reset(Iterator expected_first, Iterator out_first, Size n, T trash) 90 { 91 EXPECT_EQ_N(expected_first, out_first, n, 92 inclusive ? "wrong result from inclusive_scan" : "wrong result from exclusive_scan"); 93 std::fill_n(out_first, n, trash); 94 } 95 96 struct test_scan_with_plus 97 { 98 template <typename Policy, typename Iterator1, typename Iterator2, typename Iterator3, typename Size, typename T> 99 void 100 operator()(Policy&& exec, Iterator1 in_first, Iterator1 in_last, Iterator2 out_first, Iterator2 out_last, 101 Iterator3 expected_first, Iterator3 expected_last, Size n, T init, T trash) 102 { 103 using namespace std; 104 105 auto orr1 = inclusive ? inclusive_scan_serial(in_first, in_last, expected_first) 106 : exclusive_scan_serial(in_first, in_last, expected_first, init); 107 auto orr = inclusive ? inclusive_scan(exec, in_first, in_last, out_first) 108 : exclusive_scan(exec, in_first, in_last, out_first, init); 109 EXPECT_TRUE(out_last == orr, 110 inclusive ? "inclusive_scan returned wrong iterator" : "exclusive_scan returned wrong iterator"); 111 112 check_and_reset(expected_first, out_first, n, trash); 113 fill(out_first, out_last, trash); 114 } 115 }; 116 117 template <typename T, typename Convert> 118 void 119 test_with_plus(T init, T trash, Convert convert) 120 { 121 for (size_t n = 0; n <= 100000; n = n <= 16 ? n + 1 : size_t(3.1415 * n)) 122 { 123 Sequence<T> in(n, convert); 124 Sequence<T> expected(in); 125 Sequence<T> out(n, [&](int32_t) { return trash; }); 126 127 invoke_on_all_policies(test_scan_with_plus(), in.begin(), in.end(), out.begin(), out.end(), expected.begin(), 128 expected.end(), in.size(), init, trash); 129 invoke_on_all_policies(test_scan_with_plus(), in.cbegin(), in.cend(), out.begin(), out.end(), expected.begin(), 130 expected.end(), in.size(), init, trash); 131 } 132 } 133 struct test_scan_with_binary_op 134 { 135 template <typename Policy, typename Iterator1, typename Iterator2, typename Iterator3, typename Size, typename T, 136 typename BinaryOp> 137 typename std::enable_if<!TestUtils::isReverse<Iterator1>::value, void>::type 138 operator()(Policy&& exec, Iterator1 in_first, Iterator1 in_last, Iterator2 out_first, Iterator2 out_last, 139 Iterator3 expected_first, Iterator3 expected_last, Size n, T init, BinaryOp binary_op, T trash) 140 { 141 using namespace std; 142 143 auto orr1 = inclusive ? inclusive_scan_serial(in_first, in_last, expected_first, binary_op, init) 144 : exclusive_scan_serial(in_first, in_last, expected_first, init, binary_op); 145 auto orr = inclusive ? inclusive_scan(exec, in_first, in_last, out_first, binary_op, init) 146 : exclusive_scan(exec, in_first, in_last, out_first, init, binary_op); 147 148 EXPECT_TRUE(out_last == orr, "scan returned wrong iterator"); 149 check_and_reset(expected_first, out_first, n, trash); 150 } 151 152 template <typename Policy, typename Iterator1, typename Iterator2, typename Iterator3, typename Size, typename T, 153 typename BinaryOp> 154 typename std::enable_if<TestUtils::isReverse<Iterator1>::value, void>::type 155 operator()(Policy&& exec, Iterator1 in_first, Iterator1 in_last, Iterator2 out_first, Iterator2 out_last, 156 Iterator3 expected_first, Iterator3 expected_last, Size n, T init, BinaryOp binary_op, T trash) 157 { 158 } 159 }; 160 161 template <typename In, typename Out, typename BinaryOp> 162 void 163 test_matrix(Out init, BinaryOp binary_op, Out trash) 164 { 165 for (size_t n = 0; n <= 100000; n = n <= 16 ? n + 1 : size_t(3.1415 * n)) 166 { 167 Sequence<In> in(n, [](size_t k) { return In(k, k + 1); }); 168 169 Sequence<Out> out(n, [&](size_t) { return trash; }); 170 Sequence<Out> expected(n, [&](size_t) { return trash; }); 171 172 invoke_on_all_policies(test_scan_with_binary_op(), in.begin(), in.end(), out.begin(), out.end(), 173 expected.begin(), expected.end(), in.size(), init, binary_op, trash); 174 invoke_on_all_policies(test_scan_with_binary_op(), in.cbegin(), in.cend(), out.begin(), out.end(), 175 expected.begin(), expected.end(), in.size(), init, binary_op, trash); 176 } 177 } 178 179 int32_t 180 main() 181 { 182 for (int32_t mode = 0; mode < 2; ++mode) 183 { 184 inclusive = mode != 0; 185 #if !_PSTL_ICC_19_TEST_SIMD_UDS_WINDOWS_RELEASE_BROKEN 186 // Test with highly restricted type and associative but not commutative operation 187 test_matrix<Matrix2x2<int32_t>, Matrix2x2<int32_t>>(Matrix2x2<int32_t>(), multiply_matrix<int32_t>, 188 Matrix2x2<int32_t>(-666, 666)); 189 #endif 190 191 // Since the implict "+" forms of the scan delegate to the generic forms, 192 // there's little point in using a highly restricted type, so just use double. 193 test_with_plus<float64_t>(inclusive ? 0.0 : -1.0, -666.0, 194 [](uint32_t k) { return float64_t((k % 991 + 1) ^ (k % 997 + 2)); }); 195 } 196 std::cout << done() << std::endl; 197 return 0; 198 } 199