Hi Slava,<br><br>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.<br><br>For context, I'm working on an addition to the ArrayValuePropagation pass that makes code like this:<br><br>foo += [5]<br><br>Equivalent to this code:<br><br>foo.append(5)<br><br>Which is 6x faster.<br><br>I do not understand what the danger of using the lowered AST type over the "unlowered" AST type is. An example would help here. 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()?<br><br>I also do not understand why constructing the ArrayRef<Substitution> by hand is discouraged. I will refactor it tomorrow to start with a substitution map instead. I've looked at the methods on GenericEnvironment, and it's still not clear to me how I would use them to turn the map into an array. Can you give me a hint here?<br><br>Thanks,<br><br>Ben<br><div class="gmail_quote"><div dir="ltr">On Sun, Nov 27, 2016 at 10:17 PM Slava Pestov <<a href="mailto:spestov@apple.com">spestov@apple.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word" class="gmail_msg">One more thing:<div class="gmail_msg"><br class="gmail_msg"><div class="gmail_msg"></div></div></div><div style="word-wrap:break-word" class="gmail_msg"><div class="gmail_msg"><div class="gmail_msg"><blockquote type="cite" class="gmail_msg"><div style="word-wrap:break-word" class="gmail_msg"><blockquote style="margin:0 0 0 40px;border:none;padding:0px" class="gmail_msg"><div class="gmail_msg"><div class="gmail_msg"><br class="gmail_msg">auto subTy = V->getType();</div></div></blockquote></div></blockquote><div class="gmail_msg"><br class="gmail_msg"></div></div></div></div><div style="word-wrap:break-word" class="gmail_msg"><div class="gmail_msg"><div class="gmail_msg">This is a SILType.</div><div class="gmail_msg"></div></div></div><div style="word-wrap:break-word" class="gmail_msg"><div class="gmail_msg"><div class="gmail_msg"><br class="gmail_msg"><blockquote type="cite" class="gmail_msg"><div style="word-wrap:break-word" class="gmail_msg"><blockquote style="margin:0 0 0 40px;border:none;padding:0px" class="gmail_msg"><div class="gmail_msg"><div class="gmail_msg">auto &ValLowering = Builder.getModule().getTypeLowering(subTy);</div></div><div class="gmail_msg"><div class="gmail_msg">auto copiedVal = ValLowering.emitCopyValue(Builder, SemanticsCall->getLoc(), V);</div></div><div class="gmail_msg"><div class="gmail_msg">auto allocStackInst = Builder.createAllocStack(SemanticsCall->getLoc(), subTy);</div></div><div class="gmail_msg"><div class="gmail_msg">Builder.createStore(SemanticsCall->getLoc(), copiedVal, allocStackInst, StoreOwnershipQualifier::Unqualified);</div></div><div class="gmail_msg"><div class="gmail_msg">ArrayRef<Substitution> subs{Substitution(subTy.getSwiftType(), conformances)};</div></div></blockquote></div></blockquote><div class="gmail_msg"><br class="gmail_msg"></div></div></div></div><div style="word-wrap:break-word" class="gmail_msg"><div class="gmail_msg"><div class="gmail_msg">‘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.</div></div></div><div style="word-wrap:break-word" class="gmail_msg"><div class="gmail_msg"><div class="gmail_msg"><br class="gmail_msg"></div><div class="gmail_msg">Slava</div></div></div><div style="word-wrap:break-word" class="gmail_msg"><div class="gmail_msg"><div class="gmail_msg"><br class="gmail_msg"><blockquote type="cite" class="gmail_msg"><div style="word-wrap:break-word" class="gmail_msg"><blockquote style="margin:0 0 0 40px;border:none;padding:0px" class="gmail_msg"><div class="gmail_msg"><div class="gmail_msg">SILValue args[] = {allocStackInst, ArrRef};</div></div><div class="gmail_msg"><div class="gmail_msg">Builder.createApply(SemanticsCall->getLoc(), fnRef, fnTy,</div></div><div class="gmail_msg"><div class="gmail_msg"> fnTy.castTo<SILFunctionType>()->getSILResult(),</div></div><div class="gmail_msg"><div class="gmail_msg"> subs, args, false);</div></div><div class="gmail_msg"><div class="gmail_msg">Builder.createDeallocStack(SemanticsCall->getLoc(), allocStackInst);</div></div></blockquote><div class="gmail_msg"><br class="gmail_msg"></div><div class="gmail_msg">Here is Builder.createApply’s signature for convenience:</div><div class="gmail_msg"><br class="gmail_msg"></div><blockquote style="margin:0 0 0 40px;border:none;padding:0px" class="gmail_msg"><div class="gmail_msg"><div class="gmail_msg">ApplyInst *createApply(SILLocation Loc, SILValue Fn, SILType SubstFnTy,</div></div><div class="gmail_msg"><div class="gmail_msg"> SILType Result, ArrayRef<Substitution> Subs,</div></div><div class="gmail_msg"><div class="gmail_msg"> ArrayRef<SILValue> Args, bool isNonThrowing)</div></div></blockquote><br class="gmail_msg"><div class="gmail_msg"><blockquote type="cite" class="gmail_msg"><div class="gmail_msg">On Nov 27, 2016, at 3:22 PM, Ben Ng <<a href="mailto:me@benng.me" class="gmail_msg" target="_blank">me@benng.me</a>> wrote:</div><br class="m_-7225043623601252493Apple-interchange-newline gmail_msg"><div class="gmail_msg">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.<br class="gmail_msg"><div class="gmail_quote gmail_msg"><div dir="ltr" class="gmail_msg">On Sun, Nov 27, 2016 at 2:12 PM Michael Gottesman <<a href="mailto:mgottesman@apple.com" class="gmail_msg" target="_blank">mgottesman@apple.com</a>> wrote:<br class="gmail_msg"></div><blockquote class="gmail_quote gmail_msg" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">+CC Slava.<br class="gmail_msg">
<br class="gmail_msg">
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.<br class="gmail_msg">
<br class="gmail_msg">
Michael<br class="gmail_msg">
<br class="gmail_msg">
> On Nov 25, 2016, at 8:42 PM, Ben Ng <<a href="mailto:me@benng.me" class="gmail_msg" target="_blank">me@benng.me</a>> wrote:<br class="gmail_msg">
><br class="gmail_msg">
> Hi everyone,<br class="gmail_msg">
><br class="gmail_msg">
> 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.<br class="gmail_msg">
><br class="gmail_msg">
> The error I’m getting, as expected, is "SIL verification failed: callee of apply without substitutions must not be polymorphic: !fnTy->isPolymorphic()"<br class="gmail_msg">
><br class="gmail_msg">
> 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.<br class="gmail_msg">
><br class="gmail_msg">
> 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.<br class="gmail_msg">
><br class="gmail_msg">
> I looked into iterating through `getLoweredFunctionType()->getGenericSignature()->getGenericParams()`, but I don’t see how I can turn the information there into ProtocolConformanceRef.<br class="gmail_msg">
><br class="gmail_msg">
> Thanks for the help as always,<br class="gmail_msg">
><br class="gmail_msg">
> Ben<br class="gmail_msg">
><br class="gmail_msg">
>> On Nov 16, 2016, at 10:47 PM, Ben Ng <<a href="mailto:me@benng.me" class="gmail_msg" target="_blank">me@benng.me</a>> wrote:<br class="gmail_msg">
>><br class="gmail_msg">
>>> On Nov 16, 2016, at 7:11 PM, Arnold Schwaighofer <<a href="mailto:aschwaighofer@apple.com" class="gmail_msg" target="_blank">aschwaighofer@apple.com</a>> wrote:<br class="gmail_msg">
>>><br class="gmail_msg">
>>><br class="gmail_msg">
>>>> On Nov 16, 2016, at 2:58 PM, Ben Ng <<a href="mailto:me@benng.me" class="gmail_msg" target="_blank">me@benng.me</a>> wrote:<br class="gmail_msg">
>>>><br class="gmail_msg">
>>>> Correct, that is what I am trying to do.<br class="gmail_msg">
>>>><br class="gmail_msg">
>>>>> On Nov 16, 2016, at 12:22 PM, Arnold Schwaighofer <<a href="mailto:aschwaighofer@apple.com" class="gmail_msg" target="_blank">aschwaighofer@apple.com</a>> wrote:<br class="gmail_msg">
>>>>><br class="gmail_msg">
>>>>> // Really, by the time you look at this in array value prop<br class="gmail_msg">
>>>>> // this call should have been inline and you would see a call<br class="gmail_msg">
>>>>> // to:<br class="gmail_msg">
>>>>> // a.append(contentsOf: [1])<br class="gmail_msg">
>>>><br class="gmail_msg">
>>>> 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?<br class="gmail_msg">
>>><br class="gmail_msg">
>>><br class="gmail_msg">
>>> Inlining of functions with @_semantics is delayed until after high-level SIL optimizations are run. Other functions are inlined.<br class="gmail_msg">
>>><br class="gmail_msg">
>>> <a href="https://github.com/apple/swift/blob/master/lib/SILOptimizer/PassManager/Passes.cpp#L221" rel="noreferrer" class="gmail_msg" target="_blank">https://github.com/apple/swift/blob/master/lib/SILOptimizer/PassManager/Passes.cpp#L221</a><br class="gmail_msg">
>>> <a href="https://github.com/apple/swift/blob/master/lib/SILOptimizer/Transforms/PerformanceInliner.cpp#L722" rel="noreferrer" class="gmail_msg" target="_blank">https://github.com/apple/swift/blob/master/lib/SILOptimizer/Transforms/PerformanceInliner.cpp#L722</a><br class="gmail_msg">
>>><br class="gmail_msg">
>>><br class="gmail_msg">
>>> I recommend looking at the SIL function dump in ArrayElementValuePropagation of an example function after adding @semantics(“array.mutate_unknown”) to “append(contentsOf:)”.<br class="gmail_msg">
>>><br class="gmail_msg">
>>><br class="gmail_msg">
>>> $ git diff HEAD~<br class="gmail_msg">
>>> diff --git a/lib/SILOptimizer/Transforms/ArrayElementValuePropagation.cpp b/lib/SILOptimizer/Transforms/ArrayElementValuePropagation.cpp<br class="gmail_msg">
>>> index 76328a6..cb976f7 100644<br class="gmail_msg">
>>> --- a/lib/SILOptimizer/Transforms/ArrayElementValuePropagation.cpp<br class="gmail_msg">
>>> +++ b/lib/SILOptimizer/Transforms/ArrayElementValuePropagation.cpp<br class="gmail_msg">
>>> @@ -259,6 +259,8 @@ public:<br class="gmail_msg">
>>> void run() override {<br class="gmail_msg">
>>> auto &Fn = *getFunction();<br class="gmail_msg">
>>><br class="gmail_msg">
>>> + Fn.dump();<br class="gmail_msg">
>>> +<br class="gmail_msg">
>>> bool Changed = false;<br class="gmail_msg">
>>><br class="gmail_msg">
>>> // Propagate the elements an of array value to its users.<br class="gmail_msg">
>>> diff --git a/stdlib/public/core/Arrays.swift.gyb b/stdlib/public/core/Arrays.swift.gyb<br class="gmail_msg">
>>> index f00cc23..2acfd06 100644<br class="gmail_msg">
>>> --- a/stdlib/public/core/Arrays.swift.gyb<br class="gmail_msg">
>>> +++ b/stdlib/public/core/Arrays.swift.gyb<br class="gmail_msg">
>>> @@ -1344,6 +1344,7 @@ extension ${Self} : RangeReplaceableCollection, _ArrayProtocol {<br class="gmail_msg">
>>> /// - Parameter newElements: The elements to append to the array.<br class="gmail_msg">
>>> ///<br class="gmail_msg">
>>> /// - Complexity: O(*n*), where *n* is the length of the resulting array.<br class="gmail_msg">
>>> + @_semantics("array.mutate_unknown")<br class="gmail_msg">
>>> public mutating func append<C : Collection>(contentsOf newElements: C)<br class="gmail_msg">
>>> where C.Iterator.Element == Element {<br class="gmail_msg">
>>><br class="gmail_msg">
>>><br class="gmail_msg">
>>> # Rebuild the compiler and stdlib (without stdlib assertions).<br class="gmail_msg">
>>> $ swift/utils/build-script -r --assertions --no-swift-stdlib-assertions<br class="gmail_msg">
>>><br class="gmail_msg">
>>><br class="gmail_msg">
>>> $ cat TestArray.swift<br class="gmail_msg">
>>> @inline(never)<br class="gmail_msg">
>>> public func test() {<br class="gmail_msg">
>>> var a = [1, 2, 3]<br class="gmail_msg">
>>> a += [1]<br class="gmail_msg">
>>> print(a)<br class="gmail_msg">
>>> }<br class="gmail_msg">
>>><br class="gmail_msg">
>>> $ bin/swiftc -O 2>&1 | less<br class="gmail_msg">
>>> ...<br class="gmail_msg">
>>> sil shared [_semantics "array.mutate_unknown"] @_TTSg5Si_GSaSi_GSaSi_s10Collections___TFSa6appenduRd__s10CollectionxzWd__8Iterator7Element_rfT10contentsOfqd___T_ : $@convention(method) (@owned Array<I<br class="gmail_msg">
>>> nt>, @inout Array<Int>) -> () {<br class="gmail_msg">
>>><br class="gmail_msg">
>>> …<br class="gmail_msg">
>>> // testArray() -> ()<br class="gmail_msg">
>>> sil [noinline] @_TF9TestArray9testArrayFT_T_ : $@convention(thin) () -> () {<br class="gmail_msg">
>>> bb0:<br class="gmail_msg">
>>> %0 = alloc_stack $Array<Int>, var, name "a", loc "TestArray.swift":3:7, scope 2 // users: %54, %32, %60, %23, %43<br class="gmail_msg">
>>> %1 = integer_literal $Builtin.Word, 3, loc "TestArray.swift":3:12, scope 2 // user: %4<br class="gmail_msg">
>>> %2 = integer_literal $Builtin.Int64, 3, scope 5 // user: %3<br class="gmail_msg">
>>> %3 = struct $Int (%2 : $Builtin.Int64), scope 5 // users: %22, %7<br class="gmail_msg">
>>> %4 = alloc_ref [tail_elems $Int * %1 : $Builtin.Word] $_ContiguousArrayStorage<Int>, scope 5 // user: %7<br class="gmail_msg">
>>> %5 = metatype $@thin Array<Int>.Type, scope 5 // users: %25, %7<br class="gmail_msg">
>>> // function_ref specialized static Array._adoptStorage(_ContiguousArrayStorage<A>, count : Int) -> ([A], UnsafeMutablePointer<A>)<br class="gmail_msg">
>>> %6 = function_ref @_TTSg5Si___TZFSa13_adoptStoragefTGCs23_ContiguousArrayStoragex_5countSi_TGSax_GSpx__ : $@convention(method) (@owned _ContiguousArrayStorage<Int>, Int, @thin Array<Int>.Type) -> (@<br class="gmail_msg">
>>> owned Array<Int>, UnsafeMutablePointer<Int>), scope 5 // users: %25, %7<br class="gmail_msg">
>>> %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<br class="gmail_msg">
>>> %8 = tuple_extract %7 : $(Array<Int>, UnsafeMutablePointer<Int>), 0, scope 5 // user: %23<br class="gmail_msg">
>>> %9 = tuple_extract %7 : $(Array<Int>, UnsafeMutablePointer<Int>), 1, scope 5 // user: %10<br class="gmail_msg">
>>> %10 = struct_extract %9 : $UnsafeMutablePointer<Int>, #UnsafeMutablePointer._rawValue, scope 5 // user: %11<br class="gmail_msg">
>>> %11 = pointer_to_address %10 : $Builtin.RawPointer to [strict] $*Int, loc "TestArray.swift":3:12, scope 2 // users: %14, %21, %16<br class="gmail_msg">
>>> %12 = integer_literal $Builtin.Int64, 1, loc "TestArray.swift":3:12, scope 2 // user: %13<br class="gmail_msg">
>>> %13 = struct $Int (%12 : $Builtin.Int64), loc "TestArray.swift":3:12, scope 2 // users: %37, %30, %25, %14<br class="gmail_msg">
>>> store %13 to %11 : $*Int, loc "TestArray.swift":3:12, scope 2 // id: %14<br class="gmail_msg">
>>> %15 = integer_literal $Builtin.Word, 1, loc "TestArray.swift":3:15, scope 2 // users: %34, %24, %16<br class="gmail_msg">
>>> %16 = index_addr %11 : $*Int, %15 : $Builtin.Word, loc "TestArray.swift":3:15, scope 2 // user: %19<br class="gmail_msg">
>>> %17 = integer_literal $Builtin.Int64, 2, loc "TestArray.swift":3:15, scope 2 // user: %18<br class="gmail_msg">
>>> %18 = struct $Int (%17 : $Builtin.Int64), loc "TestArray.swift":3:15, scope 2 // user: %19<br class="gmail_msg">
>>> store %18 to %16 : $*Int, loc "TestArray.swift":3:15, scope 2 // id: %19<br class="gmail_msg">
>>> %20 = integer_literal $Builtin.Word, 2, loc "TestArray.swift":3:18, scope 2 // user: %21<br class="gmail_msg">
>>> %21 = index_addr %11 : $*Int, %20 : $Builtin.Word, loc "TestArray.swift":3:18, scope 2 // user: %22<br class="gmail_msg">
>>> store %3 to %21 : $*Int, loc "TestArray.swift":3:18, scope 2 // id: %22<br class="gmail_msg">
>>> store %8 to %0 : $*Array<Int>, loc "TestArray.swift":3:18, scope 2 // id: %23<br class="gmail_msg">
>>> %24 = alloc_ref [tail_elems $Int * %15 : $Builtin.Word] $_ContiguousArrayStorage<Int>, scope 7 // user: %25<br class="gmail_msg">
>>> %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<br class="gmail_msg">
>>> %26 = tuple_extract %25 : $(Array<Int>, UnsafeMutablePointer<Int>), 0, scope 7 // user: %32<br class="gmail_msg">
>>> %27 = tuple_extract %25 : $(Array<Int>, UnsafeMutablePointer<Int>), 1, scope 7 // user: %28<br class="gmail_msg">
>>> %28 = struct_extract %27 : $UnsafeMutablePointer<Int>, #UnsafeMutablePointer._rawValue, scope 7 // user: %29<br class="gmail_msg">
>>> %29 = pointer_to_address %28 : $Builtin.RawPointer to [strict] $*Int, loc "TestArray.swift":4:9, scope 2 // user: %30<br class="gmail_msg">
>>> store %13 to %29 : $*Int, loc "TestArray.swift":4:9, scope 2 // id: %30<br class="gmail_msg">
>>> // function_ref specialized Array.append<A where ...> (contentsOf : A1) -> ()<br class="gmail_msg">
>>> %31 = function_ref @_TTSg5Si_GSaSi_GSaSi_s10Collections___TFSa6appenduRd__s10CollectionxzWd__8Iterator7Element_rfT10contentsOfqd___T_ : $@convention(method) (@owned Array<Int>, @inout Array<Int>) -> (), scope 10 // user: %32<br class="gmail_msg">
>>> %32 = apply %31(%26, %0) : $@convention(method) (@owned Array<Int>, @inout Array<Int>) -> (), scope 10<br class="gmail_msg">
>><br class="gmail_msg">
>> 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!<br class="gmail_msg">
>><br class="gmail_msg">
>><br class="gmail_msg">
><br class="gmail_msg">
<br class="gmail_msg">
</blockquote></div></div></blockquote></div><br class="gmail_msg"></div></blockquote></div><br class="gmail_msg"></div></div></blockquote></div>