This is an archive of the discontinued LLVM Phabricator instance.

Make rotate a constexpr
ClosedPublic

Authored by zoecarver on Aug 4 2019, 10:27 AM.

Details

Summary

This patch makes std::rotate a constexpr. This way it can be used in other constexpr functions such as shift_left and shift_right.

Diff Detail

Event Timeline

zoecarver created this revision.Aug 4 2019, 10:27 AM
ldionne requested changes to this revision.Aug 5 2019, 9:27 AM
ldionne added inline comments.
libcxx/include/algorithm
2308

This function can be made constexpr in all standard modes that support generalized constexpr (so C++14 and above).

That holds for all helper functions below.

2367

Ditto.

2381

Ditto.

libcxx/test/std/algorithms/alg.modifying.operations/alg.rotate/rotate.pass.cpp
425

Typo: test_constexpr

458

It would be nice if we could run all the same tests for constexpr and non-constexpr. It's not clear to me why we can't just run test<....> in a constexpr context. As for test1, it allocates memory but it might be possible to change the test to avoid that?

Generally speaking, I'd like for us to develop a fairly mechanical way of testing things in a constexpr context, since we're going to have to do that for almost all of <algorithm>. I think it's important to have the same test coverage for constexpr and non-constexpr (whenever it makes sense, of course).

This revision now requires changes to proceed.Aug 5 2019, 9:27 AM
zoecarver marked 2 inline comments as done.Aug 5 2019, 7:47 PM
zoecarver added inline comments.
libcxx/include/algorithm
2308

Was std::rotate updated as a paper or an issue? Or have we decided to extend constexpr support back to C++14 independent of the standard?

libcxx/test/std/algorithms/alg.modifying.operations/alg.rotate/rotate.pass.cpp
458

I agree. What if we decided that we test constexpr by adding return true to the end of the test function and modifying the function to be a constexpr that returns a bool. This should work for almost all <algorithm> tests.

rotate and a bunch of other algorithms were made constexpr in P0202, adopted in ABQ.

We've done some of them already; we should do the rest.

mclow.lists added inline comments.Aug 6 2019, 9:57 AM
libcxx/include/algorithm
2308

We don't have the freedom to add constexpr to things in the standard.
We do have the freedom to add noexcept.

Odd, but that's the world we've got.

ldionne added inline comments.Aug 6 2019, 11:32 AM
libcxx/include/algorithm
2308

My comment was only about helper functions. Make the helper functions constexpr whenever possible, but only mark the actual algorithm std::rotate constexpr when the Standard says so.

libcxx/test/std/algorithms/alg.modifying.operations/alg.rotate/rotate.pass.cpp
458

Yes, something along those lines is what I was thinking about. Can you see if that works?

rotate and a bunch of other algorithms were made constexpr in P0202, adopted in ABQ.

We've done some of them already; we should do the rest.

That paper says:

Note for editor: All the functions in [algorithms.general] must be marked with constexpr, except functions shuffle, sample, stable_sort, stable_partition, inplace_merge, functions accepting ExecutionPolicy and algorithms that have ValueSwappable requirement(20.5.3.2):

std::rotate is not one of the updated functions in that paper. It is updated in the standard, though.

We have only done a very few of them. I am starting to make my way through the list. There are several papers which update various algorithms IIRC.

  • update constexpr tests (now they have full test coverage in a constexpr context)
  • add constexpr to internal functions
  • upgrade move functions to be constexpr
zoecarver marked 4 inline comments as done.Aug 12 2019, 11:11 AM
zoecarver added inline comments.
libcxx/include/algorithm
1854

I am concerned we are losing performance for those who do not have is_constant_evaluated and are not in a constexpr context.

2308

Ah, I see. Good call. Done.

