Hi Ben,
On Nov 29, 2016, at 12:10 AM, Ben Ng <me@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@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@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@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@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@benng.me> wrote:
>>
>>> On Nov 16, 2016, at 7:11 PM, Arnold Schwaighofer < > aschwaighofer@apple.com> wrote:
>>>
>>>
>>>> On Nov 16, 2016, at 2:58 PM, Ben Ng <me@benng.me> wrote:
>>>>
>>>> Correct, that is what I am trying to do.
>>>>
>>>>> On Nov 16, 2016, at 12:22 PM, Arnold Schwaighofer < > aschwaighofer@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/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
>>> >, @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!
>>
>>
>
