This is an archive of the discontinued LLVM Phabricator instance.

Implement P0553 and P0556
ClosedPublic

Authored by mclow.lists on Aug 25 2018, 12:36 PM.

Details

Reviewers
EricWF
ldionne
Summary

LWG adopted https://wg21.link/P0553 in Rapperswil, and suggested minor changes to https://wg21.link/P0556.

They kind of go together; for example, ispow2 is easily implemented using popcount - and they share a bunch of infastructure.

I don't recommend landing this until P0556 is approved, but when I implemented one, the other was easy.
None of this stuff will be constexpr on Windows, because the underlying primitives are not constexpr on Windows.

Sorry for the large-ish diff, but (like span) it's 85%+ tests.

Diff Detail

Event Timeline

mclow.lists created this revision.Aug 25 2018, 12:36 PM

I should also mention that as a conforming extension, I have implemented the non-numeric bit operations for std::byte

Please use Clang format on these changes.

Otherwise the implementation looks great, I've left some nits.

include/bit
190 ↗(On Diff #162561)

Use an alias template to produce this. fewer instantiations.

254 ↗(On Diff #162561)

Cool use of if constexpr.

Please clang-format these changes.

EricWF added inline comments.Jun 13 2019, 11:26 PM
include/bit
193 ↗(On Diff #162561)

is bool unsigned? Otherwise it should already be excluded.
Also are the unsigned types that aren't integral?

209 ↗(On Diff #162561)

Nit:

Use an if over a long ternary operator.

405 ↗(On Diff #162561)
test/std/numerics/bit/bitops.rot/rotl.pass.cpp
106 ↗(On Diff #162561)

Commented out code.

test/std/numerics/bit/bitops.rot/rotr.pass.cpp
119 ↗(On Diff #162561)

Please don't add commented out code.

Update this patch to implement P1355R2 which makes out-of-bound inputs for ceil2UB. This was easy for integer types that are at least as big as int, but harder for smaller ones.

mclow.lists marked 4 inline comments as done.Jun 24 2019, 5:47 PM
mclow.lists added inline comments.
include/bit
254 ↗(On Diff #162561)

I really like this formatting; it reflects the structure of the code.

405 ↗(On Diff #162561)

I think that document is misguided in cases like this; the enable_if on the return type cannot be "interfered with" by the caller the way an extra template parameter can be.

Also are the unsigned types that aren't integral?

I believe that people are allowed to specialize is_unsigned for their own (bignum, say) types.
However, is_integral is not extensible. It refers to the types in [basic.fundamental]

Type bool is a distinct type that has the same object representation, value representation, and alignment requirements as an implementation-defined unsigned integer type.

Quuxplusone added inline comments.
libcxx/include/bit
200

Given how heavily the code controlled by this trait depends on numeric_limits<_Tp>, would it make sense to add something in here about how that specialization should exist?

I agree with @EricWF's earlier comment: I can't think of any types that would satisfy (!is_integral_v<_Tp>) && is_unsigned_v<_Tp>. (But just TIL that the signedness of wchar_t is implementation-defined.)

212

No sane compiler would actually generate three mod operations for the three instances of repeated subexpression __cnt % __dig, would they?

253

Since __t is already of type _Tp, the explicit template argument <_Tp> is unnecessary here.
Also, is the ADL here intentional?

254

I forget the rules of name hiding; is this countl_zero also an ADL call? (My experimentation implies it's not? but it would still be clearer to use _VSTD::countl_zero if that's what you mean.)

As a general rule, I strongly recommend writing side-effects outside of if conditions; like, on the previous line or something; unless writing it all on a single line has some concrete benefit.

256

clang-format?

332

FWIW, this comment seems tautological.

366

Incidentally, why (_Tp)(__t - 1u) instead of the formula __t - _Tp{1} used elsewhere in this header?

379

Why so complicated? Is there a unit test that demonstrates why you can't just use return _Tp{1} << __n; in this case as well?

Also, is this a kosher use of sizeof(X) * 8 as a stand-in for numeric_limits<X>::digits?

Also, speaking of unit tests, I don't see any unit tests for e.g. std::ceil2(256) or std::ceil2(65536). Shouldn't there be some?

mclow.lists marked an inline comment as done.Jun 24 2019, 7:22 PM
mclow.lists added inline comments.
libcxx/include/bit
379

Yes. I want to generate some UB here, so that this is not a "core constant expression" as per P1355.

mclow.lists marked 2 inline comments as done.Jun 24 2019, 7:30 PM
mclow.lists added inline comments.
libcxx/include/bit
200

is_unsigned_v<Bignum> could be true, but is_integral_v<Bignum> is not ever true.

212

At -O0? Sure it would.

mclow.lists marked an inline comment as done.Jun 24 2019, 7:40 PM
mclow.lists added inline comments.
libcxx/include/bit
379

Yes, the ceil2.fail.cpp test will not fail (for short types) if I just return _Tp{1} << __n; - because of integer promotion.

libcxx/include/bit
379

Yikes. Sounds like there's some "library maintainer"ship going on here, then. Naively, I would have thought that the Working Draft had left the behavior of such constructs undefined in order to make the library vendor's life easier and the code more efficient. But you're saying that you need to pessimize the code here in order to make it "sufficiently undefined" so that its behavior at compile time will be well-defined and produce a diagnostic instead of being undefined and producing garbage?

Maybe WG21 needs to invent a "really actually undefined behavior" that does not have unwanted interactions with constexpr, so that library writers can go back to generating fast clean code!

Rant aside, why don't you just do _LIBCPP_ASSERT(__n < numeric_limits<_Tp>::digits); and leave it at that? An assertion failure isn't a compile-time constant, is it?

mclow.lists marked 4 inline comments as done.Jun 24 2019, 8:20 PM
mclow.lists added inline comments.
libcxx/include/bit
253

Right about the <_Tp>

254

Not an ADL call, because _Tp is always a built-in type.

366

Because I want to end up with a value of type _Tp, and (for short types), __t - _Tp{1} doesn't get me that. (Integer promotion). ((char) 23) - ((char) 1) is not type char

379

Also, is this a kosher use of sizeof(X) * 8 as a stand-in for numeric_limits<X>::digits?

Good catch.

mclow.lists marked an inline comment as done.Jun 24 2019, 8:23 PM
mclow.lists added inline comments.
libcxx/include/bit
379

that's exactly what P1355 says.

mclow.lists marked an inline comment as done.Jun 24 2019, 8:25 PM
mclow.lists added inline comments.
libcxx/include/bit
379

There are three things that I'd like this code to do in the case of bad inputs:

  • Produce a diagnostic if called at constexpr time (required by P1355)
  • Cause UBSAN to catch it at runtime
  • Cause a libc++ assertion to go off if they are enabled.

Note that these are all more or less independent.

I should also mention that as a conforming extension, I have implemented the non-numeric bit operations for std::byte

I thought there was a DR or proposal to enable that, but I don't see one now.

include/bit
405 ↗(On Diff #162561)

Yes (except on constructors) libstdc++ always uses the return type instead of a default template argument list, to stop "clever" people doing ceil2<int>(3) and avoiding the contraint.

libcxx/include/bit
379

Those are exactly the three things that my implementation also does, which is not a coincidence because this requirement of P1355 has been discussed offline (and feedback from implementation experience sent to the author about this particular aspect of it).

@Quuxplusone an assertion failure is not enabled by default, so doesn't do any good in a constant expression. There are a few different ways to make the shift undefined when the operand promotes, but you can't just avoid the complexity altogether.

mclow.lists added a comment.EditedJun 25 2019, 6:18 AM

I should also mention that as a conforming extension, I have implemented the non-numeric bit operations for std::byte

I thought there was a DR or proposal to enable that, but I don't see one now.

There was, but LEWG rejected it, so I took that out of this patch.

mclow.lists marked 4 inline comments as done.

Address a couple of review comments. Added a few more uint128_t rotation tests

mclow.lists marked 3 inline comments as done.Jun 25 2019, 6:23 PM
EricWF added a comment.Jul 1 2019, 9:55 AM

I would like to see a version of this after the inline comments are addressed.

libcxx/include/bit
194

_IsNotSame is faster and better to use here.

Also please put _LIBCPP_NODEBUG_TYPE on this alias. Otherwise it could generate unwanted debug info.

204

Why the explicit inline hint?

209

Why did you choose to use the ternary operator here, but you use an if in rotr?

237

Weird indentation. Clang-format please.

241

Do we even need if constexpr here?

252

This call needs to be qualified.

269

This should be qualified.

323

Do we need if constexpr here.

367

You don't need to guard debug assertions in C++14 constexpr functions.

385

__bit_log2 needs to be qualified to prevent ADL.

libcxx/test/std/numerics/bit/bit.pow.two/ceil2.fail.cpp
37

This can be written as a .pass.cpp test that uses is_invocable.

libcxx/test/std/numerics/bit/bit.pow.two/floor2.fail.cpp
30 ↗(On Diff #206571)

Use is_invocable.

libcxx/test/std/numerics/bit/bit.pow.two/ispow2.fail.cpp
29 ↗(On Diff #206571)

Use is_invocable.

libcxx/test/std/numerics/bit/bitops.count/countl_one.fail.cpp
30 ↗(On Diff #206571)

Use is_invocable.

libcxx/test/std/numerics/bit/bitops.count/countl_zero.fail.cpp
29 ↗(On Diff #206571)

Use is_invocable.

libcxx/test/std/numerics/bit/bitops.count/countr_one.fail.cpp
30 ↗(On Diff #206571)

Use is_invocable.

libcxx/test/std/numerics/bit/bitops.count/countr_zero.fail.cpp
29 ↗(On Diff #206571)

Use is_invocable.

libcxx/test/std/numerics/bit/bitops.count/popcount.fail.cpp
30 ↗(On Diff #206571)

Use is_invocable.

xbolva00 added inline comments.
libcxx/include/bit
212

Hoist it?

mclow.lists marked 7 inline comments as done.Jul 1 2019, 10:33 AM
mclow.lists added inline comments.
libcxx/include/bit
237

The indentation is purposeful. It illustrates the structure of the code.

241

Yes. When instantiated with _Tp == unsigned long (say), this should be a single call to __clz, w/o any other code.

252

I don't see why. _Tp must be an unsigned integral type.

323

Yes. See above.

367

Good to know; thanks.

385

See above. ADL on what? There are no user-defined types here.

libcxx/test/std/numerics/bit/bitops.count/countr_zero.fail.cpp
29 ↗(On Diff #206571)

I can do that.

libcxx/include/bit
241

The optimizer should take care of that just fine. But, if constexpr also prevents us from unnecessarily trying to instantiate, say, static_cast<unsigned long long>(__t), in the case that __t is of a user-defined type where that conversion's definition is ill-formed or explicitly deleted. I'm still extremely skeptical that any user-defined type is ever allowed to reach this code without UB; but if it is, then instantiating just the bare minimum of conversions might be a QoI issue. (The standard doesn't say anything about what this template should do for user-defined types, so keeping the surface area small is a good idea.)

385

FWIW, my intuition still agrees with Eric's: adding _VSTD:: throughout might not help anything, but if it wouldn't hurt, and if it stops every future code-reviewer from making the same exact comment about ADL, shouldn't you just do it? Wouldn't it save everyone some time?

libcxx/test/std/numerics/bit/nothing_to_do.pass.cpp
2

Peanut gallery says: I thought nothing_to_do.pass.cpp files were obsolete these days?

mclow.lists marked an inline comment as done.

Updated patch based on Eric's comments.

mclow.lists marked 5 inline comments as done.Jul 1 2019, 1:05 PM

I missed a couple of Eric's comments.

libcxx/include/bit
212

Hoist it?

IMHO, people building at -O0 are not people who care about code size/performance.

385

I disagree. When I review a chunk of code, if I see _VSTD:, I think "why is this here?", and I go looking for ADL points. I think it slows down reviewing.

mclow.lists marked an inline comment as done.

Removed explicit inlines, changed ternary into if

mclow.lists marked 2 inline comments as done.Jul 1 2019, 1:10 PM
mclow.lists added inline comments.
libcxx/include/bit
209

Because Arthur suggested it, and said "Meh".

mclow.lists marked 2 inline comments as done.Jul 1 2019, 1:47 PM
mclow.lists added inline comments.
libcxx/include/bit
204

Dang. Apparently I missed one. Will fix before committing.

EricWF accepted this revision.Jul 1 2019, 3:27 PM
EricWF added inline comments.
libcxx/include/bit
241

@mclow.lists That's what already happens https://godbolt.org/z/5JX3md

Clang doesn't emit the dead branch at any optimization level. So the if constexpr isn't needed.
But the extra tokens make it read like it is needed, which as you argued for _VSTD, is confusing.

366

I don't want us to get in the habit of conditionally compiling based on __builtin_is_constant_evaluated().

I think the following formulation would be cleaner.

// Somewhere in <type_traits>
#if _LIBCPP_HAS_NO_BUILTIN_IS_CONSTANT_EVALUATED
constexpr bool __libcpp_is_constant_evaluated() { return false; }
#else
constexpr bool __libcpp_is_constant_evaluated() { return __builtin_is_constant_evaluated(); }
#endif

// in ceil2

_LIBCPP_ASSERT(__libcpp_is_constant_evaluated() || <cond>);
This revision is now accepted and ready to land.Jul 1 2019, 3:27 PM
mclow.lists closed this revision.Jul 1 2019, 4:01 PM

Committed as revision 364862