Computing dominance relation between instructions in the same block was done with linear search, e.g. when checking if a value-use is before its lifetime ending instruction.
This resulted in quadratic complexity and very long compile times for very large basic blocks.
Now we do the dominance check with pre-computed instruction indices, which is O(0) instead of O(n).
https://github.com/swiftlang/swift/issues/86663
rdar://168511262
This was a wrong use of the InstructionDeleter.
When replacing a mark_dependence with a new one the old one has to be deleted _without_ fixing its lifetime.
Otherwise destroy_value instructions are inserted, which is obviously wrong.
Fixes a SIL ownership verification error.
rdar://161831308
Preserve ownership for empty non-trivial structs. This currently applies to
~Escapable structs. People often use empty structs to investigate language
behavior. They should behave just like a struct that wraps a
pointer.
Previously, this would crash later during OSSA lifetime completion:
Assertion failed: (isa<UnreachableInst>(block->getTerminator())),
function computeRegion, file OSSALifetimeCompletion.cpp.
PredictableMemOpt only runs with OSSA. The recent refactoring did not
preserve non-OSSA conditions because it adds complexity. This commit
just makes it official.
In the near future, this pass will be replaced by an OSSA-only pass
anyway, so this brings us one small step closer to that.
This fixes a logic error that will only be exposed by the additional
functionality that motivated the cleanup. When the additional
functionality is checked in, it will contain a unit test for this fix.
This bug was introduced in:
commit 755a146730 (public/predmem_rewrite)
Author: Andrew Trick <atrick@apple.com>
Date: Fri Sep 27 22:18:29 2024
[NFC] rewrite PredictableMemOpts dead allocation elimination
Generalize the code that promotes the remaining uses of an allocation to make it
readable and extensible. We need to be able to promote allocations with more
interesting uses, namely mark_dependence.
Although I don't plan to bring over new assertions wholesale
into the current qualification branch, it's entirely possible
that various minor changes in main will use the new assertions;
having this basic support in the release branch will simplify that.
(This is why I'm adding the includes as a separate pass from
rewriting the individual assertions)
For years, optimizer engineers have been hitting a common bug caused by passes
assuming all SILValues have a parent function only to be surprised by SILUndef.
Generally we see SILUndef not that often so we see this come up later in
testing. This patch eliminates that problem by making SILUndef uniqued at the
function level instead of the module level. This ensures that it makes sense for
SILUndef to have a parent function, eliminating this possibility since we can
define an API to get its parent function.
rdar://123484595
When promoting a load_borrow, the re-borrows were not considered which lead to leaked values.
Now, just bail if a load_borrow has re-borrows.
rdar://118402432
llvm::SmallSetVector changed semantics
(https://reviews.llvm.org/D152497) resulting in build failures in Swift.
The old semantics allowed usage of types that did not have an
`operator==` because `SmallDenseSet` uses `DenseSetInfo<T>::isEqual` to
determine equality. The new implementation switched to using
`std::find`, which internally uses `operator==`. This type is used
pretty frequently with `swift::Type`, which intentionally deletes
`operator==` as it is not the canonical type and therefore cannot be
compared in normal circumstances.
This patch adds a new type-alias to the Swift namespace that provides
the old semantic behavior for `SmallSetVector`. I've also gone through
and replaced usages of `llvm::SmallSetVector` with the
`Swift::SmallSetVector` in places where we're storing a type that
doesn't implement or explicitly deletes `operator==`. The changes to
`llvm::SmallSetVector` should improve compile-time performance, so I
left the `llvm::SmallSetVector` where possible.
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.
It's not correct to copy the location from an instruction and turn it into a
RegularLocation if the Location was, e.g., a CleanupLocation. It's always safe
to use a compilergenerated location instead.
Caught by the dihole verification int the source compatibility suite.
rdar://107984038
Add `deletableInstructions()` and `reverseDeletableInstructions()` in SILBasicBlock.
It allows deleting instructions while iterating over all instructions of the block.
This is a replacement for `InstructionDeleter::updatingRange()`.
It's a simpler implementation than the existing `UpdatingListIterator` and `UpdatingInstructionIteratorRegistry`, because it just needs to keep the prev/next pointers for "deleted" instructions instead of the iterator-registration machinery.
It's also safer, because it doesn't require to delete instructions via a specific instance of an InstructionDeleter (which can be missed easily).
`getValue` -> `value`
`getValueOr` -> `value_or`
`hasValue` -> `has_value`
`map` -> `transform`
The old API will be deprecated in the rebranch.
To avoid merge conflicts, use the new API already in the main branch.
rdar://102362022
Otherwise in certain cases due to load promotion, we emit incorrect errors. As
an example:
let x = ...
var y = x
print(y)
would show an error that x is consumed twice... which is incorrect.
Andy some time ago already created the new API but didn't go through and update
the old occurences. I did that in this PR and then deprecated the old API. The
tree is clean, so I could just remove it, but I decided to be nicer to
downstream people by deprecating it first.
Track in-use iterators and update them both when instructions are
deleted and when they are added.
Safe iteration in the presence of arbitrary changes now looks like
this:
for (SILInstruction *inst : deleter.updatingRange(&bb)) {
modify(inst);
}
