Reformatting everything now that we have `llvm` namespaces. I've
separated this from the main commit to help manage merge-conflicts and
for making it a bit easier to read the mega-patch.
This is phase-1 of switching from llvm::Optional to std::optional in the
next rebranch. llvm::Optional was removed from upstream LLVM, so we need
to migrate off rather soon. On Darwin, std::optional, and llvm::Optional
have the same layout, so we don't need to be as concerned about ABI
beyond the name mangling. `llvm::Optional` is only returned from one
function in
```
getStandardTypeSubst(StringRef TypeName,
bool allowConcurrencyManglings);
```
It's the return value, so it should not impact the mangling of the
function, and the layout is the same as `std::optional`, so it should be
mostly okay. This function doesn't appear to have users, and the ABI was
already broken 2 years ago for concurrency and no one seemed to notice
so this should be "okay".
I'm doing the migration incrementally so that folks working on main can
cherry-pick back to the release/5.9 branch. Once 5.9 is done and locked
away, then we can go through and finish the replacement. Since `None`
and `Optional` show up in contexts where they are not `llvm::None` and
`llvm::Optional`, I'm preparing the work now by going through and
removing the namespace unwrapping and making the `llvm` namespace
explicit. This should make it fairly mechanical to go through and
replace llvm::Optional with std::optional, and llvm::None with
std::nullopt. It's also a change that can be brought onto the
release/5.9 with minimal impact. This should be an NFC change.
- Replaced usage of raw map and vector with the type that wraps the
combination (BlotSetVector); that provided a significant deduplication
since a sizeable portion of the worklist's implementation was in
vector and map management now provided by the BlotSetVector.
- Templated over the type of map and vector used by the blot set vector.
- Added SmallSILInstructionWorklist where the map and vector are
specified to be SmallDenseMap and SmallVector respectively.
- Replaced usages of bare ValueBase with usages of SILValue.
- Renamed zap to resetChecked.
Added a bit of functionality to BlotSetVector, specifically to support
SILInstructionWorklist:
- Made insert return not just the index that the potentially-inserted
item is at on return but additionally whether an insertion occurred,
matching the behavior of llvm::DenseMap::insert.
- Added a method to reserve capacity in the backing vector and map:
BlotSetVector::reserve.
- Added a method to free extra storage used by the backing vector and
map: BlotSetVector::clear.
- Modified SmallBlotSetVector's template parameters so that only a value
and size can be specified--that type will always use SmallVector and
SmallDenseMap for its superclass' VectorT and MapT template
parameters.
- Updated variable names.
Blotting is a trick with Map/Set vectors that involves one assigning None to the
vector at the index mapped to an entry instead of deleting the entry itself from
the vector. This ensures that we do not need to move elements of the vector down
when erasing elements from the worklist.
We've been running doxygen with the autobrief option for a couple of
years now. This makes the \brief markers into our comments
redundant. Since they are a visual distraction and we don't want to
encourage more \brief markers in new code either, this patch removes
them all.
Patch produced by
for i in $(git grep -l '\\brief'); do perl -pi -e 's/\\brief //g' $i & done
- Add const getItems().
- Fix const find().
- erase() returns a boolean.
- Set erase() should not perform two lookups.
The implementation is covered by the unit tests with a small addition.
Other trivial API changes are trivially tested in upcoming commits.
Previously we represented all successors in a list where each successor
was represented by a SuccessorID. A SuccessorID is essentially an
unsigned int that stores some flags in the lower bits of the
integer. The two flags are: 1. IsDead, 2. IsNonLocal (where non local
means that it is a loop exit edge). When the IsNonLocal flag is not set,
the integer that is actually stored represents the ID of the successor
region. If the IsNonLocal flag is set, then the integer represents the
index in the parent region's successor list of the actual loop exit
successor.
The bug I mentioned was that we were not being careful enough in the
replacement code to distinguish in between successors that were loop
exit successors and those that were not. This could cause us to replace
a loop exit successor whose integer value was the same as the index of a
non-loop exit successor with the non-loop exit successor. This then
would cause us to miscompile and or introduce duplicate values into the
successor list. Luckily an assert I added caught the latter condition.
After I fixed this problem, an interesting performance issue was
exposed. I had assumed when using a list that I would never have more
than 10-20 successors (in general a reasonable assumption). But
introducing loop exit successors adds in an interesting wrinkle, namely
every block with an unreachable terminator will result in a successor
edge. This makes just iterating over a uniqued list really slow.
I solved the issue by writing a new data structure called
BlotSetVector. The interesting thing about BlotSetVector is that all
operations preserve index offsets. This means that if one erases a
value, all other values in the set vector are not moved around in the
internal vector. This is important since a loop exit edge needs to refer
to an invariant offset in the parent region's successor array since we
do not want to have to go through and update large amounts of unrelated
edges every time we erase an edge.
In terms of a test case, this invariant was impossible for me to reproduce since
it is sensitive to the order of successors. Even dumping the file and running
the analysis would not catch it. After 2 days of trying to make a test case I
gave up. But I filed rdar://23228299 to verify that sil-opt can round trip
in memory ordering of various items such as use lists, successors, predecessors,
block ordering, function ordering, etc.
rdar://22238658
Swift SVN r32839
