This is an archive of the discontinued LLVM Phabricator instance.

[libc++][PSTL] Overhaul exceptions handling
ClosedPublic

Authored by philnik on Jun 30 2023, 10:18 AM.

Details

Reviewers
ldionne
Group Reviewers
Restricted Project
Commits
rGaade74675c15: [libc++][PSTL] Overhaul exceptions handling
Summary

This makes exception handling a lot simpler, since we don't have to convert any exceptions this way. Is also properly handles all the user-thrown exceptions.

Diff Detail

Event Timeline

philnik created this revision.Jun 30 2023, 10:18 AM
Herald added a project: Restricted Project. · View Herald TranscriptJun 30 2023, 10:18 AM
philnik requested review of this revision.Jun 30 2023, 10:18 AM
Herald added a project: Restricted Project. · View Herald TranscriptJun 30 2023, 10:18 AM
Herald added a reviewer: Restricted Project. · View Herald Transcript
ldionne requested changes to this revision.Jul 3 2023, 10:08 AM
ldionne added inline comments.
libcxx/include/__algorithm/pstl_backends/cpu_backends/any_of.h
65

We should document how backends are expected to handle exceptions in libcxx/include/__algorithm/pstl_backend.h and in libcxx/include/__algorithm/pstl_backends/cpu_backend.h.

libcxx/include/__algorithm/pstl_backends/cpu_backends/find_if.h
95

Notes from our 1:1 session:

// Option 1:
// Pros:
// - CPU sub-backends don't have to handle user exceptions in any special way. They only have to care
//   about any exception that might be thrown in their own setup code (aka std::bad_alloc).
// - Handling of excetpions at the `__pstl_foo` level is uniform across all algorithms.
// - We can write all code inside the PSTL with the mindset that exceptions are disabled,
//   i.e. we never throw and we use appropriate types to report errors instead. This might be
//   a nice systematic approach?
// Cons:
// - Requires introducing a custom std::expected-like type for internal use.
// - Hardcodes the fact that we can only throw `std::bad_alloc` from backends.
// - We can't elide the move construction of the return value out of `__pstl_find_if`.
template <class _ExecutionPolicy, class _ForwardIterator, class _Predicate>
_LIBCPP_HIDE_FROM_ABI _ForwardIterator
__pstl_find_if(__cpu_backend_tag, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) {
  auto __maybe_result = std::__terminate_on_exception([&] -> __funky_expected<_ForwardIterator, std::bad_alloc> {
    if constexpr (__is_parallel_execution_policy_v<_ExecutionPolicy> &&
                  __has_random_access_iterator_category<_ForwardIterator>::value) {
      return std::__parallel_find(
          __first,
          __last,
          [&__pred](_ForwardIterator __brick_first, _ForwardIterator __brick_last) {
            return std::__pstl_find_if<__remove_parallel_policy_t<_ExecutionPolicy>>(
                __cpu_backend_tag{}, __brick_first, __brick_last, __pred);
          },
          less<>{},
          true);
    } else if constexpr (__is_unsequenced_execution_policy_v<_ExecutionPolicy> &&
                        __has_random_access_iterator_category<_ForwardIterator>::value) {
      using __diff_t = __iter_diff_t<_ForwardIterator>;
      return std::__simd_first(__first, __diff_t(0), __last - __first, [&__pred](_ForwardIterator __iter, __diff_t __i) {
        return __pred(__iter[__i]);
      });
    } else {
      return std::find_if(__first, __last, __pred);
    }
  });
  return *std::move(__maybe_result).or_else([](auto&& __exception) -> __funky_expected<_ForwardIterator, void> { std::__throw_bad_alloc(); });
}

