OSSA lifetime canonicalization can take a very long time in certain
cases in which there are large basic blocks. to mitigate this, add logic
to skip walking the liveness boundary for extending liveness to dead
ends when there aren't any dead ends in the function.
Updates `DeadEndBlocks` with a new `isEmpty` method and cache to
determine if there are any dead-end blocks in a given function.
(cherry picked from commit 1f3f830fc7)
When the utility is used by the ConsumeOperatorCopyableValuesChecker,
the checker guarantees that the lifetime can end at the consumes, that
there are no uses after those consumes. In that circumstance, the
utility maintains liveness to those consumes and as far as possible
without introducing a copy everywhere else.
The lack of complete lifetimes has forced the utility to extend liveness
of values to dead-ends. That extension, however, is in tension with the
use that the checker is putting the utility to. If there is a dead-end
after a consume, liveness must not be maintained to that dead-end.
rdar://147586673
Regardless of consumes of copies, if the original lexical value is not
consumed on a dead-end path, it must remain live to that dead-end.
rdar://145226757
It's sufficient just to have a struct with a kind and a value. There
aren't any cases where the payload's original type benefits from being
statically preserved--they're only ever obtained as `SILValue`s. Keep
the type safety by way of constructors.
This is necessary to fix a recent OSSA bug that breaks common occurrences on
mark_dependence [nonescaping]. Rather than reverting that change above, we make
forward progress toward implicit borrows scopes, as was the original intention.
In the near future, all InteriorPointer instructions will create an implicit
borrow scope. This means we have the option of not emitting extraneous
begin/end_borrow instructions around intructions like ref_element_addr,
open_existential, and project_box. After that, we can also migrate
GuaranteedForwarding instructions like tuple_extract and struct_extract.
To determine where a lifetime ends within dead-end blocks,
OSSACanonicalizeOwned uses OSSACompleteLifetime's
visitAvailabilityBoundary. This API takes a liveness which it uses to
walk forward to the availability boundary. Specifically, the liveness
passed from OSSACanonicalizeOwned to OSSACompleteLifetime is a variation
of OSSACanonicalizeOwned's own liveness (it has destroys added).
There is a mismatch in the characteristics of livenesses created by
OSSACanonicalizeOwned and OSSACompleteLifetime: The former deals with
not only direct uses of a value but also uses of its copies; that
introduces the possibility for consuming uses in the middle of liveness.
The latter on the other hand deals only with uses of a single value
(nestedly, but at each level of nesting only a single value). Passing a
liveness from the former to the latter without handling this mismatch
is incorrect: OSSACompleteLifetime understands consuming uses to always
end a lifetime, even when they are in the middle of a copy-extended
liveness. The result is that OSSACompleteLifetime produces non-sensical
results when provided with such a liveness.
To address this, fixup the liveness passed from OSSACanonicalizeOwned to
OSSACompleteLifetime by demoting consuming uses that appear within
(that's to say _not_ on the boundary) of liveness to non-consuming uses.
rdar://142846936
Because discovery of defs walks into reborrows and borrowed-from
instructions, copies may be seen whose underlying value is a guaranteed
value (namely, a reborrow or a borrowed-from instruction). Such copies
may be used beyond the lifetime end of such guaranteed values, so it's
not allowed to sink copies to their consuming uses. Such
canonicalization is the responsibility of the OSSACanonicalizeGuaranteed
utility.
rdar://139842132
The utility performs two def-use traversals. The first determines
liveness from uses. The second rewrites copies.
Previously, the defs whose uses were analyzed were discovered twice,
once during each traversal. The non-triviality of the discovery logic
(i.e. the logic determining when to walk into the values produced by the
instructions which were the users of visited uses) opened the
possibility for a divergence between the two discoveries. This
possibility had indeed been realized--the two traversals didn't visit
exactly the same uses, and issues ensue.
Here, the defs whose uses are analyzed are discovered only once (and not
discarded as their uses are analyzed) during the first traversal. The
second traversal reuses the defs discovered in the first traversal,
eliminating the possibility of a def discovery difference.
The second traversal is now done in a different order. This results in
perturbing the SIL in certain cases.
In preparation for only recording the defs once, replace the
GraphNodeWorklist of defs with a SetVector. Preserve the current
visitation order by creating a worklist of indices to be visited.
When rewriting uses, determine how that rewriting should proceed based
on the kind of def whose use is being visited. Direct uses of reborrows
and borrowed-froms never need to be rewritten because every such use is
a use of a guaranteed value and can never require a copy.
Add a type which distinguishes among the types of defs that are pushed
onto the "def-use worklist". Note that it's not possible to rely on the
kind of value because the root may itself be a copy_value. For now, the
distinction is discarded as soon as the def is visited.
When creating `destroy_value`s, create them with the `dead_end` flag if
all subsequent destroys (those from which it is notionally being
hoisted) have the flag.
When creating `destroy_value`s, create them with the `dead_end` flag if
all subsequent destroys (those from which it is notionally being
hoisted) have the flag.
Now that `isWithinBoundary` and `areUsesWithinBoundary` are "the same"
(up to the fact that one takes an instruction and the other an array of
operands), there's no reason to use the latter when looking at a single
instruction.
When checking whether an instruction is contained in a liveness
boundary, a pointer to a DeadEndBlocks instance must always be passed.
When the pointer is null, it is only checked that the instruction occurs
within the direct live region. When the pointer is non-null, it is
checked whether the instruction occurs within the region obtained by
extending the live region up to the availability boundary within
dead-end regions that are adjacent to the non-lifetime-ending portion of
the liveness boundary.
Use the more precise areUsesWithinBoundary API (which takes dead-end
blocks into account). This requires first updating liveness with the
newly created destroys.
Just clear all structures in a single method which is called wherever
clearing is done. Fixes a failure to clear discoveredBlocks under
certain circumstances.
Copies of a lexical lifetime are not lexical. Their destroys can be
hoisted over deinit barriers. So when extending lifetimes to deinit
barriers, only deal with the direct lifetime, not the copy-extended
lifetime.
Now that the two known issues which resulted in invalid SIL being
provided to lifetime completion have been addressed, tighten up the
completion done on the availability boundary not to allow leaks.
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)
Enhance the utility with the ability to end lifetimes of lexical values
at indicated instructions, overriding the usual behavior of maintaining
such lifetimes' previous endpoints (modulo non-deinit-barrier
instructions).
Parameterized `extendUnconsumedLiveness` on the ends of interest and the
action to take when visiting the extended boundary and named the
resulting function `visitExtendedUnconsumedBoundary`.
The new boundary allows for invalid OSSA where values are not consumed
on paths leading to blocks that exit the function normally. In such
cases, the value is allowed to continue leaking as before.
Compute, update and handle borrowed-from instruction in various utilities and passes.
Also, used borrowed-from to simplify `gatherBorrowIntroducers` and `gatherEnclosingValues`.
Replace those utilities by `Value.getBorrowIntroducers` and `Value.getEnclosingValues`, which return a lazily computed Sequence of borrowed/enclosing values.
