High-level SIL Optimization: How do I get a FuncRef from the stdlib?


(Ben Ng) #1

Good evening, folks.

I’ve been working on a high-level SIL optimization pass that replaces an application of the `+=` function with an application of `Array.concat(A: Element)`. I’m blocked because I can’t figure out how to get a FuncRef to `Array.append` from the SILTransform.

I’ve tried getting the stdlib module from the ASTContext, and looking through the visible decls, but the function that I want isn’t there. The next thing I was going to try was recursively looking through the imports, but I thought I’d stop to do a sanity check with the mailing list.

It seems like even if I did succeed in getting a FuncRef to the generic `Array.append`, I’d still need to figure out how to get the specialized version, and add the appropriate declaration to the SIL. It also feels wrong that I’m depending on stuff in the AST from a SILTransform.

Thanks,

Ben


(Roman Levenstein) #2

Hi,

Good evening, folks.

I’ve been working on a high-level SIL optimization pass that replaces an application of the `+=` function with an application of `Array.concat(A: Element)`. I’m blocked because I can’t figure out how to get a FuncRef to `Array.append` from the SILTransform.

You could use SILModule::hasFunction(FunctionName, SILLinkage::PublicExternal) to get the SILFunction. The FunctionName should be a mangled name of your Array.concat(A:Element) function.

I’ve tried getting the stdlib module from the ASTContext, and looking through the visible decls, but the function that I want isn’t there. The next thing I was going to try was recursively looking through the imports, but I thought I’d stop to do a sanity check with the mailing list.

It seems like even if I did succeed in getting a FuncRef to the generic `Array.append`, I’d still need to figure out how to get the specialized version, and add the appropriate declaration to the SIL. It also feels wrong that I’m depending on stuff in the AST from a SILTransform.

You can just create the invocation of the generic version of Array.concat SILFunction (with a proper set of substitutions) and let the generic specializer produce a specialization for you.

-Roman

···

On Nov 15, 2016, at 5:17 PM, Ben Ng via swift-dev <swift-dev@swift.org> wrote:

Thanks,

Ben
_______________________________________________
swift-dev mailing list
swift-dev@swift.org
https://lists.swift.org/mailman/listinfo/swift-dev


(Michael Gottesman) #3

Hi Michael,

No, I did not. I don't see swift-dev in the cc line of your email... this might be an issue with the Inbox for iOS client that I'm using.

Ok! This happens sometimes (hit reply instead of reply-all or the like). +CC swift-dev.

···

On Nov 15, 2016, at 9:02 PM, Ben Ng <me@benng.me> wrote:

On Wed, Nov 16, 2016 at 12:01 AM Michael Gottesman <mgottesman@apple.com <mailto:mgottesman@apple.com>> wrote:

On Nov 15, 2016, at 8:54 PM, Ben Ng <me@benng.me <mailto:me@benng.me>> wrote:

Hi Michael,

It can probably be stuck in the Array Value Propagation pass since its pretty similar. Yes, it uses Array semantics. I isolated it in a separate file because it's my first time working on the Swift compiler and I wanted to keep the moving parts to a minimum.

Ok. I was just saying this transformation is small enough it probably makes sense not to have a pass just for it. That is all.

Am I confusing the nouns? i.e Is a pass the same thing as a transform?

No you are not confusing anything. A pass is a transform.

Also, did you remove swift-dev for a reason? Can I re-add?

Michael

On Tue, Nov 15, 2016 at 11:49 PM Michael Gottesman <mgottesman@apple.com <mailto:mgottesman@apple.com>> wrote:
Question, is there any reason why you want to create a new pass? We already have array semantic ops. Maybe stick this there?

+CC Arnold who is more familiar with this area.

Sent from my iPhone

