Add missing comparison operators to SmallVector

Differential Revision: https://reviews.llvm.org/D124407

ADT: Add SmallVectorImpl::truncate() to replace uses of set_size()

Add `SmallVectorImpl::truncate()`, a variant of `resize()` that cannot
increase the size.

- Compared to `resize()`, this has no co

ADT: Add SmallVectorImpl::truncate() to replace uses of set_size()

Add `SmallVectorImpl::truncate()`, a variant of `resize()` that cannot
increase the size.

- Compared to `resize()`, this has no code path for growing the
allocation and can be better optimized.
- Compared to `set_size()`, this formally calls destructors, and does
not skip any constructors.
- Compared to `pop_back_n()`, this takes the new desired size, which in
many contexts is more intuitive than the number of elements to remove.

The immediate motivation is to pair this with `resize_for_overwrite()`
to remove uses of `set_size()`, which can then be made private.

Differential Revision: https://reviews.llvm.org/D115383

show more ...

Put back the trailing commas on TYPED_TEST_SUITE

This avoids a -pedantic warning:
warning: ISO C++11 requires at least one argument for the "..." in a variadic macro

See also https://github.com/goo

Put back the trailing commas on TYPED_TEST_SUITE

This avoids a -pedantic warning:
warning: ISO C++11 requires at least one argument for the "..." in a variadic macro

See also https://github.com/google/googletest/issues/2271

show more ...

Bump googletest to 1.10.0

ADT: Use 'using' to inherit assign and append in SmallString