// Option 2:
// Pros:
// - Each layer fully handles all of its exceptions independently. That can be simpler or more complicated depending
//   on how you look at it.
// Cons:
// - When you're writing a CPU backend, you need to explicitly handle user-thrown exceptions and carve out the
//   setup-thrown exceptions from the `terminate_on_exception` code paths.
template <class _ExecutionPolicy, class _ForwardIterator, class _Predicate>
_LIBCPP_HIDE_FROM_ABI _ForwardIterator
__pstl_find_if(__cpu_backend_tag, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) {
  if constexpr (__is_parallel_execution_policy_v<_ExecutionPolicy> &&
                __has_random_access_iterator_category<_ForwardIterator>::value) {
    return std::__parallel_find( // we would document that CPU sub-backends need to handle exceptions appropriately
        __first,
        __last,
        [&__pred](_ForwardIterator __brick_first, _ForwardIterator __brick_last) {
          return std::__pstl_find_if<__remove_parallel_policy_t<_ExecutionPolicy>>(
              __cpu_backend_tag{}, __brick_first, __brick_last, __pred);
        },
        less<>{},
        true);
  } else if constexpr (__is_unsequenced_execution_policy_v<_ExecutionPolicy> &&
                      __has_random_access_iterator_category<_ForwardIterator>::value) {
    using __diff_t = __iter_diff_t<_ForwardIterator>;
    return std::__terminate_on_exception([&] {
      return std::__simd_first(__first, __diff_t(0), __last - __first, [&__pred](_ForwardIterator __iter, __diff_t __i) {
        return __pred(__iter[__i]);
      });
    });
  } else {
    return std::__terminate_on_exception([&] {
      return std::find_if(__first, __last, __pred);
    });
  }
}

At the end, we both agreed that option 2 is the way to go for now, largely because implementing an expected-like type in C++17 drives the cost of option 1 up a lot.

114–116

If an exception is thrown in here, we would also need to terminate. This needs to be fixed + a test.

118

If an exception is thrown in here, we should also terminate even though this is actually running serial. This needs fix + tests.

This revision now requires changes to proceed.Jul 3 2023, 10:08 AM
philnik updated this revision to Diff 537895.Jul 6 2023, 3:00 PM
philnik marked 4 inline comments as done.

Address comments

ldionne added inline comments.Aug 7 2023, 10:00 AM
libcxx/include/__algorithm/pstl_backend.h
166–167

And also below.

libcxx/include/__algorithm/pstl_backends/cpu_backend.h
52
libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/pstl.fill.pass.cpp
27

This include is not necessary.

libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/pstl.fill.terminate.pass.cpp
31

Can we also test iterators that throw when some operation (e.g. increment) is applied to them? I think this might catch issues in backends when they e.g. compute the size of the range. For this algorithms but others as well.

Or throwing on copy of the iterator.

Actually, this raises the question of how to handle throwing iterators at all. I think this approach doesn't work, since an iterator could technically throw even in one of the frontend functions. It's possible that the only approach that will work is to actually make the top-level function noexcept (but still throw std::bad_alloc in a few cases).

philnik updated this revision to Diff 548302.Aug 8 2023, 11:48 AM

Use an expected type

ldionne added inline comments.Aug 8 2023, 2:59 PM
libcxx/include/__algorithm/pstl_backends/cpu_backends/libdispatch.h
103

noexcept?

141–142

We don't need __terminate_on_exception anymore here.

libcxx/include/__algorithm/pstl_backends/cpu_backends/merge.h
40

noexcept?

