> On Dec 20, 2017, at 3:56 PM, Raj Barik <[email protected]> wrote:
>
> Thank you Arnold & Slava! The protocol devirtualizer pass works fine now for
> most cases. I should be creating a PR soon (after some more testing).
>
> I am thinking about extending this to Optional types as well, i.e.,
I’m not sure if its possible in the general case. What you might think of doing
is rewriting this into a function that takes an Optional<T> where T :
SumProtocol. But the trouble is if the value of ‘a’ is nil, then there’s no
concrete type to bind to the type parameter T at runtime. What you really want
is a way to write
enum WeirdOptional {
case <T> some(T)
case none
}
But we don’t allow this.
I think even without handling optionals though, this optimization definitely
has value.
Are you implementing it as a separate pass, or is it part of function signature
specialization?
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 <[email protected]
> <mailto:[email protected]>> 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
>
> <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
>
> <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 <[email protected]
> > <mailto:[email protected]>> 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 <[email protected]
> > <mailto:[email protected]>> 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 <[email protected]
> >> <mailto:[email protected]>> 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
> >> [email protected] <mailto:[email protected]>
> >> https://lists.swift.org/mailman/listinfo/swift-dev
> >> <https://lists.swift.org/mailman/listinfo/swift-dev>
> >
> >
> > _______________________________________________
> > swift-dev mailing list
> > [email protected] <mailto:[email protected]>
> > https://lists.swift.org/mailman/listinfo/swift-dev
> > <https://lists.swift.org/mailman/listinfo/swift-dev>
>
>
_______________________________________________
swift-dev mailing list
[email protected]
https://lists.swift.org/mailman/listinfo/swift-dev
