[swift-dev] Protocol Devirtualizer Pass

Raj Barik rkbarik at gmail.com
Tue Dec 12 13:51:00 CST 2017


Thanks for the recommendations, Slava. Although I am able to create both
the generic function and the wrapper thunk, I get a crash in the existing
performance inliner pass while iterating over the apply instruction and
trying to perform substitution. Here is the SIL that I generate:

sil hidden [thunk] [always_inline]
@_T04main8wrap_incSiAA11SumProtocol_p1a_Si3valtF : $@convention(thin)
(@owned SumProtocol, Int) -> Int {
// %0                                             // user: %3
// %1                                             // user: %4
bb0(%0 : $SumProtocol, %1 : $Int):
  // function_ref specialized wrap_inc(a:val:)
  %2 = function_ref @_T04main8wrap_incSiAA11SumProtocol_p1a_Si3valtFTf4nn_n
: $@convention(thin) <τ_0_0 where τ_0_0 : SumProtocol> (@owned τ_0_0, Int)
-> Int // user: %4
  %3 = open_existential_ref %0 : $SumProtocol to
$@opened("E6196082-DF72-11E7-8C84-420039484801") SumProtocol // user: %4
  %4 = apply %2<τ_0_0>(%3, %1) : $@convention(thin) <τ_0_0 where τ_0_0 :
SumProtocol> (@owned τ_0_0, Int) -> Int // user: %5
  return %4 : $Int                                // id: %5
} // end sil function '_T04main8wrap_incSiAA11SumProtocol_p1a_Si3valtF'

// specialized wrap_inc(a:val:)
sil shared [noinline]
@_T04main8wrap_incSiAA11SumProtocol_p1a_Si3valtFTf4nn_n :
$@convention(thin) <τ_0_0 where τ_0_0 : SumProtocol> (@owned τ_0_0, Int) ->
Int {
// %0                                             // users: %3, %2
// %1                                             // user: %4
bb0(%0 : $τ_0_0, %1 : $Int):
  debug_value_addr %0 : $τ_0_0, let, name "a"    // id: %2
  %3 = unchecked_ref_cast %0 : $τ_0_0 to $SumProtocol // user: %4
  br bb1(%3 : $SumProtocol, %1 : $Int)            // id: %4

// %5                                             // users: %12, %9, %7
// %6                                             // users: %11, %8
bb1(%5 : $SumProtocol, %6 : $Int):                // Preds: bb0
  debug_value %5 : $SumProtocol, let, name "a", argno 1 // id: %7
  debug_value %6 : $Int, let, name "val", argno 2 // id: %8
  %9 = open_existential_ref %5 : $SumProtocol to
$@opened("E60585BC-DF72-11E7-8C84-420039484801") SumProtocol // users: %11,
%11, %10
  %10 = witness_method $@opened("E60585BC-DF72-11E7-8C84-420039484801")
SumProtocol, #SumProtocol.increment!1 : <Self where Self : SumProtocol>
(Self) -> (Int) -> Int, %9 :
$@opened("E60585BC-DF72-11E7-8C84-420039484801") SumProtocol :
$@convention(witness_method) <τ_0_0 where τ_0_0 : SumProtocol> (Int,
@guaranteed τ_0_0) -> Int // type-defs: %9; user: %11
  %11 = apply %10<@opened("E60585BC-DF72-11E7-8C84-420039484801")
SumProtocol>(%6, %9) : $@convention(witness_method) <τ_0_0 where τ_0_0 :
SumProtocol> (Int, @guaranteed τ_0_0) -> Int // type-defs: %9; user: %13
  strong_release %5 : $SumProtocol                // id: %12
  return %11 : $Int                               // id: %13
} // end sil function
'_T04main8wrap_incSiAA11SumProtocol_p1a_Si3valtFTf4nn_n'


*One more question*: Is it OK to open an existential reference twice? In
the above code, I open the protocol in the thunk and also in the generic
wrapper.


