summaryrefslogtreecommitdiff
path: root/pstl/include
diff options
context:
space:
mode:
authorDvorskiy, Mikhail <mikhail.dvorskiy@intel.com>2020-03-10 19:09:57 +0300
committerDvorskiy, Mikhail <mikhail.dvorskiy@intel.com>2020-05-18 17:00:13 +0300
commit5b0502dff5b6f510fbf823059faa042dd1523cef (patch)
treea1342e83f850955f8debc01bed156ed1e76d26b3 /pstl/include
parent03092f2fa7b4d2609858666f8bba293078582fdd (diff)
downloadllvm-5b0502dff5b6f510fbf823059faa042dd1523cef.tar.gz
[pstl] A fix for move placement-new (and destroy) allocated objects from raw memory.
https://reviews.llvm.org/D74123 The fix affects follow algorithms: remove_if, unique, rotate, inplace_merge, partial_sort_copy, set_union, set_intersection, set_difference, set_symmetric_difference. For "is_trivial" types there are no problems with "creating objects/clean-up" For non-trivial types the algo results are also correct, but possible incorrect copying/moving "operator=" calls "by raw memory" within one of mentioned algo or incorrect destructor calls in the end of algo.
Diffstat (limited to 'pstl/include')
-rw-r--r--pstl/include/pstl/internal/algorithm_impl.h120
-rw-r--r--pstl/include/pstl/internal/memory_impl.h67
-rw-r--r--pstl/include/pstl/internal/parallel_backend_utils.h118
3 files changed, 267 insertions, 38 deletions
diff --git a/pstl/include/pstl/internal/algorithm_impl.h b/pstl/include/pstl/internal/algorithm_impl.h
index 5d09652f7215..01a9405e6130 100644
--- a/pstl/include/pstl/internal/algorithm_impl.h
+++ b/pstl/include/pstl/internal/algorithm_impl.h
@@ -282,10 +282,10 @@ template <class _ExecutionPolicy, class _RandomAccessIterator1, class _Size, cla
class _Function, class _IsVector>
_RandomAccessIterator2
__pattern_walk2_n(_ExecutionPolicy&& __exec, _RandomAccessIterator1 __first1, _Size __n, _RandomAccessIterator2 __first2,
- _Function __f, _IsVector __is_vector, /*parallel=*/std::true_type)
+ _Function __f, _IsVector is_vector, /*parallel=*/std::true_type)
{
return __internal::__pattern_walk2(std::forward<_ExecutionPolicy>(__exec), __first1, __first1 + __n, __first2, __f,
- __is_vector, std::true_type());
+ is_vector, std::true_type());
}
template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _Brick>
@@ -900,6 +900,36 @@ __brick_move(_RandomAccessIterator __first, _RandomAccessIterator __last, _Outpu
[](_RandomAccessIterator __first, _OutputIterator __result) { *__result = std::move(*__first); });
}
+struct __brick_move_destroy
+{
+ template <typename _Iterator, typename _OutputIterator>
+ _OutputIterator
+ operator()(_Iterator __first, _Iterator __last, _OutputIterator __result, /*vec*/ std::true_type) const
+ {
+ using _IteratorValueType = typename std::iterator_traits<_Iterator>::value_type;
+
+ return __unseq_backend::__simd_assign(__first, __last - __first, __result,
+ [](_Iterator __first, _OutputIterator __result) {
+ *__result = std::move(*__first);
+ (*__first).~_IteratorValueType();
+ });
+ }
+
+ template <typename _Iterator, typename _OutputIterator>
+ _OutputIterator
+ operator()(_Iterator __first, _Iterator __last, _OutputIterator __result, /*vec*/ std::false_type) const
+ {
+ using _IteratorValueType = typename std::iterator_traits<_Iterator>::value_type;
+
+ for (; __first != __last; ++__first, ++__result)
+ {
+ *__result = std::move(*__first);
+ (*__first).~_IteratorValueType();
+ }
+ return __result;
+ }
+};
+
//------------------------------------------------------------------------
// swap_ranges
//------------------------------------------------------------------------
@@ -1221,10 +1251,16 @@ __remove_elements(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardI
[&__m](_DifferenceType __total) { __m = __total; });
// 3. Elements from result are moved to [first, last)
- __par_backend::__parallel_for(std::forward<_ExecutionPolicy>(__exec), __result, __result + __m,
- [__result, __first, __is_vector](_Tp* __i, _Tp* __j) {
- __internal::__brick_move(__i, __j, __first + (__i - __result), __is_vector);
- });
+ __par_backend::__parallel_for(
+ std::forward<_ExecutionPolicy>(__exec), __result, __result + __m,
+ [__result, __first, __is_vector](_Tp* __i, _Tp* __j) {
+ __invoke_if_else(
+ std::is_trivial<_Tp>(),
+ [&]() { __brick_move(__i, __j, __first + (__i - __result), __is_vector); },
+ [&]() {
+ __brick_move_destroy()(__i, __j, __first + (__i - __result), __is_vector);
+ });
+ });
return __first + __m;
});
}
@@ -1573,8 +1609,8 @@ __pattern_rotate(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIt
__par_backend::__parallel_for(std::forward<_ExecutionPolicy>(__exec), __result, __result + (__n - __m),
[__first, __result, __is_vector](_Tp* __b, _Tp* __e) {
- __internal::__brick_move(__b, __e, __first + (__b - __result),
- __is_vector);
+ __brick_move_destroy()(
+ __b, __e, __first + (__b - __result), __is_vector);
});
return __first + (__last - __middle);
@@ -1599,7 +1635,7 @@ __pattern_rotate(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIt
__par_backend::__parallel_for(std::forward<_ExecutionPolicy>(__exec), __result, __result + __m,
[__n, __m, __first, __result, __is_vector](_Tp* __b, _Tp* __e) {
- __internal::__brick_move(
+ __brick_move_destroy()(
__b, __e, __first + ((__n - __m) + (__b - __result)), __is_vector);
});
@@ -2222,8 +2258,13 @@ __pattern_partial_sort_copy(_ExecutionPolicy&& __exec, _ForwardIterator __first,
// 3. Move elements from temporary __buffer to output
__par_backend::__parallel_for(std::forward<_ExecutionPolicy>(__exec), __r, __r + __n2,
[__r, __d_first, __is_vector](_T1* __i, _T1* __j) {
- __internal::__brick_move(__i, __j, __d_first + (__i - __r), __is_vector);
+ __brick_move_destroy()(
+ __i, __j, __d_first + (__i - __r), __is_vector);
});
+ __par_backend::__parallel_for(
+ std::forward<_ExecutionPolicy>(__exec), __r + __n2, __r + __n1,
+ [__is_vector](_T1* __i, _T1* __j) { __brick_destroy(__i, __j, __is_vector); });
+
return __d_first + __n2;
}
});
@@ -2673,10 +2714,10 @@ __pattern_inplace_merge(_ExecutionPolicy&& __exec, _BidirectionalIterator __firs
__move_sequences, __move_sequences);
return __f3 + (__l1 - __f1) + (__l2 - __f2);
});
- __par_backend::__parallel_for(std::forward<_ExecutionPolicy>(__exec), __r, __r + __n,
- [__r, __first, __is_vector](_Tp* __i, _Tp* __j) {
- __internal::__brick_move(__i, __j, __first + (__i - __r), __is_vector);
- });
+ __par_backend::__parallel_for(
+ std::forward<_ExecutionPolicy>(__exec), __r, __r + __n, [__r, __first, __is_vector](_Tp* __i, _Tp* __j) {
+ __brick_move_destroy()(__i, __j, __first + (__i - __r), __is_vector);
+ });
});
}
@@ -2781,8 +2822,9 @@ __parallel_set_op(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _Forwar
_DifferenceType __m{};
auto __scan = [=](_DifferenceType, _DifferenceType, const _SetRange& __s) { // Scan
if (!__s.empty())
- __internal::__brick_move(__buffer + __s.__buf_pos, __buffer + (__s.__buf_pos + __s.__len),
- __result + __s.__pos, __is_vector);
+ __brick_move_destroy()(__buffer + __s.__buf_pos,
+ __buffer + (__s.__buf_pos + __s.__len), __result + __s.__pos,
+ __is_vector);
};
__par_backend::__parallel_strict_scan(
std::forward<_ExecutionPolicy>(__exec), __n1, _SetRange{0, 0, 0}, //-1, 0},
@@ -2968,6 +3010,17 @@ __brick_set_union(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _Forwar
return std::set_union(__first1, __last1, __first2, __last2, __result, __comp);
}
+template <typename _IsVector>
+struct __BrickCopyConstruct
+{
+ template <typename _ForwardIterator, typename _OutputIterator>
+ _OutputIterator
+ operator()(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result)
+ {
+ return __brick_uninitialized_copy(__first, __last, __result, _IsVector());
+ }
+};
+
template <class _ForwardIterator1, class _ForwardIterator2, class _OutputIterator, class _Compare>
_OutputIterator
__brick_set_union(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
@@ -3004,12 +3057,14 @@ __pattern_set_union(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _Forw
if (__n1 + __n2 <= __set_algo_cut_off)
return std::set_union(__first1, __last1, __first2, __last2, __result, __comp);
- typedef typename std::iterator_traits<_OutputIterator>::value_type _Tp;
- return __internal::__parallel_set_union_op(
+ typedef typename std::iterator_traits<_OutputIterator>::value_type _T;
+ return __parallel_set_union_op(
std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __last2, __result, __comp,
[](_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2,
- _Tp* __result,
- _Compare __comp) { return std::set_union(__first1, __last1, __first2, __last2, __result, __comp); },
+ _T* __result, _Compare __comp) {
+ return __pstl::__utils::__set_union_construct(__first1, __last1, __first2, __last2, __result, __comp,
+ __BrickCopyConstruct<_IsVector>());
+ },
__is_vector);
}
@@ -3084,7 +3139,8 @@ __pattern_set_intersection(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1
[](_DifferenceType __n, _DifferenceType __m) { return std::min(__n, __m); },
[](_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
_ForwardIterator2 __last2, _Tp* __result, _Compare __comp) {
- return std::set_intersection(__first1, __last1, __first2, __last2, __result, __comp);
+ return __pstl::__utils::__set_intersection_construct(__first1, __last1, __first2, __last2, __result,
+ __comp);
},
__is_vector);
}
@@ -3098,7 +3154,8 @@ __pattern_set_intersection(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1
[](_DifferenceType __n, _DifferenceType __m) { return std::min(__n, __m); },
[](_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
_ForwardIterator2 __last2, _Tp* __result, _Compare __comp) {
- return std::set_intersection(__first2, __last2, __first1, __last1, __result, __comp);
+ return __pstl::__utils::__set_intersection_construct(__first2, __last2, __first1, __last1, __result,
+ __comp);
},
__is_vector);
return __result;
@@ -3190,13 +3247,15 @@ __pattern_set_difference(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1,
std::true_type());
if (__n1 + __n2 > __set_algo_cut_off)
- return __internal::__parallel_set_op(
- std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __last2, __result, __comp,
- [](_DifferenceType __n, _DifferenceType) { return __n; },
- [](_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
- _ForwardIterator2 __last2, _Tp* __result,
- _Compare __comp) { return std::set_difference(__first1, __last1, __first2, __last2, __result, __comp); },
- __is_vector);
+ return __parallel_set_op(std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __last2, __result,
+ __comp, [](_DifferenceType __n, _DifferenceType __m) { return __n; },
+ [](_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
+ _ForwardIterator2 __last2, _Tp* __result, _Compare __comp) {
+ return __pstl::__utils::__set_difference_construct(
+ __first1, __last1, __first2, __last2, __result, __comp,
+ __BrickCopyConstruct<_IsVector>());
+ },
+ __is_vector);
// use serial algorithm
return std::set_difference(__first1, __last1, __first2, __last2, __result, __comp);
@@ -3256,7 +3315,8 @@ __pattern_set_symmetric_difference(_ExecutionPolicy&& __exec, _ForwardIterator1
std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __last2, __result, __comp,
[](_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2,
_Tp* __result, _Compare __comp) {
- return std::set_symmetric_difference(__first1, __last1, __first2, __last2, __result, __comp);
+ return __pstl::__utils::__set_symmetric_difference_construct(__first1, __last1, __first2, __last2, __result,
+ __comp, __BrickCopyConstruct<_IsVector>());
},
__is_vector);
}
diff --git a/pstl/include/pstl/internal/memory_impl.h b/pstl/include/pstl/internal/memory_impl.h
index 241f00a1033f..1eb2fe4e267b 100644
--- a/pstl/include/pstl/internal/memory_impl.h
+++ b/pstl/include/pstl/internal/memory_impl.h
@@ -26,31 +26,82 @@ namespace __internal
// uninitialized_move
//------------------------------------------------------------------------
-template <class _ForwardIterator, class _OutputIterator>
+template <typename _ForwardIterator, typename _OutputIterator>
_OutputIterator
__brick_uninitialized_move(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result,
/*vector=*/std::false_type) noexcept
{
- typedef typename std::iterator_traits<_OutputIterator>::value_type _ValueType2;
+ using _ValueType = typename std::iterator_traits<_OutputIterator>::value_type;
for (; __first != __last; ++__first, ++__result)
{
- ::new (std::addressof(*__result)) _ValueType2(std::move(*__first));
+ ::new (std::addressof(*__result)) _ValueType(std::move(*__first));
}
return __result;
}
-template <class _ForwardIterator, class _OutputIterator>
+template <typename _ForwardIterator, typename _OutputIterator>
_OutputIterator
__brick_uninitialized_move(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result,
/*vector=*/std::true_type) noexcept
{
- typedef typename std::iterator_traits<_OutputIterator>::value_type __ValueType2;
- typedef typename std::iterator_traits<_ForwardIterator>::reference _ReferenceType1;
- typedef typename std::iterator_traits<_OutputIterator>::reference _ReferenceType2;
+ using __ValueType = typename std::iterator_traits<_OutputIterator>::value_type;
+ using _ReferenceType1 = typename std::iterator_traits<_ForwardIterator>::reference;
+ using _ReferenceType2 = typename std::iterator_traits<_OutputIterator>::reference;
return __unseq_backend::__simd_walk_2(
__first, __last - __first, __result,
- [](_ReferenceType1 __x, _ReferenceType2 __y) { ::new (std::addressof(__y)) __ValueType2(std::move(__x)); });
+ [](_ReferenceType1 __x, _ReferenceType2 __y) { ::new (std::addressof(__y)) __ValueType(std::move(__x)); });
+}
+
+template <typename _Iterator>
+void
+__brick_destroy(_Iterator __first, _Iterator __last, /*vector*/ std::false_type) noexcept
+{
+ using _ValueType = typename std::iterator_traits<_Iterator>::value_type;
+
+ for (; __first != __last; ++__first)
+ __first->~_ValueType();
+}
+
+template <typename _Iterator>
+void
+__brick_destroy(_Iterator __first, _Iterator __last, /*vector*/ std::true_type) noexcept
+{
+ using _ValueType = typename std::iterator_traits<_Iterator>::value_type;
+ using _ReferenceType = typename std::iterator_traits<_Iterator>::reference;
+
+ __unseq_backend::__simd_walk_1(__first, __last - __first, [](_ReferenceType __x) { __x.~_ValueType(); });
+}
+
+//------------------------------------------------------------------------
+// uninitialized copy
+//------------------------------------------------------------------------
+
+template <typename _ForwardIterator, typename _OutputIterator>
+_OutputIterator
+__brick_uninitialized_copy(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result,
+ /*vector=*/std::false_type) noexcept
+{
+ using _ValueType = typename std::iterator_traits<_OutputIterator>::value_type;
+ for (; __first != __last; ++__first, ++__result)
+ {
+ ::new (std::addressof(*__result)) _ValueType(*__first);
+ }
+ return __result;
+}
+
+template <typename _ForwardIterator, typename _OutputIterator>
+_OutputIterator
+__brick_uninitialized_copy(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result,
+ /*vector=*/std::true_type) noexcept
+{
+ using __ValueType = typename std::iterator_traits<_OutputIterator>::value_type;
+ using _ReferenceType1 = typename std::iterator_traits<_ForwardIterator>::reference;
+ using _ReferenceType2 = typename std::iterator_traits<_OutputIterator>::reference;
+
+ return __unseq_backend::__simd_walk_2(
+ __first, __last - __first, __result,
+ [](_ReferenceType1 __x, _ReferenceType2 __y) { ::new (std::addressof(__y)) __ValueType(__x); });
}
} // namespace __internal
diff --git a/pstl/include/pstl/internal/parallel_backend_utils.h b/pstl/include/pstl/internal/parallel_backend_utils.h
index 5728b48b1cf7..448f924806dc 100644
--- a/pstl/include/pstl/internal/parallel_backend_utils.h
+++ b/pstl/include/pstl/internal/parallel_backend_utils.h
@@ -138,6 +138,124 @@ struct __serial_move_merge
}
};
+template <typename _ForwardIterator1, typename _ForwardIterator2, typename _OutputIterator, typename _Compare,
+ typename _CopyConstructRange>
+_OutputIterator
+__set_union_construct(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
+ _ForwardIterator2 __last2, _OutputIterator __result, _Compare __comp,
+ _CopyConstructRange __cc_range)
+{
+ using _Tp = typename std::iterator_traits<_OutputIterator>::value_type;
+
+ for (; __first1 != __last1; ++__result)
+ {
+ if (__first2 == __last2)
+ return __cc_range(__first1, __last1, __result);
+ if (__comp(*__first2, *__first1))
+ {
+ ::new (std::addressof(*__result)) _Tp(*__first2);
+ ++__first2;
+ }
+ else
+ {
+ ::new (std::addressof(*__result)) _Tp(*__first1);
+ if (!__comp(*__first1, *__first2))
+ ++__first2;
+ ++__first1;
+ }
+ }
+ return __cc_range(__first2, __last2, __result);
+}
+
+template <typename _ForwardIterator1, typename _ForwardIterator2, typename _OutputIterator, typename _Compare>
+_OutputIterator
+__set_intersection_construct(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
+ _ForwardIterator2 __last2, _OutputIterator __result, _Compare __comp)
+{
+ using _Tp = typename std::iterator_traits<_OutputIterator>::value_type;
+
+ for (; __first1 != __last1 && __first2 != __last2;)
+ {
+ if (__comp(*__first1, *__first2))
+ ++__first1;
+ else
+ {
+ if (!__comp(*__first2, *__first1))
+ {
+ ::new (std::addressof(*__result)) _Tp(*__first1);
+ ++__result;
+ ++__first1;
+ }
+ ++__first2;
+ }
+ }
+ return __result;
+}
+
+template <typename _ForwardIterator1, typename _ForwardIterator2, typename _OutputIterator, typename _Compare,
+ typename _CopyConstructRange>
+_OutputIterator
+__set_difference_construct(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
+ _ForwardIterator2 __last2, _OutputIterator __result, _Compare __comp,
+ _CopyConstructRange __cc_range)
+{
+ using _Tp = typename std::iterator_traits<_OutputIterator>::value_type;
+
+ for (; __first1 != __last1;)
+ {
+ if (__first2 == __last2)
+ return __cc_range(__first1, __last1, __result);
+
+ if (__comp(*__first1, *__first2))
+ {
+ ::new (std::addressof(*__result)) _Tp(*__first1);
+ ++__result;
+ ++__first1;
+ }
+ else
+ {
+ if (!__comp(*__first2, *__first1))
+ ++__first1;
+ ++__first2;
+ }
+ }
+ return __result;
+}
+template <typename _ForwardIterator1, typename _ForwardIterator2, typename _OutputIterator, typename _Compare,
+ typename _CopyConstructRange>
+_OutputIterator
+__set_symmetric_difference_construct(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
+ _ForwardIterator2 __last2, _OutputIterator __result, _Compare __comp,
+ _CopyConstructRange __cc_range)
+{
+ using _Tp = typename std::iterator_traits<_OutputIterator>::value_type;
+
+ for (; __first1 != __last1;)
+ {
+ if (__first2 == __last2)
+ return __cc_range(__first1, __last1, __result);
+
+ if (__comp(*__first1, *__first2))
+ {
+ ::new (std::addressof(*__result)) _Tp(*__first1);
+ ++__result;
+ ++__first1;
+ }
+ else
+ {
+ if (__comp(*__first2, *__first1))
+ {
+ ::new (std::addressof(*__result)) _Tp(*__first2);
+ ++__result;
+ }
+ else
+ ++__first1;
+ ++__first2;
+ }
+ }
+ return __cc_range(__first2, __last2, __result);
+}
+
} // namespace __utils
} // namespace __pstl