[swift-dev] Protocol Devirtualizer Pass
Raj Barik
rkbarik at gmail.com
Wed Jan 17 11:52:03 CST 2018
I created a pull request for the protocol devirtualizer and the peephole
optimizer at https://github.com/apple/swift/pull/13991.
Really appreciate all the help from Arnold and Slava.
Here is an example of what the transformation achieves (in conjunction with
other existing passes of swift) :
*Input SIL*:
------------
import Builtin
import Swift
internal protocol SomeProtocol : AnyObject {
func increment() -> Int
}
internal class SomeClass : SomeProtocol {
init()
func increment() -> Int
}
sil @something : $@convention(thin) () -> Int {
bb0:
%0 = alloc_ref $SomeClass
%1 = init_existential_ref %0 : $SomeClass : $SomeClass, $SomeProtocol
%2 = function_ref @something_to_devirtualize : $@convention(thin)
(@guaranteed SomeProtocol) -> Int
%3 = apply %2(%1) : $@convention(thin) (@guaranteed SomeProtocol) -> Int
return %3 : $Int
}
sil private [transparent] [thunk] @increment : $@convention(witness_method:
SomeProtocol) (@guaranteed SomeClass) -> Int {
bb0(%0 : $SomeClass):
%1 = integer_literal $Builtin.Int64, 10
%2 = struct $Int (%1 : $Builtin.Int64)
return %2 : $Int
}
sil shared [noinline] @something_to_devirtualize : $@convention(thin)
(@guaranteed SomeProtocol) -> Int {
bb0(%0 : $SomeProtocol):
%2 = open_existential_ref %0 : $SomeProtocol to
$@opened("D346AB00-F998-11E7-93AE-DCA9048B1C6D") SomeProtocol
%3 = witness_method $@opened("D346AB00-F998-11E7-93AE-DCA9048B1C6D")
SomeProtocol, #SomeProtocol.increment!1 : <Self where Self : SomeProtocol>
(Self) -> () -> Int, %2 : $@opened("D346AB00-F998-11E7-93AE-DCA9048B1C6D")
SomeProtocol : $@convention(witness_method: SomeProtocol) <τ_0_0 where
τ_0_0 : SomeProtocol> (@guaranteed τ_0_0) -> Int
%4 = apply %3<@opened("D346AB00-F998-11E7-93AE-DCA9048B1C6D")
SomeProtocol>(%2) : $@convention(witness_method: SomeProtocol) <τ_0_0 where
τ_0_0 : SomeProtocol> (@guaranteed τ_0_0) -> Int
return %4 : $Int
}
sil_witness_table hidden SomeClass: SomeProtocol module test {
method #SomeProtocol.increment!1: <Self where Self : SomeProtocol> (Self)
-> () -> Int : @increment
}
*Output SIL after running "sil-opt -wmo
-assume-parsing-unqualified-ownership-sil -protocol-devirtualizer -inline
-sil-combine -generic-specializer -devirtualizer -late-inline
-dead-arg-signature-opt -dce -sil-deadfuncelim"*
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
import Builtin
import Swift
import SwiftShims
internal protocol SomeProtocol : AnyObject {
func increment() -> Int
}
internal class SomeClass : SomeProtocol {
init()
func increment() -> Int
deinit
}
// something
sil @something : $@convention(thin) () -> Int {
bb0:
%0 = alloc_ref $SomeClass // user: %2
%1 = function_ref
@$S25something_to_devirtualizeTf5n_n4main9SomeClassC_Tg5 :
$@convention(thin) (@guaranteed SomeClass) -> Int // user: %2
%2 = apply %1(%0) : $@convention(thin) (@guaranteed SomeClass) -> Int //
user: %3
return %2 : $Int // id: %3
} // end sil function 'something'
// specialized something_to_devirtualize
sil shared [noinline]
@$S25something_to_devirtualizeTf5n_n4main9SomeClassC_Tg5 :
$@convention(thin) (@guaranteed SomeClass) -> Int {
bb0(%0 : $SomeClass):
%1 = integer_literal $Builtin.Int64, 10 // user: %2
%2 = struct $Int (%1 : $Builtin.Int64) // user: %3
return %2 : $Int // id: %3
} // end sil function
'$S25something_to_devirtualizeTf5n_n4main9SomeClassC_Tg5'
sil_witness_table hidden_external SomeClass: SomeProtocol module main {
method #SomeProtocol.increment!1: <Self where Self : SomeProtocol> (Self)
-> () -> Int : nil
}
On Thu, Dec 21, 2017 at 2:50 PM, Raj Barik <rkbarik at gmail.com> wrote:
> 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_optionalSi
>> SgAA11SumProtocol_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_incSiAA11SumPro
>> tocol_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/SILOptimize
>> r/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/20180117/2dfa24e6/attachment.html>
More information about the swift-dev
mailing list