[SSAUpdater] Add a SmallPtrSet reserve method for IDFcalc (#97823)

As per the LLVM programmers manual, SmallPtrSets do linear scans on
insertion and then turn into a hash-table if the set gets big.

[SSAUpdater] Add a SmallPtrSet reserve method for IDFcalc (#97823)

As per the LLVM programmers manual, SmallPtrSets do linear scans on
insertion and then turn into a hash-table if the set gets big. Here in
the IDFCalculator, the SmallPtrSets have been configured to have 32
elements in each static allocation... which means that we linearly scan
for all problems with up to 32 elements, which I feel is quite a large
N.

Shorten the SmallPtrSet size, and add a reserve method to avoid any
repeated allocations, plus corresponding unit tests. Doing this yields a
0.13% compile-time improvement for debug-info builds, as we hit
IDFCalculator pretty hard in InstrRefBasedLDV.

show more ...

[SmallPtrSet] Don't leave tombstones in small mode (#96762)

When erasing elements in small mode, we currently leave behind
tombstones. This means that insertion into the SmallPtrSet also has to
ch

[SmallPtrSet] Don't leave tombstones in small mode (#96762)

When erasing elements in small mode, we currently leave behind
tombstones. This means that insertion into the SmallPtrSet also has to
check for these, making the operation more expensive than it really
should be.

We don't really need the tombstones in small mode, because we can just
replace with the last element in the set instead. This changes the
order, but SmallPtrSet order is fundamentally unstable anyway.

However, not leaving tombstones means that the erase() operation now
invalidates iterators. This means that consumers that want to remove
elements while iterating over the set have to use remove_if() instead.
If they fail to do so, there will be an assertion failure thanks to
debug epochs, so any such cases are easy to detect (and I have already
fixed all cases inside llvm at least).

show more ...

[ADT] Return bool from SmallPtrSet::remove_if()

Return whether anything was removed. This matches the API of
SetVector::remove_if() and is convenient for some future uses.

[SmallPtrSet] Add remove_if() method (#96468)

Add remove_if() method, similar to the one already present on SetVector.
It is intended to replace the following pattern:

for (Foo *Ptr : Set)

[SmallPtrSet] Add remove_if() method (#96468)

Add remove_if() method, similar to the one already present on SetVector.
It is intended to replace the following pattern:

for (Foo *Ptr : Set)
if (Pred(Ptr))
Set.erase(Ptr);

With:

Set.remove_if(Pred);

This pattern is commonly used for set intersection, where `Pred` is
something like `!OtherSet.contains(Ptr)`.

The implementation provided here is a bit more efficient than the naive
loop, because it does not require looking up the bucket during the
erase() operation again.

However, my actual motivation for this is to have a way to perform this
operation without relying on the current `std::set`-style guarantee that
erase() does not invalidate iterators. I'd like to stop making use of
tombstones in the small regime, which will make insertion operations a
good bit more efficient. However, this will invalidate iterators during
erase().

show more ...

Use the range-based overload of llvm::sort where possible

Reviewed By: MaskRay

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

Move STLFunctionalExtras out of STLExtras

Only using that change in StringRef already decreases the number of
preoprocessed lines from 7837621 to 7776151 for LLVMSupport

Perhaps more interestingly,

Move STLFunctionalExtras out of STLExtras

Only using that change in StringRef already decreases the number of
preoprocessed lines from 7837621 to 7776151 for LLVMSupport

Perhaps more interestingly, it shows that many files were relying on the
inclusion of StringRef.h to have the declaration from STLExtras.h. This
patch tries hard to patch relevant part of llvm-project impacted by this
hidden dependency removal.

Potential impact:
- "llvm/ADT/StringRef.h" no longer includes <memory>,
"llvm/ADT/Optional.h" nor "llvm/ADT/STLExtras.h"

Related Discourse thread:
https://llvm.discourse.group/t/include-what-you-use-include-cleanup/5831

show more ...

Allow SmallPtrSet to be used with a std::insert_iterator

Currently, the SmallPtrSet type allows inserting elements but it does
not support inserting elements with a positional hint. The lack of this

Allow SmallPtrSet to be used with a std::insert_iterator

Currently, the SmallPtrSet type allows inserting elements but it does
not support inserting elements with a positional hint. The lack of this
signature means that you cannot use SmallPtrSet with
std::insert_iterator or std::inserter(), which makes some code
constructs more awkward. This adds an overload of insert() that can be
used in these scenarios.

The positional hint is unused by SmallPtrSet and the call is equivalent
to calling insert() without a hint.

show more ...

[llvm] Add contains(KeyType) -> bool methods to SmallPtrSet

Matches C++20 API addition.

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

[ADT] Add equality operator for SmallPtrSet

Reviewed By: tellenbach
Differential Revision: https://reviews.llvm.org/D69429

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

[unittests] ADT: silence -Wself-assign diagnostics

Summary:
D44883 extends -Wself-assign to also work on C++ classes.
In it's current state (as suggested by @rjmccall), it is not under it's own sub-

[unittests] ADT: silence -Wself-assign diagnostics

Summary:
D44883 extends -Wself-assign to also work on C++ classes.
In it's current state (as suggested by @rjmccall), it is not under it's own sub-group.
Since that diag is enabled by `-Wall`, stage2 testing showed that:
* It does not fire on any llvm code
* It does fire for these 3 unittests
* It does fire for libc++ tests

This diff simply silences those new warnings in llvm's unittests.
A similar diff will be needed for libcxx. (`libcxx/test/std/language.support/support.types/byteops/`, maybe something else)

Since i don't think we want to repeat rL322901, let's talk about it.
I've subscribed everyone who i think might be interested...

There are several ways forward:
* Not extend -Wself-assign, close D44883. Not very productive outcome i'd say.
* Keep D44883 in it's current state.
Unless your custom overloaded operators do something unusual for when self-assigning,
the warning is no less of a false-positive than the current -Wself-assign.
Except for tests of course, there you'd want to silence it. The current suggestion is:
```
S a;
a = (S &)a;
```
* Split the diagnostic in two - `-Wself-assign-builtin` (i.e. what is `-Wself-assign` in trunk),
and `-Wself-assign-overloaded` - the new part in D44883.
Since, as i said, i'm not really sure why it would be less of a error than the current `-Wself-assign`,
both would still be in `-Wall`. That way one could simply pass `-Wno-self-assign-overloaded` for all the tests.
Pretty simple to do, and will surely work.
* Split the diagnostic in two - `-Wself-assign-trivial`, and `-Wself-assign-nontrivial`.
The choice of which diag to emit would depend on trivial-ness of that particular operator.
The current `-Wself-assign` would be `-Wself-assign-trivial`.
https://godbolt.org/g/gwDASe - `A`, `B` and `C` case would be treated as trivial, and `D`, `E` and `F` as non-trivial.
Will be the most complicated to implement.

Thoughts?

Reviewers: aaron.ballman, rsmith, rtrieu, rjmccall, dblaikie, atrick, gottesmm

Reviewed By: dblaikie

Subscribers: lebedev.ri, phosek, vsk, rnk, thakis, sammccall, mclow.lists, llvm-commits, rjmccall

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

llvm-svn: 329491

show more ...

[unittests] Change std::sort to llvm::sort in response to r327219

r327219 added wrappers to std::sort which randomly shuffle the container before
sorting. This will help in uncovering non-determini

[unittests] Change std::sort to llvm::sort in response to r327219

r327219 added wrappers to std::sort which randomly shuffle the container before
sorting. This will help in uncovering non-determinism caused due to undefined
sorting order of objects having the same key.

To make use of that infrastructure we need to invoke llvm::sort instead of
std::sort.

Note: This patch is one of a series of patches to replace *all* std::sort to
llvm::sort. Refer the comments section in D44363 for a list of all the
required patches.

llvm-svn: 329475

show more ...

Re-sort #include lines for unittests. This uses a slightly modified
clang-format (https://reviews.llvm.org/D33932) to keep primary headers
at the top and handle new utility headers like 'gmock' consi

Re-sort #include lines for unittests. This uses a slightly modified
clang-format (https://reviews.llvm.org/D33932) to keep primary headers
at the top and handle new utility headers like 'gmock' consistently with
other utility headers.

No other change was made. I did no manual edits, all of this is
clang-format.

This should allow other changes to have more clear and focused diffs,
and is especially motivated by moving some headers into more focused
libraries.

llvm-svn: 304786

show more ...

ADT: Fix SmallPtrSet iterators in reverse mode

Fix SmallPtrSet::iterator behaviour and creation ReverseIterate is true.

- Any function that creates an iterator now uses
SmallPtrSet::makeItera

ADT: Fix SmallPtrSet iterators in reverse mode

Fix SmallPtrSet::iterator behaviour and creation ReverseIterate is true.

- Any function that creates an iterator now uses
SmallPtrSet::makeIterator, which creates an iterator that
dereferences to the given pointer.

- In reverse-iterate mode, initialze iterator::End with "CurArray"
instead of EndPointer.

- In reverse-iterate mode, the current node is iterator::Buffer[-1].
iterator::operator* and SmallPtrSet::makeIterator are the only ones
that need to know.

- Fix the assertions for reverse-iterate mode.

This fixes the tests Danny B added in r297182, and adds a couple of
others to confirm that dereferencing does the right thing, regardless of
how the iterator was found, and that iteration works correctly from each
return from find.

llvm-svn: 297234

show more ...

Add unit tests for changes to SmallPtrSet and PointerLikeTypeTraits

llvm-svn: 297182

[ADT] Add initializer list support to SmallPtrSet so that sets can be
easily initialized with some initial values.

llvm-svn: 287610

SmallPtrSetTest: More checks for the swap() testing

llvm-svn: 259152

SmallPtrSetTest: Check that iterators are still valid after erase()

llvm-svn: 259151

[C++11] Switch all uses of the llvm_move macro to use std::move
directly, and remove the macro.

llvm-svn: 202612

[C++11] Remove uses of LLVM_HAS_RVALUE_REFERENCES from the unittests.

llvm-svn: 202583

Make the moved-from SmallPtrSet be a valid, empty, small-state object.
Enhance the tests to actually require moves in C++11 mode, in addition
to testing the moved-from state. Further enhance the test

Make the moved-from SmallPtrSet be a valid, empty, small-state object.
Enhance the tests to actually require moves in C++11 mode, in addition
to testing the moved-from state. Further enhance the tests to cover
copy-assignment into a moved-from object and moving a large-state
object. (Note that we can't really test small-state vs. large-state as
that isn't an observable property of the API really.) This should finish
addressing review on r195239.

llvm-svn: 195261

show more ...

Add a test for assignment operator behavior which was changed in
r195239, as well as a comment about the fact that assigning over
a moved-from object was in fact tested. Addresses some of the review

Add a test for assignment operator behavior which was changed in
r195239, as well as a comment about the fact that assigning over
a moved-from object was in fact tested. Addresses some of the review
feedback on r195239.

llvm-svn: 195260

show more ...

Give SmallPtrSet move semantics when we have R-value references.
Somehow, this ADT got missed which is moderately terrifying considering
the efficiency of move for it.

The code to implement move sem

Give SmallPtrSet move semantics when we have R-value references.
Somehow, this ADT got missed which is moderately terrifying considering
the efficiency of move for it.

The code to implement move semantics for it is pretty horrible
currently but was written to reasonably closely match the rest of the
code. Unittests that cover both copying and moving (at a basic level)
added.

llvm-svn: 195239

show more ...

SmallVector and SmallPtrSet allocations now power-of-two aligned.
This time tested on both OSX and Linux.

llvm-svn: 178377

Revert "Fix allocations of SmallVector and SmallPtrSet so they are more prone to"

This reverts commit 617330909f0c26a3f2ab8601a029b9bdca48aa61.

It broke the bots:

/home/clangbuild2/clang-ppc64-2/l

Revert "Fix allocations of SmallVector and SmallPtrSet so they are more prone to"

This reverts commit 617330909f0c26a3f2ab8601a029b9bdca48aa61.

It broke the bots:

/home/clangbuild2/clang-ppc64-2/llvm.src/unittests/ADT/SmallVectorTest.cpp:150: PushPopTest
/home/clangbuild2/clang-ppc64-2/llvm.src/unittests/ADT/SmallVectorTest.cpp:118: Failure
Value of: v[i].getValue()
Actual: 0
Expected: value
Which is: 2

llvm-svn: 178334

show more ...