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.
The utility provides a standard way for backwards traversing a region of
a function constrained by a predicate (isInRegion) starting from some
root blocks. It exposes a visit function for post-order and iterable
collections for post-order and reverse post-order. Adding corresponding
pre-order functionality will be straightforward.
This is a tiny routine that is useful for writing assertions to be
used for quick sanity checks without computing Dominance.
It doesn't always make sense to require a pass to maintain and pass
around Dominance just for an assert.
Instead make `findJointPostDominatingSet` a stand-alone function.
There is no need to keep the temporary SmallVector alive across multiple calls of findJointPostDominatingSet for the purpose of re-using malloc'ed memory. The worklist usually contains way less elements than its small size.
Importantly this also lets us use the analysis framework to validate that we do
properly invalidate DeadEndBlocks, preventing bugs.
I did not thread this all over the compiler. Instead I just used it for now in
SemanticARCOpts just to add some coverage without threading it into too many
places.
NFC
Not only that this function _is_ not used anymore, it also _should_ not be used.
Optimizations should not make decisions based on if there are any dead-end blocks in a function.
This could lead to situations, e.g. where an optimization can be done before inlining, but not after inlining a (potentially small) function which has a dead-end block.
This is a generic API that when ownership is enabled allows one to replace all
uses of a value with a value with a differing ownership by transforming/lifetime
extending as appropriate.
This API supports all pairings of ownership /except/ replacing a value with
OwnershipKind::None with a value without OwnershipKind::None. This is a more
complex optimization that we do not support today. As a result, we include on
our state struct a helper routine that callers can use to know if the two values
that they want to process can be handled by the algorithm.
My moticiation is to use this to to update InstSimplify and SILCombiner in a
less bug prone way rather than just turn stuff off.
Noting that this transformation inserts ownership instructions, I have made sure
to test this API in two ways:
1. With Mandatory Combiner alone (to make sure it works period).
2. With Mandatory Combiner + Semantic ARC Opts to make sure that we can
eliminate the extra ownership instructions it inserts.
As one can see from the tests, the optimizer today is able to handle all of
these transforms except one conditional case where I need to eliminate a dead
phi arg. I have a separate branch that hits that today but I have exposed unsafe
behavior in ClosureLifetimeFixup that I need to fix first before I can land
that. I don't want that to stop this PR since I think the current low level ARC
optimizer may be able to help me here since this is a simple transform it does
all of the time.
Often times when one is working with ownership one has a value V and a set of
use points Uses where you want V's lifetime to end at, but those Uses together
(while not reachable from each other) only partially post-dominate
V. JointPostDominanceSetComputer is a struct that implements a general solution
to that operation at the block level. The struct itself is just a set of state
that the computation uses so that a pass can clear the state (allowing for us to
avoid needing to remalloc if we had any small data structures that went big).
To get into the semantics, the API
JointPostDominanceSetComputer::findJointPostDominatingSet() takes in a
"dominating block" and a "dominated block set" and returns two things to the user:
1. A set of blocks that together with the "dominated block set"
jointly-postdominate the "dominating block".
2. A list of blocks in the "dominated block set" that were reachable from any of
the other "dominated blocks", including itself in the case of a block in aloop.
Conceptually we are performing a backwards walk up the CFG towards the
"dominating block" starting at each block in the "dominated block set". As we
go, we track successor blocks and report any successor blocks that we do not hit
during our traversal as result blocks and are passed to the result callback.
Now what does this actually mean:
1. All blocks in the "dominated blockset" that are at the same loop nest level
as our dominating block will always be part of the final post-dominating block
set.
2. All "lifetime ending" blocks that are at a different loop nest level than our
dominating block are not going to be in our final result set. Let
LifetimeEndingBlock be such a block. Then note that our assumed condition
implies that there must be a sub-loop, SubLoop, at the same level of the
loop-nest as the dominating block that contains LifetimeEndingBlock. The
algorithm will yield to the caller the exiting blocks of that loop. It will also
flag the blocks that were found to be a different use level, so the caller can
introduce a copy at that point if needed.
NOTE: Part of the reason why I am writing this rather than using the linear
lifetime checker (LLChecker) is that LLChecker is being used in too many places
because it is convenient. Its original true use was for emitting diagnostics and
that can be seen through the implementation. I don't want to add more
contortions to that code, so as I am finding new use cases where I could either
write something new or add contortions to the LLChecker, I am doing the former.
The only reason why BranchPropagatedUser existed was because early on in SIL, we
weren't sure if cond_br should be able to handle non-trivial values in
ossa. Now, we have reached the point where we have enough experience to make the
judgement that it is not worth having in the representation due to it not
holding its weight.
Now that in ToT we have banned cond_br from having non-trivial operands in ossa,
I can just eliminate BranchPropagatedUser and replace it with the operands that
we used to construct them!
A few notes:
1. Part of my motiviation in doing this is that I want to change LiveRange to
store operands instead of instructions. This is because we are interested in
being able to understand the LiveRange at a use granularity in cases where we
have multiple operands. While doing this, I discovered that I needed
SILInstructions to use the Linear Lifetime Checker. Then I realized that now was
the time to just unwind BranchPropagatedUser.
2. In certain places in SemanticARCOpts, I had to do add some extra copies to
transform arrays of instructions from LiveRange into their operand form. I am
going to remove them in a subsequent commit when I change LiveRange to work on
operands. I am doing this split to be incremental.
3. I changed isSingleInitAllocStack to have an out array of Operand *. The only
user of this code is today in SemanticARCOpts and this information is fed to the
Linear Lifetime Checker, so I needed to do it.
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
Avoid emitting unnecessary basic block for cleanup chains. This is a
general approach that handles all cases while simplifying SILGen
emission and keeping the CFG in a valid state during SILGen.
