Page MenuHomePhabricator

ADT: Fix reference invalidation in SmallVector::push_back and single-element insert
ClosedPublic

Authored by dexonsmith on Dec 23 2020, 1:53 PM.

Details

Summary

For small enough, trivially copyable T, take the argument by value in
SmallVector::push_back and copy it when forwarding to
SmallVector::insert_one_impl. Otherwise, when growing, update the
argument appropriately.

Depends on https://reviews.llvm.org/D93777.
Split out from https://reviews.llvm.org/D91837.

Diff Detail

Event Timeline

dexonsmith created this revision.Dec 23 2020, 1:53 PM
dexonsmith requested review of this revision.Dec 23 2020, 1:53 PM
Herald added a project: Restricted Project. · View Herald TranscriptDec 23 2020, 1:53 PM
dexonsmith added inline comments.Dec 23 2020, 2:18 PM
llvm/include/llvm/ADT/SmallVector.h
235

reserveForAndGetAddressImpl is used in SmallVectorTemplateBase<T> and needs to call grow() here, but the text of the implementation does not depend on whether T is trivially copyable.

https://reviews.llvm.org/D91837#inline-875946 suggested using CRTP, but that seemed to require yet more names for SmallVector base classes and it seemed like a bit of a mess.

Actually... now I realize there is another option I'd missed: just add a CRTP parameter to SmallVectorTemplateCommon (no need for a new name). If you think that's worth trying I can try it and post an update.

dexonsmith added inline comments.Dec 23 2020, 2:24 PM
llvm/include/llvm/ADT/SmallVector.h
235

Ah, no, it's not that easy... we can't easily add new parameters to SmallVectorTemplateCommon.

/// [...] The extra dummy template argument is used by ArrayRef
/// to avoid unnecessarily requiring T to be complete.
template <typename T, typename = void>
class SmallVectorTemplateCommon

I suspect adding a DerivedT template parameter would defeat this compile-time optimization.

dblaikie added inline comments.Dec 23 2020, 3:43 PM
llvm/include/llvm/ADT/SmallVector.h
484–494

While I think it's not technically a problem (because the casted-away-const-ness pointer is never dereferenced) - I'd usually implement these the other way around. Have an implementation that uses const pointers only, then the non-const wrapper can cast-to-const, call, cast away const, and it's "clearer" (marginally, perhaps) that it's const correct because only that non-const wrapper has the interesting const handling - rather than the longer distance behavior in this implementation.

706–707

Is this correct? If ArgType differs from the container's value type, wouldn't this break? (if you insert something that's convertible to the element type, but isn't the actual element type)

I guess insert_one_maybe_copy does SFINAE, etc to ensure this is always called with the value type? So ArgType is only ever some kind of ref qualified T?

llvm/unittests/ADT/SmallVectorTest.cpp
1089–1090

I'm not following what this part of the test does - could you walk me through it?

1206–1210

I'm not following how this validates that a copy was taken (I'd have thought it'd be unobservable whether a copy was made or the pointer-index-pointer dance was done) - could you walk me through that in a bit more detail?

Rebase and respond to review feedback.

dexonsmith marked 4 inline comments as done.Mon, Jan 11, 1:11 PM

Thanks for the review! (Just coming back to this now after the holidays.)

llvm/include/llvm/ADT/SmallVector.h
484–494

Good point; I've updated ...Impl() to take/return const, and both callers now call it directly.

706–707

Correct. I added a comment and static assertion above to document this.

717–719

I added a static assert here to confirm we have a copy, since the logic relies on that.

llvm/unittests/ADT/SmallVectorTest.cpp
1089–1090

I've rewritten it (I couldn't fully make sense of it either, coming back to it). It now tests:

  • The correct value gets copied when pushing back with a reference, growing from small storage.
  • The correct value gets copied when pushing back with a reference, growing from large storage.
  • The value is actually copied, not moved (the difference is only observable for Constructable). See PushBackMoved below, where a 0 is left behind. This seems potentially worth testing in case a std::forward is missed somewhere, but i'm open to dropping that part if you think it's already covered well enough above.
1206–1210

I've rewritten this in the same way as the push_back tests.

dblaikie accepted this revision.Wed, Jan 13, 1:24 PM

Looks good, thanks!

llvm/unittests/ADT/SmallVectorTest.cpp
1089–1090

Looks good, don't have strong feelings about the last test case - take it or leave it as you see fit

This revision is now accepted and ready to land.Wed, Jan 13, 1:24 PM
dexonsmith reopened this revision.Wed, Jan 13, 7:05 PM

