* Add all [differential operators](https://github.com/apple/swift/blob/master/docs/DifferentiableProgramming.md#list-of-differential-operators).
* Add `withoutDerivative(at:)`, used for efficiently stopping the derivative propagation at a value and causing the derivative at the value to be zero.
* Add utility `differentiableFunction(from:)`, used for creating a `@differentiable` function from an original function and a derivative function.
Mostly work done by @marcrasi and @dan-zheng.
Partially resolves TF-843.
TODO:
* Add `AnyDerivative`.
* Add `Array.differentiableMap(_:)` and `differentiableReduce(_:_:)`.
RedundantPhiElimination eliminates block phi-arguments which have the same value as other arguments of the same block.
This also works with cycles, like two equivalent loop induction variables. Such patterns are generated e.g. when using stdlib's enumerated() on Array.
preheader:
br bb1(%initval, %initval)
header(%phi1, %phi2):
%next1 = builtin "add" (%phi1, %one)
%next2 = builtin "add" (%phi2, %one)
cond_br %loopcond, header(%next1, %next2), exit
exit:
is replaced with
preheader:
br bb1(%initval)
header(%phi1):
%next1 = builtin "add" (%phi1, %one)
%next2 = builtin "add" (%phi1, %one) // dead: will be cleaned-up later
cond_br %loopcond, header(%next1), exit
exit:
Any remaining dead or "trivially" equivalent instructions will then be cleaned-up by DCE and CSE, respectively.
rdar://problem/33438123
Andy and I for some time have been discussing the right name for these two
"ownership concepts". What we realized is that the "ing" on
BorrowScopeIntroducingValue is very unfortunate since this value is the result
of a new borrow scope being introduced. So the name should be really:
BorrowScopeIntroducedValue. Given that is sort of unsatisfying, we settled on
the name BorrowedValue.
Once we found the name BorrowedValue, we naturally realized that
BorrowScopeOperand -> BorrowingOperand followed. This is because the operand is
the operand of the instruction that is creating the new borrow scope. So in a
sense the Operand is the "Use" that causes the original value to become
borrowed. So a BorrowingOperand is where the action is and is "active".
Devirtualizing try_apply modified the CFG, but passes that run
devirtualization were not invalidating any CFG analyses, such as the
domtree.
This could hypothetically have caused miscompilation, but will be
caught by running with -sil-verify-all.
If such a call is dominated by another call to the same getter, it is replaced by a direct load of the property - assuming that it is already computed.
rdar://problem/34715412
TLDR: This will allow me to in a forthcoming commit to eliminate the extra run
of the peephole optimizer to seed the phi arg analysis since this eliminates
potential data invalidation issues. That being said, I am formalizing the
language/model in the pass a little in this commit, so I wanted to give a long
description below.
----
In this commit, I am formalizing some of the language around this optimization
away phi nodes specifically and more towards a notion that Andy and I have
discussed called "Joined Live Ranges". The idea is a "Live Range" in OSSA is an
owned value together with its set of forwarding uses. The owned value is in a
certain sense the equivalence class representative of all of the values that are
derived from the owned value via forwarding instructions.
This works well as long as all of the "forwarding" instructions only derive
their ownership from a single operand. Some instructions without that property
are branch, tuple, struct. Since such a "forwarding" instruction derives its
ownership by merging the ownership of multiple operands, if multiple of its
operands are non-trivial owned operands, we are in a sense joining together the
live ranges of those non-trivial owned operands. The main implication of this is
that if we want to convert the joined live range from owned to guaranteed, we
can only do it if we can also do it for all of its incoming values at the same
time.
This creates a conundrum though since this pass has been written like a peephole
pass which is ill-suited to be converted into this form. So instead, this pass
seeds an analysis from peephole runs that /could/ have been converted from owned
to guaranteed except for a specific joined live range. Then after we reach a
fixed point, we use that information from the failed peepholes to try to
eliminate the joined live ranges.
This approach is a good approach, but if implemented in certain ways exposes the
risk of problems around touching invalidated data. Specifically, before this
patch, this was implemented with the concern that each branch
instruction (currently the only supported type of joined live range instruction)
could be paired with multiple owned value introducers. This is because
initially, we were allowing for tuple, struct with multiple non-trivial operands
to be used as owned value introducers. This implied that we could not rely on
just storing a bool per joined live range operand since we would need to know
that all introducers associated with the operand were optimizable.
After some thought/discussion, I realized that this sort of optimization can
also apply to tuple/struct/similar insts. This let to the shift in
thinking/realization that we could talk instead about general joined live ranges
and handle tuple/struct/similar instructions just like they were branch/phi! As
such, if we assume that all such instructions are treated as separate
LiveRanges, then we know that our branch can only have a single owned value
introducer since we do not look through /any/ joined live ranges when computing
LiveRanges.
This realization then allows us to store a single bool value marking the operand
on the joined live range as being one that we /may/ be able to optimize. This
then allows us to simplify the state we handle and not have to worry about
storing memory to instructions that may be eliminated. Since we have a joined
live range use, we know that any value that is used by the joined live range can
not be eliminated by the peephole optimizer.
We are checking the unknown consuming use vector, so the name makes this clearer
and makes it clear we are not talking about destroying consumers.
I also eliminated the phiToIncomingValueMultiMap being passed in favor of a bool
argument since that is how we are using it today. That was a vestige of an
earlier version of the patch that had to be sunk.
We need this anyways for -Onone and I want to do some experiments with running
this very early so I can expose more of the stdlib (modulo inlining) to the new
ownership optimizing passes.
I also changed how the inliner handles inlining around OSSA by changing it to
check early that if the caller is in ossa, then we only inline if all of the
callees that the caller calls are in ossa. The intention is to hopefully avoid
weird swings in code-size/perf due to the inliner heuristic's calculation being
artificially manipulated due to some callees not being available to inline (due
to this difference) when others are already available.
I was being too clever here and in the process of "foot-gunned"
myself. Specifically, I was hoping to use bisection to do some is contained in
list tests. But the list that I actually bisected upon was not the original list
and was just based on the original sorted list! So the pointer comparison for
the bisect no longer worked. Since the bisection was on pointer addresses, if we
were lucky and the new addresses in the new array were sorted the same as the
original array, we wouldn't hit anything.
rdar://60262326
* Use in_guaranteed for let captures
With this all let values will be captured with in_guaranteed convention
by the closure. Following are the main changes :
SILGen changes:
- A new CaptureKind::Immutable is introduced, to capture let values as in_guaranteed.
- SILGen of in_guaranteed capture had to be fixed.
in_guaranteed captures as per convention are consumed by the closure. And so SILGen should not generate a destroy_addr for an in_guaranteed capture.
But LetValueInitialization can push Dealloc and Release states of the captured arg in the Cleanup stack, and there is no way to access the CleanupHandle and disable the emission of destroy_addr while emitting the captures in SILGenFunction::emitCaptures.
So we now create, temporary allocation of the in_guaranteed capture iduring SILGenFunction::emitCaptures without emitting destroy_addr for it.
SILOptimizer changes:
- Handle in_guaranteed in CopyForwarding.
- Adjust dealloc_stack of in_guaranteed capture to occur after destroy_addr for on_stack closures in ClosureLifetimeFixup.
IRGen changes :
- Since HeapLayout can be non-fixed now, make sure emitSize is used conditionally
- Don't consider ClassPointerSource kind parameter type for fulfillments while generating code for partial apply forwarder.
The TypeMetadata of ClassPointSource kind sources are not populated in HeapLayout's NecessaryBindings. If we have a generic parameter on the HeapLayout which can be fulfilled by a ClassPointerSource, its TypeMetaData will not be found while constructing the dtor function of the HeapLayout.
So it is important to skip considering sources of ClassPointerSource kind, so that TypeMetadata of a dependent generic parameters gets populated in HeapLayout's NecessaryBindings.