Rather than reimplement, use a `using` declaration to bring in
`SmallVectorImpl<char>`'s assign and append implementations in
`SmallStrin

ADT: Use 'using' to inherit assign and append in SmallString

Rather than reimplement, use a `using` declaration to bring in
`SmallVectorImpl<char>`'s assign and append implementations in
`SmallString`.

The `SmallString` versions were missing reference invalidation
assertions from `SmallVector`. This patch also fixes a bug in
`llvm::FileCollector::addFileImpl`, which was a copy/paste from
`clang::ModuleDependencyCollector::copyToRoot`, both caught by the
no-longer-skipped assertions.

As a drive-by, this also sinks the `const SmallVectorImpl&` versions of
these methods down into `SmallVectorImpl`, since I imagine they'd be
useful elsewhere.

Differential Revision: https://reviews.llvm.org/D95202

show more ...

ADT: Fix reference invalidation in SmallVector::emplace_back and assign(N,V)

This fixes the final (I think?) reference invalidation in `SmallVector`
that we need to fix to align with `std::vector`.

ADT: Fix reference invalidation in SmallVector::emplace_back and assign(N,V)

This fixes the final (I think?) reference invalidation in `SmallVector`
that we need to fix to align with `std::vector`. (There is still some
left in the range insert / append / assign, but the standard calls that
UB for `std::vector` so I think we don't care?)

For POD-like types, reimplement `emplace_back()` in terms of
`push_back()`, taking a copy even for large `T` rather than lose the
realloc optimization in `grow_pod()`.

For other types, split the grow operation in three and construct the new
element in the middle.

- `mallocForGrow()` calculates the new capacity and returns the result
of `safe_malloc()`. We only need a single definition per
`SmallVectorBase` so this is defined in SmallVector.cpp to avoid code
size bloat. Moving this part of non-POD grow to the source file also
allows the logic to be easily shared with `grow_pod`, and
`report_size_overflow()` and `report_at_maximum_capacity()` can move
there too.
- `moveElementsForGrow()` moves elements from the old to the new
allocation.
- `takeAllocationForGrow()` frees the old allocation and saves the
new allocation and capacity .

`SmallVector:assign(size_type, const T&)` also uses the split-grow
operations for non-POD, but it also has a semantic change when not
growing. Previously, assign would start with `clear()`, and so the old
elements were destructed and all elements of the new vector were
copy-constructed (potentially invalidating references). The new
implementation skips destruction and uses copy-assignment for the prefix
of the new vector that fits. The new semantics match what libc++ does
for `std::vector::assign()`.

Note that the following is another possible implementation:
```
void assign(size_type NumElts, ValueParamT Elt) {
std::fill_n(this->begin(), std::min(NumElts, this->size()), Elt);
this->resize(NumElts, Elt);
}
```
The downside of this simpler implementation is that if the vector has to
grow there will be `size()` redundant copy operations.

(I had planned on splitting this patch up into three for committing
(after getting performance numbers / initial review), but I've realized
that if this does for some reason need to be reverted we'll probably
want to revert the whole package...)

Differential Revision: https://reviews.llvm.org/D94739

show more ...

Revert "Revert "ADT: Fix reference invalidation in SmallVector...""

This reverts commit 33be50daa9ce1074c3b423a4ab27c70c0722113a,
effectively reapplying:

- 260a856c2abcef49c7cb3bdcd999701db3e2af38

Revert "Revert "ADT: Fix reference invalidation in SmallVector...""

This reverts commit 33be50daa9ce1074c3b423a4ab27c70c0722113a,
effectively reapplying:

- 260a856c2abcef49c7cb3bdcd999701db3e2af38
- 3043e5a5c33c4c871f4a1dfd621a8839f9a1f0b3
- 49142991a685bd427d7e877c29c77371dfb7634c

... with a fix to skip a call to `SmallVector::isReferenceToStorage()`
when we know the parameter had been taken by value for small, POD-like
`T`. See https://reviews.llvm.org/D93779 for the discussion on the
revert.

At a high-level, these commits fix reference invalidation in
SmallVector's push_back, append, insert (one or N), and resize
operations. For more details, please see the original commit messages.

This commit fixes a bug that crept into
`SmallVectorTemplateCommon::reserveForAndGetAddress()` during the review
process after performance analysis was done. That function is now called
`reserveForParamAndGetAddress()`, clarifying that it only works for
parameter values. It uses that knowledge to bypass
`SmallVector::isReferenceToStorage()` when `TakesParamByValue`. This is
`constexpr` and avoids adding overhead for "small enough", trivially
copyable `T`.

Performance could potentially be tuned further by increasing the
threshold for `TakesParamByValue`, which is currently defined as:
```
bool TakesParamByValue = sizeof(T) <= 2 * sizeof(void *);
```
in the POD-like version of SmallVectorTemplateBase (else, `false`).

Differential Revision: https://reviews.llvm.org/D94800

show more ...

Revert "Reapply "ADT: Fix reference invalidation in SmallVector::push_back and single-element insert""

This reverts commit 260a856c2abcef49c7cb3bdcd999701db3e2af38.
This reverts commit 3043e5a5c33c4

Revert "Reapply "ADT: Fix reference invalidation in SmallVector::push_back and single-element insert""

This reverts commit 260a856c2abcef49c7cb3bdcd999701db3e2af38.
This reverts commit 3043e5a5c33c4c871f4a1dfd621a8839f9a1f0b3.
This reverts commit 49142991a685bd427d7e877c29c77371dfb7634c.

This change had a larger than anticipated compile-time impact,
possibly because the small value optimization is not working as
intended. See D93779.

show more ...

ADT: Fix reference invalidation in SmallVector::resize

For small enough, trivially copyable `T`, take the parameter by-value in
`SmallVector::resize`. Otherwise, when growing, update the arugment
a

ADT: Fix reference invalidation in SmallVector::resize

For small enough, trivially copyable `T`, take the parameter by-value in
`SmallVector::resize`. Otherwise, when growing, update the arugment
appropriately.

Differential Revision: https://reviews.llvm.org/D93781

show more ...

ADT: Fix reference invalidation in N-element SmallVector::append and insert

For small enough, trivially copyable `T`, take the parameter by-value in
`SmallVector::append` and `SmallVector::insert`.

ADT: Fix reference invalidation in N-element SmallVector::append and insert

For small enough, trivially copyable `T`, take the parameter by-value in
`SmallVector::append` and `SmallVector::insert`. Otherwise, when
growing, update the arugment appropriately.

Differential Revision: https://reviews.llvm.org/D93780

show more ...

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

This reverts commit 56d1ffb927d03958a7a31442596df749264a7792, reapplying
9abac60309006db00eca0af406c2e16

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

This reverts commit 56d1ffb927d03958a7a31442596df749264a7792, reapplying
9abac60309006db00eca0af406c2e16bef26807c, removing insert_one_maybe_copy
and using a helper called forward_value_param instead. This avoids use
of `std::is_same` (or any SFINAE), so I'm hoping it's more portable and
MSVC will be happier.

Original commit message follows:

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.

Differential Revision: https://reviews.llvm.org/D93779

show more ...

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

This reverts commit 9abac60309006db00eca0af406c2e16bef26807c since there
are some bot errors on Windows:

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

This reverts commit 9abac60309006db00eca0af406c2e16bef26807c since there
are some bot errors on Windows:
http://lab.llvm.org:8011/#/builders/127/builds/4489

```
FAILED: lib/Support/CMakeFiles/LLVMSupport.dir/IntervalMap.cpp.obj
C:\PROGRA~2\MIB055~1\2017\PROFES~1\VC\Tools\MSVC\1416~1.270\bin\Hostx64\x64\cl.exe /nologo /TP -DGTEST_HAS_RTTI=0 -DUNICODE -D_CRT_NONSTDC_NO_DEPRECATE -D_CRT_NONSTDC_NO_WARNINGS -D_CRT_SECURE_NO_DEPRECATE -D_CRT_SECURE_NO_WARNINGS -D_HAS_EXCEPTIONS=0 -D_SCL_SECURE_NO_DEPRECATE -D_SCL_SECURE_NO_WARNINGS -D_UNICODE -D__STDC_CONSTANT_MACROS -D__STDC_FORMAT_MACROS -D__STDC_LIMIT_MACROS -Ilib\Support -IC:\b\slave\sanitizer-windows\llvm-project\llvm\lib\Support -Iinclude -IC:\b\slave\sanitizer-windows\llvm-project\llvm\include /DWIN32 /D_WINDOWS /Zc:inline /Zc:__cplusplus /Zi /Zc:strictStrings /Oi /Zc:rvalueCast /bigobj /W4 -wd4141 -wd4146 -wd4244 -wd4267 -wd4291 -wd4351 -wd4456 -wd4457 -wd4458 -wd4459 -wd4503 -wd4624 -wd4722 -wd4100 -wd4127 -wd4512 -wd4505 -wd4610 -wd4510 -wd4702 -wd4245 -wd4706 -wd4310 -wd4701 -wd4703 -wd4389 -wd4611 -wd4805 -wd4204 -wd4577 -wd4091 -wd4592 -wd4319 -wd4709 -wd4324 -w14062 -we4238 /Gw /MD /O2 /Ob2 -UNDEBUG -std:c++14 /EHs-c- /GR- /showIncludes /Folib\Support\CMakeFiles\LLVMSupport.dir\IntervalMap.cpp.obj /Fdlib\Support\CMakeFiles\LLVMSupport.dir\LLVMSupport.pdb /FS -c C:\b\slave\sanitizer-windows\llvm-project\llvm\lib\Support\IntervalMap.cpp
C:\b\slave\sanitizer-windows\llvm-project\llvm\include\llvm/ADT/SmallVector.h(746): error C2672: 'llvm::SmallVectorImpl<T>::insert_one_maybe_copy': no matching overloaded function found
with
[
T=llvm::IntervalMapImpl::Path::Entry
]
C:\b\slave\sanitizer-windows\llvm-project\llvm\include\llvm/ADT/SmallVector.h(745): note: while compiling class template member function 'llvm::IntervalMapImpl::Path::Entry *llvm::SmallVectorImpl<T>::insert(llvm::IntervalMapImpl::Path::Entry *,T &&)'
with
[
T=llvm::IntervalMapImpl::Path::Entry
]
C:\b\slave\sanitizer-windows\llvm-project\llvm\lib\Support\IntervalMap.cpp(22): note: see reference to function template instantiation 'llvm::IntervalMapImpl::Path::Entry *llvm::SmallVectorImpl<T>::insert(llvm::IntervalMapImpl::Path::Entry *,T &&)' being compiled
with
[
T=llvm::IntervalMapImpl::Path::Entry
]
C:\b\slave\sanitizer-windows\llvm-project\llvm\include\llvm/ADT/SmallVector.h(1136): note: see reference to class template instantiation 'llvm::SmallVectorImpl<T>' being compiled
with
[
T=llvm::IntervalMapImpl::Path::Entry
]
C:\b\slave\sanitizer-windows\llvm-project\llvm\include\llvm/ADT/IntervalMap.h(790): note: see reference to class template instantiation 'llvm::SmallVector<llvm::IntervalMapImpl::Path::Entry,4>' being compiled
C:\b\slave\sanitizer-windows\llvm-project\llvm\include\llvm/ADT/SmallVector.h(746): error C2783: 'llvm::IntervalMapImpl::Path::Entry *llvm::SmallVectorImpl<T>::insert_one_maybe_copy(llvm::IntervalMapImpl::Path::Entry *,ArgType &&)': could not deduce template argument for '__formal'
with
[
T=llvm::IntervalMapImpl::Path::Entry
]
C:\b\slave\sanitizer-windows\llvm-project\llvm\include\llvm/ADT/SmallVector.h(727): note: see declaration of 'llvm::SmallVectorImpl<T>::insert_one_maybe_copy'
with
[
T=llvm::IntervalMapImpl::Path::Entry
]
```

show more ...

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

For small enough, trivially copyable `T`, take the argument by value in
`SmallVector::push_back` and copy it when

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

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.

Differential Revision: https://reviews.llvm.org/D93779

show more ...

[ADT] Fix some tests after 5d10b8ad

Some bots were failing due to signed/unsigned comparison.

[ADT] Add resize_for_overwrite method to SmallVector.

Analagous to the std::make_(unqiue|shared)_for_overwrite added in c++20.
If T is POD, and the container gets larger, any new values added wont b

[ADT] Add resize_for_overwrite method to SmallVector.

Analagous to the std::make_(unqiue|shared)_for_overwrite added in c++20.
If T is POD, and the container gets larger, any new values added wont be initialized.
This is useful when using SmallVector as a buffer where its planned to overwrite any potential new values added.
If T is not POD, `new (Storage) T` functions identically to `new (Storage) T()` so this will function identically to `resize(size_type)`.

Reviewed By: dexonsmith

Differential Revision: https://reviews.llvm.org/D93532

show more ...

[SmallVector] Allow SmallVector<T>

This patch adds a capability to SmallVector to decide a number of
inlined elements automatically. The policy is:

- A minimum of 1 inlined elements, with more as l

[SmallVector] Allow SmallVector<T>

This patch adds a capability to SmallVector to decide a number of
inlined elements automatically. The policy is:

- A minimum of 1 inlined elements, with more as long as
sizeof(SmallVector<T>) <= 64.
- If sizeof(T) is "too big", then trigger a static_assert: this dodges
the more pathological cases

This is expected to systematically improve SmallVector use in the
LLVM codebase, which has historically been plagued by semi-arbitrary /
cargo culted N parameters, often leading to bad outcomes due to
excessive sizeof(SmallVector<T, N>). This default also makes
programming more convenient by avoiding edit/rebuild cycles due to
forgetting to type the N parameter.

Differential Revision: https://reviews.llvm.org/D92522

show more ...

ADT: Weaken SmallVector::resize assertion from 5abf76fbe37380874a88cc9aa02164800e4e10f3

There's no need to check for reference invalidation when
`SmallVector::resize` is shrinking; the parameter isn

ADT: Weaken SmallVector::resize assertion from 5abf76fbe37380874a88cc9aa02164800e4e10f3

There's no need to check for reference invalidation when
`SmallVector::resize` is shrinking; the parameter isn't accessed.

Differential Revision: https://reviews.llvm.org/D91832

show more ...

ADT: Add assertions to SmallVector::insert, etc., for reference invalidation

2c196bbc6bd897b3dcc1d87a3baac28e1e88df41 asserted that
`SmallVector::push_back` doesn't invalidate the parameter when it

ADT: Add assertions to SmallVector::insert, etc., for reference invalidation

2c196bbc6bd897b3dcc1d87a3baac28e1e88df41 asserted that
`SmallVector::push_back` doesn't invalidate the parameter when it needs
to grow. Do the same for `resize`, `append`, `assign`, `insert`, and
`emplace_back`.

Differential Revision: https://reviews.llvm.org/D91744

show more ...

[ADT] Add SmallVector::pop_back_n

Adds a method called pop_back_n to SmallVector.
This is more readable and less error prone than the alternatives of using
```lang=c++
Vector.resize(Vector.size() -

[ADT] Add SmallVector::pop_back_n

Adds a method called pop_back_n to SmallVector.
This is more readable and less error prone than the alternatives of using
```lang=c++
Vector.resize(Vector.size() - N);
Vector.erase(Vector.end() - N, Vector.end());
for (unsigned I = 0;I<N;++I) Vector.pop_back();
```

Reviewed By: dblaikie

Differential Revision: https://reviews.llvm.org/D90576

show more ...

[ADT] Update SmallVectorTest.EmplaceBack tests after rL356312

rL356312 changed the return type of emplace_back from void to reference.
Update the tests to check the behavior.

Reviewers: dblaikie

R

[ADT] Update SmallVectorTest.EmplaceBack tests after rL356312

rL356312 changed the return type of emplace_back from void to reference.
Update the tests to check the behavior.

Reviewers: dblaikie

Reviewed By: dblaikie

Subscribers: dexonsmith, llvm-commits

Tags: #llvm

Differential Revision: https://reviews.llvm.org/D59809

llvm-svn: 356980

show more ...

Update the file headers across all of the LLVM projects in the monorepo
to reflect the new license.

We understand that people may be surprised that we're moving the header
entirely to discuss the ne

Update the file headers across all of the LLVM projects in the monorepo
to reflect the new license.

We understand that people may be surprised that we're moving the header
entirely to discuss the new license. We checked this carefully with the
Foundation's lawyer and we believe this is the correct approach.

Essentially, all code in the project is now made available by the LLVM
project under our new license, so you will see that the license headers
include that license only. Some of our contributors have contributed
code under our old license, and accordingly, we have retained a copy of
our old license notice in the top-level files in each project and
repository.

llvm-svn: 351636

show more ...

[ADT] Don't use __used__ attribute on struct members in unit test

On some compilers, __used__ can only be applied to variables
or functions.

llvm-svn: 305188

[ADT] Use LLVM_ATTRIBUTE_USED instead of __attribute__ for unit test

llvm-svn: 305168

[ADT] Suppress unused attribute warning in unit test

llvm-svn: 305166

[SmallVector] Reinstate the typedefs.

They're unused with recent versions of libstdc++ but older ones
(e.g. libstdc++ 4.9 still requires them). Maybe we should bump
the requirements on the minimum v

[SmallVector] Reinstate the typedefs.

They're unused with recent versions of libstdc++ but older ones
(e.g. libstdc++ 4.9 still requires them). Maybe we should bump
the requirements on the minimum version to make GCC 7 happy, but
in the meanwhile we need to live with the warning.

llvm-svn: 305158

show more ...