Reverted in 56d1ffb927d03958a7a31442596df749264a7792 due to an error on Windows:
http://lab.llvm.org:8011/#/builders/127/builds/4489/steps/7/logs/stdio
if it's obvious I'll recommit in a minute, but if anyone has ideas I'd welcome them.

This revision is now accepted and ready to land.Wed, Jan 13, 7:05 PM

Reverted in 56d1ffb927d03958a7a31442596df749264a7792 due to an error on Windows:
http://lab.llvm.org:8011/#/builders/127/builds/4489/steps/7/logs/stdio
if it's obvious I'll recommit in a minute, but if anyone has ideas I'd welcome them.

Guess maybe something in the std::is_same<std::remove_const_t<std::remove_reference_t<ArgType>>, T>::value isn't working quite right on MSVC? (could test that with godbolt, maybe) - is it needed? Since it's on both insert_one_maybe_copy and there's an implementation detail/doesn't need to protect from violations of that constraint (admittedly I'm proposing removing it because maybe MSVC is violating it... )? And instead SFINAE/enable_if only on the TakesParamByValue part?

Replacing insert_one_maybe_copy indirection with a forwarding helper called forward_value_param.

Reverted in 56d1ffb927d03958a7a31442596df749264a7792 due to an error on Windows:
http://lab.llvm.org:8011/#/builders/127/builds/4489/steps/7/logs/stdio
if it's obvious I'll recommit in a minute, but if anyone has ideas I'd welcome them.

Guess maybe something in the std::is_same<std::remove_const_t<std::remove_reference_t<ArgType>>, T>::value isn't working quite right on MSVC? (could test that with godbolt, maybe) - is it needed? Since it's on both insert_one_maybe_copy and there's an implementation detail/doesn't need to protect from violations of that constraint (admittedly I'm proposing removing it because maybe MSVC is violating it... )? And instead SFINAE/enable_if only on the TakesParamByValue part?

Thanks for looking; I think you're right. The constraint was a trick to allow use of SFINAE since TakesParamByValue didn't depend on the template parameter so I can't just remove it, I need a different solution...

...but I've found one, and it's a bit cleaner too. Instead of the indirection through insert_one_maybe_copy, I've added a forwarding function defined in the POD vs. non-POD base classes called forward_value_param.

I'll commit the new version once I confirm check-llvm passes locally.

llvm/include/llvm/ADT/SmallVector.h
370–371

In the non-POD case it just returns what it has been given.

496–497

In the POD (well, trivially move/copy constructible) case it's either T (a copy) or const T& (a reference). No need for moving since it's trivially constructible.

727–734

The new forwarding function also means we don't need to indirect through instert_one_maybe_copy.

Reverted in 56d1ffb927d03958a7a31442596df749264a7792 due to an error on Windows:
http://lab.llvm.org:8011/#/builders/127/builds/4489/steps/7/logs/stdio
if it's obvious I'll recommit in a minute, but if anyone has ideas I'd welcome them.

Guess maybe something in the std::is_same<std::remove_const_t<std::remove_reference_t<ArgType>>, T>::value isn't working quite right on MSVC? (could test that with godbolt, maybe) - is it needed? Since it's on both insert_one_maybe_copy and there's an implementation detail/doesn't need to protect from violations of that constraint (admittedly I'm proposing removing it because maybe MSVC is violating it... )? And instead SFINAE/enable_if only on the TakesParamByValue part?

Thanks for looking; I think you're right. The constraint was a trick to allow use of SFINAE since TakesParamByValue didn't depend on the template parameter so I can't just remove it, I need a different solution...

...but I've found one, and it's a bit cleaner too. Instead of the indirection through insert_one_maybe_copy, I've added a forwarding function defined in the POD vs. non-POD base classes called forward_value_param.

I'll commit the new version once I confirm check-llvm passes locally.

Yeah, looks nice/simpler to me!

This patch seems to have found a bug: in AArch64InstrInfo.cpp, there is a -Wsometimes-uninitialized warning that now triggers, and adding an assertion to make sure the value is eventually set causes a few tests to fail. The usage is DelInstrs.push_back(MUL), which I guess is how it ties in to this patch.

More details in 752fafda3dbf1f4885c64408a13ddb67c91ccb13, which gets things back to building, but doesn't do anything about the bug.

This patch seems to have found a bug: in AArch64InstrInfo.cpp, there is a -Wsometimes-uninitialized warning that now triggers, and adding an assertion to make sure the value is eventually set causes a few tests to fail. The usage is DelInstrs.push_back(MUL), which I guess is how it ties in to this patch.

More details in 752fafda3dbf1f4885c64408a13ddb67c91ccb13, which gets things back to building, but doesn't do anything about the bug.

Oh weird, I saw that too, but (wrongly) assumed it was unrelated to my change. Thanks for digging into it.

This patch seems to have found a bug: in AArch64InstrInfo.cpp, there is a -Wsometimes-uninitialized warning that now triggers, and adding an assertion to make sure the value is eventually set causes a few tests to fail. The usage is DelInstrs.push_back(MUL), which I guess is how it ties in to this patch.

More details in 752fafda3dbf1f4885c64408a13ddb67c91ccb13, which gets things back to building, but doesn't do anything about the bug.

Oh weird, I saw that too, but (wrongly) assumed it was unrelated to my change. Thanks for digging into it.

@t.p.northover, maybe you can take a look at 752fafda3dbf1f4885c64408a13ddb67c91ccb13?

Why do we even want to bend over backwards and try to handle broken code correctly,
at the cost of regressed performance for everything,
instead of just adding defensive asserts against such problems,
and letting/telling the user fix the code?

Why do we even want to bend over backwards and try to handle broken code correctly,
at the cost of regressed performance for everything,
instead of just adding defensive asserts against such problems,
and letting/telling the user fix the code?

I believe the standard library supports this, so I think it's a somewhat awkward limitation to have a standard-library-like container that misses that. (of course the small-mode isn't entirely compatible with std::vector, etc anyway - so some divergence is possible)

Why do we even want to bend over backwards and try to handle broken code correctly,
at the cost of regressed performance for everything,
instead of just adding defensive asserts against such problems,
and letting/telling the user fix the code?

I believe the standard library supports this, so I think it's a somewhat awkward limitation to have a standard-library-like container that misses that. (of course the small-mode isn't entirely compatible with std::vector, etc anyway - so some divergence is possible)

But currently the cost (compile time) is too high to be acceptable.

Why do we even want to bend over backwards and try to handle broken code correctly,
at the cost of regressed performance for everything,
instead of just adding defensive asserts against such problems,
and letting/telling the user fix the code?

I believe the standard library supports this, so I think it's a somewhat awkward limitation to have a standard-library-like container that misses that. (of course the small-mode isn't entirely compatible with std::vector, etc anyway - so some divergence is possible)

