[ADT] Fix reference invalidation when self referencing a SmallVector

[njames93]

Summary

Fix issues when calling methods from SmallVector that insert or append an item already inside a SmallVector where by the reference is invalidated when the container grows.

For example SmallVec.push_back(SmallVec[0]) If this call causes the vector to grow, SmallVec[0] will now be referencing invalid memory.
This also slightly speeds up SmallVec::Insert by only moving data after the insertion point once when the container grows.

This addresses https://bugs.llvm.org/show_bug.cgi?id=12728 and https://bugs.llvm.org/show_bug.cgi?id=16253

[njames93]

For the clang tidy naming warnings, is it better to follow the warnings, or the current convention of the file?

I haven't added specific test cases for this, but all ADT Tests did run without a hitch under asan

llvm/include/llvm/ADT/SmallVector.h

552

The function probably also needs fixing up, but there are 2 issues here, the other being the above FIXME. Would prefer to address all of that in a follow up.

[njames93]

Harden test cases for SmallVector

Make the test case Constructable track if an object has been moved as well as created and destructed.
This makes the SmallVectorTest fail without the GrowBuffer implementation.

[njames93]

Extend behaviour to more methods.

SmallVectorImpl<T>::insert(iterator, size_t, const T&);
SmallVectorImpl<T>::insert(iterator, ItTy, ItTy);

Fixed up test cases for these usages.

[nikic]

Could you please rebase this to current master? I wasn't able to git apply it. (Sorry, Phabricator troubles. It's hard to believe that a code review tool is incapable of properly retaining merge bases.)

[njames93]

Rebased trunk and fixed up assign to use new buffer

[njames93]

In D87326#2265246, @nikic wrote:

Could you please rebase this to current master? I wasn't able to git apply it. (Sorry, Phabricator troubles. It's hard to believe that a code review tool is incapable of properly retaining merge bases.)

To be fair it wasn't a simple automatic merge fix, the last commit to the affected file definitely conflicted this patch

[njames93]

Add buffer to append(iterator, iterator) to handle SmallVec.append(SmallVec.begin(), SmallVec.end());

[njames93]

Fix build error when appending iterators of types convertible to SmallVector::value_type

[nikic]

Here's the compile-time impact I see with this change:

1.2% regression in instructions retired: https://llvm-compile-time-tracker.com/compare.php?from=3c42c0dcf631ad6b90e718df895c05f79718659f&to=606330864b2349e29beb460ae69fa41c0170674e&stat=instructions
1.0% max-rss regression: https://llvm-compile-time-tracker.com/compare.php?from=3c42c0dcf631ad6b90e718df895c05f79718659f&to=606330864b2349e29beb460ae69fa41c0170674e&stat=max-rss

The max-rss regression is presumably due to an increase in clang binary size. Manually checking the data, size-text goes from 80490755 to 81122130, i.e. 0.8% increase.

[njames93]

In D87326#2265673, @nikic wrote:

Here's the compile-time impact I see with this change:

1.2% regression in instructions retired: https://llvm-compile-time-tracker.com/compare.php?from=3c42c0dcf631ad6b90e718df895c05f79718659f&to=606330864b2349e29beb460ae69fa41c0170674e&stat=instructions
1.0% max-rss regression: https://llvm-compile-time-tracker.com/compare.php?from=3c42c0dcf631ad6b90e718df895c05f79718659f&to=606330864b2349e29beb460ae69fa41c0170674e&stat=max-rss

The max-rss regression is presumably due to an increase in clang binary size. Manually checking the data, size-text goes from 80490755 to 81122130, i.e. 0.8% increase.

What build flags are you using. I tried a release build with thinlto. Also tried to move some of this code into the cpp file by type erasing the template out of GrowBufferBase.
For the record I'm testing on a Ryzen 2600X on ubuntu 20.04 and using clang-10 as the host compiler and linking with lld-10

trunk      - size.text = 42483D6, size.binary = 6141438
this       - size.text = 3EBD276, size.binary = 5DDD940
type-erase - size.text = 3EC0B26, size.binary = 5DE1290

[xbolva00]

This comment was removed by xbolva00.

[lattner]

Thank you for working on this! I don't have cycles for a detailed review of the patch, but I'm thrilled to see this footgun get fixed.

[dblaikie]

I believe I filed the second bug ( https://bugs.llvm.org/show_bug.cgi?id=16253 ) a while back because I tried to do it myself (admittedly, it was myself 7 years ago, so maybe my perspective has changed over the years) and found it too difficult. That there were corner cases or something that made me unsure how to move forward - so I filed the bug and forgot about it.

Wish I'd written down more of what those corner cases were... let's see what I can construct from what I did say in the bug.

r183465: Clearly a workaround for this bug (or a fix for an incorrect use of SmallVector, if we deem this use to be out of contract for SmallVector), though a somewhat confusing/unclear commit message to justify it.
r183459: Another of the same

Hmm - I think maybe what I had trouble with was understanding how much this shuold generalize. Should this handle subranges? (if you try to append half of a vector onto itself) and if so, how? Anyone happen to know what's guaranteed by the standard (perhaps only push_back of single elements - that's easier to handle)

In D87326#2263471, @njames93 wrote:

For the clang tidy naming warnings, is it better to follow the warnings, or the current convention of the file?

Current convention of the file, thanks!

I haven't added specific test cases for this, but all ADT Tests did run without a hitch under asan

Did they run without a hitch under asan before the change too? I imagine so.

So probably worth adding specific tests for overlapping - ones that would've failed under asan before this change, but pass with it.

The test updates you have done in the patch so far - they're intended to make the test coverage a bit more robust to have more confidence over the refactoring? Could those test changes be committed first/separately - I assume they're intended to pass before and after the patch? So might be good as a preliminary/separate patch before this one.

llvm/include/llvm/ADT/SmallVector.h

334

Prefer range-based-for rather than std::for_each, probably (here and below)?

[njames93]

In D87326#2269286, @dblaikie wrote:

Hmm - I think maybe what I had trouble with was understanding how much this shuold generalize. Should this handle subranges? (if you try to append half of a vector onto itself) and if so, how? Anyone happen to know what's guaranteed by the standard (perhaps only push_back of single elements - that's easier to handle)

From what I can see insert and append fully support when the range to insert is enclosed by the vector, however assign makes no such promise as it would potentially require allocating more storage even if the container itself doesn't need to grow

I haven't added specific test cases for this, but all ADT Tests did run without a hitch under asan

Did they run without a hitch under asan before the change too? I imagine so.

They did but that was only because the test cases don't grow multiple times from what I can see

So probably worth adding specific tests for overlapping - ones that would've failed under asan before this change, but pass with it.

The test updates you have done in the patch so far - they're intended to make the test coverage a bit more robust to have more confidence over the refactoring? Could those test changes be committed first/separately - I assume they're intended to pass before and after the patch? So might be good as a preliminary/separate patch before this one.

The code to make the tests more robust fail without the modifications to small vector as they expose issues for insert moving an already deleted item.

[MaskRay]

Yeah, seems that SmallVector::push_back should be fixed to allow a.push_back(a[0]). SmallVector::insert has been fixed in rL134554

[dblaikie]

In D87326#2269455, @njames93 wrote:

In D87326#2269286, @dblaikie wrote:

Hmm - I think maybe what I had trouble with was understanding how much this shuold generalize. Should this handle subranges? (if you try to append half of a vector onto itself) and if so, how? Anyone happen to know what's guaranteed by the standard (perhaps only push_back of single elements - that's easier to handle)

From what I can see insert and append fully support when the range to insert is enclosed by the vector, however assign makes no such promise as it would potentially require allocating more storage even if the container itself doesn't need to grow

Makes sense.

I haven't added specific test cases for this, but all ADT Tests did run without a hitch under asan

Did they run without a hitch under asan before the change too? I imagine so.

They did but that was only because the test cases don't grow multiple times from what I can see

Hmm - I thought this was about self-referential inserts/push_back, etc? Was/is there also bugs related to multiple growth? Could you show a small test case that'd fail asan with the current in-tree code related to multiple growth?

So probably worth adding specific tests for overlapping - ones that would've failed under asan before this change, but pass with it.

The test updates you have done in the patch so far - they're intended to make the test coverage a bit more robust to have more confidence over the refactoring? Could those test changes be committed first/separately - I assume they're intended to pass before and after the patch? So might be good as a preliminary/separate patch before this one.

The code to make the tests more robust fail without the modifications to small vector as they expose issues for insert moving an already deleted item.