libcxx/include/__algorithm/pstl_backends/pstl_expected.h
1 ↗(On Diff #548302)

As discussed, let's go for std::optional. It handles triviality properly and it resolves a lot of complexity that we run into if we try to do expected.

libcxx/include/__algorithm/pstl_merge.h
76–79

We need a test that we behave properly if the iterators throw when they are moved here.

Also note that it would be possible to pass by rvalue ref into __pstl_merge and drop __terminate_on_exception altogether here (and in fact I don't think we'd need it anywhere anymore, which would be great). But I'm neutral on that, what I care about most is to add tests for this.

libcxx/include/__numeric/pstl_transform_reduce.h
78–82

Same thing for moving iterators applies here.

88

This could be:

*std::__terminate_on_exception(...).or_else([]{ std::__throw_bad_alloc(); });

We only need to use some pre-C++23 or_else version.

philnik updated this revision to Diff 548422.Aug 8 2023, 5:57 PM
philnik marked an inline comment as done.

Address comments

ldionne requested changes to this revision.Aug 9 2023, 9:27 AM
ldionne added inline comments.
libcxx/include/__algorithm/pstl_backend.h
80

These should be updated for optional<foo>

167

a disengaged optional. Same below.

ldionne added inline comments.Aug 9 2023, 9:27 AM
libcxx/include/__algorithm/pstl_backends/cpu_backend.h
52

Actually, I think we want to say:

CPU backends are expected to report errors (i.e. failure to allocate) by returning a disengaged `optional` from their implementation. Exceptions shouldn't be used to report an internal failure-to-allocate, since all exceptions are turned into a program termination at the front-end level. When a backend returns a disengaged `optional` to the frontend, the frontend will turn that into a call to `std::__throw_bad_alloc();` to report the internal failure to the user.
libcxx/include/__algorithm/pstl_backends/cpu_backends/find_if.h
104

Let's add an internal assertion here to document why __pstl_find_if will never return nullopt (the reason is that unseq isn't allowed to allocate, assuming that's true).

If that's not true, then this is a bug.

libcxx/include/__algorithm/pstl_backends/cpu_backends/libdispatch.h
66

Per our discussion just now, we should actually remove noexcept here!

libcxx/include/__algorithm/pstl_backends/cpu_backends/transform_reduce.h
165

Same, internal assertion.

libcxx/include/__algorithm/pstl_for_each.h
64–65

As discussed, it looks like we actually need to do this (otherwise we'd terminate in case std::for_each(policy, ...) throws bad_alloc):

template <class _ExecutionPolicy,
          class _ForwardIterator,
          class _Size,
          class _Function,
          class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
          enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
_LIBCPP_HIDE_FROM_ABI void
__for_each_n(_ExecutionPolicy&& __policy, _ForwardIterator __first, _Size __size, _Function __func) noexcept {
  _LIBCPP_REQUIRE_CPP17_FORWARD_ITERATOR(_ForwardIterator);
  return std::__pstl_frontend_dispatch(
      _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_for_each_n),
      [&](_ForwardIterator __g_first, _Size __g_size, _Function __g_func) -> optional<__empty> {
        if constexpr (__has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
          std::for_each(__policy, std::move(__g_first), __g_first + __g_size, std::move(__g_func));
          return __empty{};
        } else {
          std::for_each_n(std::move(__g_first), __g_size, std::move(__g_func));
          return __empty{};
        }
      },
      __first,
      __size,
      std::move(__func));
}

template <class _ExecutionPolicy,
          class _ForwardIterator,
          class _Size,
          class _Function,
          class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
          enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
_LIBCPP_HIDE_FROM_ABI void
for_each_n(_ExecutionPolicy&& __policy, _ForwardIterator __first, _Size __size, _Function __func) {
  auto __res = std::__for_each_n(...);
  if (!__res)
    std::__throw_bad_alloc();
}

And then we should use the noexcept version from fallback implementations.

libcxx/include/__utility/terminate_on_exception.h
0

I think this is just not needed at all anymore.

This revision now requires changes to proceed.Aug 9 2023, 9:27 AM
philnik updated this revision to Diff 548774.Aug 9 2023, 2:41 PM
philnik marked 16 inline comments as done.

Address comments

ldionne added inline comments.Aug 10 2023, 8:58 AM
libcxx/include/__algorithm/pstl_any_all_none_of.h
14

Missing <optional> include. Please make a pass throughout.

libcxx/include/__algorithm/pstl_backends/cpu_backends/any_of.h
21

<__utility/move.h>

libcxx/include/__algorithm/pstl_backends/cpu_backends/find_if.h
33

This seems like a leftover, we decided to only mark the top-level __find algo noexcept.

libcxx/include/__algorithm/pstl_backends/cpu_backends/thread.h
38

noexcept leftover

libcxx/include/__algorithm/pstl_backends/cpu_backends/transform.h
44

noexcept leftover

91

noexcept leftover

libcxx/include/__algorithm/pstl_is_partitioned.h
60

In another patch, can you please make a pass to make sure you're not missing _LLIBCPP_REQUIRE_CPP17_FOO from any of them?

libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/pstl.fill.terminate.pass.cpp
1

Let's name this test pstl.exception_handling.pass.cpp since this isn't only specific to std::fill. WDYT?

13

You can adjust all the comments

13

Also you should mention that you're testing std::fill_n here (this applies to all these tests).

40

everywhere

43

Please add a comment like // test std::fill_n to separate each algorithm you're testing. This is kinda dumb here cause there's 2, but when there's more it's useful to have a visual marker

libcxx/test/std/algorithms/alg.nonmodifying/alg.foreach/pstl.for_each.terminate.pass.cpp
1

I think you need to UNSUPPORT these tests when -fno-exceptions

philnik updated this revision to Diff 549081.Aug 10 2023, 9:38 AM
philnik marked 13 inline comments as done.

Address comments

ldionne accepted this revision.Aug 10 2023, 10:10 AM

LGTM, thanks!

This revision is now accepted and ready to land.Aug 10 2023, 10:10 AM
philnik updated this revision to Diff 549993.Aug 14 2023, 9:35 AM

Try to fix CI

philnik updated this revision to Diff 550018.Aug 14 2023, 10:27 AM

Try to fix CI

philnik updated this revision to Diff 550132.Aug 14 2023, 4:38 PM

Try to fix CI

philnik updated this revision to Diff 550429.Aug 15 2023, 12:23 PM

Fix formatting

philnik retitled this revision from [libc++][PSTL] Move exception handling to the CPU backends to [libc++][PSTL] Overhaul exceptions handling.Aug 15 2023, 2:53 PM
philnik edited the summary of this revision. (Show Details)
philnik updated this revision to Diff 550833.Aug 16 2023, 11:55 AM

Try to fix CI

philnik updated this revision to Diff 555638.Sep 3 2023, 3:33 PM

Try to fix CI

philnik updated this revision to Diff 556472.Sep 11 2023, 11:59 AM

Try to fix CI

philnik updated this revision to Diff 556491.Sep 11 2023, 3:18 PM

Try to fix CI

philnik updated this revision to Diff 556725.Sep 13 2023, 3:18 PM

Try to fix CI

philnik updated this revision to Diff 556928.Sep 18 2023, 12:11 AM

Try to fix CI

philnik updated this revision to Diff 556953.Sep 18 2023, 8:37 AM

Try to fix CI

philnik updated this revision to Diff 556993.Sep 18 2023, 8:46 PM

Try to fix CI

philnik updated this revision to Diff 557002.Sep 18 2023, 11:04 PM

Try to fix CTry to fix CII

philnik updated this revision to Diff 557515.Oct 1 2023, 2:51 AM

Try to fix CI

philnik updated this revision to Diff 557516.Oct 1 2023, 4:11 AM

Try to fix CI

philnik updated this revision to Diff 557518.Oct 1 2023, 5:58 AM

Try to fix CI

philnik updated this revision to Diff 557521.Oct 1 2023, 7:05 AM

Try to fix CI

philnik updated this revision to Diff 557552.Oct 3 2023, 2:19 AM

Try to fix CI

philnik updated this revision to Diff 557553.Oct 3 2023, 3:51 AM

Try to fix CI

philnik updated this revision to Diff 557624.Oct 6 2023, 2:27 AM
  • Rebased
  • Run the full pipeline
philnik updated this revision to Diff 557627.Oct 6 2023, 2:50 AM

Try to fix CI

This revision was automatically updated to reflect the committed changes.