Page MenuHomePhabricator

Disable invalid isPodLike<> specialization
ClosedPublic

Authored by serge-sans-paille on Nov 13 2018, 6:51 AM.

Details

Summary

As noted in https://bugs.llvm.org/show_bug.cgi?id=36651, the specialization for isPodLike<std::pair<...>> did not match the expectation of std::is_trivially_copyable which makes the memcpy optimization invalid.

This patch renames the llvm::isPodLike trait into llvm::is_trivially_copyable. Unfortunately std::is_trivially_copyable is not portable across compiler / STL versions. So a portable version is provided too.

Note that the following specialization were invalid:

  • std::pair<T0, T1>
  • llvm::Optional<T>

Tests have been added to assert that former specialization are respected by the standard usage of llvm::is_trivially_copyable, and that in debug build, and when a decent version of std::is_trivially_copyable is available, llvm::is_trivially_copyable is compared to std::is_trivially_copyable

As of this patch, llvm::Optional is no longer considered trivially copyable, even if T is. this is to be fixed in a later patch, as it has impact on a long-running bug (see r347004)

Note that GCC warns about this UB, but this got silented by https://reviews.llvm.org/D50296.

Diff Detail

Repository
rL LLVM

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
include/llvm/ADT/bit.h
45 ↗(On Diff #175453)

Yep, fixed

While I like the update (keeping any potential changes to Optional and SmallVector separate seems good) I have a serious concern that this has the same fundamental problem as the prior mentioned ABI issue.

Specifically, if we end up mixing .o files from GCC and Clang, they may have subtly different ABIs due to different types being considered "trivially copyable". That can in turn cause these .o files to expect different specializations of SmallVector (or any other type utilizing this trait). And that in turn can lead to horrible ABI issues.

So, at the very least, I do not think we can mix std::is_trivial and std::is_trivially_copyable in this way.

If we want to do this, we have to use predicates that will be *ABI stable* between compilers on the same platform where we might reasonably mix .o files. This is... challenging.

I believe the most portable and reliably implementations I'm aware of don't *technically* implement std::is_trivially_copyable. Instead, they separately implement std::is_trivially_copy_constructible and std::is_trivially_copy_assignable. I believe we could change LLVM's existing usag of isPodLike to use these traits and then implement them using the same core technique used by Abseil here:
https://github.com/abseil/abseil-cpp/blob/master/absl/meta/type_traits.h#L291-L295
https://github.com/abseil/abseil-cpp/blob/master/absl/meta/type_traits.h#L325-L329

I'm still not 100% sure this is going to be reliable from an ABI perspective. I'm asking a group of Abseil and C++ ABI experts to see if they see any problems here.

include/llvm/ADT/SmallVector.h
185 ↗(On Diff #175453)

While this might be an independently nice improvement, I agree w/ the current mechanics of the patch to make the diff more isolated.

Simple ABI breakage reproducer:

compile the following codes and run nm on the generated objects, with clang 6 and gcc 4.8

#include <llvm/ADT/StringRef.h>
#include <llvm/ADT/SmallVector.h>

llvm::SmallVector<llvm::StringRef, 4> ff;

the list of symbol differ because a different SmallVector specialization is used...

dexonsmith added inline comments.Nov 28 2018, 2:06 AM
include/llvm/ADT/SmallVector.h
185 ↗(On Diff #175453)

It doesn't seem completely independent to me, because this patch introduces repeated instances of (reader's) ambiguity between is_trivially_copyable and std::is_trivially_copyable.

Can the mechanical change suggested by @Quuxplusone be implemented as an initial NFC commit on isPodLike (and then this patch rebased on top)? If so, that would avoid cluttering this diff.

serge-sans-paille marked an inline comment as done.Nov 28 2018, 7:15 AM
serge-sans-paille added inline comments.
include/llvm/ADT/SmallVector.h
185 ↗(On Diff #175453)

https://godbolt.org/z/_gK-9m provides a first draft of a compiler-agnostic implementation of `std::is_trivially_copyable`. It uses no builtin and compiles fine with gcc 4.9. I'll do more testing soon.

Lighter version, using bits of std:: but still works for gcc 4.9: https://godbolt.org/z/Dq9pMk

serge-sans-paille edited the summary of this revision. (Show Details)
Quuxplusone added inline comments.Nov 30 2018, 6:17 PM
include/llvm/ADT/SmallVector.h
333 ↗(On Diff #176110)

The , is_trivially_copyable<T>::value can safely be removed here. Sorry I missed it on the other review.

include/llvm/Analysis/BlockFrequencyInfoImpl.h
188 ↗(On Diff #176110)

Unintended diff? Also, surely noexcept(true) a.k.a. noexcept would be the default here anyway. If anything wants noexcept, it'd be line 189, not line 188. :)

include/llvm/Support/type_traits.h
163 ↗(On Diff #176110)

This last clause — (has_trivial_copy_constructor || has_trivial_copy_assign || has_trivial_move_constructor || has_trivial_move_assign) — does not correspond to anything in the Standard. So:

https://godbolt.org/z/R5hCff

struct S {
    S(S&&) = delete;
};
static_assert(is_trivially_copyable<S>::value);
error: static_assert failed "consistent behavior"
  static_assert(value == std::is_trivially_copyable<T>::value, "consistent behavior");
  ^             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

I'm not sure but I would suggest just getting rid of this last clause.

tools/clang/lib/Sema/SemaChecking.cpp
11553 ↗(On Diff #176110)

Unintended diff? But harmless.

unittests/ADT/ArrayRefTest.cpp
252 ↗(On Diff #176110)

Why does this need the guard? You're not using the std:: version here.
(And likewise on the next 7-or-so diffs.)

serge-sans-paille marked 20 inline comments as done.
serge-sans-paille added inline comments.
include/llvm/Analysis/BlockFrequencyInfoImpl.h
188 ↗(On Diff #176110)

That's unfortunate but intended: for some reason, and for some clang version, the type trait `is_trivially_copyable` leads to this being required. There's no such issue with the gcc version I compiled clang with.

include/llvm/Support/type_traits.h
163 ↗(On Diff #176110)

From https://en.cppreference.com/w/cpp/named_req/TriviallyCopyable (yeah that's not the standard, but I do hope it's derived from the standard)

at least one copy constructor, move constructor, copy assignment operator, or move assignment operator is non-deleted

That's the intent I was trying to capture.

I'm okay with getting rid of this capture, especially when looking at https://godbolt.org/z/p3-Cy4.

tools/clang/lib/Sema/SemaChecking.cpp
11553 ↗(On Diff #176110)

Same as above, omitting this change leads to error in type traits instantiation for some compiler version.

Rebase against master + minor fixes + take into account reviews

chandlerc added inline comments.Dec 4 2018, 3:18 AM
include/llvm/ADT/PointerIntPair.h
133–134 ↗(On Diff #176577)

The compiler may pass __has_feature(is_trivially_copyable) and yet the standard library not provide std::is_trivially_copyable. And I don't see any feature test spelled is_trivially_copyable? Do you mean __has_trivially_copy, which is the Clang and GCC builtin?

Also, the message is printed on an *error*.

serge-sans-paille marked an inline comment as done.Dec 4 2018, 4:46 AM
serge-sans-paille added inline comments.
include/llvm/ADT/PointerIntPair.h
133–134 ↗(On Diff #176577)

The legacy code for isPodLike was using the very same guard without issue, so I tend to think it's okay. +1 for the error stuff, I'll update that.

Quuxplusone added inline comments.Dec 4 2018, 9:50 AM
include/llvm/ADT/PointerIntPair.h
133–134 ↗(On Diff #176577)

I see Clang providing both __has_feature(has_trivial_copy) and __has_feature(is_trivially_copyable) (using exactly the spellings I just wrote).
GCC doesn't support __has_feature at all, so a bunch of places in LLVM do #define __has_feature(x) 0.
I think this snippet is OK as written.

include/llvm/Analysis/BlockFrequencyInfoImpl.h
188 ↗(On Diff #176110)

That's extremely weird and scary. Is it worth digging further into why that happens?

serge-sans-paille marked an inline comment as done.Dec 5 2018, 1:36 AM
serge-sans-paille added inline comments.
include/llvm/Analysis/BlockFrequencyInfoImpl.h
188 ↗(On Diff #176110)

I reduced the test case to that: https://godbolt.org/z/briQXa
This is gcc-specific, and adding the noexcept clause fixes the bug.

serge-sans-paille marked 2 inline comments as done.Dec 5 2018, 6:11 AM
serge-sans-paille added inline comments.
include/llvm/Analysis/BlockFrequencyInfoImpl.h
188 ↗(On Diff #176110)
serge-sans-paille edited the summary of this revision. (Show Details)Dec 5 2018, 6:12 AM

@chandlerc concerning union as a way to detect non-trivial operations, according to https://en.cppreference.com/w/cpp/language/union

If a union contains a non-static data member with a non-trivial special member function (copy/move constructor, copy/move assignment, or destructor), that function is deleted by default in the union and needs to be defined explicitly by the programmer.

So I guess it's a decent way to implement these checks.

LGTM at this point modulo my two comments (one important but trivial, the other completely trivial).
I don't know whether Chandler's concern about __has_feature in "include/llvm/ADT/PointerIntPair.h" has been 100% resolved yet — @chandlerc?

include/llvm/ADT/PointerIntPair.h
133–134 ↗(On Diff #176577)

Wait, you definitely need something like

using T = PointerIntPair<PointerTy, IntBits, IntType, PtrTraits, Info>;

before this line, or else it won't know what T is here! (Probably means you should find a way to compile without NDEBUG before merging. :))

tools/llvm-xray/trie-node.h
45 ↗(On Diff #176638)

Extraneous diff.

serge-sans-paille marked 3 inline comments as done.Dec 19 2018, 5:21 AM

@Quuxplusone this patch has been rebuilt without NDEBUG, which triggered a few minor changes I have commented above. If @chandlerc is fine with current state, we should be able to merge it. Then move on to the llvm::Optional special case.

include/llvm/Support/type_traits.h
163 ↗(On Diff #176110)

@Quuxplusone I had to reintroduce the (has_trivial_move_assign || has_trivial_move_constructor || has_trivial_copy_assign || has_trivial_copy_constructor) condition, which is indeed a standard requirement. It basically states « if the class is not meant to be copied, don't allow to copy it ».

Quuxplusone added inline comments.Dec 19 2018, 8:21 AM
include/llvm/Support/type_traits.h
163 ↗(On Diff #176110)

The standard trait "trivially copyable" is not related to copy-{constructibility,assignability}; it's its own thing.

I insist that if you're naming your thing "trivially copyable," it should exactly match the Standard trait's behavior, i.e., it should succeed at this test case:

struct S {
    S(S&&) = delete;
};
static_assert(is_trivially_copyable<S>::value);

Your current code doesn't pass that test. https://godbolt.org/z/j6pkaS

Any users of is_trivially_copyable should use it only to enable perf optimizations. They shouldn't be using it to ask, "Should I make a copy of this?" First of all, "make a copy" is underspecified. What they should have asked is "Should I copy-construct this?" or "Should I copy-assign this?" And we already have traits for that. Then, once they've already decided to make a copy (or maybe not to make any copies, but just to move the value without copying), then they should look at is_trivially_copyable to decide how to make that copy.

serge-sans-paille marked an inline comment as done.Dec 19 2018, 9:37 AM
serge-sans-paille added inline comments.
include/llvm/Support/type_traits.h
163 ↗(On Diff #176110)

I totally agree on your point. Unfortunately, I don't think it's possible to achieve a portable implementation of is_trivially_copyable without compiler support for all supported compiler version (including gcc 4.9). And that's exactly why this patch exist: to cope with this limitation, while ensuring the memcpy are valid, which is not the case with current implementation (which is both invalid for some type/compiler combination, and not conservative with respect to ABI because of the impact of isPodLike on ADT like SmallVector. So I would advocate for renaming this trait is_memc(o)pyable and ensuring that forall T instanciated in LLVM where std::is_trivially_copyable matters, is_memcopyable<T>::value == true implies std::is_trivially_copyable<T> == true, which is currently the case (as we actually even verify that is_memcopyable<T>::value == std::is_trivially_copyable<T>::value).

Does that sound OK to you?

Quuxplusone added inline comments.Dec 19 2018, 11:02 AM
include/llvm/Support/type_traits.h
163 ↗(On Diff #176110)

I think that is_memcpyable sounds underdetermined: it ought to be is_move_assignable_via_memcpy, is_copy_constructible_via_memcpy, or whatever operation we're asserting is tantamount to memcpy. At which point you've just reinvented is_trivially_move_assignable, is_trivially_copy_constructible etc. (and here I'll insert a shameless plug for D50119 is_trivially_relocatable, because quite often the operation we want to replace is "relocating", not merely "copy-constructing" or "move-assigning").

The situation is complicated by the fact that right now the C++17 standard specifies that memcpying is technically permitted only for trivially copyable types. So if by is_memcpyable you mean "is memcpying technically permitted for this type under any circumstances — never mind whether it's semantically correct —" then is_memcpyable would be just a synonym for std::is_trivially_copyable. (But then specializing it would be UB.)

I think this patch has been evolving toward "Provide an llvm::is_trivially_copyable trait that is exactly the same as std::is_trivially_copyable, but portable." I think it should keep going in that direction.

If we say "Maybe the trait shouldn't be is_trivially_copyable at all, but something else," then that reopens the can of worms. (At that point, why not just keep the name isPodLike?)

Quuxplusone added inline comments.Dec 19 2018, 11:09 AM
include/llvm/Support/type_traits.h
163 ↗(On Diff #176110)

But on the other hand, I see that MSVC's standard library agrees with you that an immovable type is not is_trivially_copyable. (GCC/libstdc++, Clang/libc++, and ICC agree with me that it's unrelated.)
https://godbolt.org/z/Gv_hcj
So we'll never get value == std::is_trivially_copyable<T>::value to pass on all platforms.

So I won't block this review over the (has_trivial_move_assign || has_trivial_move_constructor || has_trivial_copy_assign || has_trivial_copy_constructor) condition. If you want it, you can keep it. But I hope that that line isn't necessary for correctness! I mean, I hope that if someone removes that line in the future, or switches from llvm::is_trivially_copyable to std::is_trivially_copyable, it won't cause silent breakage of any of LLVM's data structures. Is that reasonable?

serge-sans-paille marked an inline comment as done.Dec 19 2018, 12:00 PM
serge-sans-paille added inline comments.
include/llvm/Support/type_traits.h
163 ↗(On Diff #176110)

So I won't block this review

Cool.

switches from llvm::is_trivially_copyable to std::is_trivially_copyable

In current state, thanks to the assert, llvm::is_trivially_copyable and std::is_trivially_copyable are equivalent *with respect to LLVM codebase*.

Given the ... very subtle ABI implications here, I really want Richard to look at this and make sure we're not barking up the wrong tree.

Also I think the example raised in https://godbolt.org/z/59_R-J is a bug in all but MSVC, although I'm not the expert here and Richard may have DRs or issues to cite. My reading of the standard supports the implementation of is_trivially_copyable in this patch and in MSVC. Specifically, [class.prop]p1.2 in the latest draft has the *exact* requirement that this code enforces: one of the copy or move constructors or assignment operators must be non-deleted. And the example given has all of those deleted (all but one because they are defined as deleted implicitly IIRC). But again, happy to defer to Richard here, this is a subtle and complex part of the standard.

include/llvm/ADT/PointerIntPair.h
128–129 ↗(On Diff #178865)

This comment doesn't really make sense here...

I would say something more about the *effect* of this, not the symptom that made you add it. So, talk about the fact that this allows even an incomplete PointerIntPair type (or some such) to be known to be trivially copyable.

include/llvm/Support/type_traits.h
123–124 ↗(On Diff #178865)

Can you re-flow this comment to fit in 80-columns?

128–154 ↗(On Diff #178865)

All of this should be private, no?

169–175 ↗(On Diff #178865)

Why is this needed? Due to incomplete types? (answer in a comment please!)

serge-sans-paille marked 3 inline comments as done.Wed, Jan 2, 1:24 AM

@chandlerc: thanks for the final review! everything should be okay right now, waiting for @rsmith for the final call.

rsmith marked an inline comment as done.Mon, Jan 14, 6:04 PM
rsmith added inline comments.
include/llvm/ADT/PointerIntPair.h
132 ↗(On Diff #179822)

Why is this guarded by NDEBUG?

133 ↗(On Diff #179822)

I am confused by this. If the type in question is incomplete, how can this static_assert work? (And if it's complete, why do you need the specialization at all?) Have you made sure this actually compiles in a Debug build?

If you need this, I think what you should probably do instead is to put this static_assert inside PointerIntPair, in some member function that is commonly instantiated, such as the default constructor. (It can't go in the body of the class itself because the class isn't complete there.)

include/llvm/ADT/SmallVector.h
240 ↗(On Diff #179822)

Please give this a suitable, LLVM-style-conforming name that doesn't shadow the trait. Maybe TriviallyCopyable?

include/llvm/Support/type_traits.h
169–175 ↗(On Diff #178865)

The comment still doesn't explain why you need this. Why would the above implementation not work for pointers to incomplete types? (As far as I can see, the above implementation should work fine in that case, and works fine in practice: https://godbolt.org/z/FJ09dy)

163 ↗(On Diff #176110)

The problem here is a bug in GCC and Clang's __is_trivially_copyable, not a bug in this patch. Example: https://godbolt.org/z/XKaLOa (The specific issue is that neither compiler implements DR1734 yet.)

168 ↗(On Diff #179822)

Why check NDEBUG here?

serge-sans-paille marked 6 inline comments as done.

Take into account @rsmith review.

include/llvm/ADT/PointerIntPair.h
132 ↗(On Diff #179822)

To limit compile-time overhead.

include/llvm/Support/type_traits.h
169–175 ↗(On Diff #178865)

That definitively was a left over. I removed it in the updated patch.

168 ↗(On Diff #179822)

It's debug code, to ensure the consistency of llvm::is_trivially_copyable with std:: version. I assume ignoring this on release build make them faster.

serge-sans-paille marked an inline comment as done.Wed, Jan 16, 6:02 AM
serge-sans-paille added inline comments.
include/llvm/ADT/PointerIntPair.h
133 ↗(On Diff #179822)
If the type in question is incomplete, how can this static_assert work?

My *guess* is that std::is_trivially_copyable

Have you made sure this actually compiles in a Debug build?

yes. Double checked right now!

rsmith added inline comments.Wed, Jan 16, 2:14 PM
include/llvm/ADT/PointerIntPair.h
132 ↗(On Diff #179822)

I don't think that's worth the loss of safety, particularly for folks who aren't clang developers and just try to make a release build with an untested toolchain. I would prefer to take the (likely tiny) compile time cost and always have the check enabled.

133 ↗(On Diff #179822)

Some of your comment seems to have gotten lost here. I still don't see how this can be right (if the type is complete, then this specialization should be unnecessary, and if it's incomplete, then this use of std::is_trivially_copyable should be ill-formed). Have you tried removing this specialization entirely to see if it's actually necessary? If so, what compile error do you get?

include/llvm/Support/type_traits.h
168 ↗(On Diff #179822)

(As for the other case, I would prefer that we always static_assert this, even in release builds.)

For some reason, all the specialization were not required, so we end up with a very clean implementation. Thanks a lot @rsmith for pointing that out!

serge-sans-paille marked 3 inline comments as done.Thu, Jan 17, 7:18 AM

LGTM!

docs/ProgrammersManual.rst
1459 ↗(On Diff #182284)

Bikeshed: This isn't technically an advantage over std::vector, since std::vector also does this. :)

I do think you should explicitly say llvm::is_trivially_copyable<Type> here, to distinguish it from std::is_trivially_copyable<Type> (which IIUC should not be used anywhere in the LLVM codebase). But maybe the llvm:: qualification would be implicitly assumed by people who work with LLVM frequently?

serge-sans-paille marked 4 inline comments as done.
chandlerc added inline comments.Fri, Jan 18, 6:26 AM
docs/ProgrammersManual.rst
1459 ↗(On Diff #182284)

Not all implementations of vector reliably implement this optimization is I think what this is trying to say.

serge-sans-paille marked an inline comment as done.Fri, Jan 18, 6:29 AM

@rsmith thanks a lot for the final review. I rebased the patch, did a final check with both GCC and Clang, and everything looks fine now. Waiting for a green light!

docs/ProgrammersManual.rst
1459 ↗(On Diff #182284)

I totally agreee on std::vector using the same technique. That's independent from that commit though :-)

And yeah, better be explicit about llvm::is_trivially_copyable.

include/llvm/Analysis/BlockFrequencyInfoImpl.h
188 ↗(On Diff #182506)

I still needed to rewrite it that way. Clang was happy with the original version bug gcc wasn't (i.e. it made std:: and llvm:: version behave differently).

include/llvm/CodeGen/DIE.h
803 ↗(On Diff #182506)

This class has a virtual member, so it needs a virtual destructor. And without that qualifier, std:: and llvm:: behave differently.

include/llvm/Support/type_traits.h
163 ↗(On Diff #176110)

The standard trait "trivially copyable" is not related to copy-{constructibility,assignability}; it's its own thing.

Again, when recompiling with both GCC and Clang, I realized that they both agree with you; i double checked the clang source code and it also agrees with you, so I removed the final condition.

rsmith accepted this revision.Fri, Jan 18, 3:02 PM

Thanks, looks great!

This revision is now accepted and ready to land.Fri, Jan 18, 3:02 PM
This revision was automatically updated to reflect the committed changes.