0  swift                    0x000000010980e278
llvm::sys::PrintStackTrace(llvm::raw_ostream&) + 40
1  swift                    0x000000010980d1c6
llvm::sys::RunSignalHandlers() + 86
2  swift                    0x000000010980e83e SignalHandler(int) + 366
3  libsystem_platform.dylib 0x00007fff7baa4f5a _sigtramp + 26
4  libdyld.dylib            0x00007fff7b824279 dyldGlobalLockRelease() + 0
5  libsystem_c.dylib        0x00007fff7b8d030a abort + 127
6  libsystem_c.dylib        0x00007fff7b898360 basename_r + 0
7  swift                    0x00000001075230cb
swift::SubstitutionMap::lookupSubstitution(swift::CanTypeWrapper<swift::SubstitutableType>)
const + 651
8  swift                    0x0000000107534904 llvm::Optional<swift::Type>
llvm::function_ref<llvm::Optional<swift::Type>
(swift::TypeBase*)>::callback_fn<substType(swift::Type,
llvm::function_ref<swift::Type (swift::SubstitutableType*)>,
llvm::function_ref<llvm::Optional<swift::ProtocolConformanceRef>
(swift::CanType, swift::Type, swift::ProtocolType*)>,
swift::SubstOptions)::$_18>(long, swift::TypeBase*) + 884
9  swift                    0x0000000107531367
swift::Type::transformRec(llvm::function_ref<llvm::Optional<swift::Type>
(swift::TypeBase*)>) const + 151
10 swift                    0x000000010752fcb4
swift::Type::subst(llvm::function_ref<swift::Type
(swift::SubstitutableType*)>,
llvm::function_ref<llvm::Optional<swift::ProtocolConformanceRef>
(swift::CanType, swift::Type, swift::ProtocolType*)>, swift::SubstOptions)
const + 196
11 swift                    0x0000000106fe9ad7 (anonymous
namespace)::SILTypeSubstituter::visitType(swift::CanType) + 119
12 swift                    0x0000000106fe953e swift::CanType
swift::CanTypeVisitor<(anonymous namespace)::SILTypeSubstituter,
swift::CanType>::visit<>(swift::CanType) + 94
13 swift                    0x0000000106fe4e8f (anonymous
namespace)::SILTypeSubstituter::substSILFunctionType(swift::CanTypeWrapper<swift::SILFunctionType>)
+ 607
14 swift                    0x0000000106fe961f swift::CanType
swift::CanTypeVisitor<(anonymous namespace)::SILTypeSubstituter,
swift::CanType>::visit<>(swift::CanType) + 319
15 swift                    0x0000000106fe49ea
swift::SILType::subst(swift::SILModule&, llvm::function_ref<swift::Type
(swift::SubstitutableType*)>,
llvm::function_ref<llvm::Optional<swift::ProtocolConformanceRef>
(swift::CanType, swift::Type, swift::ProtocolType*)>,
swift::CanGenericSignature) const + 218
16 swift                    0x0000000106fe4a63
swift::SILType::subst(swift::SILModule&, swift::SubstitutionMap const&)
const + 51
17 swift                    0x0000000106cc93ec
swift::TypeSubstCloner<swift::SILInliner>::ApplySiteCloningHelper::ApplySiteCloningHelper(swift::ApplySite,
swift::TypeSubstCloner<swift::SILInliner>&) + 220
18 swift                    0x0000000106cbaff1
swift::TypeSubstCloner<swift::SILInliner>::visitApplyInst(swift::ApplyInst*)
+ 113
19 swift                    0x0000000106caf993
swift::SILCloner<swift::SILInliner>::visitSILBasicBlock(swift::SILBasicBlock*)
+ 83
20 swift                    0x0000000106caf3b8
swift::SILInliner::inlineFunction(swift::FullApplySite,
llvm::ArrayRef<swift::SILValue>) + 1048
21 swift                    0x0000000106dbd6e7 (anonymous
namespace)::SILPerformanceInlinerPass::run() + 1735
22 swift                    0x0000000106cd47cf
swift::SILPassManager::runPassOnFunction(swift::SILFunctionTransform*,
swift::SILFunction*) + 4015
23 swift                    0x0000000106cd5947
swift::SILPassManager::runFunctionPasses(llvm::ArrayRef<swift::SILFunctionTransform*>)
+ 1079
24 swift                    0x0000000106cd6d94
swift::SILPassManager::runOneIteration() + 964
25 swift                    0x00000001065ada1b
swift::SILPassManager::executePassPipelinePlan(swift::SILPassPipelinePlan
const&) + 187
26 swift                    0x0000000106cdf652
swift::runSILOptimizationPasses(swift::SILModule&) + 114
27 swift                    0x000000010646deb2
performCompile(swift::CompilerInstance&, swift::CompilerInvocation&,
llvm::ArrayRef<char const*>, int&, swift::FrontendObserver*,
swift::UnifiedStatsReporter*) + 13634
28 swift                    0x0000000106469a6a
swift::performFrontend(llvm::ArrayRef<char const*>, char const*, void*,
swift::FrontendObserver*) + 3530
29 swift                    0x000000010642aa60 main + 3360
30 libdyld.dylib            0x00007fff7b824145 start + 1

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
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-dev/attachments/20171212/ba877cb4/attachment.html>


More information about the swift-dev mailing list