zoecarver added inline comments.Aug 12 2019, 11:11 AM
libcxx/include/iterator
1536 ↗(On Diff #214669)

What was the reasoning behind _LIBCPP_CONSTEXPR_IF_NODEBUG? I updated it to _LIBCPP_CONSTEXPR but, I want to make sure that is OK.

libcxx/test/std/algorithms/alg.modifying.operations/alg.rotate/rotate.pass.cpp
458

It does.

  • fix tests
  • make internal functions always constexpr
ldionne requested changes to this revision.May 12 2020, 8:23 AM
ldionne added inline comments.
libcxx/include/algorithm
1854

This doesn't work because is_constant_evaluated is not a macro. We have the macro _LIBCPP_HAS_NO_BUILTIN_IS_CONSTANT_EVALUATED that tells you whether std::is_constant_evaluated is supported.

This revision now requires changes to proceed.May 12 2020, 8:23 AM
zoecarver updated this revision to Diff 263594.May 12 2020, 7:39 PM
  • Rebase off master.
  • Use _LIBCPP_HAS_NO_BUILTIN_IS_CONSTANT_EVALUATED
Herald added a project: Restricted Project. · View Herald TranscriptMay 12 2020, 7:39 PM
Herald added a reviewer: Restricted Project. · View Herald Transcript
ldionne requested changes to this revision.May 14 2020, 5:46 AM
ldionne added inline comments.
libcxx/include/algorithm
1682

Does this break the library when used with the debug mode? There must have been a reason why we added _LIBCPP_CONSTEXPR_IF_NODEBUG in the first place?

@EricWF Do we care about this? If not, it looks like now's the time to remove the debug mode (for something better) as we discussed.

1858

I don't see the point of this #elif, can you explain?

1900

This needs to be constexpr in C++20 and above only, since it's part of the API.

libcxx/include/iterator
1376 ↗(On Diff #263594)

Please keep the previous formatting.

This revision now requires changes to proceed.May 14 2020, 5:46 AM
zoecarver marked 2 inline comments as done.May 18 2020, 7:48 AM
zoecarver added inline comments.
libcxx/include/algorithm
1682

I think it should be the opposite: the tests fail in debug mode because this is no longer constexpr. I'll test it, though.

1858

After C++17 the standard says some users of this function should be constexpr so, we have to support that. But before C++20, if _LIBCPP_HAS_NO_BUILTIN_IS_CONSTANT_EVALUATED we probably want to take the fast path even if it means no constexpr. WDYT?

zoecarver marked 4 inline comments as done.May 18 2020, 8:05 AM
zoecarver added inline comments.
libcxx/include/algorithm
1682

The tests all pass with _LIBCPP_DEBUG=1.

1835

These all need to be _LIBCPP_CONSTEXPR_AFTER_CXX17. Otherwise, the compiler will complain about the loops in pre C++20 mode.

zoecarver updated this revision to Diff 264627.May 18 2020, 8:06 AM
  • Rebase off master
  • Revert formatting change
  • Make everything _LIBCPP_CONSTEXPR_AFTER_CXX17
ldionne requested changes to this revision.May 19 2020, 5:54 AM

Your comment about loops made me think about generalized constexpr in C++14. Can you run the tests with your patch in C++11 and C++14 to make sure it works? I would expect failures due to the lack of generalized constexpr in C++11.

libcxx/include/algorithm
1682

Can you try with _LIBCPP_DEBUG=2? It's a different debug level. I know it's kind of confusing.

1835

I don't see why. Loops are allowed in constexpr since C++14. I guess we would need to use _LIBCPP_CONSTEXPR_AFTER_CXX14 then.

Essentially, the rule I'm trying to go for is: make private helpers constexpr as often as they can be, and make public APIs constexpr when the standard requires them to.

1858

Hmm, interesting. Yeah, that makes sense, however it also means that we might be pessimizing the runtime version in C++20 just because the compiler doesn't have is_constant_evaluated. I'm not 100% sure what the best approach is, however I would tend to say: In C++20, we are conforming w.r.t. constexpr algorithms only when the compiler supports is_constant_evaluated, otherwise we are non-conforming in favour of performance. In other words, when is_constant_evaluated isn't provided, we would not properly provide constexpr in these algorithms, and we'd always use the fast-but-not-constexpr version. This would avoid silent pessimizations, but would reduce our conformance level with older compilers. I don't think it's a huge deal because libc++ should normally be used with a recent compiler anyway, but this merits some thinking.

If we go down that route, we could simply use __libcpp_is_constant_evaluated() instead of the logic you have here.

This revision now requires changes to proceed.May 19 2020, 5:54 AM
zoecarver marked 3 inline comments as done.May 19 2020, 5:10 PM
zoecarver added inline comments.
libcxx/include/algorithm
1682

All tests pass :)

1835

I didn't think to check, you're right loops in constexpr in C++14 work fine.

Essentially, the rule I'm trying to go for is: make private helpers constexpr as often as they can be, and make public APIs constexpr when the standard requires them to.

Great, I think this is a good idea.

1858

My thinking here is that it's doubtful (especially at this point in time) that someone will be enabling C++20 on a compiler that isn't fairly recent.

But, this is actually a moot point because I just realized after P0202 we can use memmove in a constexpr context. So, we can remove __move_constexpr altogether.

zoecarver updated this revision to Diff 265094.May 19 2020, 5:13 PM
  • Make some things _LIBCPP_CONSTEXPR_AFTER_CXX14
  • Remove *_constexpr functions
ldionne requested changes to this revision.May 20 2020, 2:28 PM
ldionne added inline comments.
libcxx/include/algorithm
1845

Wait, this doesn't work at all because memmove isn't constexpr. You still need the _constexpr functions, I just meant that it was reasonable to not try to use their constexpr version when is_constant_evaluated() isn't supported by the compiler.

I would expect that your tests fail with the patch as it is (and if not there's something I don't understand, so please LMK).

This revision now requires changes to proceed.May 20 2020, 2:28 PM
zoecarver marked an inline comment as done.May 20 2020, 3:29 PM
zoecarver added inline comments.
libcxx/include/algorithm
1845

You're right. I was looking at an earlier version of the paper where memmove was constexpr and then ran the tests in C++17 mode (when the constexpr bits weren't enabled) and thought, "this is great!"

Anyway, we could use __builtin_memmove after in Clang 8+ (which is constexpr).

