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 <rkba...@gmail.com> wrote: > Sure, I can :) > > On Thu, Dec 21, 2017 at 12:24 PM, Michael Gottesman <mgottes...@apple.com> > wrote: > >> Is it possible to merge them? >> >> > On Dec 21, 2017, at 11:07 AM, Raj Barik via swift-dev < >> swift-dev@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 < >> aschwaigho...@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@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 <spes...@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@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@swift.org >> >> >> https://lists.swift.org/mailman/listinfo/swift-dev >> >> > >> >> > >> >> > _______________________________________________ >> >> > swift-dev mailing list >> >> > swift-dev@swift.org >> >> > https://lists.swift.org/mailman/listinfo/swift-dev >> >> >> >> >> > >> > >> > _______________________________________________ >> > swift-dev mailing list >> > swift-dev@swift.org >> > https://lists.swift.org/mailman/listinfo/swift-dev >> >> >
_______________________________________________ swift-dev mailing list swift-dev@swift.org https://lists.swift.org/mailman/listinfo/swift-dev