Ah, I see now the new code avoids extra moves - the old code would grow the container, then insert the elements - which could cause an extra shift of elements after the insertion point to then make space for the to-be-inserted elements. Great to have that fixed too, but I think there should be at least some test coverage for the self-insertion otherwise we could keep the efficiency gains but accidentally break the self-insertion(self-push back, etc) by doing the same operations, but in the wrong order (eg: moving over to the new buffer first, then inserting the new elements, rather than new elements first, then old elements).

In D87326#2269796, @MaskRay wrote:

Yeah, seems that SmallVector::push_back should be fixed to allow a.push_back(a[0]). SmallVector::insert has been fixed in rL134554

Ah, right, sort of a related but maybe slightly different problem - when not resizing the underlying buffer, elements are moved, then the new one is inserted so the reference may've been invalidated. Probably best to handle that in a separate/follow-up commit - any idea if the C++ standard guarantees this for std::vector, for instance? And if so, how does libc++ implement this guarantee?

llvm/include/llvm/ADT/SmallVector.h

582–584

Could this use a range-based for loop? (I realize that'd mean moving the increment into the loop - so totally OK if you reckon that'd be less readable)

Can also drop the {} on single-line constructs like this. (& the if == size above)

llvm/unittests/ADT/SmallVectorTest.cpp

35

Maybe Destroyed rather than Invalid (& I think MovedFrom is maybe the more common phrasing than MovedOut)

Could use an enum class so you don't need to have the OS_ prefix, instead ObjectState::Constructed, etc?

[dblaikie]

In D87326#2269796, @MaskRay wrote:

Yeah, seems that SmallVector::push_back should be fixed to allow a.push_back(a[0]). SmallVector::insert has been fixed in rL134554

Ah, right, sort of a related but maybe slightly different problem - when not resizing the underlying buffer, elements are moved, then the new one is inserted so the reference may've been invalidated. Probably best to handle that in a separate/follow-up commit - any idea if the C++ standard guarantees this for std::vector, for instance? And if so, how does libc++ implement this guarantee?

Ah, I see at the end of rL134554 "Thanks to Howard Hinnant for clarifying the correct behavior, and explaining how std::vector solves this problem." - so I guess it does guarantee it, and implements it in the same way, by testing address/fixing up the address.

[njames93]

Address a few inlines

[njames93]

In D87326#2269796, @MaskRay wrote:

Yeah, seems that SmallVector::push_back should be fixed to allow a.push_back(a[0]). SmallVector::insert has been fixed in rL134554

It hasn't, that handles the case where the element to insert is moved when shifting the elements down to make room, but not when the element to insert is moved because of container growth.

In D87326#2269802, @dblaikie wrote:

They did but that was only because the test cases don't grow multiple times from what I can see

Hmm - I thought this was about self-referential inserts/push_back, etc? Was/is there also bugs related to multiple growth? Could you show a small test case that'd fail asan with the current in-tree code related to multiple growth?

When I say grow multiple times, I mean the container has already grown once, then when the call to insert etc is made the container grows a second time. In that case the element to insert would now be in freed memory which would cause asan to fail. However right now that test case doesn't seem to appear, it does happen where the container grows from small size to insert. but as the memory is stack based there, its fine, from asans POV, to reference it.
In D87237, I experimented by putting asan instrumentation inside SmallVector, which caused a test case to fail when ran under asan.

[dblaikie]

In D87326#2270142, @njames93 wrote:

In D87326#2269796, @MaskRay wrote:

Yeah, seems that SmallVector::push_back should be fixed to allow a.push_back(a[0]). SmallVector::insert has been fixed in rL134554

It hasn't, that handles the case where the element to insert is moved when shifting the elements down to make room, but not when the element to insert is moved because of container growth.