But currently the cost (compile time) is too high to be acceptable.

Perhaps - my comment was intended to address "why are we trying to support this rather than using assertions" not the compile time cost question.

The last time I tested this in https://reviews.llvm.org/D91837#2464554, the impact was much smaller. Some change between then and the landed version must have regressed things again. I think the numbers are now similar to what we saw before the "small value" optimization was added.

nikic added a comment.Thu, Jan 14, 1:07 PM

Over in D91837 the reserveForAndGetAddress() implementation contained a check for TakesParamByValue that seems to be gone in this revision. My first guess is that this is the culprit, and we're now always performing the isReferenceToStorage() check.

Over in D91837 the reserveForAndGetAddress() implementation contained a check for TakesParamByValue that seems to be gone in this revision. My first guess is that this is the culprit, and we're now always performing the isReferenceToStorage() check.

Somehow I missed the replies here until now. I came across the same thing independently: https://reviews.llvm.org/D94800.

@xbolva00, thanks for reporting the regression. After the performance analysis was finished in https://reviews.llvm.org/D91837, I split the patch up for more detailed review, and in responding to review comments I somehow lost the critical check against TakesParamByValue.

Also, @nikic, thanks for the reverts yesterday when I missed the updates here.

https://reviews.llvm.org/D94800 adds back the critical check.

Why do we even want to bend over backwards and try to handle broken code correctly,
at the cost of regressed performance for everything,
instead of just adding defensive asserts against such problems,
and letting/telling the user fix the code?

I believe the standard library supports this, so I think it's a somewhat awkward limitation to have a standard-library-like container that misses that. (of course the small-mode isn't entirely compatible with std::vector, etc anyway - so some divergence is possible)

Exactly, this is part of rectifying some unnecessary awkwardness in SmallVector. I'm 100% agreed it's not worth it with the compile-time impact you reported, but this approach seems to get the benefits without significant cost (when I don't drop critical checks...). You can see the numbers in https://reviews.llvm.org/D91837.

llvm/include/llvm/ADT/SmallVector.h
232

The cause of the regression was dropping the check against TakesParamByValue on this line when I moved this function to SmallVectorTemplateCommon...