[swift-dev] High-level SIL Optimization: How do I get a FuncRef from the stdlib?
Slava Pestov
spestov at apple.com
Wed Nov 30 15:07:27 CST 2016
What is the generic signature of the method you’re generating the call to?
if it’s always something like
func foo<T>(a: Array<T>)
ie, single generic parameter, without any constraints, then you can manually create a single-element substitution list with no conformances.
Slava
> On Nov 29, 2016, at 7:28 AM, Ben Ng <me at benng.me> wrote:
>
> Hi Slava,
>
> I was hoping I'd be able to reuse the ArrayRef<Substitution>, but at this point, the call has already been specialized, and I don't see a way to recover the substitutions that were used. Do you know of a way to do this?
>
> Ben
>
> On Tue, Nov 29, 2016 at 5:40 AM Slava Pestov <spestov at apple.com <mailto:spestov at apple.com>> wrote:
> Hi Ben,
>
>> On Nov 29, 2016, at 12:10 AM, Ben Ng <me at benng.me <mailto:me at benng.me>> wrote:
>>
>> Hi Slava,
>>
>> The use of the unsubstituted function type turned out to be the issue. The verifier was satisfied after I fixed that, and my proof of concept worked.
>
> Great to hear!
>
>>
>> For context, I'm working on an addition to the ArrayValuePropagation pass that makes code like this:
>>
>> foo += [5]
>>
>> Equivalent to this code:
>>
>> foo.append(5)
>>
>> Which is 6x faster.
>
> Awesome.
>
>> Additionally, I am not sure how to get the unlowered AST type. This code is in an optimization pass, so I don't see how I can reach back into the original AST to get the unlowered type. Does it involve SilInstruction::getLoc()?
>
> Can you use the original ArrayRef<Substitution> from the Apply to += in 'foo += [5]’? In both cases, you’re applying a function value whose original type has a single generic parameter <T> right?
>
>>
>> Thanks,
>>
>> Ben
>> On Sun, Nov 27, 2016 at 10:17 PM Slava Pestov <spestov at apple.com <mailto:spestov at apple.com>> wrote:
>> One more thing:
>>
>>>
>>> auto subTy = V->getType();
>>
>> This is a SILType.
>>
>>> auto &ValLowering = Builder.getModule().getTypeLowering(subTy);
>>> auto copiedVal = ValLowering.emitCopyValue(Builder, SemanticsCall->getLoc(), V);
>>> auto allocStackInst = Builder.createAllocStack(SemanticsCall->getLoc(), subTy);
>>> Builder.createStore(SemanticsCall->getLoc(), copiedVal, allocStackInst, StoreOwnershipQualifier::Unqualified);
>>> ArrayRef<Substitution> subs{Substitution(subTy.getSwiftType(), conformances)};
>>
>> ‘subTy.getSwiftType()’ is a “lowered AST type”. The replacement type in a substitution should be the “unlowered” AST type that came from the original Expr that you’re emitting into SIL.
>>
>> Slava
>>
>>> SILValue args[] = {allocStackInst, ArrRef};
>>> Builder.createApply(SemanticsCall->getLoc(), fnRef, fnTy,
>>> fnTy.castTo<SILFunctionType>()->getSILResult(),
>>> subs, args, false);
>>> Builder.createDeallocStack(SemanticsCall->getLoc(), allocStackInst);
>>>
>>> Here is Builder.createApply’s signature for convenience:
>>>
>>> ApplyInst *createApply(SILLocation Loc, SILValue Fn, SILType SubstFnTy,
>>> SILType Result, ArrayRef<Substitution> Subs,
>>> ArrayRef<SILValue> Args, bool isNonThrowing)
>>>
>>>> On Nov 27, 2016, at 3:22 PM, Ben Ng <me at benng.me <mailto:me at benng.me>> wrote:
>>>>
>>>> Slava gave me a hint: create a SubstitutionMap and then use the methods on GenericEnvironment to turn it into ArrayRef<Substitution>. I'll try that out tonight and see how far I get.
>>>> On Sun, Nov 27, 2016 at 2:12 PM Michael Gottesman <mgottesman at apple.com <mailto:mgottesman at apple.com>> wrote:
>>>> +CC Slava.
>>>>
>>>> He has been messing around with this area in the past bit since many of us have looked at this. He is the person you want.
>>>>
>>>> Michael
>>>>
>>>> > On Nov 25, 2016, at 8:42 PM, Ben Ng <me at benng.me <mailto:me at benng.me>> wrote:
>>>> >
>>>> > Hi everyone,
>>>> >
>>>> > I’ve made good progress with the information in this thread but I can’t figure out how to create the proper set of substitutions for the method that I’m calling.
>>>> >
>>>> > The error I’m getting, as expected, is "SIL verification failed: callee of apply without substitutions must not be polymorphic: !fnTy->isPolymorphic()"
>>>> >
>>>> > I was hoping that there would be a way to delay specialization of the function that I’m replacing so that I can simply reuse those substitutions, but it doesn’t seem like that’s possible.
>>>> >
>>>> > At a high level I assumed that I’d simply be able to substitute a type like `Int` for `τ_0_0`, but it looks like I have to use a ProtocolConformanceRef, which I don’t understand.
>>>> >
>>>> > I looked into iterating through `getLoweredFunctionType()->getGenericSignature()->getGenericParams()`, but I don’t see how I can turn the information there into ProtocolConformanceRef.
>>>> >
>>>> > Thanks for the help as always,
>>>> >
>>>> > Ben
>>>> >
>>>> >> On Nov 16, 2016, at 10:47 PM, Ben Ng <me at benng.me <mailto:me at benng.me>> wrote:
>>>> >>
>>>> >>> On Nov 16, 2016, at 7:11 PM, Arnold Schwaighofer <aschwaighofer at apple.com <mailto:aschwaighofer at apple.com>> wrote:
>>>> >>>
>>>> >>>
>>>> >>>> On Nov 16, 2016, at 2:58 PM, Ben Ng <me at benng.me <mailto:me at benng.me>> wrote:
>>>> >>>>
>>>> >>>> Correct, that is what I am trying to do.
>>>> >>>>
>>>> >>>>> On Nov 16, 2016, at 12:22 PM, Arnold Schwaighofer <aschwaighofer at apple.com <mailto:aschwaighofer at apple.com>> wrote:
>>>> >>>>>
>>>> >>>>> // Really, by the time you look at this in array value prop
>>>> >>>>> // this call should have been inline and you would see a call
>>>> >>>>> // to:
>>>> >>>>> // a.append(contentsOf: [1])
>>>> >>>>
>>>> >>>> I do not understand this comment; I thought that inlining of stdlib functions happened after high-level SIL optimizations are run. Is my understanding incorrect?
>>>> >>>
>>>> >>>
>>>> >>> Inlining of functions with @_semantics is delayed until after high-level SIL optimizations are run. Other functions are inlined.
>>>> >>>
>>>> >>> https://github.com/apple/swift/blob/master/lib/SILOptimizer/PassManager/Passes.cpp#L221 <https://github.com/apple/swift/blob/master/lib/SILOptimizer/PassManager/Passes.cpp#L221>
>>>> >>> https://github.com/apple/swift/blob/master/lib/SILOptimizer/Transforms/PerformanceInliner.cpp#L722 <https://github.com/apple/swift/blob/master/lib/SILOptimizer/Transforms/PerformanceInliner.cpp#L722>
>>>> >>>
>>>> >>>
>>>> >>> I recommend looking at the SIL function dump in ArrayElementValuePropagation of an example function after adding @semantics(“array.mutate_unknown”) to “append(contentsOf:)”.
>>>> >>>
>>>> >>>
>>>> >>> $ git diff HEAD~
>>>> >>> diff --git a/lib/SILOptimizer/Transforms/ArrayElementValuePropagation.cpp b/lib/SILOptimizer/Transforms/ArrayElementValuePropagation.cpp
>>>> >>> index 76328a6..cb976f7 100644
>>>> >>> --- a/lib/SILOptimizer/Transforms/ArrayElementValuePropagation.cpp
>>>> >>> +++ b/lib/SILOptimizer/Transforms/ArrayElementValuePropagation.cpp
>>>> >>> @@ -259,6 +259,8 @@ public:
>>>> >>> void run() override {
>>>> >>> auto &Fn = *getFunction();
>>>> >>>
>>>> >>> + Fn.dump();
>>>> >>> +
>>>> >>> bool Changed = false;
>>>> >>>
>>>> >>> // Propagate the elements an of array value to its users.
>>>> >>> diff --git a/stdlib/public/core/Arrays.swift.gyb b/stdlib/public/core/Arrays.swift.gyb
>>>> >>> index f00cc23..2acfd06 100644
>>>> >>> --- a/stdlib/public/core/Arrays.swift.gyb
>>>> >>> +++ b/stdlib/public/core/Arrays.swift.gyb
>>>> >>> @@ -1344,6 +1344,7 @@ extension ${Self} : RangeReplaceableCollection, _ArrayProtocol {
>>>> >>> /// - Parameter newElements: The elements to append to the array.
>>>> >>> ///
>>>> >>> /// - Complexity: O(*n*), where *n* is the length of the resulting array.
>>>> >>> + @_semantics("array.mutate_unknown")
>>>> >>> public mutating func append<C : Collection>(contentsOf newElements: C)
>>>> >>> where C.Iterator.Element == Element {
>>>> >>>
>>>> >>>
>>>> >>> # Rebuild the compiler and stdlib (without stdlib assertions).
>>>> >>> $ swift/utils/build-script -r --assertions --no-swift-stdlib-assertions
>>>> >>>
>>>> >>>
>>>> >>> $ cat TestArray.swift
>>>> >>> @inline(never)
>>>> >>> public func test() {
>>>> >>> var a = [1, 2, 3]
>>>> >>> a += [1]
>>>> >>> print(a)
>>>> >>> }
>>>> >>>
>>>> >>> $ bin/swiftc -O 2>&1 | less
>>>> >>> ...
>>>> >>> sil shared [_semantics "array.mutate_unknown"] @_TTSg5Si_GSaSi_GSaSi_s10Collections___TFSa6appenduRd__s10CollectionxzWd__8Iterator7Element_rfT10contentsOfqd___T_ : $@convention(method) (@owned Array<I
>>>> >>> nt>, @inout Array<Int>) -> () {
>>>> >>>
>>>> >>> …
>>>> >>> // testArray() -> ()
>>>> >>> sil [noinline] @_TF9TestArray9testArrayFT_T_ : $@convention(thin) () -> () {
>>>> >>> bb0:
>>>> >>> %0 = alloc_stack $Array<Int>, var, name "a", loc "TestArray.swift":3:7, scope 2 // users: %54, %32, %60, %23, %43
>>>> >>> %1 = integer_literal $Builtin.Word, 3, loc "TestArray.swift":3:12, scope 2 // user: %4
>>>> >>> %2 = integer_literal $Builtin.Int64, 3, scope 5 // user: %3
>>>> >>> %3 = struct $Int (%2 : $Builtin.Int64), scope 5 // users: %22, %7
>>>> >>> %4 = alloc_ref [tail_elems $Int * %1 : $Builtin.Word] $_ContiguousArrayStorage<Int>, scope 5 // user: %7
>>>> >>> %5 = metatype $@thin Array<Int>.Type, scope 5 // users: %25, %7
>>>> >>> // function_ref specialized static Array._adoptStorage(_ContiguousArrayStorage<A>, count : Int) -> ([A], UnsafeMutablePointer<A>)
>>>> >>> %6 = function_ref @_TTSg5Si___TZFSa13_adoptStoragefTGCs23_ContiguousArrayStoragex_5countSi_TGSax_GSpx__ : $@convention(method) (@owned _ContiguousArrayStorage<Int>, Int, @thin Array<Int>.Type) -> (@
>>>> >>> owned Array<Int>, UnsafeMutablePointer<Int>), scope 5 // users: %25, %7
>>>> >>> %7 = apply %6(%4, %3, %5) : $@convention(method) (@owned _ContiguousArrayStorage<Int>, Int, @thin Array<Int>.Type) -> (@owned Array<Int>, UnsafeMutablePointer<Int>), scope 5 // users: %9, %8
>>>> >>> %8 = tuple_extract %7 : $(Array<Int>, UnsafeMutablePointer<Int>), 0, scope 5 // user: %23
>>>> >>> %9 = tuple_extract %7 : $(Array<Int>, UnsafeMutablePointer<Int>), 1, scope 5 // user: %10
>>>> >>> %10 = struct_extract %9 : $UnsafeMutablePointer<Int>, #UnsafeMutablePointer._rawValue, scope 5 // user: %11
>>>> >>> %11 = pointer_to_address %10 : $Builtin.RawPointer to [strict] $*Int, loc "TestArray.swift":3:12, scope 2 // users: %14, %21, %16
>>>> >>> %12 = integer_literal $Builtin.Int64, 1, loc "TestArray.swift":3:12, scope 2 // user: %13
>>>> >>> %13 = struct $Int (%12 : $Builtin.Int64), loc "TestArray.swift":3:12, scope 2 // users: %37, %30, %25, %14
>>>> >>> store %13 to %11 : $*Int, loc "TestArray.swift":3:12, scope 2 // id: %14
>>>> >>> %15 = integer_literal $Builtin.Word, 1, loc "TestArray.swift":3:15, scope 2 // users: %34, %24, %16
>>>> >>> %16 = index_addr %11 : $*Int, %15 : $Builtin.Word, loc "TestArray.swift":3:15, scope 2 // user: %19
>>>> >>> %17 = integer_literal $Builtin.Int64, 2, loc "TestArray.swift":3:15, scope 2 // user: %18
>>>> >>> %18 = struct $Int (%17 : $Builtin.Int64), loc "TestArray.swift":3:15, scope 2 // user: %19
>>>> >>> store %18 to %16 : $*Int, loc "TestArray.swift":3:15, scope 2 // id: %19
>>>> >>> %20 = integer_literal $Builtin.Word, 2, loc "TestArray.swift":3:18, scope 2 // user: %21
>>>> >>> %21 = index_addr %11 : $*Int, %20 : $Builtin.Word, loc "TestArray.swift":3:18, scope 2 // user: %22
>>>> >>> store %3 to %21 : $*Int, loc "TestArray.swift":3:18, scope 2 // id: %22
>>>> >>> store %8 to %0 : $*Array<Int>, loc "TestArray.swift":3:18, scope 2 // id: %23
>>>> >>> %24 = alloc_ref [tail_elems $Int * %15 : $Builtin.Word] $_ContiguousArrayStorage<Int>, scope 7 // user: %25
>>>> >>> %25 = apply %6(%24, %13, %5) : $@convention(method) (@owned _ContiguousArrayStorage<Int>, Int, @thin Array<Int>.Type) -> (@owned Array<Int>, UnsafeMutablePointer<Int>), scope 7 // users: %27, %26
>>>> >>> %26 = tuple_extract %25 : $(Array<Int>, UnsafeMutablePointer<Int>), 0, scope 7 // user: %32
>>>> >>> %27 = tuple_extract %25 : $(Array<Int>, UnsafeMutablePointer<Int>), 1, scope 7 // user: %28
>>>> >>> %28 = struct_extract %27 : $UnsafeMutablePointer<Int>, #UnsafeMutablePointer._rawValue, scope 7 // user: %29
>>>> >>> %29 = pointer_to_address %28 : $Builtin.RawPointer to [strict] $*Int, loc "TestArray.swift":4:9, scope 2 // user: %30
>>>> >>> store %13 to %29 : $*Int, loc "TestArray.swift":4:9, scope 2 // id: %30
>>>> >>> // function_ref specialized Array.append<A where ...> (contentsOf : A1) -> ()
>>>> >>> %31 = function_ref @_TTSg5Si_GSaSi_GSaSi_s10Collections___TFSa6appenduRd__s10CollectionxzWd__8Iterator7Element_rfT10contentsOfqd___T_ : $@convention(method) (@owned Array<Int>, @inout Array<Int>) -> (), scope 10 // user: %32
>>>> >>> %32 = apply %31(%26, %0) : $@convention(method) (@owned Array<Int>, @inout Array<Int>) -> (), scope 10
>>>> >>
>>>> >> Ah, I do remember seeing something about how the semantic attribute stops some functions from being inlined early. Thanks for saving me a bunch of head-scratching!
>>>> >>
>>>> >>
>>>> >
>>>>
>>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-dev/attachments/20161130/d674c658/attachment.html>
More information about the swift-dev
mailing list