Yeah, agreed. rL134554 was only half the fix (fixing the non-growth case). Your/this patch now fixes the other half (the growth case) and fixes the push_back case (which only has a problem on growth, doesn't have a problem on non-growth, unlike insert). Great! :)

In D87326#2269802, @dblaikie wrote:

They did but that was only because the test cases don't grow multiple times from what I can see

Hmm - I thought this was about self-referential inserts/push_back, etc? Was/is there also bugs related to multiple growth? Could you show a small test case that'd fail asan with the current in-tree code related to multiple growth?

When I say grow multiple times, I mean the container has already grown once,

You mean the container is in non-small mode? (it might not've grown to get there - it might've been initialized with too much data to fit in the small buffer - though I guess that still might look like "growth" so we're probably on the same page here).

then when the call to insert etc is made the container grows a second time. In that case the element to insert would now be in freed memory which would cause asan to fail. However right now that test case doesn't seem to appear, it does happen where the container grows from small size to insert. but as the memory is stack based there, its fine, from asans POV, to reference it.
In D87237, I experimented by putting asan instrumentation inside SmallVector, which caused a test case to fail when ran under asan.

OK, so I think you're saying - the current in-tree tests, and the tests you're adding, currently don't fail even though they do test self-insertion only because they're testing in small -> big (not big -> big) mode? But with ASan instrumented SmallVector, even a small->big would cause test failures of the existing tests, without this patch to fix self-insertion?

[njames93]

In D87326#2270332, @dblaikie wrote:

In D87326#2270142, @njames93 wrote:

In D87326#2269796, @MaskRay wrote:

Yeah, seems that SmallVector::push_back should be fixed to allow a.push_back(a[0]). SmallVector::insert has been fixed in rL134554

It hasn't, that handles the case where the element to insert is moved when shifting the elements down to make room, but not when the element to insert is moved because of container growth.

Yeah, agreed. rL134554 was only half the fix (fixing the non-growth case). Your/this patch now fixes the other half (the growth case) and fixes the push_back case (which only has a problem on growth, doesn't have a problem on non-growth, unlike insert). Great! :)

Yeah thats whats happening here.

then when the call to insert etc is made the container grows a second time. In that case the element to insert would now be in freed memory which would cause asan to fail. However right now that test case doesn't seem to appear, it does happen where the container grows from small size to insert. but as the memory is stack based there, its fine, from asans POV, to reference it.
In D87237, I experimented by putting asan instrumentation inside SmallVector, which caused a test case to fail when ran under asan.

OK, so I think you're saying - the current in-tree tests, and the tests you're adding, currently don't fail even though they do test self-insertion only because they're testing in small -> big (not big -> big) mode? But with ASan instrumented SmallVector, even a small->big would cause test failures of the existing tests, without this patch to fix self-insertion?

The tests inside Constructable will cause the current in-tree self-insertion test to fail as that will detect copying from a destructed value in the call to insert. The asan instrumented SmallVector would also fail because it will detect accessing the poisoned inline buffer in the small->big growth. However with this patch both of these causes of failing tests will be fixed.

[njames93]

Fix for the case if anyone tries SmallVector.emplace_back(SmallVector[X]) being invalidated on growth.
Added missing else if inside SmallVector append methods.
Refactored GrowBufferBase to take the Size_T as the template arguments to reduce template instantiations.
Use global namespace new inside GrowBuffer.

[njames93]

Move grow_size into SmallVectorBase

It can live in here as it doesn't require any specific machinery from SmallVectorTemplateCommon.
This also decreases the number of template instantiations needed for the function.

[njames93]

Format was provided by clang-format-11. the pre-merge bot is using 10 so I think I should ignore the format messages.

[dblaikie]

then when the call to insert etc is made the container grows a second time. In that case the element to insert would now be in freed memory which would cause asan to fail. However right now that test case doesn't seem to appear, it does happen where the container grows from small size to insert. but as the memory is stack based there, its fine, from asans POV, to reference it.
In D87237, I experimented by putting asan instrumentation inside SmallVector, which caused a test case to fail when ran under asan.

OK, so I think you're saying - the current in-tree tests, and the tests you're adding, currently don't fail even though they do test self-insertion only because they're testing in small -> big (not big -> big) mode? But with ASan instrumented SmallVector, even a small->big would cause test failures of the existing tests, without this patch to fix self-insertion?

The tests inside Constructable will cause the current in-tree self-insertion test to fail as that will detect copying from a destructed value in the call to insert. The asan instrumented SmallVector would also fail because it will detect accessing the poisoned inline buffer in the small->big growth. However with this patch both of these causes of failing tests will be fixed.

Ah, makes sense - sweet!

Use global namespace new inside GrowBuffer.

Why this change? Would've thought op new overloads might be desirable, but I certainly don't know the specifics off-hand right now.

llvm/include/llvm/ADT/SmallVector.h

315–316

Do these (and other) member function calls need to be qualified with "this->"? If not, please remove that. (usually only see that needed when it's a call into a dependent base class, right?)

344

Generally prefer range-based-for loops rather than std/llvm::for_each (about the only time I might suggest for_each would be if you had an existing lambda to pass)

566

what was wrong/happening in the absence of these "else" clauses? were tests failing? I guess the fill was happening twice, maybe? That should've failed the tests with the tighter constraints you added, right? Did it?

[njames93]

In D87326#2272611, @dblaikie wrote:

Use global namespace new inside GrowBuffer.

Why this change? Would've thought op new overloads might be desirable, but I certainly don't know the specifics off-hand right now.

SmallVector seems to use global namespace new for all its operations, so I thought I'd follow the convention there.

llvm/include/llvm/ADT/SmallVector.h

566

Technically nothing wrong is happening without this else. In the case where NumElts == this->size() it'll just copy to copy assign the whole vector with Elt twice. Which while bad for performance it isn't breaching any object lifetime rules. The reason no tests fail is because the tests for SmallVector::assign, just check if the contents of the SmallVector are correct, not how many times constructors and assignment operators were called.

[njames93]

Remove excessive this-> from GrowBuffer.
Use range-based loop instead of for_each.

[dblaikie]

In D87326#2272934, @njames93 wrote:

In D87326#2272611, @dblaikie wrote:

Use global namespace new inside GrowBuffer.

Why this change? Would've thought op new overloads might be desirable, but I certainly don't know the specifics off-hand right now.

SmallVector seems to use global namespace new for all its operations, so I thought I'd follow the convention there.

Fair enough - thanks for walking me through it.

llvm/include/llvm/ADT/SmallVector.h

566

Could you make the tests a bit more rigorous to test for this fix?

[njames93]

Add tests for SmallVector::assign to ensure contents aren't copied excessive amounts of times.

[dblaikie]

Great, thanks a bunch!

llvm/unittests/ADT/SmallVectorTest.cpp

478–480

Worth testing for the specific amounts separately, or does it vary over the test variations?

[MaskRay]

I have checked every GrowBuffer<T> use site. They look good!

llvm/include/llvm/ADT/SmallVector.h

354

The libc++ implementation (__swap_out_circular_buffer) returns a pointer so that the call sites do not need this->begin() + EltNo. Have you thought about adopting it?

[nikic]

Tested the newest version of this patch and I'm still seeing massive regressions, even larger than before.

Compile-time (instructions retired): https://llvm-compile-time-tracker.com/compare.php?from=cc947207283f934c72af0eb0b1a08978c59d40a2&to=d99c6d441764431519c1c11d490e7e88ffe06775&stat=instructions This is now a 1.4% geomean regression at O3, with 2% at O3, with tramp3d-v4 hitting 3%.

Max RSS: https://llvm-compile-time-tracker.com/compare.php?from=cc947207283f934c72af0eb0b1a08978c59d40a2&to=d99c6d441764431519c1c11d490e7e88ffe06775&stat=max-rss This is now a 1.6% geomean regression at O3, with 2.1% at O0.

Clang text size goes from 80560905 to 82179908, a 2% regression (non-LTO build using GCC 9.3).

[dblaikie]

In D87326#2273355, @nikic wrote:

Tested the newest version of this patch and I'm still seeing massive regressions, even larger than before.

Compile-time (instructions retired): https://llvm-compile-time-tracker.com/compare.php?from=cc947207283f934c72af0eb0b1a08978c59d40a2&to=d99c6d441764431519c1c11d490e7e88ffe06775&stat=instructions This is now a 1.4% geomean regression at O3, with 2% at O3, with tramp3d-v4 hitting 3%.

Max RSS: https://llvm-compile-time-tracker.com/compare.php?from=cc947207283f934c72af0eb0b1a08978c59d40a2&to=d99c6d441764431519c1c11d490e7e88ffe06775&stat=max-rss This is now a 1.6% geomean regression at O3, with 2.1% at O0.

Clang text size goes from 80560905 to 82179908, a 2% regression (non-LTO build using GCC 9.3).

@njames93 - mind looking at the memory usage a bit? that's probably relatively easy to check (well, maybe not, since it'll be smeared over all the different instantiations of this template) & seems a bit surprising. Code growth is probably just what it is - but if there's a way to quantify it and check we've got minimal extra instantiations, that'd be good.

The compile-time stat: @nikic: can you measure a wall performance difference? (otherwise possible they're shorter instructions, etc/ doesn't necessarily mean this makes compile times worse, perhaps?)

[njames93]

In D87326#2273355, @nikic wrote:

Tested the newest version of this patch and I'm still seeing massive regressions, even larger than before.

Compile-time (instructions retired): https://llvm-compile-time-tracker.com/compare.php?from=cc947207283f934c72af0eb0b1a08978c59d40a2&to=d99c6d441764431519c1c11d490e7e88ffe06775&stat=instructions This is now a 1.4% geomean regression at O3, with 2% at O3, with tramp3d-v4 hitting 3%.

Max RSS: https://llvm-compile-time-tracker.com/compare.php?from=cc947207283f934c72af0eb0b1a08978c59d40a2&to=d99c6d441764431519c1c11d490e7e88ffe06775&stat=max-rss This is now a 1.6% geomean regression at O3, with 2.1% at O0.

Clang text size goes from 80560905 to 82179908, a 2% regression (non-LTO build using GCC 9.3).

I'm still seeing a different picture with clang-10 as the host compiler, I'm only targetting x86 which explains why my binaries are so much smaller than yours.

orig-o3  54404996
this-03  54046228
orig-lto 69549814
this-lto 65981798

The most likely reason for a larger binary in GCC is in the original file, the calls to grow weren't inlined. Now, most of that code for using a new buffer is inlined. Clang may handle things a little differently.
Maybe I could define the swap buffer methods out of line to dissuade inlining.

llvm/unittests/ADT/SmallVectorTest.cpp

478–480

If the container grows there will be 2 copy constructors called, if it doesn't, there is one copy constructor and one copy assign.

[njames93]

@nikic Would you be able to see what the delta with this is https://gist.github.com/njames93/f26f159f06bda9e7ed2270adb39d9b08, should apply on top of trunk. It has the most expensive part of the grow buffer defined outline to dissuade inlining, may reduce binary size and improve performance with gcc9.3

[dblaikie]

In D87326#2273410, @dblaikie wrote:

In D87326#2273355, @nikic wrote:

Tested the newest version of this patch and I'm still seeing massive regressions, even larger than before.

Compile-time (instructions retired): https://llvm-compile-time-tracker.com/compare.php?from=cc947207283f934c72af0eb0b1a08978c59d40a2&to=d99c6d441764431519c1c11d490e7e88ffe06775&stat=instructions This is now a 1.4% geomean regression at O3, with 2% at O3, with tramp3d-v4 hitting 3%.

Max RSS: https://llvm-compile-time-tracker.com/compare.php?from=cc947207283f934c72af0eb0b1a08978c59d40a2&to=d99c6d441764431519c1c11d490e7e88ffe06775&stat=max-rss This is now a 1.6% geomean regression at O3, with 2.1% at O0.

Clang text size goes from 80560905 to 82179908, a 2% regression (non-LTO build using GCC 9.3).

@njames93 - mind looking at the memory usage a bit? that's probably relatively easy to check (well, maybe not, since it'll be smeared over all the different instantiations of this template) & seems a bit surprising. Code growth is probably just what it is - but if there's a way to quantify it and check we've got minimal extra instantiations, that'd be good.

The compile-time stat: @nikic: can you measure a wall performance difference? (otherwise possible they're shorter instructions, etc/ doesn't necessarily mean this makes compile times worse, perhaps?)

Oh, also - any chance you can get measurements with a self-host clang? (either a full two-stage bootstrap, or an LLVM 10 or 11 used to build)

llvm/unittests/ADT/SmallVectorTest.cpp

478–480

Ah, thanks!

[nikic]

In D87326#2273732, @njames93 wrote:

@nikic Would you be able to see what the delta with this is https://gist.github.com/njames93/f26f159f06bda9e7ed2270adb39d9b08, should apply on top of trunk. It has the most expensive part of the grow buffer defined outline to dissuade inlining, may reduce binary size and improve performance with gcc9.3

Unfortunately this makes things even worse, with clang binary size increasing from 80560905 to 85871535 bytes, which is an increase of 6.5%. Max RSS goes up by 3-5% accordingly.

Before looking further into what exactly is going on there, I would like to take a step back and ask whether this change is really necessary. SmallVector is some of the most performance-critical code in the LLVM project and has tens of thousands of use-sites that magnify any change to it. Given what this patch does, I think that at least some degree of either performance of code-size impact is not avoidable (though the exact impact can be mitigated). This also makes the implementation of SmallVector quite a bit more complex, with subtle invariants to upkeep.

The problem this patch is solving seems like something of an edge-case to me, and specifying that "inserting self-references requires up-front reservation of enough capacity" seems like a sufficient solution (possibly combined with some assertions to make this checkable without asan). LLVM's ADT library is thankfully in a position where it does not need to comply with the std::vector spec to the letter, and can deviate from it where useful. For example, the LLVM programming manual mentions that SmallVector forgoes some exception-safety guarantees to achieve better performance. This seems like a similar situation.

I'm sure that if sufficient effort is put into it, it's possible to make this change with a lower impact. I looked at the libc++ implementation a bit, and there are a few differences that stand out, e.g. libc++ more carefully splits the inline fast-path from the out-of-line slow-path for methods like push_back. It also seems like it provides weaker guarantees on some methods, e.g. the assign() implementation does not look grow-safe at all. Figuring out what the most efficient way to do this is would take a lot of time though, as it would involve reapplying this patch in pieces, measuring the impact individual parts have, and trying out variations. If it's necessary to do this across two different host compilers that evidently have quite different optimization behavior in this area, this becomes even more involved. So again the question: Is it really necessary?

[dblaikie]

I don't fundamentally mind not supporting this - especially with asan checks that might help catch clients in the codebase that violate the contract. But I'm guessing there's existing violations in the codebase given the previous patches/filed bugs about implementing this behavior.

[njames93]

So, I think either this patch needs to be landed after some tweaking to try and bring the compile size down, though as it only appears to be an issue with clang it can probably afford some regression on gcc. Or we explicitly state that small vector is not safe to self reference itself and add instrumentation to enforce that behaviour. Right now we are in a middle ground where there are some guarantees made but not enough.
I would hedge my bets that there are definitely some code clients(whether in tree or not) that are currently using SmallVector incorrectly and sometimes run into little bugs like this.
Also for the record I have just built with gcc and noticed the same kind of regressions on the text size so at least I can have a look into this myself

[xbolva00]

Tested the newest version of this patch and I'm still seeing massive regressions, even larger than before.

^.

People are hard working to improve compile times and patch like this can just kill their improvements.

I dont think we this is worth it. You can try to create SmallVectorXYZ to handle this case and be strict for SmallVector.

[njames93]

Tried to control binary size when compiling for gcc. Reworked everything here (apart from the test cases)

@nikic I'd appreciate if you could test benchmark this diff using the compile time tracker.

[nikic]

Here's the numbers I see with the current version of the patch:

Instructions: https://llvm-compile-time-tracker.com/compare.php?from=4b7dafd9046f0ceaadacaafe0ea4a1fb00cf70a5&to=24b013b651f8f204f633d2edffa0baa7b121e21b&stat=instructions 1.26% regression at O3, 1.72% at O0-g
Max-rss: https://llvm-compile-time-tracker.com/compare.php?from=4b7dafd9046f0ceaadacaafe0ea4a1fb00cf70a5&to=24b013b651f8f204f633d2edffa0baa7b121e21b&stat=max-rss 1.64% regression at O3, 3.55% at O0-g
Clang binary size: 82132053 to 82490366 which is an 0.4% increase

Peculiarly, even though the increase in clang binary size is indeed greatly mitigated (0.4%, where the last version had a 6.5% increase), the impact on max-rss does not seem mitigated. Maybe my assumption that the max-rss increase is caused entirely by the binary size increase was not correct.

[MaskRay]

If the regressions on the 'max-rss' and 'instructions' metrics cannot be addressed, maybe we should unsupport this usage. We may need a check. If it increases LLVM_ENABLE_ASSERTIONS time significantly, this can be an EXPENSIVE_CHECKS check.

[njames93]

Overhead is likely caused by slightly more code needing to be emitted. However there is a glaring hole here that SmallVector isn't very smart about how it should take paramaters for calls like push_back.
For small trivial types it makes sense to take those by value and in those instances the current implementation of just calling grow would have no issue about reference invalidation as there no longer a reference.
Downside is it would require copying most of the small vector implementation code for this special case, kind of like what currently happens for SmallVectorTemplateBase with trivially copyable types.

Given that a lot of use cases of SmallVector seem to be for storing pointers or as the base class for SmallString, this would remove this specific overhead in these cases.

[dexonsmith]

In D87326#2352570, @njames93 wrote:

Overhead is likely caused by slightly more code needing to be emitted. However there is a glaring hole here that SmallVector isn't very smart about how it should take paramaters for calls like push_back.
For small trivial types it makes sense to take those by value and in those instances the current implementation of just calling grow would have no issue about reference invalidation as there no longer a reference.
Downside is it would require copying most of the small vector implementation code for this special case, kind of like what currently happens for SmallVectorTemplateBase with trivially copyable types.

Given that a lot of use cases of SmallVector seem to be for storing pointers or as the base class for SmallString, this would remove this specific overhead in these cases.

That seems really valuable, and could be committed separately/ahead of the rest of this patch. I don't think you need to split the template; you can just:

using ParamT = std::conditional<should_take_by_value<T>, T, const T&>;
void push_back(ParamT Val);

Note also https://reviews.llvm.org/D84293, which proposes adding an assertion when growing is unsafe.

[dexonsmith]

In D87326#2395162, @dexonsmith wrote:

Downside is it would require copying most of the small vector implementation code for this special case, kind of like what currently happens for SmallVectorTemplateBase with trivially copyable types.

Given that a lot of use cases of SmallVector seem to be for storing pointers or as the base class for SmallString, this would remove this specific overhead in these cases.

That seems really valuable, and could be committed separately/ahead of the rest of this patch.

Here's a quick attempt at it: https://reviews.llvm.org/D91467

[dexonsmith]

FYI, I landed assertions for various reference invalidations in https://reviews.llvm.org/D91744.

I wonder if this patch could be landed incrementally, fixing one API at a time from the bottom up. For example, we might start with just push_back or assign, hopefully side-stepping any compile-time regression by incorporating the relevant parts of https://reviews.llvm.org/D91467 to skip the slow path for small enough, trivial T.

llvm/include/llvm/ADT/SmallVector.h

 //===- llvm/ADT/SmallVector.h - 'Normally small' vectors --------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file defines the SmallVector class.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ADT_SMALLVECTOR_H
 #define LLVM_ADT_SMALLVECTOR_H
 
+#include "llvm/ADT/PointerIntPair.h"
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Support/MemAlloc.h"
 #include "llvm/Support/type_traits.h"
 #include <algorithm>
 #include <cassert>
 #include <cstddef>
 #include <cstdlib>
 #include <cstring>
 #include <initializer_list>
 #include <iterator>
 #include <limits>
 #include <memory>
 #include <new>
 #include <type_traits>
 #include <utility>
 
 namespace llvm {
 
+template <class Size_T> class GrowBufferBase {
+private:
+  llvm::PointerIntPair<void *, 1, bool> PtrAndNeedsFree;
+  Size_T Size;
+
+public:
+  Size_T getSize() const { return Size; }
+  void setSize(Size_T NewSize) { Size = NewSize; }
+
+  void *getBegin() const { return PtrAndNeedsFree.getPointer(); }
+  void setBegin(void *Ptr) { PtrAndNeedsFree.setPointer(Ptr); }
+
+  bool getNeedsFree() const { return PtrAndNeedsFree.getInt(); }
+  void setNeedsFree(bool Val) { PtrAndNeedsFree.setInt(Val); }
+};
+
 /// This is all the stuff common to all SmallVectors.
 ///
 /// The template parameter specifies the type which should be used to hold the
 /// Size and Capacity of the SmallVector, so it can be adjusted.
 /// Using 32 bit size is desirable to shrink the size of the SmallVector.
 /// Using 64 bit size is desirable for cases like SmallVector<char>, where a
 /// 32 bit size would limit the vector to ~4GB. SmallVectors are used for
 /// buffering bitcode output - which can exceed 4GB.
 template <class Size_T> class SmallVectorBase {
 protected:
   void *BeginX;
   Size_T Size = 0, Capacity;
 
   /// The maximum value of the Size_T used.
   static constexpr size_t SizeTypeMax() {
     return std::numeric_limits<Size_T>::max();
   }
 
   SmallVectorBase() = delete;
   SmallVectorBase(void *FirstEl, size_t TotalCapacity)
       : BeginX(FirstEl), Capacity(TotalCapacity) {}
 
+  size_t grow_size(size_t MinSize);
+
   /// This is an implementation of the grow() method which only works
   /// on POD-like data types and is out of line to reduce code duplication.
   /// This function will report a fatal error if it cannot increase capacity.
   void grow_pod(void *FirstEl, size_t MinSize, size_t TSize);
 
+  GrowBufferBase<Size_T> split_grow_impl(void *FirstEl, size_t MinSize,
+                                         size_t TSize);
+
+  void finish_grow(const GrowBufferBase<Size_T> &Buffer, size_t TSize);
+
   /// Report that MinSize doesn't fit into this vector's size type. Throws
   /// std::length_error or calls report_fatal_error.
   LLVM_ATTRIBUTE_NORETURN static void report_size_overflow(size_t MinSize);
   /// Report that this vector is already at maximum capacity. Throws
   /// std::length_error or calls report_fatal_error.
   LLVM_ATTRIBUTE_NORETURN static void report_at_maximum_capacity();
 
 public:

 
 /// This is the part of SmallVectorTemplateBase which does not depend on whether
 /// the type T is a POD. The extra dummy template argument is used by ArrayRef
 /// to avoid unnecessarily requiring T to be complete.
 template <typename T, typename = void>
 class SmallVectorTemplateCommon
     : public SmallVectorBase<SmallVectorSizeType<T>> {
   using Base = SmallVectorBase<SmallVectorSizeType<T>>;
+  using GrowBuffer = GrowBufferBase<SmallVectorSizeType<T>>;
 
   /// Find the address of the first element.  For this pointer math to be valid
   /// with small-size of 0 for T with lots of alignment, it's important that
   /// SmallVectorStorage is properly-aligned even for small-size of 0.
   void *getFirstEl() const {
     return const_cast<void *>(reinterpret_cast<const void *>(
         reinterpret_cast<const char *>(this) +
         offsetof(SmallVectorAlignmentAndSize<T>, FirstEl)));
   }
   // Space after 'FirstEl' is clobbered, do not add any instance vars after it.
 
 protected:
   SmallVectorTemplateCommon(size_t Size) : Base(getFirstEl(), Size) {}
 
   void grow_pod(size_t MinSize, size_t TSize) {
     Base::grow_pod(getFirstEl(), MinSize, TSize);
   }
 
+  GrowBuffer split_grow_common(size_t MinSize, size_t TSize) {
+    return this->split_grow_impl(getFirstEl(), MinSize, TSize);
+  }
+
+  void finish_grow_pod(const GrowBuffer &Buffer, size_t TSize) {
+    Base::finish_grow(Buffer, TSize);
+  }
+
   /// Return true if this is a smallvector which has not had dynamic
   /// memory allocated for it.
   bool isSmall() const { return this->BeginX == getFirstEl(); }
 
   /// Put this vector in a state of being small.
   void resetToSmall() {
     this->BeginX = getFirstEl();
     this->Size = this->Capacity = 0; // FIXME: Setting Capacity to 0 is suspect.

 /// This catches the important case of std::pair<POD, POD>, which is not
 /// trivially assignable.
 template <typename T, bool = (is_trivially_copy_constructible<T>::value) &&
                              (is_trivially_move_constructible<T>::value) &&
                              std::is_trivially_destructible<T>::value>
 class SmallVectorTemplateBase : public SmallVectorTemplateCommon<T> {
 protected:
   SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {}
+  using GrowBuffer = GrowBufferBase<SmallVectorSizeType<T>>;
 
   static void destroy_range(T *S, T *E) {
     while (S != E) {
       --E;
       E->~T();
     }
   }
 
static void uninitialized_copy(It1 I, It1 E, It2 Dest) {
     std::uninitialized_copy(I, E, Dest);
   }
 
   /// Grow the allocated memory (without initializing new elements), doubling
   /// the size of the allocated memory. Guarantees space for at least one more
   /// element, or MinSize more elements if specified.
   void grow(size_t MinSize = 0);
 
+  GrowBuffer split_grow(size_t MinSize = 0) {
+    return this->split_grow_common(MinSize, sizeof(T));
+  }
+
+  void finish_grow(const GrowBuffer &Buff);
+
 public:
   void push_back(const T &Elt) {
-    if (LLVM_UNLIKELY(this->size() >= this->capacity()))
-      this->grow();
+    GrowBuffer Buffer;
+    bool NeedsSwap = false;
+    if (LLVM_UNLIKELY(this->size() >= this->capacity())) {
+      Buffer = split_grow();
+      NeedsSwap = true;
+    }
     ::new ((void*) this->end()) T(Elt);
     this->set_size(this->size() + 1);
+    if (NeedsSwap)
+      finish_grow(Buffer);
   }
 
   void push_back(T &&Elt) {
-    if (LLVM_UNLIKELY(this->size() >= this->capacity()))
-      this->grow();
+    GrowBuffer Buffer;
+    bool NeedsSwap = false;
+    if (LLVM_UNLIKELY(this->size() >= this->capacity())) {
+      Buffer = split_grow();
+      NeedsSwap = true;
+    }
     ::new ((void*) this->end()) T(::std::move(Elt));
     this->set_size(this->size() + 1);
+    if (NeedsSwap)
+      finish_grow(Buffer);
   }
 
   void pop_back() {
     this->set_size(this->size() - 1);
     this->end()->~T();
   }
 };
 
 // Define this out-of-line to dissuade the C++ compiler from inlining it.
 template <typename T, bool TriviallyCopyable>
 void SmallVectorTemplateBase<T, TriviallyCopyable>::grow(size_t MinSize) {
-  // Ensure we can fit the new capacity.
-  // This is only going to be applicable when the capacity is 32 bit.
-  if (MinSize > this->SizeTypeMax())
-    this->report_size_overflow(MinSize);
-
-  // Ensure we can meet the guarantee of space for at least one more element.
-  // The above check alone will not catch the case where grow is called with a
-  // default MinSize of 0, but the current capacity cannot be increased.
-  // This is only going to be applicable when the capacity is 32 bit.
-  if (this->capacity() == this->SizeTypeMax())
-    this->report_at_maximum_capacity();
-
-  // Always grow, even from zero.
-  size_t NewCapacity = size_t(NextPowerOf2(this->capacity() + 2));
-  NewCapacity = std::min(std::max(NewCapacity, MinSize), this->SizeTypeMax());
+
+  size_t NewCapacity = this->grow_size(MinSize);
   T *NewElts = static_cast<T*>(llvm::safe_malloc(NewCapacity*sizeof(T)));
 
   // Move the elements over.
   this->uninitialized_move(this->begin(), this->end(), NewElts);
 
   // Destroy the original elements.
   destroy_range(this->begin(), this->end());
 
   // If this wasn't grown from the inline copy, deallocate the old space.
   if (!this->isSmall())
     free(this->begin());
 
   this->BeginX = NewElts;
   this->Capacity = NewCapacity;
 }
 
+// Define this out-of-line to dissuade the C++ compiler from inlining it.
+template <typename T, bool TriviallyCopyable>
+void SmallVectorTemplateBase<T, TriviallyCopyable>::finish_grow(
+    const GrowBuffer &Buff) {
+  T *Begin = static_cast<T *>(Buff.getBegin());
+  T *End = Begin + Buff.getSize();
+  // Move the elements over.
+  this->uninitialized_move(Begin, End, this->begin());
+
+  // Destroy the original elements.
+  destroy_range(Begin, End);
+
+  // If this wasn't grown from the inline copy, deallocate the old space.
+  if (Buff.getNeedsFree())
+    free(Buff.getBegin());
+}
+
 /// SmallVectorTemplateBase<TriviallyCopyable = true> - This is where we put
 /// method implementations that are designed to work with trivially copyable
 /// T's. This allows using memcpy in place of copy/move construction and
 /// skipping destruction.
 template <typename T>
 class SmallVectorTemplateBase<T, true> : public SmallVectorTemplateCommon<T> {
 protected:
   SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {}
+  using GrowBuffer = GrowBufferBase<SmallVectorSizeType<T>>;
 
   // No need to do a destroy loop for POD's.
   static void destroy_range(T *, T *) {}
 
   /// Move the range [I, E) onto the uninitialized memory
   /// starting with "Dest", constructing elements into it as needed.
   template<typename It1, typename It2>
   static void uninitialized_move(It1 I, It1 E, It2 Dest) {
static void uninitialized_copy(
     if (I != E)
       memcpy(reinterpret_cast<void *>(Dest), I, (E - I) * sizeof(T));
   }
 
   /// Double the size of the allocated memory, guaranteeing space for at
   /// least one more element or MinSize if specified.
   void grow(size_t MinSize = 0) { this->grow_pod(MinSize, sizeof(T)); }
 
+  GrowBuffer split_grow(size_t MinSize = 0) {
+    return this->split_grow_common(MinSize, sizeof(T));
+  }
+
+  void finish_grow(const GrowBuffer &Buffer) {
+    return this->finish_grow_pod(Buffer, sizeof(T));
+  }
+
 public:
   void push_back(const T &Elt) {
-    if (LLVM_UNLIKELY(this->size() >= this->capacity()))
-      this->grow();
+    GrowBuffer Buffer;
+    bool NeedsSwap = false;
+    if (LLVM_UNLIKELY(this->size() >= this->capacity())) {
+      Buffer = split_grow();
+      NeedsSwap = true;
+    }
     memcpy(reinterpret_cast<void *>(this->end()), &Elt, sizeof(T));
     this->set_size(this->size() + 1);
+    if (NeedsSwap)
+      finish_grow(Buffer);
   }
 
   void pop_back() { this->set_size(this->size() - 1); }
 };
 
 /// This class consists of common code factored out of the SmallVector class to
 /// reduce code duplication based on the SmallVector 'N' template parameter.
 template <typename T>
 class SmallVectorImpl : public SmallVectorTemplateBase<T> {
   using SuperClass = SmallVectorTemplateBase<T>;
+  using GrowBuffer = GrowBufferBase<SmallVectorSizeType<T>>;
 
 public:
   using iterator = typename SuperClass::iterator;
   using const_iterator = typename SuperClass::const_iterator;
   using reference = typename SuperClass::reference;
   using size_type = typename SuperClass::size_type;
 
 protected:
   // Default ctor - Initialize to empty.
   explicit SmallVectorImpl(unsigned N)
       : SmallVectorTemplateBase<T>(N) {}
 
+  void finish_grow_split(const GrowBuffer &Buffer, size_t InsStart,
+                         size_t InsCount = 1);
+
 public:
   SmallVectorImpl(const SmallVectorImpl &) = delete;
 
   ~SmallVectorImpl() {
     // Subclass has already destructed this vector's elements.
     // If this wasn't grown from the inline copy, deallocate the old space.
     if (!this->isSmall())
       free(this->begin());
public:
 
   /// Add the specified range to the end of the SmallVector.
   template <typename in_iter,
             typename = std::enable_if_t<std::is_convertible<
                 typename std::iterator_traits<in_iter>::iterator_category,
                 std::input_iterator_tag>::value>>
   void append(in_iter in_start, in_iter in_end) {
     size_type NumInputs = std::distance(in_start, in_end);
-    if (NumInputs > this->capacity() - this->size())
-      this->grow(this->size()+NumInputs);
+    GrowBuffer Buffer;
+    bool NeedsSwap = false;
+    if (NumInputs > this->capacity() - this->size()) {
+      Buffer = this->split_grow(this->size() + NumInputs);
+      NeedsSwap = true;
+    }
 
     this->uninitialized_copy(in_start, in_end, this->end());
+    if (NeedsSwap)
+      this->finish_grow(Buffer);
     this->set_size(this->size() + NumInputs);
   }
 
   /// Append \p NumInputs copies of \p Elt to the end.
   void append(size_type NumInputs, const T &Elt) {
-    if (NumInputs > this->capacity() - this->size())
-      this->grow(this->size()+NumInputs);
+    GrowBuffer Buffer;
+    bool NeedsSwap = false;
+    if (NumInputs > this->capacity() - this->size()) {
+      Buffer = this->split_grow(this->size() + NumInputs);
+      NeedsSwap = true;
+    }
 
     std::uninitialized_fill_n(this->end(), NumInputs, Elt);
+    if (NeedsSwap)
+      this->finish_grow(Buffer);
     this->set_size(this->size() + NumInputs);
   }
 
   void append(std::initializer_list<T> IL) {
     append(IL.begin(), IL.end());
   }
 
   // FIXME: Consider assigning over existing elements, rather than clearing &
   // re-initializing them - for all assign(...) variants.
 
   void assign(size_type NumElts, const T &Elt) {
     clear();
     if (this->capacity() < NumElts)
       this->grow(NumElts);
     this->set_size(NumElts);
     std::uninitialized_fill(this->begin(), this->end(), Elt);
   }
 
   template <typename in_iter,
             typename = std::enable_if_t<std::is_convertible<
                 typename std::iterator_traits<in_iter>::iterator_category,
                 std::input_iterator_tag>::value>>
   void assign(in_iter in_start, in_iter in_end) {
     clear();
     append(in_start, in_end);
   }
 
   void assign(std::initializer_list<T> IL) {
     clear();
     append(IL);
   }
 
   iterator erase(const_iterator CI) {
     // Just cast away constness because this is a non-const member function.
     iterator I = const_cast<iterator>(CI);
 
     assert(I >= this->begin() && "Iterator to erase is out of bounds.");
     assert(I < this->end() && "Erasing at past-the-end iterator.");
 
     iterator N = I;
     // Shift all elts down one.
     std::move(I+1, this->end(), I);
     // Drop the last elt.
     this->pop_back();
     return(N);
   }
 
   iterator erase(const_iterator CS, const_iterator CE) {
     // Just cast away constness because this is a non-const member function.
     iterator S = const_cast<iterator>(CS);
     iterator E = const_cast<iterator>(CE);
if (I == this->end()) {  // Important special case for empty vector.
       return this->end()-1;
     }
 
     assert(I >= this->begin() && "Insertion iterator is out of bounds.");
     assert(I <= this->end() && "Inserting past the end of the vector.");
 
     if (this->size() >= this->capacity()) {
       size_t EltNo = I-this->begin();
-      this->grow();
-      I = this->begin()+EltNo;
+      GrowBuffer Buffer = this->split_grow();
+      I = this->begin() + EltNo;
+      ::new (I) T(::std::move(Elt));
+      finish_grow_split(Buffer, EltNo, 1);
+      return I;
     }
 
     ::new ((void*) this->end()) T(::std::move(this->back()));
     // Push everything else over.
     std::move_backward(I, this->end()-1, this->end());
     this->set_size(this->size() + 1);
 
     // If we just moved the element we're inserting, be sure to update
if (I == this->end()) {  // Important special case for empty vector.
       return this->end()-1;
     }
 
     assert(I >= this->begin() && "Insertion iterator is out of bounds.");
     assert(I <= this->end() && "Inserting past the end of the vector.");
 
     if (this->size() >= this->capacity()) {
       size_t EltNo = I-this->begin();
-      this->grow();
-      I = this->begin()+EltNo;
+      GrowBuffer Buffer = this->split_grow();
+      I = this->begin() + EltNo;
+      ::new (I) T(Elt);
+      finish_grow_split(Buffer, EltNo, 1);
+      return I;
     }
     ::new ((void*) this->end()) T(std::move(this->back()));
     // Push everything else over.
     std::move_backward(I, this->end()-1, this->end());
     this->set_size(this->size() + 1);
 
     // If we just moved the element we're inserting, be sure to update
     // the reference.
iterator insert(iterator I, size_type NumToInsert, const T &Elt) {
     if (I == this->end()) {  // Important special case for empty vector.
       append(NumToInsert, Elt);
       return this->begin()+InsertElt;
     }
 
     assert(I >= this->begin() && "Insertion iterator is out of bounds.");
     assert(I <= this->end() && "Inserting past the end of the vector.");
 
-    // Ensure there is enough space.
-    reserve(this->size() + NumToInsert);
-
-    // Uninvalidate the iterator.
-    I = this->begin()+InsertElt;
+    if (this->size() + NumToInsert > this->capacity()) {
+      GrowBuffer Buffer = this->split_grow(this->size() + NumToInsert);
+      I = this->begin() + InsertElt;
+      std::uninitialized_fill_n(I, NumToInsert, Elt);
+      finish_grow_split(Buffer, InsertElt, NumToInsert);
+      return I;
+    }
 
     // If there are more elements between the insertion point and the end of the
     // range than there are being inserted, we can use a simple approach to
     // insertion.  Since we already reserved space, we know that this won't
     // reallocate the vector.
     if (size_t(this->end()-I) >= NumToInsert) {
       T *OldEnd = this->end();
       append(std::move_iterator<iterator>(this->end() - NumToInsert),
if (I == this->end()) {  // Important special case for empty vector.
       return this->begin()+InsertElt;
     }
 
     assert(I >= this->begin() && "Insertion iterator is out of bounds.");
     assert(I <= this->end() && "Inserting past the end of the vector.");
 
     size_t NumToInsert = std::distance(From, To);
 
-    // Ensure there is enough space.
-    reserve(this->size() + NumToInsert);
-
-    // Uninvalidate the iterator.
-    I = this->begin()+InsertElt;
+    if (this->size() + NumToInsert > this->capacity()) {
+      GrowBuffer Buffer = this->split_grow(this->size() + NumToInsert);
+      I = this->begin() + InsertElt;
+      this->uninitialized_copy(From, To, I);
+      finish_grow_split(Buffer, InsertElt, NumToInsert);
+      return I;
+    }
 
     // If there are more elements between the insertion point and the end of the
     // range than there are being inserted, we can use a simple approach to
     // insertion.  Since we already reserved space, we know that this won't
     // reallocate the vector.
     if (size_t(this->end()-I) >= NumToInsert) {
       T *OldEnd = this->end();
       append(std::move_iterator<iterator>(this->end() - NumToInsert),
iterator insert(iterator I, ItTy From, ItTy To) {
     return I;
   }
 
   void insert(iterator I, std::initializer_list<T> IL) {
     insert(I, IL.begin(), IL.end());
   }
 
   template <typename... ArgTypes> reference emplace_back(ArgTypes &&... Args) {
-    if (LLVM_UNLIKELY(this->size() >= this->capacity()))
-      this->grow();
+    GrowBuffer Buffer;
+    bool NeedsSwap = false;
+    if (LLVM_UNLIKELY(this->size() >= this->capacity())) {
+      Buffer = this->split_grow();
+      NeedsSwap = true;
+    }
     ::new ((void *)this->end()) T(std::forward<ArgTypes>(Args)...);
     this->set_size(this->size() + 1);
+    if (NeedsSwap)
+      this->finish_grow(Buffer);
     return this->back();
   }
 
   SmallVectorImpl &operator=(const SmallVectorImpl &RHS);
 
   SmallVectorImpl &operator=(SmallVectorImpl &&RHS);
 
   bool operator==(const SmallVectorImpl &RHS) const {
     if (this->size() != RHS.size()) return false;
     return std::equal(this->begin(), this->end(), RHS.begin());
   }
   bool operator!=(const SmallVectorImpl &RHS) const {
     return !(*this == RHS);
   }
 
   bool operator<(const SmallVectorImpl &RHS) const {
     return std::lexicographical_compare(this->begin(), this->end(),
                                         RHS.begin(), RHS.end());
   }
 };
 
 template <typename T>
+void SmallVectorImpl<T>::finish_grow_split(const GrowBuffer &Buffer,
+                                           size_t InsStart, size_t InsCount) {
+
+  iterator OldBegin = static_cast<T *>(Buffer.getBegin());
+  this->uninitialized_move(OldBegin, OldBegin + InsStart, this->begin());
+  this->uninitialized_move(OldBegin + InsStart, OldBegin + Buffer.getSize(),
+                           this->begin() + InsStart + InsCount);
+  this->destroy_range(OldBegin, OldBegin + Buffer.getSize());
+  if (Buffer.getNeedsFree())
+    free(OldBegin);
+  this->set_size(this->size() + InsCount);
+}
+
+template <typename T>
 void SmallVectorImpl<T>::swap(SmallVectorImpl<T> &RHS) {
   if (this == &RHS) return;
 
   // We can only avoid copying elements if neither vector is small.
   if (!this->isSmall() && !RHS.isSmall()) {
     std::swap(this->BeginX, RHS.BeginX);
     std::swap(this->Size, RHS.Size);
     std::swap(this->Capacity, RHS.Capacity);

llvm/lib/Support/SmallVector.cpp

std::string Reason =
       std::to_string(SizeTypeMax());
 #ifdef LLVM_ENABLE_EXCEPTIONS
   throw std::length_error(Reason);
 #else
   report_fatal_error(Reason);
 #endif
 }
 
-// Note: Moving this function into the header may cause performance regression.
 template <class Size_T>
-void SmallVectorBase<Size_T>::grow_pod(void *FirstEl, size_t MinSize,
-                                       size_t TSize) {
+size_t SmallVectorBase<Size_T>::grow_size(size_t MinSize) {
   // Ensure we can fit the new capacity.
   // This is only going to be applicable when the capacity is 32 bit.
   if (MinSize > SizeTypeMax())
     report_size_overflow(MinSize);
 
   // Ensure we can meet the guarantee of space for at least one more element.
   // The above check alone will not catch the case where grow is called with a
   // default MinSize of 0, but the current capacity cannot be increased.
   // This is only going to be applicable when the capacity is 32 bit.
   if (capacity() == SizeTypeMax())
     report_at_maximum_capacity();
 
   // In theory 2*capacity can overflow if the capacity is 64 bit, but the
   // original capacity would never be large enough for this to be a problem.
   size_t NewCapacity = 2 * capacity() + 1; // Always grow.
-  NewCapacity = std::min(std::max(NewCapacity, MinSize), SizeTypeMax());
+  return std::min(std::max(NewCapacity, MinSize), SizeTypeMax());
+}
+
+// Note: Moving this function into the header may cause performance regression.
+template <class Size_T>
+void SmallVectorBase<Size_T>::grow_pod(void *FirstEl, size_t MinSize,
+                                       size_t TSize) {
 
+  size_t NewCapacity = grow_size(MinSize);
   void *NewElts;
   if (BeginX == FirstEl) {
     NewElts = safe_malloc(NewCapacity * TSize);
 
     // Copy the elements over.  No need to run dtors on PODs.
     memcpy(NewElts, this->BeginX, size() * TSize);
   } else {
     // If this wasn't grown from the inline copy, grow the allocated space.
     NewElts = safe_realloc(this->BeginX, NewCapacity * TSize);
   }
 
   this->BeginX = NewElts;
   this->Capacity = NewCapacity;
 }
 
+template <class Size_T>
+GrowBufferBase<Size_T> SmallVectorBase<Size_T>::split_grow_impl(void *FirstEl,
+                                                                size_t MinSize,
+                                                                size_t TSize) {
+  size_t NewCapacity = grow_size(MinSize);
+
+  void *NewElts = safe_malloc(NewCapacity * TSize);
+
+  GrowBufferBase<Size_T> Buffer;
+  Buffer.setBegin(this->BeginX);
+  Buffer.setSize(this->Size);
+  Buffer.setNeedsFree(this->BeginX != FirstEl);
+
+  this->BeginX = NewElts;
+  this->Capacity = NewCapacity;
+
+  return Buffer;
+}
+
+template <class Size_T>
+void SmallVectorBase<Size_T>::finish_grow(const GrowBufferBase<Size_T> &Buffer,
+                                          size_t TSize) {
+  memcpy(this->BeginX, Buffer.getBegin(), Buffer.getSize() * TSize);
+
+  // If this wasn't grown from the inline copy, deallocate the old space.
+  if (Buffer.getNeedsFree())
+    free(Buffer.getBegin());
+}
+
 template class llvm::SmallVectorBase<uint32_t>;
 
 // Disable the uint64_t instantiation for 32-bit builds.
 // Both uint32_t and uint64_t instantations are needed for 64-bit builds.
 // This instantiation will never be used in 32-bit builds, and will cause
 // warnings when sizeof(Size_T) > sizeof(size_t).
 #if SIZE_MAX > UINT32_MAX
 template class llvm::SmallVectorBase<uint64_t>;
 
 // Assertions to ensure this #if stays in sync with SmallVectorSizeType.
 static_assert(sizeof(SmallVectorSizeType<char>) == sizeof(uint64_t),
               "Expected SmallVectorBase<uint64_t> variant to be in use.");
 #else
 static_assert(sizeof(SmallVectorSizeType<char>) == sizeof(uint32_t),
               "Expected SmallVectorBase<uint32_t> variant to be in use.");
 #endif

llvm/unittests/ADT/SmallVectorTest.cpp

 private:
   static int numConstructorCalls;
   static int numMoveConstructorCalls;
   static int numCopyConstructorCalls;
   static int numDestructorCalls;
   static int numAssignmentCalls;
   static int numMoveAssignmentCalls;
   static int numCopyAssignmentCalls;
+  enum class ObjectState { Destroyed = 0, Constructed, MovedFrom };
 
-  bool constructed;
+  ObjectState State;
   int value;
 
 public:
-  Constructable() : constructed(true), value(0) {
+  Constructable() : State(ObjectState::Constructed), value(0) {
     ++numConstructorCalls;
   }
 
-  Constructable(int val) : constructed(true), value(val) {
+  Constructable(int val) : State(ObjectState::Constructed), value(val) {
     ++numConstructorCalls;
   }
 
-  Constructable(const Constructable & src) : constructed(true) {
+  Constructable(const Constructable &src) : State(src.State) {
+    EXPECT_EQ(State, ObjectState::Constructed);
     value = src.value;
     ++numConstructorCalls;
     ++numCopyConstructorCalls;
   }
 
-  Constructable(Constructable && src) : constructed(true) {
+  Constructable(Constructable &&src) : State(src.State) {
+    EXPECT_EQ(State, ObjectState::Constructed);
     value = src.value;
+    src.State = ObjectState::MovedFrom;
     ++numConstructorCalls;
     ++numMoveConstructorCalls;
   }
 
   ~Constructable() {
-    EXPECT_TRUE(constructed);
+    EXPECT_NE(State, ObjectState::Destroyed);
     ++numDestructorCalls;
-    constructed = false;
+    State = ObjectState::Destroyed;
   }
 
   Constructable & operator=(const Constructable & src) {
-    EXPECT_TRUE(constructed);
+    EXPECT_NE(State, ObjectState::Destroyed);
+    EXPECT_EQ(src.State, ObjectState::Constructed);
+    State = src.State;
     value = src.value;
     ++numAssignmentCalls;
     ++numCopyAssignmentCalls;
     return *this;
   }
 
   Constructable & operator=(Constructable && src) {
-    EXPECT_TRUE(constructed);
+    EXPECT_NE(State, ObjectState::Destroyed);
+    EXPECT_EQ(src.State, ObjectState::Constructed);
+    State = src.State;
     value = src.value;
+    src.State = ObjectState::MovedFrom;
     ++numAssignmentCalls;
     ++numMoveAssignmentCalls;
     return *this;
   }
 
   int getValue() const {
+    EXPECT_EQ(State, ObjectState::Constructed);
     return abs(value);
   }
 
   static void reset() {
     numConstructorCalls = 0;
     numMoveConstructorCalls = 0;
     numCopyConstructorCalls = 0;
     numDestructorCalls = 0;
TYPED_TEST(SmallVectorTest, AppendRepeatedNonForwardIterator) {
   this->assertValuesInOrder(this->theVector, 3u, 1, 7, 7);
 }
 
 // Assign test
 TYPED_TEST(SmallVectorTest, AssignTest) {
   SCOPED_TRACE("AssignTest");
 
   this->theVector.push_back(Constructable(1));
+  Constructable::reset();
   this->theVector.assign(2, Constructable(77));
   this->assertValuesInOrder(this->theVector, 2u, 77, 77);
+  EXPECT_EQ(Constructable::getNumCopyAssignmentCalls() +
+                Constructable::getNumCopyConstructorCalls(),
+            2);
 }
 
 // Assign test
 TYPED_TEST(SmallVectorTest, AssignRangeTest) {
   SCOPED_TRACE("AssignTest");
 
   this->theVector.push_back(Constructable(1));
   int arr[] = {1, 2, 3};
   this->theVector.assign(std::begin(arr), std::end(arr));
   this->assertValuesInOrder(this->theVector, 3u, 1, 2, 3);
 }
 
 // Assign test
 TYPED_TEST(SmallVectorTest, AssignNonIterTest) {
   SCOPED_TRACE("AssignTest");
 
   this->theVector.push_back(Constructable(1));
+  Constructable::reset();
   this->theVector.assign(2, 7);
   this->assertValuesInOrder(this->theVector, 2u, 7, 7);
+  EXPECT_EQ(Constructable::getNumCopyAssignmentCalls() +
+                Constructable::getNumCopyConstructorCalls(),
+            2);
 }
 
 // Move-assign test
 TYPED_TEST(SmallVectorTest, MoveAssignTest) {
   SCOPED_TRACE("MoveAssignTest");
 
   // Set up our vector with a single element, but enough capacity for 4.
   this->theVector.reserve(4);

 }
 
 // Insert repeated elements.
 TYPED_TEST(SmallVectorTest, InsertRepeatedTest) {
   SCOPED_TRACE("InsertRepeatedTest");
 
   this->makeSequence(this->theVector, 1, 4);
   Constructable::reset();
+  bool RequiresGrowth = this->theVector.capacity() < 6;
   auto I =
       this->theVector.insert(this->theVector.begin() + 1, 2, Constructable(16));
-  // Move construct the top element into newly allocated space, and optionally
-  // reallocate the whole buffer, move constructing into it.
-  // FIXME: This is inefficient, we shouldn't move things into newly allocated
-  // space, then move them up/around, there should only be 2 or 4 move
-  // constructions here.
-  EXPECT_TRUE(Constructable::getNumMoveConstructorCalls() == 2 ||
-              Constructable::getNumMoveConstructorCalls() == 6);
-  // Move assign the next two to shift them up and make a gap.
+
+  if (RequiresGrowth) {
+    // Moving [1] and [2,3,4] into the new storage.
+    EXPECT_EQ(4, Constructable::getNumMoveConstructorCalls());
+    // Copy construct the new elements directly into the new storage.
+    EXPECT_EQ(2, Constructable::getNumCopyConstructorCalls());
+    // Nothing is move or copy assigned in the growth case.
+    EXPECT_EQ(0, Constructable::getNumMoveAssignmentCalls());
+    EXPECT_EQ(0, Constructable::getNumCopyAssignmentCalls());
+  } else {
+    // Shifting [3,4] down 2 blocks into uninitialized storage.
+    EXPECT_EQ(2, Constructable::getNumMoveConstructorCalls());
+    // Shifting [2] into where [4] lived.
     EXPECT_EQ(1, Constructable::getNumMoveAssignmentCalls());
-  // Copy construct the two new elements from the parameter.
+    // Copy assign the two new elements inside the buffer.
     EXPECT_EQ(2, Constructable::getNumCopyAssignmentCalls());
-  // All without any copy construction.
     EXPECT_EQ(0, Constructable::getNumCopyConstructorCalls());
+  }
+
   EXPECT_EQ(this->theVector.begin() + 1, I);
   this->assertValuesInOrder(this->theVector, 6u, 1, 16, 16, 2, 3, 4);
 }
 
 TYPED_TEST(SmallVectorTest, InsertRepeatedNonIterTest) {
   SCOPED_TRACE("InsertRepeatedTest");
 
   this->makeSequence(this->theVector, 1, 4);

 TYPED_TEST(SmallVectorTest, InsertRangeTest) {
   SCOPED_TRACE("InsertRangeTest");
 
   Constructable Arr[3] =
     { Constructable(77), Constructable(77), Constructable(77) };
 
   this->makeSequence(this->theVector, 1, 3);
   Constructable::reset();
+  bool RequiresGrowth = this->theVector.capacity() < 6;
   auto I = this->theVector.insert(this->theVector.begin() + 1, Arr, Arr + 3);
-  // Move construct the top 3 elements into newly allocated space.
-  // Possibly move the whole sequence into new space first.
-  // FIXME: This is inefficient, we shouldn't move things into newly allocated
-  // space, then move them up/around, there should only be 2 or 3 move
-  // constructions here.
-  EXPECT_TRUE(Constructable::getNumMoveConstructorCalls() == 2 ||
-              Constructable::getNumMoveConstructorCalls() == 5);
-  // Copy assign the lower 2 new elements into existing space.
+
+  if (RequiresGrowth) {
+    // Moving [1] and [2,3] into the new storage.
+    EXPECT_EQ(3, Constructable::getNumMoveConstructorCalls());
+    // Copy construct the 3 items from Arr into the new storage.
+    EXPECT_EQ(3, Constructable::getNumCopyConstructorCalls());
+    // Nothing is move or copy assigned in the growth case.
+    EXPECT_EQ(0, Constructable::getNumMoveAssignmentCalls());
+    EXPECT_EQ(0, Constructable::getNumCopyAssignmentCalls());
+  } else {
+    // Shifting [2,3] down 3 blocks into uninitialized storage.
+    EXPECT_EQ(2, Constructable::getNumMoveConstructorCalls());
+    // Copy assign the lower 2 new elements into existing storage.
     EXPECT_EQ(2, Constructable::getNumCopyAssignmentCalls());
-  // Copy construct the third element into newly allocated space.
+    // Copy construct the third element into uninitialized storage.
     EXPECT_EQ(1, Constructable::getNumCopyConstructorCalls());
+    // Nothing needs to be move assigned here as the only items that need
+    // shifting, are shifted into uninitialized storage.
+    EXPECT_EQ(0, Constructable::getNumMoveAssignmentCalls());
+  }
   EXPECT_EQ(this->theVector.begin() + 1, I);
   this->assertValuesInOrder(this->theVector, 6u, 1, 77, 77, 77, 2, 3);
 }
 
 
 TYPED_TEST(SmallVectorTest, InsertRangeAtEndTest) {
   SCOPED_TRACE("InsertRangeTest");