zoecarver updated this revision to Diff 265894.May 23 2020, 2:57 PM
  • Rebase off master
  • Add back move_constexpr and move_backward_constexpr
zoecarver updated this revision to Diff 265895.May 23 2020, 3:03 PM
  • Pass correct args to __move_constexpr
ldionne requested changes to this revision.May 25 2020, 8:15 AM
ldionne added inline comments.
libcxx/include/algorithm
2448

This can't be constexpr in C++14 since it uses __rotate_forward, which is only marked as constexpr starting in C++17 and above.

libcxx/test/std/algorithms/alg.modifying.operations/alg.move/move.pass.cpp
133 ↗(On Diff #265895)

I would remove && !defined(_LIBCPP_HAS_NO_BUILTIN_IS_CONSTANT_EVALUATED) -- the test suite isn't supposed to have libc++ or compiler specific knowledge. If the test fails with some older compilers (e.g. clang 5), we can mark it as unsupported on that compiler.

This revision now requires changes to proceed.May 25 2020, 8:15 AM
  • Update comment about P0202 in 2a status
zoecarver marked 2 inline comments as done.May 25 2020, 11:10 AM
zoecarver added inline comments.
libcxx/include/algorithm
2448

If it can take one of the first two paths, then it can be constexpr. I think it makes sense to support it in C++14 when possible.

libcxx/test/std/algorithms/alg.modifying.operations/alg.move/move.pass.cpp
133 ↗(On Diff #265895)

__builtin_is_constant_evalutated is actually pretty new. It was only added to clang in the last year IIRC. I think this will be a long list of compilers. The clang that ships on the latest macOS (Apple clang 11) doesn't even support it. It may be worth adding something to test_macros. WDYT?

  • Use __libcpp_is_constant_evaluated instead of is_constant_evaluated.
ldionne requested changes to this revision.May 25 2020, 11:33 AM
ldionne added inline comments.
libcxx/include/algorithm
1854

You don't need #if _LIBCPP_HAS_NO_BUILTIN_IS_CONSTANT_EVALUATED anymore if you're using __libcpp_is_constant_evaluated() -- IIUC.

2448

Geez, you're right. I really glanced too quickly here.

libcxx/test/std/algorithms/alg.modifying.operations/alg.move/move.pass.cpp
133 ↗(On Diff #265895)

My preference would still be to say // UNSUPPORTED: c++2a && apple-clang-11 (and the same for all unsupported compilers). The reason is that these UNSUPPORTED annotations are easy to get rid of as time goes by and we stop caring about older compilers. As such, it's easy-to-remove tech debt in the test suite.

On the other hand, if we engineer the test suite such that it can be run with compilers that don't support is_constant_evaluated(), we add complexity to the test suite itself, and removing it will require making sure that e.g. nobody's using the test suite with a compiler that doesn't support is_constant_evaluated(). Also, in theory, we should do the same for all features that involve compiler support, which isn't really scalable.

So.. my preference would be to be aggressive with compilers that don't support required features -- after all, libc++ is normally shipped alongside a matching Clang.

This revision now requires changes to proceed.May 25 2020, 11:33 AM
zoecarver marked 2 inline comments as done.Jul 22 2020, 10:56 PM
zoecarver added inline comments.
libcxx/include/algorithm
1854

Yep, you're right.

libcxx/test/std/algorithms/alg.modifying.operations/alg.move/move.pass.cpp
133 ↗(On Diff #265895)

Fair enough. I'll use UNSUPPORTED.

Why the C++2a part, though? I think I'll leave the TEST_STD_VER > 17 condition because that's what the standard says so, we shouldn't need the C++2a condition.

Also, I think we should support clang-8 and up. What are the corresponding apple-clang versions?

  • Remove "has builtin" check in __move.
  • Replace #if in test with UNSUPPORTED.
ldionne accepted this revision.Sep 14 2020, 12:43 PM

This almost LGTM. You can commit after fixing those comments and I'll adjust the markup for AppleClang as needed.

libcxx/include/algorithm
1890

Same here, _LIBCPP_HAS_NO_BUILTIN_IS_CONSTANT_EVALUATED isn't needed.

libcxx/test/std/algorithms/alg.modifying.operations/alg.move/move_backward.pass.cpp
87 ↗(On Diff #280032)

Same as above, please remove && !defined(_LIBCPP_HAS_NO_BUILTIN_IS_CONSTANT_EVALUATED)

libcxx/test/std/algorithms/alg.modifying.operations/alg.rotate/rotate.pass.cpp
457

Same as above for && !defined(_LIBCPP_HAS_NO_BUILTIN_IS_CONSTANT_EVALUATED).

This revision is now accepted and ready to land.Sep 14 2020, 12:43 PM
This revision was landed with ongoing or failed builds.Sep 14 2020, 1:57 PM
This revision was automatically updated to reflect the committed changes.

@ldionne thanks for your patience with this patch. It's great to finally get it in.

Re-committed as 3ed89b51da38f081fedb57727076262abb81d149 with UNSUPPORTED markup.

@zoecarver Thanks to you for the contribution and for being patient with the review. Greatly appreciated.