> On Nov 15, 2016, at 5:17 PM, Ben Ng via swift-dev <swift-dev@swift.org <mailto:swift-dev@swift.org>> wrote:
>
> Good evening, folks.
>
> I’ve been working on a high-level SIL optimization pass that replaces an application of the `+=` function with an application of `Array.concat(A: Element)`. I’m blocked because I can’t figure out how to get a FuncRef to `Array.append` from the SILTransform.
>
> I’ve tried getting the stdlib module from the ASTContext, and looking through the visible decls, but the function that I want isn’t there. The next thing I was going to try was recursively looking through the imports, but I thought I’d stop to do a sanity check with the mailing list.
>
> It seems like even if I did succeed in getting a FuncRef to the generic `Array.append`, I’d still need to figure out how to get the specialized version, and add the appropriate declaration to the SIL. It also feels wrong that I’m depending on stuff in the AST from a SILTransform.
>
> Thanks,
>
> Ben
> _______________________________________________
> swift-dev mailing list
> swift-dev@swift.org <mailto:swift-dev@swift.org>
> https://lists.swift.org/mailman/listinfo/swift-dev


(Arnold Schwaighofer) #4

It makes sense for this to eventually be part of array value
propagation. I think you will reuse some code that is in there
(probably most of “ArrayAllocation” to get at the element of the
appended array).

As I understand, you are going to transform:

  var a = […]
  a += [1]
  // 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])

to

  var a = […]
  a.append(1)

I agree with Roman that you should emit a call to the unspecialized
“append(_:)” method and be able to rely on later specialization passes
to clean up the unspecialized code.

···

On Wed, Nov 16, 2016 at 12:01 AM Michael Gottesman <mgottesman@apple.com> wrote:

On Nov 15, 2016, at 8:54 PM, Ben Ng <me@benng.me> wrote:

Hi Michael,

It can probably be stuck in the Array Value Propagation pass since its pretty similar. Yes, it uses Array semantics. I isolated it in a separate file because it's my first time working on the Swift compiler and I wanted to keep the moving parts to a minimum.

Ok. I was just saying this transformation is small enough it probably makes sense not to have a pass just for it. That is all.


(Ben Ng) #5

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?


(Arnold Schwaighofer) #6

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();

···

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?

+
     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


(Ben Ng) #7

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!

···

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


(Ben Ng) #8

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!


(Michael Gottesman) #9

+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!


(Ben Ng) #10

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!
>>
>>
>


(Ben Ng) #11

I managed to create the substitution, and the generated SIL looks right, but I’m failing verification:

SIL verification failed: substituted callee type should not be generic: !site.getSubstCalleeType()->isPolymorphic()
Verifying instruction:
     %0 = alloc_stack $Array<Int>, scope 0 // users: %22, %30, %24, %4
     // function_ref Array.append(A) -> ()
  %19 = function_ref @_TFSa6appendfxT_ : $@convention(method) <τ_0_0> (@in τ_0_0, @inout Array<τ_0_0>) -> (), scope 0 // user: %22
     %20 = alloc_stack $Int, scope 0 // users: %23, %22, %21
-> %22 = apply %19<Int>(%20, %0) : $@convention(method) <τ_0_0> (@in τ_0_0, @inout Array<τ_0_0>) -> ()

I don’t understand the error message. What is the “callee”? I’m guessing that it’s the @_TFSa6appendfxT_ function. The generated SIL looks identical to the SIL that I expect. I suspect that I’m calling Builder.createApply with the wrong arguments, and while I can't see the problem in the generated SIL, the verifier is catching it.

Here’s an excerpt of the relevant code:

auto ArrRef = SemanticsCall->getArgument(1);
SILBuilderWithScope Builder(SemanticsCall);
auto *fnRef = Builder.createFunctionRef(SemanticsCall->getLoc(), appendFn);
auto fnTy = fnRef->getType();

… then, inside a loop where V is the SILValue of the element to append:

auto subTy = V->getType();
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)};
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 <mailto: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 <mailto: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 <mailto:me@benng.me>> wrote:
>>
>>> On Nov 16, 2016, at 7:11 PM, Arnold Schwaighofer <aschwaighofer@apple.com <mailto:aschwaighofer@apple.com>> wrote:
>>>
>>>
>>>> On Nov 16, 2016, at 2:58 PM, Ben Ng <me@benng.me <mailto: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 <mailto: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!
>>
>>
>


(Slava Pestov) #12

I managed to create the substitution, and the generated SIL looks right, but I’m failing verification:

SIL verification failed: substituted callee type should not be generic: !site.getSubstCalleeType()->isPolymorphic()
Verifying instruction:
     %0 = alloc_stack $Array<Int>, scope 0 // users: %22, %30, %24, %4
     // function_ref Array.append(A) -> ()
  %19 = function_ref @_TFSa6appendfxT_ : $@convention(method) <τ_0_0> (@in τ_0_0, @inout Array<τ_0_0>) -> (), scope 0 // user: %22
     %20 = alloc_stack $Int, scope 0 // users: %23, %22, %21
