<div dir="ltr">I created a pull request for the protocol devirtualizer and the peephole optimizer at <a href="https://github.com/apple/swift/pull/13991">https://github.com/apple/swift/pull/13991</a>.<div><br></div><div>Really appreciate all the help from Arnold and Slava.</div><div><br></div><div>Here is an example of what the transformation achieves (in conjunction with other existing passes of swift) :</div><div><br></div><div><b>Input SIL</b>:</div><div>------------</div><div><div>import Builtin</div><div>import Swift</div><div><br></div><div>internal protocol SomeProtocol : AnyObject {</div><div> func increment() -> Int</div><div>}</div><div><br></div><div>internal class SomeClass : SomeProtocol {</div><div> init()</div><div> func increment() -> Int</div><div>}</div><div><br></div><div>sil @something : $@convention(thin) () -> Int {</div><div>bb0:</div><div> %0 = alloc_ref $SomeClass</div><div> %1 = init_existential_ref %0 : $SomeClass : $SomeClass, $SomeProtocol</div><div> %2 = function_ref @something_to_devirtualize : $@convention(thin) (@guaranteed SomeProtocol) -> Int</div><div> %3 = apply %2(%1) : $@convention(thin) (@guaranteed SomeProtocol) -> Int</div><div> return %3 : $Int</div><div>}</div><div><br></div><div>sil private [transparent] [thunk] @increment : $@convention(witness_method: SomeProtocol) (@guaranteed SomeClass) -> Int {</div><div>bb0(%0 : $SomeClass):</div><div> %1 = integer_literal $Builtin.Int64, 10</div><div> %2 = struct $Int (%1 : $Builtin.Int64)</div><div> return %2 : $Int</div><div>}</div><div><br></div><div>sil shared [noinline] @something_to_devirtualize : $@convention(thin) (@guaranteed SomeProtocol) -> Int {</div><div>bb0(%0 : $SomeProtocol):</div><div> %2 = open_existential_ref %0 : $SomeProtocol to $@opened("D346AB00-F998-11E7-93AE-DCA9048B1C6D") SomeProtocol</div><div> %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</div><div> %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</div><div> return %4 : $Int</div><div>}</div><div><br></div><div>sil_witness_table hidden SomeClass: SomeProtocol module test {</div><div> method #SomeProtocol.increment!1: <Self where Self : SomeProtocol> (Self) -> () -> Int : @increment</div><div>}</div></div><div><br></div><div><b>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"</b></div><div>------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------</div><div><div>import Builtin</div><div>import Swift</div><div>import SwiftShims</div><div><br></div><div>internal protocol SomeProtocol : AnyObject {</div><div> func increment() -> Int</div><div>}</div><div><br></div><div>internal class SomeClass : SomeProtocol {</div><div> init()</div><div> func increment() -> Int</div><div> deinit</div><div>}</div><div><br></div><div>// something</div><div>sil @something : $@convention(thin) () -> Int {</div><div>bb0:</div><div> %0 = alloc_ref $SomeClass // user: %2</div><div> %1 = function_ref @$S25something_to_devirtualizeTf5n_n4main9SomeClassC_Tg5 : $@convention(thin) (@guaranteed SomeClass) -> Int // user: %2<br></div><div> %2 = apply %1(%0) : $@convention(thin) (@guaranteed SomeClass) -> Int // user: %3</div><div> return %2 : $Int // id: %3</div><div>} // end sil function 'something'</div><div><br></div><div>// specialized something_to_devirtualize</div><div>sil shared [noinline] @$S25something_to_devirtualizeTf5n_n4main9SomeClassC_Tg5 : $@convention(thin) (@guaranteed SomeClass) -> Int {</div><div>bb0(%0 : $SomeClass):</div><div> %1 = integer_literal $Builtin.Int64, 10 // user: %2</div><div> %2 = struct $Int (%1 : $Builtin.Int64) // user: %3</div><div> return %2 : $Int // id: %3</div><div>} // end sil function '$S25something_to_devirtualizeTf5n_n4main9SomeClassC_Tg5'</div><div><br></div><div>sil_witness_table hidden_external SomeClass: SomeProtocol module main {</div><div> method #SomeProtocol.increment!1: <Self where Self : SomeProtocol> (Self) -> () -> Int : nil</div><div>}</div></div><div><br></div><div><br></div><div> </div></div><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Dec 21, 2017 at 2:50 PM, Raj Barik <span dir="ltr"><<a href="mailto:rkbarik@gmail.com" target="_blank">rkbarik@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Sure, I can :)</div><div class="HOEnZb"><div class="h5"><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Dec 21, 2017 at 12:24 PM, Michael Gottesman <span dir="ltr"><<a href="mailto:mgottesman@apple.com" target="_blank">mgottesman@apple.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Is it possible to merge them?<br>
<div class="m_8055368114690660736HOEnZb"><div class="m_8055368114690660736h5"><br>
> On Dec 21, 2017, at 11:07 AM, Raj Barik via swift-dev <<a href="mailto:swift-dev@swift.org" target="_blank">swift-dev@swift.org</a>> wrote:<br>
><br>
> Hi,<br>
><br>
> Thanks.<br>
><br>
><br>
> Are you implementing it as a separate pass, or is it part of function signature specialization?<br>
><br>
><br>
> 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).<br>
><br>
> --Raj<br>
><br>
><br>
><br>
> Slava<br>
><br>
>><br>
>> @inline(never) internal func wrap_inc_optional(a:SumProtoco<wbr>l?, val:Int) -> Int?{<br>
>> return a?.increment(i:val)<br>
>> }<br>
>><br>
>> The generated SIL looks something like this:<br>
>><br>
>> sil hidden [noinline] @_T04main21wrap_inc_optionalSi<wbr>SgAA11SumProtocol_pSg1a_<wbr>Si3valtF : $@convention(thin) (@owned Optional<SumProtocol>, Int) -> Optional<Int> {<br>
>> // %0 // users: %11, %4, %7, %2<br>
>> // %1 // users: %10, %3<br>
>> bb0(%0 : $Optional<SumProtocol>, %1 : $Int):<br>
>> debug_value %0 : $Optional<SumProtocol>, let, name "a", argno 1 // id: %2<br>
>> debug_value %1 : $Int, let, name "val", argno 2 // id: %3<br>
>> switch_enum %0 : $Optional<SumProtocol>, case #Optional.some!enumelt.1: bb2, case #Optional.none!enumelt: bb1 // id: %4<br>
>><br>
>> bb1: // Preds: bb0<br>
>> %5 = enum $Optional<Int>, #Optional.none!enumelt // user: %6<br>
>> br bb3(%5 : $Optional<Int>) // id: %6<br>
>><br>
>> bb2: // Preds: bb0<br>
>> %7 = unchecked_enum_data %0 : $Optional<SumProtocol>, #Optional.some!enumelt.1 // user: %8<br>
>> %8 = open_existential_ref %7 : $SumProtocol to $@opened("F0395A0A-E5DE-11E7-A<wbr>06A-420039484801") SumProtocol // users: %10, %10, %9<br>
>> %9 = witness_method $@opened("F0395A0A-E5DE-11E7-A<wbr>06A-420039484801") SumProtocol, #SumProtocol.increment!1 : <Self where Self : SumProtocol> (Self) -> (Int) -> Int, %8 : $@opened("F0395A0A-E5DE-11E7-A<wbr>06A-420039484801") SumProtocol : $@convention(witness_method) <τ_0_0 where τ_0_0 : SumProtocol> (Int, @guaranteed τ_0_0) -> Int // type-defs: %8; user: %10<br>
>> %10 = apply %9<@opened("F0395A0A-E5DE-11E7<wbr>-A06A-420039484801") SumProtocol>(%1, %8) : $@convention(witness_method) <τ_0_0 where τ_0_0 : SumProtocol> (Int, @guaranteed τ_0_0) -> Int // type-defs: %8; user: %12<br>
>> release_value %0 : $Optional<SumProtocol> // id: %11<br>
>> %12 = enum $Optional<Int>, #Optional.some!enumelt.1, %10 : $Int // user: %13<br>
>> br bb3(%12 : $Optional<Int>) // id: %13<br>
>><br>
>> // %14 // user: %15<br>
>> bb3(%14 : $Optional<Int>): // Preds: bb1 bb2<br>
>> return %14 : $Optional<Int> // id: %15<br>
>><br>
>><br>
>> 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.<br>
>><br>
>> -R<br>
>><br>
>><br>
>><br>
>> On Wed, Dec 13, 2017 at 3:28 PM, Arnold Schwaighofer <<a href="mailto:aschwaighofer@apple.com" target="_blank">aschwaighofer@apple.com</a>> wrote:<br>
>> You don’t need a second open_existential_ref in the _wrap_inc<T: SumProtocol> function. It should look something like this:<br>
>><br>
>> sil @_wrap_inc : $@convention(thin) <T where T : SumProtocol> (@owned T, Int) -> Int {<br>
>> bb0(%0 : $T, %1 : $Int):<br>
>> %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<br>
>> %6 = apply %5<T>(%1, %0) : $@convention(witness_method: SumProtocol) <τ_0_0 where τ_0_0 : SumProtocol> (Int, @guaranteed τ_0_0) -> Int<br>
>> destroy_value %0 : $T<br>
>> return %6 : $Int<br>
>> }<br>
>><br>
>> In the other function it looks like you need to apply the proper substitution list to the apply instruction:<br>
>><br>
>> sil hidden [thunk] [always_inline] @_T04main8wrap_incSiAA11SumPro<wbr>tocol_p1a_Si3valtF : $@convention(thin) (@owned SumProtocol, Int) -> Int {<br>
>> bb0(%0 : $SumProtocol, %1 : $Int):<br>
>> // function_ref specialized wrap_inc(a:val:)<br>
>> %2 = function_ref @_T04main8wrap_incSiAA11SumPro<wbr>tocol_p1a_Si3valtFTf4nn_n<br>
>> %3 = open_existential_ref %0 : $SumProtocol to $@opened("E6196082-DF72-11E7-8<wbr>C84-420039484801") SumProtocol<br>
>> %4 = apply %2<τ_0_0>(%3, %1) : $@convention(thin) <τ_0_0 where τ_0_0 : SumProtocol> (@owned τ_0_0, Int) -> Int // user: %5<br>
>><br>
>> τ_0_0 should have been substituted by the opened type: $@opened("E6196082-DF72-11E7-8<wbr>C84-420039484801”) SumProtocol.<br>
>><br>
>> %3 = open_existential_ref %0 : $SumProtocol to $@opened("E6196082-DF72-11E7-8<wbr>C84-420039484801") SumProtocol<br>
>> %4 = apply %2<@opened("E6196082-DF72-11E7<wbr>-8C84-420039484801”) SumProtocol>(%3, %1) : $@convention(thin) <τ_0_0 where τ_0_0 : SumProtocol> (@owned τ_0_0, Int) -> Int<br>
>><br>
>><br>
>> Probably, you have to pass the right SubstitutionList to the createApplyInst call.<br>
>><br>
>><br>
>> The peephole that propagates types from an init existential Slava referred to is here:<br>
>><br>
>> <a href="https://github.com/apple/swift/blob/master/lib/SILOptimizer/SILCombiner/SILCombinerApplyVisitors.cpp#L974" rel="noreferrer" target="_blank">https://github.com/apple/swif<wbr>t/blob/master/lib/SILOptimizer<wbr>/SILCombiner/SILCombinerApplyV<wbr>isitors.cpp#L974</a> (SILCombiner::propagateConcret<wbr>eTypeOfInitExistential)<br>
>><br>
>> 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):<br>
>><br>
>> <a href="https://github.com/apple/swift/blob/master/test/SILOptimizer/sil_combine.sil#L2569" rel="noreferrer" target="_blank">https://github.com/apple/swif<wbr>t/blob/master/test/SILOptimize<wbr>r/sil_combine.sil#L2569</a><br>
>><br>
>> > On Dec 13, 2017, at 11:39 AM, Raj Barik via swift-dev <<a href="mailto:swift-dev@swift.org" target="_blank">swift-dev@swift.org</a>> wrote:<br>
>> ><br>
>> > Slava,<br>
>> ><br>
>> > I have two (clarification) questions in your proposed implementation:<br>
>> ><br>
>> > Original Function:<br>
>> > @inline(never) internal func wrap_inc(a:SumProtocol, val:Int) -> Int{<br>
>> > return a.increment(i:val)<br>
>> > }<br>
>> > Transformed code:<br>
>> > @inline(always) internal func wrap_inc(a: SumProtocol, val: Int) -> Int {<br>
>> > // opening an existential cannot be expressed in Swift, but it can in SIL…<br>
>> > let _a = a open as T<br>
>> ><br>
>> > return _wrap_inc(_a, val)<br>
>> > }<br>
>> ><br>
>> > @inline(never) internal func _wrap_inc<T : SumProtocol>(_a:T, val:Int) -> Int{<br>
>> > return _a.increment(i:val)<br>
>> > }<br>
>> > ******************************<wbr>******************************<wbr>****************************<br>
>> > 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?<br>
>> ><br>
>> > Thanks.<br>
>> ><br>
>> ><br>
>> > On Wed, Nov 29, 2017 at 1:43 PM, Slava Pestov <<a href="mailto:spestov@apple.com" target="_blank">spestov@apple.com</a>> wrote:<br>
>> > Hi Raj,<br>
>> ><br>
>> > 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<br>
>> ><br>
>> > @inline(never) internal func wrap_inc(a:SumProtocol, val:Int) -> Int{<br>
>> > return a.increment(i:val)<br>
>> > }<br>
>> ><br>
>> > Would become<br>
>> ><br>
>> > @inline(always) internal func wrap_inc(a: SumProtocol, val: Int) -> Int {<br>
>> > // opening an existential cannot be expressed in Swift, but it can in SIL…<br>
>> > let _a = a open as T<br>
>> ><br>
>> > return _wrap_inc(_a, val)<br>
>> > }<br>
>> ><br>
>> > @inline(never) internal func _wrap_inc<T : SumProtocol>(_a:T, val:Int) -> Int{<br>
>> > let a: SomeProtocol = _a<br>
>> > return a.increment(i:val)<br>
>> > }<br>
>> ><br>
>> > (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.)<br>
>> ><br>
>> > 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):<br>
>> ><br>
>> > @inline(always) internal func wrap_inc(a: SumProtocol, val: Int) -> Int {<br>
>> > // opening an existential cannot be expressed in Swift, but it can in SIL…<br>
>> > let _a = a open as T<br>
>> ><br>
>> > return _wrap_inc(_a, val)<br>
>> > }<br>
>> ><br>
>> > @inline(never) internal func _wrap_inc<T : SumProtocol>(_a:T, val:Int) -> Int{<br>
>> > return _a.increment(i:val)<br>
>> > }<br>
>> ><br>
>> > Now, if I have a call to wrap_inc somewhere,<br>
>> ><br>
>> > internal let magic:SumProtocol = SumClass(base:10)<br>
>> > _ = wrap_inc(magic)<br>
>> ><br>
>> > 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.<br>
>> ><br>
>> > 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.<br>
>> ><br>
>> > Slava<br>
>> ><br>
>> >> On Nov 29, 2017, at 11:30 AM, Raj Barik via swift-dev <<a href="mailto:swift-dev@swift.org" target="_blank">swift-dev@swift.org</a>> wrote:<br>
>> >><br>
>> >> Hi,<br>
>> >><br>
>> >> 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?<br>
>> >><br>
>> >> Original code:<br>
>> >><br>
>> >><br>
>> >> protocol SumProtocol: class {<br>
>> >> func increment(i:Int) -> Int<br>
>> >> }<br>
>> >><br>
>> >> internal class SumClass: SumProtocol {<br>
>> >> var a:Int<br>
>> >> init(base:Int) {<br>
>> >> self.a = base<br>
>> >> }<br>
>> >> func increment(i:Int) -> Int {<br>
>> >> self.a += i<br>
>> >> return self.a<br>
>> >> }<br>
>> >> }<br>
>> >><br>
>> >> @inline(never) internal func wrap_inc(a:SumProtocol, val:Int) -> Int{<br>
>> >> return a.increment(i:val)<br>
>> >> }<br>
>> >><br>
>> >> internal let magic:SumProtocol = SumClass(base:10)<br>
>> >> print("c=\(wrap_inc(a:magic,va<wbr>l:10))")<br>
>> >><br>
>> >><br>
>> >> After Step 1:<br>
>> >><br>
>> >><br>
>> >> protocol SumProtocol: class {<br>
>> >> func increment(i:Int) -> Int<br>
>> >> }<br>
>> >><br>
>> >> internal class SumClass: SumProtocol {<br>
>> >> var a:Int<br>
>> >> init(base:Int) {<br>
>> >> self.a = base<br>
>> >> }<br>
>> >> func increment(i:Int) -> Int {<br>
>> >> self.a += i<br>
>> >> return self.a<br>
>> >> }<br>
>> >> }<br>
>> >><br>
>> >> @inline(never) internal func wrap_inc(a:SumProtocol, val:Int) -> Int{<br>
>> >> return a.increment(i:val)<br>
>> >> }<br>
>> >><br>
>> >> @inline(never) internal func wrap_inc_1(a:SumClass, val:Int) -> Int{<br>
>> >> return a.increment(i:val)<br>
>> >> }<br>
>> >><br>
>> >> internal let magic:SumClass = SumClass(base:10)<br>
>> >> print("c=\(wrap_inc_1(a:magic,<wbr>val:10))")<br>
>> >><br>
>> >><br>
>> >> After Step 2:<br>
>> >><br>
>> >> internal class SumClass {<br>
>> >> var a:Int<br>
>> >> init(base:Int) {<br>
>> >> self.a = base<br>
>> >> }<br>
>> >> func increment(i:Int) -> Int {<br>
>> >> self.a += i<br>
>> >> return self.a<br>
>> >> }<br>
>> >> }<br>
>> >><br>
>> >> @inline(never) internal func wrap_inc(a:SumClass, val:Int) -> Int{<br>
>> >> return a.increment(i:val)<br>
>> >> }<br>
>> >><br>
>> >> internal let magic:SumClass = SumClass(base:10)<br>
>> >> print("c=\(wrap_inc(a:magic,va<wbr>l:10))")<br>
>> >><br>
>> >> Any comments/thought on this transformation?<br>
>> >><br>
>> >> Best,<br>
>> >> Raj<br>
>> >> ______________________________<wbr>_________________<br>
>> >> swift-dev mailing list<br>
>> >> <a href="mailto:swift-dev@swift.org" target="_blank">swift-dev@swift.org</a><br>
>> >> <a href="https://lists.swift.org/mailman/listinfo/swift-dev" rel="noreferrer" target="_blank">https://lists.swift.org/mailma<wbr>n/listinfo/swift-dev</a><br>
>> ><br>
>> ><br>
>> > ______________________________<wbr>_________________<br>
>> > swift-dev mailing list<br>
>> > <a href="mailto:swift-dev@swift.org" target="_blank">swift-dev@swift.org</a><br>
>> > <a href="https://lists.swift.org/mailman/listinfo/swift-dev" rel="noreferrer" target="_blank">https://lists.swift.org/mailma<wbr>n/listinfo/swift-dev</a><br>
>><br>
>><br>
><br>
><br>
> ______________________________<wbr>_________________<br>
> swift-dev mailing list<br>
> <a href="mailto:swift-dev@swift.org" target="_blank">swift-dev@swift.org</a><br>
> <a href="https://lists.swift.org/mailman/listinfo/swift-dev" rel="noreferrer" target="_blank">https://lists.swift.org/mailma<wbr>n/listinfo/swift-dev</a><br>
<br>
</div></div></blockquote></div><br></div>
</div></div></blockquote></div><br></div>