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);
}
Required to break circular dependence when introducing
UpdatingInstructionIterator.
Also, this is a lot of detail that doesn't belong in the general
InstOptUtils APIs. It's not something people should ever reach for.
Clarify the API. Make it suitable for use everywhere in the
compiler. We should try to standardize on it and allow it to do the
OSSA fixup more often.
Add InstructionDeleter::updatingIterator() factory so we never
normally need to use InstModCallbacks.
Fix bugs in which notifyWillBeDeleted() was being called on invalid
SIL. The bugs are easily exposed just by removing copy_value side
effects, but that will be in the follow-up commit.
Call notifyWillBeDeleted() only when identifying new dead instructions
that the client may not know about. Give the client control over
force-deleting instructions. When doing its own lifetime fixups, the
client may force-delete a set of related instructions. Invoking
callbacks for these force-deleted instructions is wrong.
TODO: partial_apply support is only partial. I disabled the buggy
cases. This should be easy to fix but requires designing some
InstructionDeleter test cases.
It's not needed anymore with delayed instruction deletion.
It was used for two purposes:
1. For analysis, which cache instructions, to avoid dangling instruction pointers
2. For passes, which maintain worklists of instructions, to remove a deleted instructions from the worklist. This is now done by checking SILInstruction::isDeleted().
Instead of caching alias results globally for the module, make AliasAnalysis a FunctionAnalysisBase which caches the alias results per function.
Why?
* So far the result caches could only grow. They were reset when they reached a certain size. This was not ideal. Now, they are invalidated whenever the function changes.
* It was not possible to actually invalidate an alias analysis result. This is required, for example in TempRValueOpt and TempLValueOpt (so far it was done manually with invalidateInstruction).
* Type based alias analysis results were also cached for the whole module, while it is actually dependent on the function, because it depends on the function's resilience expansion. This was a potential bug.
I also added a new PassManager API to directly get a function-base analysis:
getAnalysis(SILFunction *f)
The second change of this commit is the removal of the instruction-index indirection for the cache keys. Now the cache keys directly work on instruction pointers instead of instruction indices. This reduces the number of hash table lookups for a cache lookup from 3 to 1.
This indirection was needed to avoid dangling instruction pointers in the cache keys. But this is not needed anymore, because of the new delayed instruction deletion mechanism.
If the "regular" alias analysis thinks that an instruction may write to an address, check if the instruction is in an immutable scope of V.
That means that even if we don't know anything about the instruction (e.g. a call to an unknown function), we can be sure that it cannot write to the address.
An immutable scope is for example a read-only begin_access/end_access scope.
Another example is a borrow scope of an immutable copy-on-write buffer, for example:
%b = begin_borrow %array_buffer
%addr = ref_element_addr [immutable] %b : $BufferType, #BufferType.someField
Based on code in CopyPropagation. It is assumed that the passed in set of defs
is unique and that all such defs were found by using
CanonicalizeOSSALifetime::getCanonicalCopiedDef(copy).
InstModCallback is a value type and as such the original callback struct is not
being modified. Instead, a new InstModCallback struct is returned that is the
old callback + assignment of the passed in callback to the appropriate
field. Thus it makes sense to put this attribute on these methods so that we get
a warning if one does not use the new returned callback (otherwise, why would
one call this method?!). More likely a bug.
Without this when constructing an InstModCallback it is hard to distinguish
which closure is meant for which operation when passed to the constructor of
InstModCallback (if this was in Swift, we could use argument labels, but we do
not have such things in c++).
This new value type sort of formulation makes it unambiguous which callback is
used for what when constructing one of these.
I recently have been running into the issue that many of these APIs perform the
deletion operation themselves and notify the caller it is going to delete
instead of allowing the caller to specify how the instruction is deleted. This
causes interesting semantic issues (see the loop in deleteInstruction I
simplified) and breaks composition since many parts of the optimizer use
InstModCallbacks for this purpose.
To fix this, I added a notify will be deleted construct to InstModCallback. In a
similar way to the rest of it, if the notify is not set, we do not call any code
implying that we should have good predictable performance in loops since we will
always skip the function call.
I also changed InstModCallback::deleteInst() to notify before deleting so we
have a default safe behavior. All previous use sites of this API do not care
about being notified and the only new use sites of this API are in
InstructionDeleter that perform special notification behavior (it notifies for
certain sets of instructions it is going to delete before it deletes any of
them). To work around this, I added a bool to deleteInst to control this
behavior and defaulted to notifying. This should ensure that all other use sites
still compose correctly.
* [SR-13929][AutoDiff]: Enable [ossa] for Differentiation/Thunk.cpp:getOrCreateSubsetParametersThunkForLinearMap and promoteCurryThunkApplicationToDifferentiableFunction
This enables passes to use this as a utility that properly composes with how the
pass maintains its state. If an InstModCallback isn't passed in, we use the
default InstModCallback which should be cheap (always succeeding check for
nullptr + call inline default callback).
It now handles looking through forwarding consumes such as
destructures.
Expected to be NFC since borrow consolidation is still disabled by
default.
TODO: Write unit tests for various forwarding consumes in addition to
destructure.
struct_extract and tuple_extract do not belong in OSSA (except to
workaround certain extreme cases). They completely defeat
simplification that OSSA provides for optimizing owned lifetimes.
Copy propagation uses this utility to canonicalize owned values before
canonicalizing their lifetime.
This API is useful when writing compiler code that needs to handle ossa/non-ossa
as well as load_borrow/load while in OSSA. I am going to use this in
SILMem2Reg.
We have for a long time talked about creating a scope like data structure for
use in the SILOptimizer. The discussion was whether or not to reuse the
infrastructure in SILGen that does this already. There were concerns about doing
so since the code in the SILOptimizer and SILGen can work differently.
With that in mind, I added a small AssertingScope class and built on top of that
a composition SIL level class called SILOptScope that one can use to add various
cleanups. One is able to both destructively pop at end of scope and pop along
early exits.
At an implementation level, I kept it simple and:
1. Represented a scope as a stack of Optional<Cleanup> which are just a wrapper
around a std::function. The Optional is so that we can invalidate a cleanup.
2. Based all of these scopes around the idea that the user of the scope must
invalidate the scope by hand. If not, the scope object will assert at the end
of its RAII scope.
3. Rather than creating a whole class hierarchy, I just used std::function
closures to keep things simple.
Instead, put the archetype->instrution map into SIlModule.
SILOpenedArchetypesTracker tried to maintain and reconstruct the mapping locally, e.g. during a use of SILBuilder.
Having a "global" map in SILModule makes the whole logic _much_ simpler.
I'm wondering why we didn't do this in the first place.
This requires that opened archetypes must be unique in a module - which makes sense. This was the case anyway, except for keypath accessors (which I fixed in the previous commit) and in some sil test files.
Previously, because partial apply forwarders for async functions were
not themselves fully-fledged async functions, they were not able to
handle dynamic functions. Specifically, the reason was that it was not
possible to produce an async function pointer for the partial apply
forwarder because the size to be used was not knowable.
Thanks to https://github.com/apple/swift/pull/36700, that cause has been
eliminated. With it, partial apply forwarders are fully-fledged async
functions and in particular have their own async function pointers.
Consequently, it is again possible for these partial apply forwarders to
handle non-constant function pointers.
Here, that behavior is restored, by way of reverting part of
ee63777332 while preserving the ABI it
introduced.
rdar://76122027
The comment in LowerHopToActor explains the design here.
We want SILGen to emit hops to actors, ignoring executors,
because it's easier to fully optimize in a world where deriving
an executor is a non-trivial operation. But we also want something
prior to IRGen to lower the executor derivation because there are
useful static optimizations we can do, such as doing the derivation
exactly once on a dominance path and strength-reducing the derivation
(e.g. exploiting static knowledge that an actor is a default actor).
There are probably phase-ordering problems with doing this so late,
but hopefully they're restricted to situations like actors that
share an executor. We'll want to optimize that eventually, but
in the meantime, this unblocks the executor work.
This directly adds support to BasicBlockCloner for updating OSSA.
It also adds a much more general-purpose GuaranteedPhiBorrowFixup
utility which can be used for more complicated SSA updates, in which
multiple phis need to be created. More generally, it handles adding
nested borrow scopes for guaranteed phis even when that phi is used by
other guaranteed phis.
This is a basic SSA-based liveness algorithm. It should just do what
it says. This change rescues the core logic from the nonsense that's
been hacked in. There are now two APIs:
(1) computeLifetimeBoundary (new) only does lifetime analysis. It
provides a new API that always succeeds and provides the last use
points so clients can do the right thing based on the user. I need
this for OSSA utilities.
(2) computeFrontier (old) emulates the original API with a simplified
version of the original logic.
Next steps:
- replace the old API with a separate utility that computes destroy
insertion points. Completely remove DeadEndBlocks from lifetime
analysis, because it simply has nothing to do with liveness.
- Gradually migrate clients to either the new lifetime API provided
here or the new destroy insertion API to be provided later.
Previously, thick async functions were represented sometimes as a pair
of (AsyncFunctionPointer, nullptr)--when the thick function was produced
via a thin_to_thick_function, e.g.--and sometimes as a pair of
(FunctionPointer, ThickContext)--when the thick function was produced by
a partial_apply--with the size stored in the slot of the ThickContext.
That optimized for the wrong case: partial applies of dynamic async
functions; in that case, there is no appropriate AsyncFunctionPointer to
form when lowering the partial_apply instruction. The far more common
case is to know exactly which function is being partially applied. In
that case, we can form the appropriate AsyncFunctionPointer.
Furthermore, the previous representation made calling a thick function
more complex: it was always necessary to check whether the context was
in fact null and then proceed along two different paths depending.
Here, that behavior is corrected by creating a thunk in a mandatory
IRGen SIL pass in the case that the function that is being partially
applied is dynamic. That new thunk is then partially applied in place
of the original partial_apply of the dynamic function.
OwnershipEliminator lowers destroy_value [poison] to debug_value
[poison].
IRGen overwrites all references in shadow copies with a sentinel value
in place of debug_value [poison].
Part 2/2: rdar://75012368 (-Onone compiler support for early object
deinitialization with sentinel dead references)
Ensure that any object lifetime that will be shortened ends in
destroy_value [poison], indicating that the reference should not be
dereferenced (e.g. by the debugger) beyond this point.
This has no way of knowing whether the object will actually be
deallocated at this point. It conservatively avoids showing garbage to
debuggers.
Part 1/2: rdar://75012368 (-Onone compiler support for early object
deinitialization with sentinel dead references)
This bleeds into the implementation where "guaranteed" is used
everywhere to talk about optimization of guaranteed values. We need to
use mandatory to indicate we're talking about the pass pipeline.
It is currently disabled so this commit is NFC.
MandatoryCopyPropagation canonicalizes all all OSSA lifetimes with
either CopyValue or DestroyValue operations. While regular
CopyPropagation only canonicalizes lifetimes with copies. This ensures
that more lifetime program bugs are found in debug builds. Eventually,
regular CopyPropagation will also canonicalize all lifetimes, but for
now, we don't want to expose optimized code to more behavior change
than necessary.
Add frontend flags for developers to easily control copy propagation:
-enable-copy-propagation: enables whatever form of copy propagation
the current pipeline runs (mandatory-copy-propagation at -Onone,
regular copy-propation at -O).
-disable-copy-propagation: similarly disables any form of copy
propagation in the current pipelien.
To control a specific variant of the passes, use
-Xllvm -disable-pass=mandatory-copy-propagation
or -Xllvm -disable-pass=copy-propagation instead.
The meaning of these flags will stay the same as we adjust the
defaults. Soon mandatory-copy-propagation will be enabled by
default. There are two reasons to do this, both related to predictable
behavior across Debug and Release builds.
1. Shortening object lifetimes can cause observable changes in program
behavior in the presense of weak/unowned reference and
deinitializer side effects.
2. Programmers need to know reliably whether a given code pattern will
copy the storage for copy-on-write types (Array, Set). Eliminating
the "unexpected" copies the same way at -Onone and -O both makes
debugging tractable and provides assurance that the code isn't
relying on the luck of the optimizer in a particular compiler
release.
When the underlying utility was changed for OSSA, it changed the
semantics of the callback, which breaks the way I've always used a
deletion callback to update iterators.
/// \p callback is called on each deleted instruction before deleting any
/// instructions. This way, the SIL is valid in the callback. However, the
/// callback cannot be used to update instruction iterators since other
/// instructions to be deleted remain in the instruction list.
Enable most simplify-cfg optimizations as long as the block arguments
have trivial types. Enable most simplify CFG unit tests cases.
This massively reduces the size of the CFG during OSSA passes.
Test cases that aren't supported in OSSA yet have been moved to a
separate test file for disabled OSSA tests,
Full simplify-cfg support is currently blocked on OSSA utilities which
I haven't checked in yet.
- Properly clone and use debug scopes for all instructions in pullback functions.
- Emit `debug_value` instructions for adjoint values.
- Add debug locations and variable info to adjoint buffer allocations.
- Add `TangentBuilder` (a `SILBuilder` subclass) to unify and simplify special emitter utilities for tangent vector code generation. More simplifications to come.
Pullback variable inspection example:
```console
(lldb) n
Process 50984 stopped
* thread #1, queue = 'com.apple.main-thread', stop reason = step over
frame #0: 0x0000000100003497 main`pullback of foo(x=0) at main.swift:12:11
9 import _Differentiation
10
11 func foo(_ x: Float) -> Float {
-> 12 let y = sin(x)
13 let z = cos(y)
14 let k = tanh(z) + cos(y)
15 return k
Target 0: (main) stopped.
(lldb) fr v
(Float) x = 0
(Float) k = 1
(Float) z = 0.495846391
(Float) y = -0.689988375
```
Resolves rdar://68616528 / SR-13535.
Deinitializer side effects severely handicap the connection-graph
based EscapeAnalysis. Because it's not flow-sensitive, this approach
falls apart whenever an object is released in the current function,
which makes it seem to have escaped everywhere (it generally doesn't
matter if it doesn't escape until the release point, but the analysis
can't discern that).
This can be slightly mitigated by realizing that releasing an object
can only cause things it points to to escape if the object itself has
references or pointers.
Fix: Don't create a escaping content node when releasing an object
that can't contain any references or pointers. The previous commit,
"Fix EscapeAnalysis::mayReleaseContent" would defeat release-hoisting
in important cases without doing anything else. Adding this extra
precision to the connection graph avoids some regressions.
