This is an archive of the discontinued LLVM Phabricator instance.

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

dblaikie added inline comments.
include/llvm/Support/type_traits.h
40–44 ↗(On Diff #173838)

Does the presence of this macro mean "no one should ever specialize isPodLike"? & if they don't, then its certain that isPodLike == is_trivially_copyable, by definition?

If so, then I'm not sure of the importance of the macro - we should just say "don't specialize isPodLike, ever & leave it at that, maybe?

include/llvm/Support/type_traits.h
40–44 ↗(On Diff #173838)

Almost. It means « if you specialize `isPodLike`, then make sure that for modern compiler, it does not conflict with std::is_trivially_copyable ».

Basically for modern compiler, we should have

`template<class T> using isPodLike = std::is_trivially_copiable<T>;`

However, some compilers supported by LLVM don't implement that feature. In my opinion, it is still valid to speicalize `isPodLike` to ensure decent performance in these case. But not at the cost of UB.

dblaikie added inline comments.Nov 15 2018, 1:08 PM
include/llvm/Support/type_traits.h
40–44 ↗(On Diff #173838)

OK, fair enough.

Though does the performance matter on platforms that don't support the real trait? Which compilers/versions is that compared to the set of supported compilers/versions for building Clang/LLVM. (also, in part, the performance of Clang/LLVM is most important on a self-host build - correctness more broadly, but those interest in performance should likely be bootstrapping)

In any case, /if/ we're going to keep that performance feature (whereby LLVM developers can annotate types they know would pass is_trivially_copyable if it were available), probably validating its usage should be kept at the same place as the trait specializations, rather than in the usage?

Any chance of improving/changing Optional/SuccIterator to be trivially copyable when their parameters are trivially copyable?

(& is libc++'s std::pair trivially copyable when T1 and T2 are trivially copyable?)

@dblaikie I made a step forward and just relied on std::is_trivially_copyable and disabled specialization of isPodLike (using a type alias). That way the trait is always valid, and the logic is not split among different files.

include/llvm/Support/type_traits.h
40–44 ↗(On Diff #173838)

probably validating its usage should be kept at the same place as the trait specializations, rather than in the usage?

The only solutipon I have for that is to define struct isPodLike : details::isPodLike<T>, perform the check in isPodLike and have user specialize details::isPodLike but nothing would prevent them from directly specializing isPodLike so I'm not a big fan of this soltion.

My best catch would be to define isPodLike as a template alias, that would make it non-speicalizable, no need for extra check and (slightly?) degraded performance for legacy compilers. I have the patch ready for that.

Any chance of improving/changing Optional/SuccIterator to be trivially copyable when their parameters are trivially copyable?

Nop, they overload the assign operator, which need to be defaulted :-/
In the case of Optionnal, I may give it a try, but probably in another commit.

Can't do anything for std::pair :-)

FWIW, I really like the direction you and Dave are pursuing. My random thoughts about how to make progress below:

include/llvm/Support/type_traits.h
40–44 ↗(On Diff #173838)

I think, long-term, we should just be checking for std::is_trivially_copyable as that's what we actually want. And we *should* be fixing the types to actually be trivially copyable as it will also make those types fast in standard library containers.

What I'm having trouble extracting from a quick read here is:

  1. What types in LLVM do we want the memcpy optimization for which fail a modern compiler's std::is_trivially_copyable? We should fix those first IMO.
  1. What compilers / standard libraries actually cannot implement std::is_trivially_copyable? I suspect we could simulate it very closely (without the specialization hacks) on most if not all of them.

I suspect we should move this to be an llvm::is_trivially_copyable that is implemented via simulation rather than specialization. I suspect we have enough compiler smarts available now, but maybe not. Even if we have to do some limited specialization, I would suggest renaming it to make the intent super clear.

What types in LLVM do we want the memcpy optimization for which fail a modern compiler's std::is_trivially_copyable? We should fix those first IMO.

Based on the one that had a isPodLike specialization, and that don't match the std::is_trivially_copyable trait

  • std::pair<T0, T1> << this one is out of control
  • llvm::Optional<T> << I'll check that one and report
  • llvm::SuccIterator<T, U> << itou

What compilers / standard libraries actually cannot implement std::is_trivially_copyable? I suspect we could simulate it very closely (without the specialization hacks) on most if not all of them.

I'll investigate that, but wonder if it's worth the effort.

@chandlerc , @dblaikie

clang implements is_trivially_copyable since at least 3.4. gcc implements it since 5.x, and it implements std::_is_trivial which is slighlty stronger but ok since 4.X, as illustrated in https://godbolt.org/z/iBDvYp

I'm currently validating a slight update of llvm::Optional<T> that's trivially copyable when T is, so that point should be okay too.

So I'm going that way, renaming isPodLike into llvm::is_trivially_copyable, slightly improving the support for older GCC version and that should be all fine.

With `llvm::Optional` improvement

@chandlerc , @dblaikie this should be ready for review.

efriedma added inline comments.
include/llvm/ADT/Optional.h
134 ↗(On Diff #174927)

This looks almost identical to the specialization we had before r347004; does this avoid the miscompiles somehow?

include/llvm/ADT/Optional.h
134 ↗(On Diff #174927)

I double checked this commit, and yes it is important because the generic implementation is not trivially copyable: it has a non default destructor. Knowing that T is trivially copyable makes it possible to have a trivial destructor.

serge-sans-paille edited the summary of this revision. (Show Details)

Ensure that (almost) all types that used to be marked as `isPodLike` are trivially copyable by inserting the appropriate static_assert in the test suite.

Ensure that (almost) all types that used to be marked as `isPodLike` are trivially copyable by inserting the appropriate static_assert in the test suite.

What about the types which are marked as isPodLike in clang ? (eg: SourceLocation, QualType, ...)

@chandlerc, @efriedma et al. I've done some extra research and tests concerning the specialization of Optional for trivially copyable types.

There has been two set of patches:

  1. first set ( r346985, r342966, r322862 ) tries to find a workaround GCC bugs and introduces an ABI issue by specializing only for clang
  2. second set (r322859) tries to fix the gcc bug by introducing extra memove / copy instead of placement new.
  1. is definitively not a concern for this patch, has we don't have any compiler -specific specialization.
  2. is more difficult to accurately reproduce. I've tried the cited version of gcc on this godbolt instance https://godbolt.org/z/Pqh5R1 without issue, and as far as I understand, the only difference between the specialization and the default (*correct*) implementation is the removal of destructor handling. So What I'd like to try, if this review get accepeted, is just commit it and carefully track the bot's result.

Maybe using the correct definition of "trivially copyable" will fix the gcc issues with Optional, if we're lucky. I guess we can try.

Maybe using the correct definition of "trivially copyable" will fix the gcc issues with Optional, if we're lucky. I guess we can try.

I've tested building LLVM + clang and running tests using clang built on top of this patch with gcc 4.8 and I don't have any failure, so I'd say it should work. I will likely split this commit in two, so that the optional stuff can be reverted without affecting the whole `isPodLike` rewrite.

Include clang changes + prune out the Optional stuff, so that it can be validated in a separate commit.

(honestly, I think I've lost the thread on this - between the reviews to define a trivially copyable attribute (not your work, but it's happened around the same time/recently - Arther O'Dwyer's D50119 phab review), these changes, the different aspects for different compilers, the different design choices/iterations this has gone through, the different classes that need to be handled or functionality dropped, etc)

Might benefit from a current summary?

and/or might be better to separate these in some way - eg: for the obvious/easy cases where removing the isPodLike specialization is benign because is_trivially_copyable already does the right thing, those should be easy - they don't regress functionality, they work with the existing implementation, or any newer/narrower implementation, etc?

Is the patch description up to date anymore? It doesn't look like it describes the Optional changes as they are now (doesn't look like they revert r347004 currently - and if they did that'd require some care/attention to address the reasons r347004 was committed in the first place), but I'm not sure.

Quuxplusone added inline comments.
include/llvm/ADT/SmallVector.h
185 ↗(On Diff #175453)

Incidentally, unless there's a portability issue I'm not aware of, I would prefer to write this as

template <typename T, bool = is_trivially_copyable<T>::value>
class SmallVectorTemplateBase : public SmallVectorTemplateCommon<T> {

so that on line ~322 you could write simply

template <typename T>
class SmallVectorImpl : public SmallVectorTemplateBase<T> {
  using SuperClass = SmallVectorTemplateBase<T>;

without repeating your is_trivially_copyable<T>::value all over the place.

The more times you have to manually type out is_trivially_copyable<T>::value, the greater the chance you'll slip up and write std::is_trivially_copyable<T>::value on autopilot.

include/llvm/ADT/bit.h
45 ↗(On Diff #175453)

Should this say "is_trivially_copyable"?

serge-sans-paille edited the summary of this revision. (Show Details)Nov 28 2018, 12:32 AM

Might benefit from a current summary?

@dblaikie current state is a simplification of the original patch : no implementation change of llvm::Optional, nothing on SmallVector either, in order to keep it relatively simple while fixing the original UB bug. I've updated the summary accordingly.

I'll deal with Optional update in another patch.

serge-sans-paille marked an inline comment as done.Nov 28 2018, 12:36 AM
serge-sans-paille added inline comments.
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)
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 ».

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?

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?)

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.Jan 2 2019, 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.Jan 14 2019, 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
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?

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)

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
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.

169–175 ↗(On Diff #178865)

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

serge-sans-paille marked an inline comment as done.Jan 16 2019, 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.Jan 16 2019, 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.Jan 17 2019, 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.Jan 18 2019, 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.Jan 18 2019, 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.Jan 18 2019, 3:02 PM

Thanks, looks great!

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

I'm sorry to bring bad news, but this fails for our gcc 4.9.2 build, when building llvm/tools/llvm-xray/xray-converter.cpp.
Failures looks like this:

] g++   -DGTEST_HAS_RTTI=0 -D_DEBUG -D_GNU_SOURCE -D__STDC_CONSTANT_MACROS -D__STDC_FORMAT_MACROS -D__STDC_LIMIT_MACROS -Itools/llvm-xray -I/llvm/tools/llvm-xray -Iinclude -I/home/fsergeev/work/llvm-upstre
am/llvm/include -fPIC -fvisibility-inlines-hidden -Werror=date-time -std=c++11  -fdiagnostics-color -ffunction-sections -fdata-sections -O2 -g    -UNDEBUG  -fno-exceptions -fno-rtti  -c /llvm/tools/llvm-xr
ay/xray-converter.cpp 
In file included from /llvm/tools/llvm-xray/xray-converter.cpp:14:0:
/llvm/tools/llvm-xray/trie-node.h: In instantiation of ‘struct TrieNode<{anonymous}::StackIdData>’:
gcc/include/c++/4.9.2/type_traits:1183:45:   required by substitution of ‘template<class _Tp1, class _Up1, class> static std::true_type std::__is_assignable_helper<_Tp, _Up>::__test
(int) [with _Tp1 = llvm::detail::trivial_helper<TrieNode<{anonymous}::StackIdData>*>&; _Up1 = const llvm::detail::trivial_helper<TrieNode<{anonymous}::StackIdData>*>&; <template-parameter-1-3> = <missing>]’
gcc/include/c++/4.9.2/type_traits:1192:30:   required from ‘class std::__is_assignable_helper<llvm::detail::trivial_helper<TrieNode<{anonymous}::StackIdData>*>&, const llvm::detail:
:trivial_helper<TrieNode<{anonymous}::StackIdData>*>&>’
gcc/include/c++/4.9.2/type_traits:1197:12:   required from ‘struct std::is_assignable<llvm::detail::trivial_helper<TrieNode<{anonymous}::StackIdData>*>&, const llvm::detail::trivial
_helper<TrieNode<{anonymous}::StackIdData>*>&>’
gcc/include/c++/4.9.2/type_traits:1209:12:   required from ‘struct std::__is_copy_assignable_impl<llvm::detail::trivial_helper<TrieNode<{anonymous}::StackIdData>*>, true>’
gcc/include/c++/4.9.2/type_traits:1215:12:   required from ‘struct std::is_copy_assignable<llvm::detail::trivial_helper<TrieNode<{anonymous}::StackIdData>*> >’
/llvm/include/llvm/Support/type_traits.h:142:25:   required from ‘constexpr const bool llvm::is_trivially_copyable<TrieNode<{anonymous}::StackIdData>*>::has_trivial_copy_assign’
/llvm/include/llvm/Support/type_traits.h:163:32:   required from ‘constexpr const bool llvm::is_trivially_copyable<TrieNode<{anonymous}::StackIdData>*>::value’
/llvm/include/llvm/ADT/SmallVector.h:321:7:   required from ‘class llvm::SmallVectorImpl<TrieNode<{anonymous}::StackIdData>*>’
/llvm/include/llvm/ADT/SmallVector.h:845:7:   required from ‘class llvm::SmallVector<TrieNode<{anonymous}::StackIdData>*, 4u>’
/llvm/tools/llvm-xray/xray-converter.cpp:174:43:   required from here
/llvm/tools/llvm-xray/trie-node.h:38:52: error: ‘TrieNode<AssociatedData>::Callees’ has incomplete type
   llvm::SmallVector<TrieNode<AssociatedData> *, 4> Callees;
                                                    ^
In file included from /llvm/include/llvm/ADT/STLExtras.h:20:0,
                 from /llvm/include/llvm/ADT/StringRef.h:12,
                 from /llvm/include/llvm/ADT/StringMap.h:16,
                 from /llvm/include/llvm/Support/Host.h:16,
                 from /llvm/include/llvm/ADT/Hashing.h:48,
                 from /llvm/include/llvm/ADT/ArrayRef.h:12,
                 from /llvm/include/llvm/ADT/DenseMapInfo.h:16,
                 from /llvm/include/llvm/ADT/DenseMap.h:16,
                 from /llvm/tools/llvm-xray/func-id-helper.h:15,
                 from /llvm/tools/llvm-xray/xray-converter.h:16,
                 from /llvm/tools/llvm-xray/xray-converter.cpp:12:

Here I have a reproducer that shows the problem on godbolt:

https://gcc.godbolt.org/z/Tgk7M0

The same here! I don't think we should break builds of compiler versions that are still officially supported.

And the smallest testcase I'v been able to come up with:

#include <type_traits>
template<class T>
union trivial_helper {
    T t;
};
template <typename AssociatedData> struct TrieNode {
  AssociatedData ExtraData;
};
struct StackIdData {
  int x [std::is_copy_assignable<trivial_helper<TrieNode<StackIdData>*>>::value + 1];
};
...
copyable_test_small.cpp: In instantiation of ‘struct TrieNode<StackIdData>’:
gcc/include/c++/4.9.2/type_traits:1183:45:   required by substitution of ‘template<class _Tp1, class _Up1, class> static std::true_type std::__is_assignable_helper<_Tp, _Up>::__test(int) [with _Tp1 = trivial_helper<TrieNode<StackIdData>*>&; _Up1 = const trivial_helper<TrieNode<StackIdData>*>&; <template-parameter-1-3> = <missing>]’
gcc/include/c++/4.9.2/type_traits:1192:30:   required from ‘class std::__is_assignable_helper<trivial_helper<TrieNode<StackIdData>*>&, const trivial_helper<TrieNode<StackIdData>*>&>’
gcc/include/c++/4.9.2/type_traits:1197:12:   required from ‘struct std::is_assignable<trivial_helper<TrieNode<StackIdData>*>&, const trivial_helper<TrieNode<StackIdData>*>&>’
gcc/include/c++/4.9.2/type_traits:1209:12:   required from ‘struct std::__is_copy_assignable_impl<trivial_helper<TrieNode<StackIdData>*>, true>’
gcc/include/c++/4.9.2/type_traits:1215:12:   required from ‘struct std::is_copy_assignable<trivial_helper<TrieNode<StackIdData>*> >’
copyable_test_small.cpp:10:73:   required from here
copyable_test_small.cpp:7:18: error: ‘TrieNode<AssociatedData>::ExtraData’ has incomplete type
   AssociatedData ExtraData;
                  ^
copyable_test_small.cpp:9:8: error: forward declaration of ‘struct StackIdData’
 struct StackIdData {
        ^

It does not fail if trivial_helper wrapper is removed from the construct (just passing TrieNode to is_copy_assignable).
So, llvm::detail::trivial_helper triggers something inside the gcc4.9.2 traits implementation.
I'm not sure what the workaround could be...

@serge-sans-paille
This (probably) broke LLVM on Debian jessie with gcc 4.9. It fails with:

/build/llvm-toolchain-snapshot-9~svn351724/include/llvm/ADT/PointerIntPair.h: In instantiation of 'struct llvm::PointerIntPairInfo<clang::Module*, 2u, llvm::PointerLikeTypeTraits<clang::Module*> >':
/build/llvm-toolchain-snapshot-9~svn351724/tools/clang/include/clang/Lex/ModuleMap.h:158:29: required from here
/build/llvm-toolchain-snapshot-9~svn351724/include/llvm/ADT/PointerIntPair.h:133:3: error: static assertion failed: PointerIntPair with integer size too large for pointer
static_assert(IntBits <= PtrTraits::NumLowBitsAvailable,
^

Yeah, I knew from the start that compiling with gcc 8 and clang 6 was not enough for my tests. I've already fixed a few issues with gcc 6, let me try to move forward.

@Anastasia @fedor.sergeev : That's ultra painful :-/ I'm looking for a way to fix that for gcc 4.9, if I can't find a good solution I'm afraid we'll have to roll back. Thanks for providing a minimal test case.

@sylvestre.ledru I'll have a look at you problem later on.

https://godbolt.org/z/KaJ2is seems to be aportable implementaiton of `std::is_copy_assignable`. I'm investigating that.

@serge-sans-paille
This (probably) broke LLVM on Debian jessie with gcc 4.9. It fails with:

/build/llvm-toolchain-snapshot-9~svn351724/include/llvm/ADT/PointerIntPair.h: In instantiation of 'struct llvm::PointerIntPairInfo<clang::Module*, 2u, llvm::PointerLikeTypeTraits<clang::Module*> >':
/build/llvm-toolchain-snapshot-9~svn351724/tools/clang/include/clang/Lex/ModuleMap.h:158:29: required from here
/build/llvm-toolchain-snapshot-9~svn351724/include/llvm/ADT/PointerIntPair.h:133:3: error: static assertion failed: PointerIntPair with integer size too large for pointer
static_assert(IntBits <= PtrTraits::NumLowBitsAvailable,
^

Actually the issue I am seeing it this too, but I don't feel it belongs to this commit... after reverting it the build still seem to fail in the same way. Perhaps we have some other problem too.

FYI, this is failing on the polly-arm-linux builder (http://lab.llvm.org:8011/builders/polly-arm-linux). I guess that builder isn't sending emails to people who break it at the moment?

It looks like https://reviews.llvm.org/D57018 will fix it.