[swift-dev] Protocol Devirtualizer Pass
Raj Barik
rkbarik at gmail.com
Thu Dec 21 16:50:00 CST 2017
Sure, I can :)
On Thu, Dec 21, 2017 at 12:24 PM, Michael Gottesman <mgottesman at apple.com>
wrote:
> Is it possible to merge them?
>
> > On Dec 21, 2017, at 11:07 AM, Raj Barik via swift-dev <
> swift-dev at swift.org> wrote:
> >
> > Hi,
> >
> > Thanks.
> >
> >
> > Are you implementing it as a separate pass, or is it part of function
> signature specialization?
> >
> >
> > I am currently implementing this as a separate pass. There is some code
> overlap between the two (FunctionSignatureOpt and ProtocolDevirtualizerOpt)
> in terms of checking which functions can be optimized. Barring that, the
> code is quite different even though they follow the same pattern (thunk and
> a separate function).
> >
> > --Raj
> >
> >
> >
> > Slava
> >
> >>
> >> @inline(never) internal func wrap_inc_optional(a:SumProtocol?,
> val:Int) -> Int?{
> >> return a?.increment(i:val)
> >> }
> >>
> >> The generated SIL looks something like this:
> >>
> >> sil hidden [noinline] @_T04main21wrap_inc_optionalSiSgAA11SumProtocol_pSg1a_Si3valtF
> : $@convention(thin) (@owned Optional<SumProtocol>, Int) -> Optional<Int> {
> >> // %0 // users: %11, %4,
> %7, %2
> >> // %1 // users: %10, %3
> >> bb0(%0 : $Optional<SumProtocol>, %1 : $Int):
> >> debug_value %0 : $Optional<SumProtocol>, let, name "a", argno 1 //
> id: %2
> >> debug_value %1 : $Int, let, name "val", argno 2 // id: %3
> >> switch_enum %0 : $Optional<SumProtocol>, case
> #Optional.some!enumelt.1: bb2, case #Optional.none!enumelt: bb1 // id: %4
> >>
> >> bb1: // Preds: bb0
> >> %5 = enum $Optional<Int>, #Optional.none!enumelt // user: %6
> >> br bb3(%5 : $Optional<Int>) // id: %6
> >>
> >> bb2: // Preds: bb0
> >> %7 = unchecked_enum_data %0 : $Optional<SumProtocol>,
> #Optional.some!enumelt.1 // user: %8
> >> %8 = open_existential_ref %7 : $SumProtocol to
> $@opened("F0395A0A-E5DE-11E7-A06A-420039484801") SumProtocol // users:
> %10, %10, %9
> >> %9 = witness_method $@opened("F0395A0A-E5DE-11E7-A06A-420039484801")
> SumProtocol, #SumProtocol.increment!1 : <Self where Self : SumProtocol>
> (Self) -> (Int) -> Int, %8 : $@opened("F0395A0A-E5DE-11E7-A06A-420039484801")
> SumProtocol : $@convention(witness_method) <τ_0_0 where τ_0_0 :
> SumProtocol> (Int, @guaranteed τ_0_0) -> Int // type-defs: %8; user: %10
> >> %10 = apply %9<@opened("F0395A0A-E5DE-11E7-A06A-420039484801")
> SumProtocol>(%1, %8) : $@convention(witness_method) <τ_0_0 where τ_0_0 :
> SumProtocol> (Int, @guaranteed τ_0_0) -> Int // type-defs: %8; user: %12
> >> release_value %0 : $Optional<SumProtocol> // id: %11
> >> %12 = enum $Optional<Int>, #Optional.some!enumelt.1, %10 : $Int //
> user: %13
> >> br bb3(%12 : $Optional<Int>) // id: %13
> >>
> >> // %14 // user: %15
> >> bb3(%14 : $Optional<Int>): // Preds: bb1 bb2
> >> return %14 : $Optional<Int> // id: %15
> >>
> >>
> >> The above branching code (in red) in the SIL makes it non-trivial to
> abstract out the non-nil path to a generic outlined method while keeping
> the branching code in the thunk and also its not clear if the SILCombiner
> peephole optimizer will actually come into affect for this scenario
> (because of the branching code getting inlined in the caller). It also
> gets more complicated if there are more than one optional types as
> parameter to wrap_inc_optional. Any clue on how one can handle optional
> types for devirtualization or if there are any existing transformations in
> Swift compiler that can help implement this easily? Thanks.
> >>
> >> -R
> >>
> >>
> >>
> >> On Wed, Dec 13, 2017 at 3:28 PM, Arnold Schwaighofer <
> aschwaighofer at apple.com> wrote:
> >> You don’t need a second open_existential_ref in the _wrap_inc<T:
> SumProtocol> function. It should look something like this:
> >>
> >> sil @_wrap_inc : $@convention(thin) <T where T : SumProtocol> (@owned
> T, Int) -> Int {
> >> bb0(%0 : $T, %1 : $Int):
> >> %5 = witness_method $T, #SumProtocol.inc!1 : <Self where Self :
> SumProtocol> (Self) -> (Int) -> Int : $@convention(witness_method:
> SumProtocol) <τ_0_0 where τ_0_0 : SumProtocol> (Int, @guaranteed τ_0_0) ->
> Int
> >> %6 = apply %5<T>(%1, %0) : $@convention(witness_method: SumProtocol)
> <τ_0_0 where τ_0_0 : SumProtocol> (Int, @guaranteed τ_0_0) -> Int
> >> destroy_value %0 : $T
> >> return %6 : $Int
> >> }
> >>
> >> In the other function it looks like you need to apply the proper
> substitution list to the apply instruction:
> >>
> >> sil hidden [thunk] [always_inline] @_T04main8wrap_
> incSiAA11SumProtocol_p1a_Si3valtF : $@convention(thin) (@owned
> SumProtocol, Int) -> Int {
> >> bb0(%0 : $SumProtocol, %1 : $Int):
> >> // function_ref specialized wrap_inc(a:val:)
> >> %2 = function_ref @_T04main8wrap_incSiAA11SumProtocol_p1a_
> Si3valtFTf4nn_n
> >> %3 = open_existential_ref %0 : $SumProtocol to
> $@opened("E6196082-DF72-11E7-8C84-420039484801") SumProtocol
> >> %4 = apply %2<τ_0_0>(%3, %1) : $@convention(thin) <τ_0_0 where τ_0_0
> : SumProtocol> (@owned τ_0_0, Int) -> Int // user: %5
> >>
> >> τ_0_0 should have been substituted by the opened type:
> $@opened("E6196082-DF72-11E7-8C84-420039484801”) SumProtocol.
> >>
> >> %3 = open_existential_ref %0 : $SumProtocol to
> $@opened("E6196082-DF72-11E7-8C84-420039484801") SumProtocol
> >> %4 = apply %2<@opened("E6196082-DF72-11E7-8C84-420039484801”)
> SumProtocol>(%3, %1) : $@convention(thin) <τ_0_0 where τ_0_0 : SumProtocol>
> (@owned τ_0_0, Int) -> Int
> >>
> >>
> >> Probably, you have to pass the right SubstitutionList to the
> createApplyInst call.
> >>
> >>
> >> The peephole that propagates types from an init existential Slava
> referred to is here:
> >>
> >> https://github.com/apple/swift/blob/master/lib/
> SILOptimizer/SILCombiner/SILCombinerApplyVisitors.cpp#L974 (SILCombiner::
> propagateConcreteTypeOfInitExistential)
> >>
> >> Here is a test case that shows how the type from the init existential
> is propagated (instead of a generic type ’T’ as in the test case, in your
> case it would be the class type SumClass):
> >>
> >> https://github.com/apple/swift/blob/master/test/
> SILOptimizer/sil_combine.sil#L2569
> >>
> >> > On Dec 13, 2017, at 11:39 AM, Raj Barik via swift-dev <
> swift-dev at swift.org> wrote:
> >> >
> >> > Slava,
> >> >
> >> > I have two (clarification) questions in your proposed implementation:
> >> >
> >> > Original Function:
> >> > @inline(never) internal func wrap_inc(a:SumProtocol, val:Int) -> Int{
> >> > return a.increment(i:val)
> >> > }
> >> > Transformed code:
> >> > @inline(always) internal func wrap_inc(a: SumProtocol, val: Int) ->
> Int {
> >> > // opening an existential cannot be expressed in Swift, but it can
> in SIL…
> >> > let _a = a open as T
> >> >
> >> > return _wrap_inc(_a, val)
> >> > }
> >> >
> >> > @inline(never) internal func _wrap_inc<T : SumProtocol>(_a:T,
> val:Int) -> Int{
> >> > return _a.increment(i:val)
> >> > }
> >> > ************************************************************
> ****************************
> >> > In the above code sequence, did you mean that "let _a = a open as T"
> opens "a:SumProtocol" using open_existential_ref instruction as "SumClass"
> which is the concrete type of a or it is opened as the "$@opened
> SumProtocol". In both cases, the open_existential_ref in the original
> function is still there and giving rise to opening the existential twice.
> Did you also intended that the _wrap_inc function is rewritten to eliminate
> the open_existential_ref as well (this is more complicated if the protocol
> is passed down a call chain)? So, I do not really understand what the "let
> _a = a open as T" is suggesting. The other part of the confusion is about
> the peephole optimization which optimizes the code sequence consisting of
> the creation of object for SumClass and then the init_existential_ref and
> followed by the open_existential_ref. Can you clarify?
> >> >
> >> > Thanks.
> >> >
> >> >
> >> > On Wed, Nov 29, 2017 at 1:43 PM, Slava Pestov <spestov at apple.com>
> wrote:
> >> > Hi Raj,
> >> >
> >> > The way I would approach this problem is first, turn a function
> taking a protocol value into one taking a protocol-constrained generic
> parameter. So
> >> >
> >> > @inline(never) internal func wrap_inc(a:SumProtocol, val:Int) -> Int{
> >> > return a.increment(i:val)
> >> > }
> >> >
> >> > Would become
> >> >
> >> > @inline(always) internal func wrap_inc(a: SumProtocol, val: Int) ->
> Int {
> >> > // opening an existential cannot be expressed in Swift, but it can
> in SIL…
> >> > let _a = a open as T
> >> >
> >> > return _wrap_inc(_a, val)
> >> > }
> >> >
> >> > @inline(never) internal func _wrap_inc<T : SumProtocol>(_a:T,
> val:Int) -> Int{
> >> > let a: SomeProtocol = _a
> >> > return a.increment(i:val)
> >> > }
> >> >
> >> > (Note that the existing function signature specialization pass
> performs a similar transformation where it creates a new function with the
> same body as the old function but a different signature, and replaces the
> old function with a short thunk that transforms arguments and results and
> calls the new function.)
> >> >
> >> > At this point, the existing “initialize existential with concrete
> type” peephole in the SILCombiner should eliminate the existential (but the
> peephole doesn’t work in 100% of cases yet):
> >> >
> >> > @inline(always) internal func wrap_inc(a: SumProtocol, val: Int) ->
> Int {
> >> > // opening an existential cannot be expressed in Swift, but it can
> in SIL…
> >> > let _a = a open as T
> >> >
> >> > return _wrap_inc(_a, val)
> >> > }
> >> >
> >> > @inline(never) internal func _wrap_inc<T : SumProtocol>(_a:T,
> val:Int) -> Int{
> >> > return _a.increment(i:val)
> >> > }
> >> >
> >> > Now, if I have a call to wrap_inc somewhere,
> >> >
> >> > internal let magic:SumProtocol = SumClass(base:10)
> >> > _ = wrap_inc(magic)
> >> >
> >> > Then the optimizer will inline the thunk, giving you a call to
> _wrap_inc. The existential value built from the SumClass instance is
> immediately opened so it will be peepholed away. At this point you have a
> call of a generic function _wrap_inc with a concrete type SumClass, and the
> generic specializer can produce a specialization of it.
> >> >
> >> > Notice how this approach combines several existing optimizations and
> only requires adding a relatively simple new transformation, and possibly
> improving some of the existing optimizations to cover more cases.
> >> >
> >> > Slava
> >> >
> >> >> On Nov 29, 2017, at 11:30 AM, Raj Barik via swift-dev <
> swift-dev at swift.org> wrote:
> >> >>
> >> >> Hi,
> >> >>
> >> >> I am thinking about writing a Protocol Devirtualizer Pass that
> specializes functions that take Protocols as arguments to transform them
> with concrete types instead of protocol types when the concrete types can
> be determined statically by some compiler analysis. This is the first step
> of the transformation that I am proposing. My goal is to extend this to
> eliminate the original function implementation and also to remove the
> corresponding protocol type (by deleting it from the witness table), if
> possible. For simple cases, where the protocol is only used for mocking for
> example and that there is just one class that conforms to it, we should be
> able to eliminate the protocol altogether. This is the second and final
> step of the transformation. Does anyone see any issues with both these
> steps? Arnold from Apple pointed out that there might be demangling issues
> when the protocol is eliminated. Any ideas on how to fix the demangling
> issues? Moreover, would such a pass be helpful to Swift folks?
> >> >>
> >> >> Original code:
> >> >>
> >> >>
> >> >> protocol SumProtocol: class {
> >> >> func increment(i:Int) -> Int
> >> >> }
> >> >>
> >> >> internal class SumClass: SumProtocol {
> >> >> var a:Int
> >> >> init(base:Int) {
> >> >> self.a = base
> >> >> }
> >> >> func increment(i:Int) -> Int {
> >> >> self.a += i
> >> >> return self.a
> >> >> }
> >> >> }
> >> >>
> >> >> @inline(never) internal func wrap_inc(a:SumProtocol, val:Int) -> Int{
> >> >> return a.increment(i:val)
> >> >> }
> >> >>
> >> >> internal let magic:SumProtocol = SumClass(base:10)
> >> >> print("c=\(wrap_inc(a:magic,val:10))")
> >> >>
> >> >>
> >> >> After Step 1:
> >> >>
> >> >>
> >> >> protocol SumProtocol: class {
> >> >> func increment(i:Int) -> Int
> >> >> }
> >> >>
> >> >> internal class SumClass: SumProtocol {
> >> >> var a:Int
> >> >> init(base:Int) {
> >> >> self.a = base
> >> >> }
> >> >> func increment(i:Int) -> Int {
> >> >> self.a += i
> >> >> return self.a
> >> >> }
> >> >> }
> >> >>
> >> >> @inline(never) internal func wrap_inc(a:SumProtocol, val:Int) -> Int{
> >> >> return a.increment(i:val)
> >> >> }
> >> >>
> >> >> @inline(never) internal func wrap_inc_1(a:SumClass, val:Int) -> Int{
> >> >> return a.increment(i:val)
> >> >> }
> >> >>
> >> >> internal let magic:SumClass = SumClass(base:10)
> >> >> print("c=\(wrap_inc_1(a:magic,val:10))")
> >> >>
> >> >>
> >> >> After Step 2:
> >> >>
> >> >> internal class SumClass {
> >> >> var a:Int
> >> >> init(base:Int) {
> >> >> self.a = base
> >> >> }
> >> >> func increment(i:Int) -> Int {
> >> >> self.a += i
> >> >> return self.a
> >> >> }
> >> >> }
> >> >>
> >> >> @inline(never) internal func wrap_inc(a:SumClass, val:Int) -> Int{
> >> >> return a.increment(i:val)
> >> >> }
> >> >>
> >> >> internal let magic:SumClass = SumClass(base:10)
> >> >> print("c=\(wrap_inc(a:magic,val:10))")
> >> >>
> >> >> Any comments/thought on this transformation?
> >> >>
> >> >> Best,
> >> >> Raj
> >> >> _______________________________________________
> >> >> swift-dev mailing list
> >> >> swift-dev at swift.org
> >> >> https://lists.swift.org/mailman/listinfo/swift-dev
> >> >
> >> >
> >> > _______________________________________________
> >> > swift-dev mailing list
> >> > swift-dev at swift.org
> >> > https://lists.swift.org/mailman/listinfo/swift-dev
> >>
> >>
> >
> >
> > _______________________________________________
> > swift-dev mailing list
> > swift-dev at swift.org
> > https://lists.swift.org/mailman/listinfo/swift-dev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-dev/attachments/20171221/3a842a42/attachment.html>
More information about the swift-dev
mailing list