-> %22 = apply %19<Int>(%20, %0) : $@convention(method) <τ_0_0> (@in τ_0_0, @inout Array<τ_0_0>) -> ()

I don’t understand the error message. What is the “callee”? I’m guessing that it’s the @_TFSa6appendfxT_ function. The generated SIL looks identical to the SIL that I expect. I suspect that I’m calling Builder.createApply with the wrong arguments, and while I can't see the problem in the generated SIL, the verifier is catching it.

Here’s an excerpt of the relevant code:

auto ArrRef = SemanticsCall->getArgument(1);
SILBuilderWithScope Builder(SemanticsCall);
auto *fnRef = Builder.createFunctionRef(SemanticsCall->getLoc(), appendFn);
auto fnTy = fnRef->getType();

… then, inside a loop where V is the SILValue of the element to append:

auto subTy = V->getType();
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)};
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)

The SubstFnTy parameter should be a concrete SILFunctionType with the generic parameters applied. You’re passing in the original SILFunctionType.

I think you just want to call substGenericArgs() on it with your ArrayRef<Substitution>.

Also please don’t construct ArrayRef<Substitution> by hand; start with a SubstitutionMap instead. Can you give more context about what you’re trying to do?

Slava

···

On Nov 27, 2016, at 6:12 PM, Ben Ng <me@benng.me> wrote:

On Nov 27, 2016, at 3:22 PM, Ben Ng <me@benng.me <mailto: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 <mailto: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 <mailto: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 <mailto:me@benng.me>> wrote:
>>
>>> On Nov 16, 2016, at 7:11 PM, Arnold Schwaighofer <aschwaighofer@apple.com <mailto:aschwaighofer@apple.com>> wrote:
>>>
>>>
>>>> On Nov 16, 2016, at 2:58 PM, Ben Ng <me@benng.me <mailto: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 <mailto: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!
>>
>>
>


(Slava Pestov) #13

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 <mailto: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 <mailto: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 <mailto: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 <mailto:me@benng.me>> wrote:
>>
>>> On Nov 16, 2016, at 7:11 PM, Arnold Schwaighofer <aschwaighofer@apple.com <mailto:aschwaighofer@apple.com>> wrote:
>>>
>>>
>>>> On Nov 16, 2016, at 2:58 PM, Ben Ng <me@benng.me <mailto: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 <mailto: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!
>>
>>
>


(Ben Ng) #14

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.

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.

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()?

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?

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!
>>
>>
>


(Slava Pestov) #15

Hi Ben,

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?

···

On Nov 29, 2016, at 12:10 AM, Ben Ng <me@benng.me> wrote:

Thanks,

Ben
On Sun, Nov 27, 2016 at 10:17 PM Slava Pestov <spestov@apple.com <mailto: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 <mailto: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 <mailto: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 <mailto: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 <mailto:me@benng.me>> wrote:
>>
>>> On Nov 16, 2016, at 7:11 PM, Arnold Schwaighofer <aschwaighofer@apple.com <mailto:aschwaighofer@apple.com>> wrote:
>>>
>>>
>>>> On Nov 16, 2016, at 2:58 PM, Ben Ng <me@benng.me <mailto: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 <mailto: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!
>>
>>
>


(Ben Ng) #16

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@apple.com> wrote:

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!
>>
>>
>


(Slava Pestov) #17

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@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@apple.com <mailto:spestov@apple.com>> wrote:
Hi Ben,

On Nov 29, 2016, at 12:10 AM, Ben Ng <me@benng.me <mailto: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 <mailto: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 <mailto: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 <mailto: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 <mailto: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 <mailto:me@benng.me>> wrote:
>>
>>> On Nov 16, 2016, at 7:11 PM, Arnold Schwaighofer <aschwaighofer@apple.com <mailto:aschwaighofer@apple.com>> wrote:
>>>
>>>
>>>> On Nov 16, 2016, at 2:58 PM, Ben Ng <me@benng.me <mailto: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 <mailto: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!
>>
>>
>