SR-5403 / Memory Optimization Opportunity (Load/Store forwarding)

Hi Michael,

Firstly: if swift-dev is not the right place for me to ask silly questions, please let me know :).

Thanks very much for all your pointers on the JIRA [1] ticket. I was just trying to get started and already have a few questions. Apologies, they're very basic as I'm just getting started with the Swift compiler source and tooling.

The first question is just about the tooling: I got sil-opt to run with an invocation like this:

   swiftc -emit-module -O test.swift
   sil-opt -sdk $(xcrun --show-sdk-path) test.swiftmodule

Now you advise to run the '-debug-only=sil-redundant-load-elim' so I tried

   sil-opt [...] -debug-only=sil-redundant-load-elim

but it doesn't seem happy with that. Did I misunderstand how to pass this option?

My second question actually relates to your first suggestion: 'creating a simple test that performs a store, then passes the address to an in_guaranteed function and then reloads the value'

I read up about @in_guaranteed and I managed to make a @in_guaranteed function this way:

protocol Foo {
    func foo()
}
extension Foo {
    func foo() {}
}

The `foo()` function will now be an @in_guaranteed function taking `self`, correct? (any other ways to create an `@in_guaranteed` function easily?) This is probably me being a bit slow but what exactly do you mean with performing a store, passing the address to an @in_guaranteed function and then reloading the value? Very naively I thought about

class C: Foo {}
func something() {
    let c = C()
    var b: Foo = c /* store */
    b.foo() /* pass the address to an `@in_guaranteed` func */
    c.foo() /* load again */
}

is this roughly what you had in mind?

Thanks,
  Johannes

[1]: https://bugs.swift.org/browse/SR-5403

Hi Michael,

Firstly: if swift-dev is not the right place for me to ask silly questions, please let me know :).

Thanks very much for all your pointers on the JIRA [1] ticket. I was just trying to get started and already have a few questions. Apologies, they're very basic as I'm just getting started with the Swift compiler source and tooling.

The first question is just about the tooling: I got sil-opt to run with an invocation like this:

  swiftc -emit-module -O test.swift
  sil-opt -sdk $(xcrun --show-sdk-path) test.swiftmodule

Now you advise to run the '-debug-only=sil-redundant-load-elim' so I tried

  sil-opt [...] -debug-only=sil-redundant-load-elim

but it doesn't seem happy with that. Did I misunderstand how to pass this option?

What do you mean by it doesn't seem happy?

My second question actually relates to your first suggestion: 'creating a simple test that performs a store, then passes the address to an in_guaranteed function and then reloads the value'

I read up about @in_guaranteed and I managed to make a @in_guaranteed function this way:

protocol Foo {
   func foo()
}
extension Foo {
   func foo() {}
}

The `foo()` function will now be an @in_guaranteed function taking `self`, correct? (any other ways to create an `@in_guaranteed` function easily?) This is probably me being a bit slow but what exactly do you mean with performing a store, passing the address to an @in_guaranteed function and then reloading the value? Very naively I thought about

class C: Foo {}
func something() {
   let c = C()
   var b: Foo = c /* store */
   b.foo() /* pass the address to an `@in_guaranteed` func */
   c.foo() /* load again */
}

is this roughly what you had in mind?

Nope. I was suggesting that you write the SIL by hand. It will be much easier.

···

On Jul 10, 2017, at 10:56 AM, Johannes Weiß <johannesweiss@apple.com> wrote:

Thanks,
Johannes

[1]: https://bugs.swift.org/browse/SR-5403

Hi Michael,

[...]

Now you advise to run the '-debug-only=sil-redundant-load-elim' so I tried

sil-opt [...] -debug-only=sil-redundant-load-elim

but it doesn't seem happy with that. Did I misunderstand how to pass this option?

What do you mean by it doesn't seem happy?

I was using a too old/wrong version of sil-opt (the one from Xcode 9 beta N) which didn't have that option. Resolved by using the one from my own swift build.

[...]

is this roughly what you had in mind?

Nope. I was suggesting that you write the SIL by hand. It will be much easier.

Ha, that's a much better idea, thanks for your help, much appreciated! No idea why I didn't think of that. This is today's update:

--- SNIP (whole file attached as test-load-forwarding.sil) ---
// bar()
sil hidden @bar : @convention\(thin\) \(\) \-&gt; \(\) \{ bb0: &nbsp;&nbsp;alloc\_global @MyIntStorage &nbsp;&nbsp;%int\_storage = global\_addr @MyIntStorage : *Int
  %value_raw = integer_literal $Builtin.Int64, 42
  %value = struct $Int (%value_raw : Builtin\.Int64\) &nbsp;&nbsp;store %value to %int\_storage : *Int

  %f_buz = function_ref @buz : @convention\(thin\) \(@in\_guaranteed Int\) \-&gt; \(\) &nbsp;&nbsp;%r1 = apply %f\_buz\(%int\_storage\) : @convention(thin) (@in_guaranteed Int) -> ()

  %value_again = load %int_storage : \*Int &nbsp;&nbsp;%f\_test = function\_ref @testNumber12345 : @convention(thin) (Int) -> ()
  %r2 = apply %f_test(%value_again) : $@convention(thin) (Int) -> ()

  // just to test an illegal function
  %f_bad = function_ref @bad : @convention\(thin\) \(@in\_guaranteed Int\) \-&gt; \(\) &nbsp;&nbsp;%r3 = apply %f\_bad\(%int\_storage\) : @convention(thin) (@in_guaranteed Int) -> ()

  %value_again2 = load %int_storage : \*Int &nbsp;&nbsp;%r4 = apply %f\_test\(%value\_again2\) : @convention(thin) (Int) -> ()

  return %r2 : $()
} // end sil function 'bar'
--- SNAP ---

So I make a global Int storage, store the number 42 to it, invoke buz() which takes an @in_guaranteed Int, then load it again (this is redundant as @in_guaranteed isn't allowed to modify it). I also pass the loaded number to the function testNumber12345() which just tests that it's the number 12345 (which it isn't but I wanted to be sure it's actually consumed)

Then (because I believe the RLE actually works) I also introduced a function `bad` which is a bit like `buz` but it does actually write to the *Int which I believe is illegal (right?).

Now let's see what we get with sil-opt

I run the following command:

    sil-opt -verify -assume-parsing-unqualified-ownership-sil -redundant-load-elim -debug-only=sil-redundant-load-elim -debug test-load-forwarding.sil

which gives me the following output (my annotations marked as [JW: ... ])

--- SNIP (whole file attached as test-load-forwarding.sil-opt) ---
*** RLE on function: testNumber12345 ***
*** RLE on function: buz ***
*** RLE on function: bad ***
*** RLE on function: bar ***
LSLocation #0 %1 = global_addr @MyIntStorage : \*Int // users: %12, %11, %7, %6, %4 Projection Path \[*Int
  Field: var _value: Int64 of: \*Builtin\.Int64\] PROCESS bb0 for RLE\. WRITE alloc\_global @MyIntStorage // id: %0 WRITE %6 = apply %5\(%1\) : @convention(thin) (@in_guaranteed Int) -> ()
FORWARD %3 = struct $Int (%2 : Builtin\.Int64\) // user: %4 &nbsp;&nbsp;to %7 = load %1 : *Int // user: %9
WRITE %9 = apply %8(%7) : @convention\(thin\) \(Int\) \-&gt; \(\) // user: %14 WRITE %11 = apply %10\(%1\) : @convention(thin) (@in_guaranteed Int) -> ()
WRITE %13 = apply %8(%12) : @convention\(thin\) \(Int\) \-&gt; \(\) Replacing %7 = load %1 : *Int // user: %9
With %3 = struct $Int (%2 : $Builtin.Int64) // user: %4
[JW: ^^^^ this looks pretty promising to me, don't understand all the output but looks like it's replacing a load :) ]
*** RLE on function: main ***
sil_stage canonical

[...]

// bar
sil hidden @bar : @convention\(thin\) \(\) \-&gt; \(\) \{ bb0: &nbsp;&nbsp;alloc\_global @MyIntStorage // id: %0 &nbsp;&nbsp;%1 = global\_addr @MyIntStorage : *Int // users: %11, %10, %6, %4
  %2 = integer_literal $Builtin.Int64, 42 // user: %3
  %3 = struct $Int (%2 : Builtin\.Int64\) // users: %8, %4 &nbsp;&nbsp;store %3 to %1 : *Int // id: %4
  // function_ref buz
  %5 = function_ref @buz : @convention\(thin\) \(@in\_guaranteed Int\) \-&gt; \(\) // user: %6 &nbsp;&nbsp;%6 = apply %5\(%1\) : @convention(thin) (@in_guaranteed Int) -> ()
  // function_ref testNumber12345
  %7 = function_ref @testNumber12345 : @convention\(thin\) \(Int\) \-&gt; \(\) // users: %12, %8 &nbsp;&nbsp;\[JW: Indeed, it seems to have optimised out the redundant load\. So that works\! \] &nbsp;&nbsp;%8 = apply %7\(%3\) : @convention(thin) (Int) -> () // user: %13
  // function_ref bad
  %9 = function_ref @bad : @convention\(thin\) \(@in\_guaranteed Int\) \-&gt; \(\) // user: %10 &nbsp;&nbsp;%10 = apply %9\(%1\) : @convention(thin) (@in_guaranteed Int) -> ()
  [JW: Wow, very clever, it didn't optimise out this load despite me giving the wrong guarantee that it's not actually modified (or am I misunderstanding something]
  %11 = load %1 : \*Int // user: %12 &nbsp;&nbsp;%12 = apply %7\(%11\) : @convention(thin) (Int) -> ()
  return %8 : $() // id: %13
} // end sil function 'bar'

[...]
--- SNAP ---

Long story short, I think the RLE actually works for the test case I created. It's even clever enough to see through my invalid function bad() which modified the storage despite its claim that it doesn't. I might also be misunderstanding something.

Does that all make sense?

Thanks,
  Johannes

test-load-forwarding.sil (2.93 KB)

test-load-forwarding.sil-opt (4.49 KB)

Hi Michael,

[...]

Now you advise to run the '-debug-only=sil-redundant-load-elim' so I tried

sil-opt [...] -debug-only=sil-redundant-load-elim

but it doesn't seem happy with that. Did I misunderstand how to pass this option?

What do you mean by it doesn't seem happy?

I was using a too old/wrong version of sil-opt (the one from Xcode 9 beta N) which didn't have that option. Resolved by using the one from my own swift build.

Ok.

[...]

is this roughly what you had in mind?

Nope. I was suggesting that you write the SIL by hand. It will be much easier.

Ha, that's a much better idea, thanks for your help, much appreciated! No idea why I didn't think of that. This is today's update:

--- SNIP (whole file attached as test-load-forwarding.sil) ---
// bar()
sil hidden @bar : $@convention(thin) () -> () {
bb0:
alloc_global @MyIntStorage
%int_storage = global_addr @MyIntStorage : $*Int
%value_raw = integer_literal $Builtin.Int64, 42
%value = struct $Int (%value_raw : $Builtin.Int64)
store %value to %int_storage : $*Int

%f_buz = function_ref @buz : $@convention(thin) (@in_guaranteed Int) -> ()
%r1 = apply %f_buz(%int_storage) : $@convention(thin) (@in_guaranteed Int) -> ()

%value_again = load %int_storage : $*Int
%f_test = function_ref @testNumber12345 : $@convention(thin) (Int) -> ()
%r2 = apply %f_test(%value_again) : $@convention(thin) (Int) -> ()

// just to test an illegal function
%f_bad = function_ref @bad : $@convention(thin) (@in_guaranteed Int) -> ()
%r3 = apply %f_bad(%int_storage) : $@convention(thin) (@in_guaranteed Int) -> ()

%value_again2 = load %int_storage : $*Int
%r4 = apply %f_test(%value_again2) : $@convention(thin) (Int) -> ()

return %r2 : $()
} // end sil function 'bar'
--- SNAP ---

So I make a global Int storage, store the number 42 to it, invoke buz() which takes an @in_guaranteed Int, then load it again (this is redundant as @in_guaranteed isn't allowed to modify it). I also pass the loaded number to the function testNumber12345() which just tests that it's the number 12345 (which it isn't but I wanted to be sure it's actually consumed)

Then (because I believe the RLE actually works) I also introduced a function `bad` which is a bit like `buz` but it does actually write to the *Int which I believe is illegal (right?).

Now let's see what we get with sil-opt

I run the following command:

   sil-opt -verify -assume-parsing-unqualified-ownership-sil -redundant-load-elim -debug-only=sil-redundant-load-elim -debug test-load-forwarding.sil

which gives me the following output (my annotations marked as [JW: ... ])

--- SNIP (whole file attached as test-load-forwarding.sil-opt) ---
*** RLE on function: testNumber12345 ***
*** RLE on function: buz ***
*** RLE on function: bad ***
*** RLE on function: bar ***
LSLocation #0 %1 = global_addr @MyIntStorage : $*Int // users: %12, %11, %7, %6, %4
Projection Path [$*Int
Field: var _value: Int64 of: $*Builtin.Int64]
PROCESS bb0 for RLE.
WRITE alloc_global @MyIntStorage // id: %0
WRITE %6 = apply %5(%1) : $@convention(thin) (@in_guaranteed Int) -> ()
FORWARD %3 = struct $Int (%2 : $Builtin.Int64) // user: %4
to %7 = load %1 : $*Int // user: %9
WRITE %9 = apply %8(%7) : $@convention(thin) (Int) -> () // user: %14
WRITE %11 = apply %10(%1) : $@convention(thin) (@in_guaranteed Int) -> ()
WRITE %13 = apply %8(%12) : $@convention(thin) (Int) -> ()
Replacing %7 = load %1 : $*Int // user: %9
With %3 = struct $Int (%2 : $Builtin.Int64) // user: %4
[JW: ^^^^ this looks pretty promising to me, don't understand all the output but looks like it's replacing a load :slight_smile: ]
*** RLE on function: main ***
sil_stage canonical

[...]

// bar
sil hidden @bar : $@convention(thin) () -> () {
bb0:
alloc_global @MyIntStorage // id: %0
%1 = global_addr @MyIntStorage : $*Int // users: %11, %10, %6, %4
%2 = integer_literal $Builtin.Int64, 42 // user: %3
%3 = struct $Int (%2 : $Builtin.Int64) // users: %8, %4
store %3 to %1 : $*Int // id: %4
// function_ref buz
%5 = function_ref @buz : $@convention(thin) (@in_guaranteed Int) -> () // user: %6
%6 = apply %5(%1) : $@convention(thin) (@in_guaranteed Int) -> ()
// function_ref testNumber12345
%7 = function_ref @testNumber12345 : $@convention(thin) (Int) -> () // users: %12, %8
[JW: Indeed, it seems to have optimised out the redundant load. So that works! ]
%8 = apply %7(%3) : $@convention(thin) (Int) -> () // user: %13
// function_ref bad
%9 = function_ref @bad : $@convention(thin) (@in_guaranteed Int) -> () // user: %10
%10 = apply %9(%1) : $@convention(thin) (@in_guaranteed Int) -> ()
[JW: Wow, very clever, it didn't optimise out this load despite me giving the wrong guarantee that it's not actually modified (or am I misunderstanding something]
%11 = load %1 : $*Int // user: %12
%12 = apply %7(%11) : $@convention(thin) (Int) -> ()
return %8 : $() // id: %13
} // end sil function 'bar'

[...]
--- SNAP ---

Long story short, I think the RLE actually works for the test case I created. It's even clever enough to see through my invalid function bad() which modified the storage despite its claim that it doesn't. I might also be misunderstanding something.

When something is marked as in_guaranteed, it should be immutable. If the callee violates that, then the SIL is malformed. Perhaps, we can add some sort of verification check.

That being said, I have a good feeling that there is some sort of analysis occuring here since you provided enough information to the optimizer. The optimization here is regardless of whether or not we can see the body of a function, we know that it is safe to optimize this just based off the @in_guaranteed. This implies using a declaration, not a definition of the bad function.

When I said write the SIL by hand, what I meant was writing the whole program by hand. In general, we prefer SIL programs that do not have extraneous stuff that is added by the compiler (for instance debug_value). Additionally, it is important for SIL files to not have dependencies on the stdlib unless absolutely necessary (i.e. your usage of Int). This prevents the stdlib maintainers from having to update these tests given chances to the stdlib. Below is a cleaned up version that shows the problem. Look at how small it is and how it tests /exactly/ what we are trying to test and via the use of declarations and the like we are able to exclude other optimizations:

···

On Jul 11, 2017, at 10:16 AM, Johannes Weiß <johannesweiss@apple.com> wrote:

----
sil_stage canonical

import Builtin

struct Int {
  var _value : Builtin.Int64
}

sil @test : $@convention(thin) (Int) -> ()
sil @buz : $@convention(thin) (@in_guaranteed Int) -> ()
sil @bad : $@convention(thin) (@in_guaranteed Int) -> ()

sil @bar : $@convention(thin) (@in Int) -> () {
bb0(%0 : $*Int):
  %value_raw = integer_literal $Builtin.Int64, 42
  %value = struct $Int (%value_raw : $Builtin.Int64)
  store %value to %0 : $*Int

  %f_buz = function_ref @buz : $@convention(thin) (@in_guaranteed Int) -> ()
  %r1 = apply %f_buz(%0) : $@convention(thin) (@in_guaranteed Int) -> ()

  %value_again = load %0 : $*Int
  %f_test = function_ref @test : $@convention(thin) (Int) -> ()
  %r2 = apply %f_test(%value_again) : $@convention(thin) (Int) -> ()

  %f_bad = function_ref @bad : $@convention(thin) (@in_guaranteed Int) -> ()
  %r3 = apply %f_bad(%0) : $@convention(thin) (@in_guaranteed Int) -> ()

  %value_again2 = load %0 : $*Int
  %r4 = apply %f_test(%value_again2) : $@convention(thin) (Int) -> ()

  %9999 = tuple()
  return %9999 : $()
}
----

When I run this test file through rle, I get:

----
sil_stage canonical

import Builtin
import Swift
import SwiftShims

struct Int {
  @sil_stored var _value: Builtin.Int64
  init(_value: Builtin.Int64)
}

// test
sil @test : $@convention(thin) (Int) -> ()

// buz
sil @buz : $@convention(thin) (@in_guaranteed Int) -> ()

// bad
sil @bad : $@convention(thin) (@in_guaranteed Int) -> ()

// bar
sil @bar : $@convention(thin) (@in Int) -> () {
// %0 // users: %11, %10, %6, %5, %3
bb0(%0 : $*Int):
  %1 = integer_literal $Builtin.Int64, 42 // user: %2
  %2 = struct $Int (%1 : $Builtin.Int64) // user: %3
  store %2 to %0 : $*Int // id: %3
  // function_ref buz
  %4 = function_ref @buz : $@convention(thin) (@in_guaranteed Int) -> () // user: %5
  %5 = apply %4(%0) : $@convention(thin) (@in_guaranteed Int) -> ()
  %6 = load %0 : $*Int // user: %8
  // function_ref test
  %7 = function_ref @test : $@convention(thin) (Int) -> () // users: %12, %8
  %8 = apply %7(%6) : $@convention(thin) (Int) -> ()
  // function_ref bad
  %9 = function_ref @bad : $@convention(thin) (@in_guaranteed Int) -> () // user: %10
  %10 = apply %9(%0) : $@convention(thin) (@in_guaranteed Int) -> ()
  %11 = load %0 : $*Int // user: %12
  %12 = apply %7(%11) : $@convention(thin) (Int) -> ()
  %13 = tuple () // user: %14
  return %13 : $() // id: %14
} // end sil function 'bar'
----

Michael

Does that all make sense?

Thanks,
Johannes
<test-load-forwarding.sil><test-load-forwarding.sil-opt>

Thanks,
Johannes

[1]: https://bugs.swift.org/browse/SR-5403

Hi Michael,

[...]

Now you advise to run the '-debug-only=sil-redundant-load-elim' so I tried

sil-opt [...] -debug-only=sil-redundant-load-elim

but it doesn't seem happy with that. Did I misunderstand how to pass this option?

What do you mean by it doesn't seem happy?

I was using a too old/wrong version of sil-opt (the one from Xcode 9 beta N) which didn't have that option. Resolved by using the one from my own swift build.

Ok.

[...]

is this roughly what you had in mind?

Nope. I was suggesting that you write the SIL by hand. It will be much easier.

Ha, that's a much better idea, thanks for your help, much appreciated! No idea why I didn't think of that. This is today's update:

--- SNIP (whole file attached as test-load-forwarding.sil) ---
// bar()
sil hidden @bar : $@convention(thin) () -> () {
bb0:
alloc_global @MyIntStorage
%int_storage = global_addr @MyIntStorage : $*Int
%value_raw = integer_literal $Builtin.Int64, 42
%value = struct $Int (%value_raw : $Builtin.Int64)
store %value to %int_storage : $*Int

%f_buz = function_ref @buz : $@convention(thin) (@in_guaranteed Int) -> ()
%r1 = apply %f_buz(%int_storage) : $@convention(thin) (@in_guaranteed Int) -> ()

%value_again = load %int_storage : $*Int
%f_test = function_ref @testNumber12345 : $@convention(thin) (Int) -> ()
%r2 = apply %f_test(%value_again) : $@convention(thin) (Int) -> ()

// just to test an illegal function
%f_bad = function_ref @bad : $@convention(thin) (@in_guaranteed Int) -> ()
%r3 = apply %f_bad(%int_storage) : $@convention(thin) (@in_guaranteed Int) -> ()

%value_again2 = load %int_storage : $*Int
%r4 = apply %f_test(%value_again2) : $@convention(thin) (Int) -> ()

return %r2 : $()
} // end sil function 'bar'
--- SNAP ---

So I make a global Int storage, store the number 42 to it, invoke buz() which takes an @in_guaranteed Int, then load it again (this is redundant as @in_guaranteed isn't allowed to modify it). I also pass the loaded number to the function testNumber12345() which just tests that it's the number 12345 (which it isn't but I wanted to be sure it's actually consumed)

Then (because I believe the RLE actually works) I also introduced a function `bad` which is a bit like `buz` but it does actually write to the *Int which I believe is illegal (right?).

Now let's see what we get with sil-opt

I run the following command:

   sil-opt -verify -assume-parsing-unqualified-ownership-sil -redundant-load-elim -debug-only=sil-redundant-load-elim -debug test-load-forwarding.sil

which gives me the following output (my annotations marked as [JW: ... ])

--- SNIP (whole file attached as test-load-forwarding.sil-opt) ---
*** RLE on function: testNumber12345 ***
*** RLE on function: buz ***
*** RLE on function: bad ***
*** RLE on function: bar ***
LSLocation #0 %1 = global_addr @MyIntStorage : $*Int // users: %12, %11, %7, %6, %4
Projection Path [$*Int
Field: var _value: Int64 of: $*Builtin.Int64]
PROCESS bb0 for RLE.
WRITE alloc_global @MyIntStorage // id: %0
WRITE %6 = apply %5(%1) : $@convention(thin) (@in_guaranteed Int) -> ()
FORWARD %3 = struct $Int (%2 : $Builtin.Int64) // user: %4
to %7 = load %1 : $*Int // user: %9
WRITE %9 = apply %8(%7) : $@convention(thin) (Int) -> () // user: %14
WRITE %11 = apply %10(%1) : $@convention(thin) (@in_guaranteed Int) -> ()
WRITE %13 = apply %8(%12) : $@convention(thin) (Int) -> ()
Replacing %7 = load %1 : $*Int // user: %9
With %3 = struct $Int (%2 : $Builtin.Int64) // user: %4
[JW: ^^^^ this looks pretty promising to me, don't understand all the output but looks like it's replacing a load :slight_smile: ]
*** RLE on function: main ***
sil_stage canonical

[...]

// bar
sil hidden @bar : $@convention(thin) () -> () {
bb0:
alloc_global @MyIntStorage // id: %0
%1 = global_addr @MyIntStorage : $*Int // users: %11, %10, %6, %4
%2 = integer_literal $Builtin.Int64, 42 // user: %3
%3 = struct $Int (%2 : $Builtin.Int64) // users: %8, %4
store %3 to %1 : $*Int // id: %4
// function_ref buz
%5 = function_ref @buz : $@convention(thin) (@in_guaranteed Int) -> () // user: %6
%6 = apply %5(%1) : $@convention(thin) (@in_guaranteed Int) -> ()
// function_ref testNumber12345
%7 = function_ref @testNumber12345 : $@convention(thin) (Int) -> () // users: %12, %8
[JW: Indeed, it seems to have optimised out the redundant load. So that works! ]
%8 = apply %7(%3) : $@convention(thin) (Int) -> () // user: %13
// function_ref bad
%9 = function_ref @bad : $@convention(thin) (@in_guaranteed Int) -> () // user: %10
%10 = apply %9(%1) : $@convention(thin) (@in_guaranteed Int) -> ()
[JW: Wow, very clever, it didn't optimise out this load despite me giving the wrong guarantee that it's not actually modified (or am I misunderstanding something]
%11 = load %1 : $*Int // user: %12
%12 = apply %7(%11) : $@convention(thin) (Int) -> ()
return %8 : $() // id: %13
} // end sil function 'bar'

[...]
--- SNAP ---

Long story short, I think the RLE actually works for the test case I created. It's even clever enough to see through my invalid function bad() which modified the storage despite its claim that it doesn't. I might also be misunderstanding something.

When something is marked as in_guaranteed, it should be immutable. If the callee violates that, then the SIL is malformed. Perhaps, we can add some sort of verification check.

That being said, I have a good feeling that there is some sort of analysis occuring here since you provided enough information to the optimizer. The optimization here is regardless of whether or not we can see the body of a function, we know that it is safe to optimize this just based off the @in_guaranteed. This implies using a declaration, not a definition of the bad function.

To elaborate slightly: what I mean here is that the optimizer has the ability to perform IPA (inter-procedural analysis), so by providing the bodies of the functions, most likely the optimizer is able to analyze the bodies of the functions you are calling and ascertain that no write is really happening. By using declarations instead of definitions, the optimizer is forced to only use the information in the declaration and be conservative. This is the case where having in_guaranteed in the declaration is interesting from an optimization perspective.

···

On Jul 11, 2017, at 4:21 PM, Michael Gottesman via swift-dev <swift-dev@swift.org> wrote:

On Jul 11, 2017, at 10:16 AM, Johannes Weiß <johannesweiss@apple.com <mailto:johannesweiss@apple.com>> wrote:

When I said write the SIL by hand, what I meant was writing the whole program by hand. In general, we prefer SIL programs that do not have extraneous stuff that is added by the compiler (for instance debug_value). Additionally, it is important for SIL files to not have dependencies on the stdlib unless absolutely necessary (i.e. your usage of Int). This prevents the stdlib maintainers from having to update these tests given chances to the stdlib. Below is a cleaned up version that shows the problem. Look at how small it is and how it tests /exactly/ what we are trying to test and via the use of declarations and the like we are able to exclude other optimizations:

----
sil_stage canonical

import Builtin

struct Int {
  var _value : Builtin.Int64
}

sil @test : $@convention(thin) (Int) -> ()
sil @buz : $@convention(thin) (@in_guaranteed Int) -> ()
sil @bad : $@convention(thin) (@in_guaranteed Int) -> ()

sil @bar : $@convention(thin) (@in Int) -> () {
bb0(%0 : $*Int):
  %value_raw = integer_literal $Builtin.Int64, 42
  %value = struct $Int (%value_raw : $Builtin.Int64)
  store %value to %0 : $*Int

  %f_buz = function_ref @buz : $@convention(thin) (@in_guaranteed Int) -> ()
  %r1 = apply %f_buz(%0) : $@convention(thin) (@in_guaranteed Int) -> ()

  %value_again = load %0 : $*Int
  %f_test = function_ref @test : $@convention(thin) (Int) -> ()
  %r2 = apply %f_test(%value_again) : $@convention(thin) (Int) -> ()

  %f_bad = function_ref @bad : $@convention(thin) (@in_guaranteed Int) -> ()
  %r3 = apply %f_bad(%0) : $@convention(thin) (@in_guaranteed Int) -> ()

  %value_again2 = load %0 : $*Int
  %r4 = apply %f_test(%value_again2) : $@convention(thin) (Int) -> ()

  %9999 = tuple()
  return %9999 : $()
}
----

When I run this test file through rle, I get:

----
sil_stage canonical

import Builtin
import Swift
import SwiftShims

struct Int {
  @sil_stored var _value: Builtin.Int64
  init(_value: Builtin.Int64)
}

// test
sil @test : $@convention(thin) (Int) -> ()

// buz
sil @buz : $@convention(thin) (@in_guaranteed Int) -> ()

// bad
sil @bad : $@convention(thin) (@in_guaranteed Int) -> ()

// bar
sil @bar : $@convention(thin) (@in Int) -> () {
// %0 // users: %11, %10, %6, %5, %3
bb0(%0 : $*Int):
  %1 = integer_literal $Builtin.Int64, 42 // user: %2
  %2 = struct $Int (%1 : $Builtin.Int64) // user: %3
  store %2 to %0 : $*Int // id: %3
  // function_ref buz
  %4 = function_ref @buz : $@convention(thin) (@in_guaranteed Int) -> () // user: %5
  %5 = apply %4(%0) : $@convention(thin) (@in_guaranteed Int) -> ()
  %6 = load %0 : $*Int // user: %8
  // function_ref test
  %7 = function_ref @test : $@convention(thin) (Int) -> () // users: %12, %8
  %8 = apply %7(%6) : $@convention(thin) (Int) -> ()
  // function_ref bad
  %9 = function_ref @bad : $@convention(thin) (@in_guaranteed Int) -> () // user: %10
  %10 = apply %9(%0) : $@convention(thin) (@in_guaranteed Int) -> ()
  %11 = load %0 : $*Int // user: %12
  %12 = apply %7(%11) : $@convention(thin) (Int) -> ()
  %13 = tuple () // user: %14
  return %13 : $() // id: %14
} // end sil function 'bar'
----

Michael

Does that all make sense?

Thanks,
Johannes
<test-load-forwarding.sil><test-load-forwarding.sil-opt>

Thanks,
Johannes

[1]: https://bugs.swift.org/browse/SR-5403

_______________________________________________
swift-dev mailing list
swift-dev@swift.org <mailto:swift-dev@swift.org>
https://lists.swift.org/mailman/listinfo/swift-dev

Hi Michael,

[...]

Long story short, I think the RLE actually works for the test case I created. It's even clever enough to see through my invalid function bad() which modified the storage despite its claim that it doesn't. I might also be misunderstanding something.

When something is marked as in_guaranteed, it should be immutable. If the callee violates that, then the SIL is malformed. Perhaps, we can add some sort of verification check.

Right, yes I was aware that that'd be illegal but I added it as a way to check whether this optimisation is 'looking into' the called function.

That being said, I have a good feeling that there is some sort of analysis occuring here since you provided enough information to the optimizer. The optimization here is regardless of whether or not we can see the body of a function, we know that it is safe to optimize this just based off the @in_guaranteed. This implies using a declaration, not a definition of the bad function.

makes sense, didn't think about just only declaring it...

When I said write the SIL by hand, what I meant was writing the whole program by hand. In general, we prefer SIL programs that do not have extraneous stuff that is added by the compiler (for instance debug_value). Additionally, it is important for SIL files to not have dependencies on the stdlib unless absolutely necessary (i.e. your usage of Int). This prevents the stdlib maintainers from having to update these tests given chances to the stdlib. Below is a cleaned up version that shows the problem. Look at how small it is and how it tests /exactly/ what we are trying to test and via the use of declarations and the like we are able to exclude other optimizations:

That makes a lot of sense, thank you. I wasn't yet that familiar with SIL so I thought I start from a program generated by the compiler and then replace the guts with handwritten SIL. But your version is clearly a lot easier to understand and shows what precisely we want to see!

Today, I looked into why this is happening more precisely.

So we don't get the RLE because in this code

  if (isComputeAvailValue(Kind) || isPerformingRLE(Kind)) {
    for (unsigned i = 0; i < Locs.size(); ++i) {
      if (isTrackingLocation(ForwardSetIn, Ctx.getLocationBit(Locs[i])))
        continue;
      updateForwardSetAndValForRead(Ctx, Ctx.getLocationBit(Locs[i]),
                                    Ctx.getValueBit(Vals[i]));
      // We can not perform the forwarding as we are at least missing
      // some pieces of the read location.
      CanForward = false;

(https://github.com/apple/swift/blob/86620aaa7ebd32d33f4cdf61add5c63a72d3f02a/lib/SILOptimizer/Transforms/RedundantLoadElimination.cpp#L917)

we're not taking the `continue` for the call to `buz()`. The reason why is that here

    if (!AA->mayWriteToMemory(I, R.getBase()))
      continue;
    // MayAlias.
    stopTrackingLocation(ForwardSetIn, i);
    stopTrackingValue(ForwardValIn, i);

(https://github.com/apple/swift/blob/86620aaa7ebd32d33f4cdf61add5c63a72d3f02a/lib/SILOptimizer/Transforms/RedundantLoadElimination.cpp#L972)

we're not taking the `continue`, ie. `AA->mayWriteToMemory(I, R.getBase())` is true. The reason for that is that the `SILFunction` for `buz` has

   EffectsKindAttr = Unspecified

which equates to `MayHaveSideEffects`, that's also what `-debug-only=sil-redundant-load-elim,sil-membehavior` outputs:

GET MEMORY BEHAVIOR FOR:
      %5 = apply %4(%0) : $@convention(thin) (@in_guaranteed Int) -> ()
      %0 = argument of bb0 : $*Int // users: %6, %5, %3
  Found apply, returning MayHaveSideEffects

So where I'm stuck today is that I'm not sure how `EffectsKindAttr` is actually defined. Sure, `$@convention(thin) (@in_guaranteed Int) -> ()` doesn't actually write to the `@in_guaranteed Int` (as that'd be illegal) but it may have other side effects. So I'm not sure if we can just create the function differently if we find only "read-only" kind of parameters. That'd be I think in

  auto *fn = SILMod.createFunction(SILLinkage::Private, Name.str(), Ty,
                                   nullptr, loc, IsNotBare,
                                   IsNotTransparent, IsNotSerialized);

(https://github.com/apple/swift/blob/ec6fc4d54db95f78ae72dab29734533f709ea2d7/lib/Parse/ParseSIL.cpp#L508 -> https://github.com/apple/swift/blob/157db57506b813837481b574a9d38e806bf954b6/lib/SIL/SILModule.cpp#L249)

which doesn't specify any EffectsAttrKind and therefore it defaults to `Unspecified`.

Just as a test, I did put a `[readonly]` in `sil @buz : $@convention(thin) (@in_guaranteed Int) -> ()` and as expected everything propagates through correctly and we get a successful RLE.

So yes, maybe you have some pointers on where to best educate the compiler that the `buz` function won't write to that bit of memory.

Many thanks,
  Johannes

···

----
sil_stage canonical

import Builtin

struct Int {
  var _value : Builtin.Int64
}

sil @test : $@convention(thin) (Int) -> ()
sil @buz : $@convention(thin) (@in_guaranteed Int) -> ()
sil @bad : $@convention(thin) (@in_guaranteed Int) -> ()

sil @bar : $@convention(thin) (@in Int) -> () {
bb0(%0 : $*Int):
  %value_raw = integer_literal $Builtin.Int64, 42
  %value = struct $Int (%value_raw : $Builtin.Int64)
  store %value to %0 : $*Int

  %f_buz = function_ref @buz : $@convention(thin) (@in_guaranteed Int) -> ()
  %r1 = apply %f_buz(%0) : $@convention(thin) (@in_guaranteed Int) -> ()

  %value_again = load %0 : $*Int
  %f_test = function_ref @test : $@convention(thin) (Int) -> ()
  %r2 = apply %f_test(%value_again) : $@convention(thin) (Int) -> ()

  %f_bad = function_ref @bad : $@convention(thin) (@in_guaranteed Int) -> ()
  %r3 = apply %f_bad(%0) : $@convention(thin) (@in_guaranteed Int) -> ()

  %value_again2 = load %0 : $*Int
  %r4 = apply %f_test(%value_again2) : $@convention(thin) (Int) -> ()

  %9999 = tuple()
  return %9999 : $()
}
----

When I run this test file through rle, I get:

----
sil_stage canonical

import Builtin
import Swift
import SwiftShims

struct Int {
  @sil_stored var _value: Builtin.Int64
  init(_value: Builtin.Int64)
}

// test
sil @test : $@convention(thin) (Int) -> ()

// buz
sil @buz : $@convention(thin) (@in_guaranteed Int) -> ()

// bad
sil @bad : $@convention(thin) (@in_guaranteed Int) -> ()

// bar
sil @bar : $@convention(thin) (@in Int) -> () {
// %0 // users: %11, %10, %6, %5, %3
bb0(%0 : $*Int):
  %1 = integer_literal $Builtin.Int64, 42 // user: %2
  %2 = struct $Int (%1 : $Builtin.Int64) // user: %3
  store %2 to %0 : $*Int // id: %3
  // function_ref buz
  %4 = function_ref @buz : $@convention(thin) (@in_guaranteed Int) -> () // user: %5
  %5 = apply %4(%0) : $@convention(thin) (@in_guaranteed Int) -> ()
  %6 = load %0 : $*Int // user: %8
  // function_ref test
  %7 = function_ref @test : $@convention(thin) (Int) -> () // users: %12, %8
  %8 = apply %7(%6) : $@convention(thin) (Int) -> ()
  // function_ref bad
  %9 = function_ref @bad : $@convention(thin) (@in_guaranteed Int) -> () // user: %10
  %10 = apply %9(%0) : $@convention(thin) (@in_guaranteed Int) -> ()
  %11 = load %0 : $*Int // user: %12
  %12 = apply %7(%11) : $@convention(thin) (Int) -> ()
  %13 = tuple () // user: %14
  return %13 : $() // id: %14
} // end sil function 'bar'
----

Michael

Does that all make sense?

Thanks,
Johannes
<test-load-forwarding.sil><test-load-forwarding.sil-opt>

Thanks,
Johannes

[1]: https://bugs.swift.org/browse/SR-5403

Hi Michael,

[...]

Long story short, I think the RLE actually works for the test case I created. It's even clever enough to see through my invalid function bad() which modified the storage despite its claim that it doesn't. I might also be misunderstanding something.

When something is marked as in_guaranteed, it should be immutable. If the callee violates that, then the SIL is malformed. Perhaps, we can add some sort of verification check.

Right, yes I was aware that that'd be illegal but I added it as a way to check whether this optimisation is 'looking into' the called function.

That being said, I have a good feeling that there is some sort of analysis occuring here since you provided enough information to the optimizer. The optimization here is regardless of whether or not we can see the body of a function, we know that it is safe to optimize this just based off the @in_guaranteed. This implies using a declaration, not a definition of the bad function.

makes sense, didn't think about just only declaring it...

When I said write the SIL by hand, what I meant was writing the whole program by hand. In general, we prefer SIL programs that do not have extraneous stuff that is added by the compiler (for instance debug_value). Additionally, it is important for SIL files to not have dependencies on the stdlib unless absolutely necessary (i.e. your usage of Int). This prevents the stdlib maintainers from having to update these tests given chances to the stdlib. Below is a cleaned up version that shows the problem. Look at how small it is and how it tests /exactly/ what we are trying to test and via the use of declarations and the like we are able to exclude other optimizations:

That makes a lot of sense, thank you. I wasn't yet that familiar with SIL so I thought I start from a program generated by the compiler and then replace the guts with handwritten SIL. But your version is clearly a lot easier to understand and shows what precisely we want to see!

Today, I looked into why this is happening more precisely.

So we don't get the RLE because in this code

if (isComputeAvailValue(Kind) || isPerformingRLE(Kind)) {
   for (unsigned i = 0; i < Locs.size(); ++i) {
     if (isTrackingLocation(ForwardSetIn, Ctx.getLocationBit(Locs[i])))
       continue;
     updateForwardSetAndValForRead(Ctx, Ctx.getLocationBit(Locs[i]),
                                   Ctx.getValueBit(Vals[i]));
     // We can not perform the forwarding as we are at least missing
     // some pieces of the read location.
     CanForward = false;

(https://github.com/apple/swift/blob/86620aaa7ebd32d33f4cdf61add5c63a72d3f02a/lib/SILOptimizer/Transforms/RedundantLoadElimination.cpp#L917)

we're not taking the `continue` for the call to `buz()`. The reason why is that here

   if (!AA->mayWriteToMemory(I, R.getBase()))
     continue;
   // MayAlias.
   stopTrackingLocation(ForwardSetIn, i);
   stopTrackingValue(ForwardValIn, i);

(https://github.com/apple/swift/blob/86620aaa7ebd32d33f4cdf61add5c63a72d3f02a/lib/SILOptimizer/Transforms/RedundantLoadElimination.cpp#L972)

we're not taking the `continue`, ie. `AA->mayWriteToMemory(I, R.getBase())` is true. The reason for that is that the `SILFunction` for `buz` has

  EffectsKindAttr = Unspecified

which equates to `MayHaveSideEffects`, that's also what `-debug-only=sil-redundant-load-elim,sil-membehavior` outputs:

GET MEMORY BEHAVIOR FOR:
     %5 = apply %4(%0) : $@convention(thin) (@in_guaranteed Int) -> ()
     %0 = argument of bb0 : $*Int // users: %6, %5, %3
Found apply, returning MayHaveSideEffects

So where I'm stuck today is that I'm not sure how `EffectsKindAttr` is actually defined. Sure, `$@convention(thin) (@in_guaranteed Int) -> ()` doesn't actually write to the `@in_guaranteed Int` (as that'd be illegal) but it may have other side effects. So I'm not sure if we can just create the function differently if we find only "read-only" kind of parameters. That'd be I think in

auto *fn = SILMod.createFunction(SILLinkage::Private, Name.str(), Ty,
                                  nullptr, loc, IsNotBare,
                                  IsNotTransparent, IsNotSerialized);

(https://github.com/apple/swift/blob/ec6fc4d54db95f78ae72dab29734533f709ea2d7/lib/Parse/ParseSIL.cpp#L508 -> https://github.com/apple/swift/blob/157db57506b813837481b574a9d38e806bf954b6/lib/SIL/SILModule.cpp#L249)

which doesn't specify any EffectsAttrKind and therefore it defaults to `Unspecified`.

Just as a test, I did put a `[readonly]` in `sil @buz : $@convention(thin) (@in_guaranteed Int) -> ()` and as expected everything propagates through correctly and we get a successful RLE.

So yes, maybe you have some pointers on where to best educate the compiler that the `buz` function won't write to that bit of memory.

I have a few ideas of where to put it, but really the person to bring in here is Erik. He is the one who wrote the side-effect part of the optimizer. Keep in mind he is on vacation right now until next week. So I wouldn't expect a response until then.

Michael

···

On Jul 12, 2017, at 9:53 AM, Johannes Weiß <johannesweiss@apple.com> wrote:

Many thanks,
Johannes

----
sil_stage canonical

import Builtin

struct Int {
var _value : Builtin.Int64
}

sil @test : $@convention(thin) (Int) -> ()
sil @buz : $@convention(thin) (@in_guaranteed Int) -> ()
sil @bad : $@convention(thin) (@in_guaranteed Int) -> ()

sil @bar : $@convention(thin) (@in Int) -> () {
bb0(%0 : $*Int):
%value_raw = integer_literal $Builtin.Int64, 42
%value = struct $Int (%value_raw : $Builtin.Int64)
store %value to %0 : $*Int

%f_buz = function_ref @buz : $@convention(thin) (@in_guaranteed Int) -> ()
%r1 = apply %f_buz(%0) : $@convention(thin) (@in_guaranteed Int) -> ()

%value_again = load %0 : $*Int
%f_test = function_ref @test : $@convention(thin) (Int) -> ()
%r2 = apply %f_test(%value_again) : $@convention(thin) (Int) -> ()

%f_bad = function_ref @bad : $@convention(thin) (@in_guaranteed Int) -> ()
%r3 = apply %f_bad(%0) : $@convention(thin) (@in_guaranteed Int) -> ()

%value_again2 = load %0 : $*Int
%r4 = apply %f_test(%value_again2) : $@convention(thin) (Int) -> ()

%9999 = tuple()
return %9999 : $()
}
----

When I run this test file through rle, I get:

----
sil_stage canonical

import Builtin
import Swift
import SwiftShims

struct Int {
@sil_stored var _value: Builtin.Int64
init(_value: Builtin.Int64)
}

// test
sil @test : $@convention(thin) (Int) -> ()

// buz
sil @buz : $@convention(thin) (@in_guaranteed Int) -> ()

// bad
sil @bad : $@convention(thin) (@in_guaranteed Int) -> ()

// bar
sil @bar : $@convention(thin) (@in Int) -> () {
// %0 // users: %11, %10, %6, %5, %3
bb0(%0 : $*Int):
%1 = integer_literal $Builtin.Int64, 42 // user: %2
%2 = struct $Int (%1 : $Builtin.Int64) // user: %3
store %2 to %0 : $*Int // id: %3
// function_ref buz
%4 = function_ref @buz : $@convention(thin) (@in_guaranteed Int) -> () // user: %5
%5 = apply %4(%0) : $@convention(thin) (@in_guaranteed Int) -> ()
%6 = load %0 : $*Int // user: %8
// function_ref test
%7 = function_ref @test : $@convention(thin) (Int) -> () // users: %12, %8
%8 = apply %7(%6) : $@convention(thin) (Int) -> ()
// function_ref bad
%9 = function_ref @bad : $@convention(thin) (@in_guaranteed Int) -> () // user: %10
%10 = apply %9(%0) : $@convention(thin) (@in_guaranteed Int) -> ()
%11 = load %0 : $*Int // user: %12
%12 = apply %7(%11) : $@convention(thin) (Int) -> ()
%13 = tuple () // user: %14
return %13 : $() // id: %14
} // end sil function 'bar'
----

Michael

Does that all make sense?

Thanks,
Johannes
<test-load-forwarding.sil><test-load-forwarding.sil-opt>

Thanks,
Johannes

[1]: https://bugs.swift.org/browse/SR-5403

Thanks Michael!

Erik, I hope what I wrote makes some sense. Any questions or suggestions, please let me know.

···

On 14 Jul 2017, at 7:30 pm, Michael Gottesman <mgottesman@apple.com> wrote:

On Jul 12, 2017, at 9:53 AM, Johannes Weiß <johannesweiss@apple.com> wrote:

Hi Michael,

[...]

Long story short, I think the RLE actually works for the test case I created. It's even clever enough to see through my invalid function bad() which modified the storage despite its claim that it doesn't. I might also be misunderstanding something.

When something is marked as in_guaranteed, it should be immutable. If the callee violates that, then the SIL is malformed. Perhaps, we can add some sort of verification check.

Right, yes I was aware that that'd be illegal but I added it as a way to check whether this optimisation is 'looking into' the called function.

That being said, I have a good feeling that there is some sort of analysis occuring here since you provided enough information to the optimizer. The optimization here is regardless of whether or not we can see the body of a function, we know that it is safe to optimize this just based off the @in_guaranteed. This implies using a declaration, not a definition of the bad function.

makes sense, didn't think about just only declaring it...

When I said write the SIL by hand, what I meant was writing the whole program by hand. In general, we prefer SIL programs that do not have extraneous stuff that is added by the compiler (for instance debug_value). Additionally, it is important for SIL files to not have dependencies on the stdlib unless absolutely necessary (i.e. your usage of Int). This prevents the stdlib maintainers from having to update these tests given chances to the stdlib. Below is a cleaned up version that shows the problem. Look at how small it is and how it tests /exactly/ what we are trying to test and via the use of declarations and the like we are able to exclude other optimizations:

That makes a lot of sense, thank you. I wasn't yet that familiar with SIL so I thought I start from a program generated by the compiler and then replace the guts with handwritten SIL. But your version is clearly a lot easier to understand and shows what precisely we want to see!

Today, I looked into why this is happening more precisely.

So we don't get the RLE because in this code

if (isComputeAvailValue(Kind) || isPerformingRLE(Kind)) {
  for (unsigned i = 0; i < Locs.size(); ++i) {
    if (isTrackingLocation(ForwardSetIn, Ctx.getLocationBit(Locs[i])))
      continue;
    updateForwardSetAndValForRead(Ctx, Ctx.getLocationBit(Locs[i]),
                                  Ctx.getValueBit(Vals[i]));
    // We can not perform the forwarding as we are at least missing
    // some pieces of the read location.
    CanForward = false;

(https://github.com/apple/swift/blob/86620aaa7ebd32d33f4cdf61add5c63a72d3f02a/lib/SILOptimizer/Transforms/RedundantLoadElimination.cpp#L917)

we're not taking the `continue` for the call to `buz()`. The reason why is that here

  if (!AA->mayWriteToMemory(I, R.getBase()))
    continue;
  // MayAlias.
  stopTrackingLocation(ForwardSetIn, i);
  stopTrackingValue(ForwardValIn, i);

(https://github.com/apple/swift/blob/86620aaa7ebd32d33f4cdf61add5c63a72d3f02a/lib/SILOptimizer/Transforms/RedundantLoadElimination.cpp#L972)

we're not taking the `continue`, ie. `AA->mayWriteToMemory(I, R.getBase())` is true. The reason for that is that the `SILFunction` for `buz` has

EffectsKindAttr = Unspecified

which equates to `MayHaveSideEffects`, that's also what `-debug-only=sil-redundant-load-elim,sil-membehavior` outputs:

GET MEMORY BEHAVIOR FOR:
    %5 = apply %4(%0) : $@convention(thin) (@in_guaranteed Int) -> ()
    %0 = argument of bb0 : $*Int // users: %6, %5, %3
Found apply, returning MayHaveSideEffects

So where I'm stuck today is that I'm not sure how `EffectsKindAttr` is actually defined. Sure, `$@convention(thin) (@in_guaranteed Int) -> ()` doesn't actually write to the `@in_guaranteed Int` (as that'd be illegal) but it may have other side effects. So I'm not sure if we can just create the function differently if we find only "read-only" kind of parameters. That'd be I think in

auto *fn = SILMod.createFunction(SILLinkage::Private, Name.str(), Ty,
                                 nullptr, loc, IsNotBare,
                                 IsNotTransparent, IsNotSerialized);

(https://github.com/apple/swift/blob/ec6fc4d54db95f78ae72dab29734533f709ea2d7/lib/Parse/ParseSIL.cpp#L508 -> https://github.com/apple/swift/blob/157db57506b813837481b574a9d38e806bf954b6/lib/SIL/SILModule.cpp#L249)

which doesn't specify any EffectsAttrKind and therefore it defaults to `Unspecified`.

Just as a test, I did put a `[readonly]` in `sil @buz : $@convention(thin) (@in_guaranteed Int) -> ()` and as expected everything propagates through correctly and we get a successful RLE.

So yes, maybe you have some pointers on where to best educate the compiler that the `buz` function won't write to that bit of memory.

I have a few ideas of where to put it, but really the person to bring in here is Erik. He is the one who wrote the side-effect part of the optimizer. Keep in mind he is on vacation right now until next week. So I wouldn't expect a response until then.

Michael

Many thanks,
Johannes

----
sil_stage canonical

import Builtin

struct Int {
var _value : Builtin.Int64
}

sil @test : $@convention(thin) (Int) -> ()
sil @buz : $@convention(thin) (@in_guaranteed Int) -> ()
sil @bad : $@convention(thin) (@in_guaranteed Int) -> ()

sil @bar : $@convention(thin) (@in Int) -> () {
bb0(%0 : $*Int):
%value_raw = integer_literal $Builtin.Int64, 42
%value = struct $Int (%value_raw : $Builtin.Int64)
store %value to %0 : $*Int

%f_buz = function_ref @buz : $@convention(thin) (@in_guaranteed Int) -> ()
%r1 = apply %f_buz(%0) : $@convention(thin) (@in_guaranteed Int) -> ()

%value_again = load %0 : $*Int
%f_test = function_ref @test : $@convention(thin) (Int) -> ()
%r2 = apply %f_test(%value_again) : $@convention(thin) (Int) -> ()

%f_bad = function_ref @bad : $@convention(thin) (@in_guaranteed Int) -> ()
%r3 = apply %f_bad(%0) : $@convention(thin) (@in_guaranteed Int) -> ()

%value_again2 = load %0 : $*Int
%r4 = apply %f_test(%value_again2) : $@convention(thin) (Int) -> ()

%9999 = tuple()
return %9999 : $()
}
----

When I run this test file through rle, I get:

----
sil_stage canonical

import Builtin
import Swift
import SwiftShims

struct Int {
@sil_stored var _value: Builtin.Int64
init(_value: Builtin.Int64)
}

// test
sil @test : $@convention(thin) (Int) -> ()

// buz
sil @buz : $@convention(thin) (@in_guaranteed Int) -> ()

// bad
sil @bad : $@convention(thin) (@in_guaranteed Int) -> ()

// bar
sil @bar : $@convention(thin) (@in Int) -> () {
// %0 // users: %11, %10, %6, %5, %3
bb0(%0 : $*Int):
%1 = integer_literal $Builtin.Int64, 42 // user: %2
%2 = struct $Int (%1 : $Builtin.Int64) // user: %3
store %2 to %0 : $*Int // id: %3
// function_ref buz
%4 = function_ref @buz : $@convention(thin) (@in_guaranteed Int) -> () // user: %5
%5 = apply %4(%0) : $@convention(thin) (@in_guaranteed Int) -> ()
%6 = load %0 : $*Int // user: %8
// function_ref test
%7 = function_ref @test : $@convention(thin) (Int) -> () // users: %12, %8
%8 = apply %7(%6) : $@convention(thin) (Int) -> ()
// function_ref bad
%9 = function_ref @bad : $@convention(thin) (@in_guaranteed Int) -> () // user: %10
%10 = apply %9(%0) : $@convention(thin) (@in_guaranteed Int) -> ()
%11 = load %0 : $*Int // user: %12
%12 = apply %7(%11) : $@convention(thin) (Int) -> ()
%13 = tuple () // user: %14
return %13 : $() // id: %14
} // end sil function 'bar'
----

Michael

Does that all make sense?

Thanks,
Johannes
<test-load-forwarding.sil><test-load-forwarding.sil-opt>

Thanks,
Johannes

[1]: https://bugs.swift.org/browse/SR-5403

Hi Johannes,

great that you want to work on this!

Some ideas:
SideEffectAnalysis currently does not have a notion of “this argument is not modified by the callee” if the callee is unknown or does anything non-trivial.
Therefore I think it’s best to put the in_guarantee check directly into MemoryBehaviorVisitor::visitApplyInst():
If the parameter convention is in_guaranteed and the parameter is V, then the behavior can be MemBehavior::MayRead

Erik

···

On Jul 17, 2017, at 9:23 AM, Johannes Weiß <johannesweiss@apple.com> wrote:

Thanks Michael!

Erik, I hope what I wrote makes some sense. Any questions or suggestions, please let me know.

On 14 Jul 2017, at 7:30 pm, Michael Gottesman <mgottesman@apple.com> wrote:

On Jul 12, 2017, at 9:53 AM, Johannes Weiß <johannesweiss@apple.com> wrote:

Hi Michael,

[...]

Long story short, I think the RLE actually works for the test case I created. It's even clever enough to see through my invalid function bad() which modified the storage despite its claim that it doesn't. I might also be misunderstanding something.

When something is marked as in_guaranteed, it should be immutable. If the callee violates that, then the SIL is malformed. Perhaps, we can add some sort of verification check.

Right, yes I was aware that that'd be illegal but I added it as a way to check whether this optimisation is 'looking into' the called function.

That being said, I have a good feeling that there is some sort of analysis occuring here since you provided enough information to the optimizer. The optimization here is regardless of whether or not we can see the body of a function, we know that it is safe to optimize this just based off the @in_guaranteed. This implies using a declaration, not a definition of the bad function.

makes sense, didn't think about just only declaring it...

When I said write the SIL by hand, what I meant was writing the whole program by hand. In general, we prefer SIL programs that do not have extraneous stuff that is added by the compiler (for instance debug_value). Additionally, it is important for SIL files to not have dependencies on the stdlib unless absolutely necessary (i.e. your usage of Int). This prevents the stdlib maintainers from having to update these tests given chances to the stdlib. Below is a cleaned up version that shows the problem. Look at how small it is and how it tests /exactly/ what we are trying to test and via the use of declarations and the like we are able to exclude other optimizations:

That makes a lot of sense, thank you. I wasn't yet that familiar with SIL so I thought I start from a program generated by the compiler and then replace the guts with handwritten SIL. But your version is clearly a lot easier to understand and shows what precisely we want to see!

Today, I looked into why this is happening more precisely.

So we don't get the RLE because in this code

if (isComputeAvailValue(Kind) || isPerformingRLE(Kind)) {
for (unsigned i = 0; i < Locs.size(); ++i) {
   if (isTrackingLocation(ForwardSetIn, Ctx.getLocationBit(Locs[i])))
     continue;
   updateForwardSetAndValForRead(Ctx, Ctx.getLocationBit(Locs[i]),
                                 Ctx.getValueBit(Vals[i]));
   // We can not perform the forwarding as we are at least missing
   // some pieces of the read location.
   CanForward = false;

(https://github.com/apple/swift/blob/86620aaa7ebd32d33f4cdf61add5c63a72d3f02a/lib/SILOptimizer/Transforms/RedundantLoadElimination.cpp#L917)

we're not taking the `continue` for the call to `buz()`. The reason why is that here

if (!AA->mayWriteToMemory(I, R.getBase()))
   continue;
// MayAlias.
stopTrackingLocation(ForwardSetIn, i);
stopTrackingValue(ForwardValIn, i);

(https://github.com/apple/swift/blob/86620aaa7ebd32d33f4cdf61add5c63a72d3f02a/lib/SILOptimizer/Transforms/RedundantLoadElimination.cpp#L972)

we're not taking the `continue`, ie. `AA->mayWriteToMemory(I, R.getBase())` is true. The reason for that is that the `SILFunction` for `buz` has

EffectsKindAttr = Unspecified

which equates to `MayHaveSideEffects`, that's also what `-debug-only=sil-redundant-load-elim,sil-membehavior` outputs:

GET MEMORY BEHAVIOR FOR:
   %5 = apply %4(%0) : $@convention(thin) (@in_guaranteed Int) -> ()
   %0 = argument of bb0 : $*Int // users: %6, %5, %3
Found apply, returning MayHaveSideEffects

So where I'm stuck today is that I'm not sure how `EffectsKindAttr` is actually defined. Sure, `$@convention(thin) (@in_guaranteed Int) -> ()` doesn't actually write to the `@in_guaranteed Int` (as that'd be illegal) but it may have other side effects. So I'm not sure if we can just create the function differently if we find only "read-only" kind of parameters. That'd be I think in

auto *fn = SILMod.createFunction(SILLinkage::Private, Name.str(), Ty,
                                nullptr, loc, IsNotBare,
                                IsNotTransparent, IsNotSerialized);

(https://github.com/apple/swift/blob/ec6fc4d54db95f78ae72dab29734533f709ea2d7/lib/Parse/ParseSIL.cpp#L508 -> https://github.com/apple/swift/blob/157db57506b813837481b574a9d38e806bf954b6/lib/SIL/SILModule.cpp#L249)

which doesn't specify any EffectsAttrKind and therefore it defaults to `Unspecified`.

Just as a test, I did put a `[readonly]` in `sil @buz : $@convention(thin) (@in_guaranteed Int) -> ()` and as expected everything propagates through correctly and we get a successful RLE.

So yes, maybe you have some pointers on where to best educate the compiler that the `buz` function won't write to that bit of memory.

I have a few ideas of where to put it, but really the person to bring in here is Erik. He is the one who wrote the side-effect part of the optimizer. Keep in mind he is on vacation right now until next week. So I wouldn't expect a response until then.

Michael

Many thanks,
Johannes

----
sil_stage canonical

import Builtin

struct Int {
var _value : Builtin.Int64
}

sil @test : $@convention(thin) (Int) -> ()
sil @buz : $@convention(thin) (@in_guaranteed Int) -> ()
sil @bad : $@convention(thin) (@in_guaranteed Int) -> ()

sil @bar : $@convention(thin) (@in Int) -> () {
bb0(%0 : $*Int):
%value_raw = integer_literal $Builtin.Int64, 42
%value = struct $Int (%value_raw : $Builtin.Int64)
store %value to %0 : $*Int

%f_buz = function_ref @buz : $@convention(thin) (@in_guaranteed Int) -> ()
%r1 = apply %f_buz(%0) : $@convention(thin) (@in_guaranteed Int) -> ()

%value_again = load %0 : $*Int
%f_test = function_ref @test : $@convention(thin) (Int) -> ()
%r2 = apply %f_test(%value_again) : $@convention(thin) (Int) -> ()

%f_bad = function_ref @bad : $@convention(thin) (@in_guaranteed Int) -> ()
%r3 = apply %f_bad(%0) : $@convention(thin) (@in_guaranteed Int) -> ()

%value_again2 = load %0 : $*Int
%r4 = apply %f_test(%value_again2) : $@convention(thin) (Int) -> ()

%9999 = tuple()
return %9999 : $()
}
----

When I run this test file through rle, I get:

----
sil_stage canonical

import Builtin
import Swift
import SwiftShims

struct Int {
@sil_stored var _value: Builtin.Int64
init(_value: Builtin.Int64)
}

// test
sil @test : $@convention(thin) (Int) -> ()

// buz
sil @buz : $@convention(thin) (@in_guaranteed Int) -> ()

// bad
sil @bad : $@convention(thin) (@in_guaranteed Int) -> ()

// bar
sil @bar : $@convention(thin) (@in Int) -> () {
// %0 // users: %11, %10, %6, %5, %3
bb0(%0 : $*Int):
%1 = integer_literal $Builtin.Int64, 42 // user: %2
%2 = struct $Int (%1 : $Builtin.Int64) // user: %3
store %2 to %0 : $*Int // id: %3
// function_ref buz
%4 = function_ref @buz : $@convention(thin) (@in_guaranteed Int) -> () // user: %5
%5 = apply %4(%0) : $@convention(thin) (@in_guaranteed Int) -> ()
%6 = load %0 : $*Int // user: %8
// function_ref test
%7 = function_ref @test : $@convention(thin) (Int) -> () // users: %12, %8
%8 = apply %7(%6) : $@convention(thin) (Int) -> ()
// function_ref bad
%9 = function_ref @bad : $@convention(thin) (@in_guaranteed Int) -> () // user: %10
%10 = apply %9(%0) : $@convention(thin) (@in_guaranteed Int) -> ()
%11 = load %0 : $*Int // user: %12
%12 = apply %7(%11) : $@convention(thin) (Int) -> ()
%13 = tuple () // user: %14
return %13 : $() // id: %14
} // end sil function 'bar'
----

Michael

Does that all make sense?

Thanks,
Johannes
<test-load-forwarding.sil><test-load-forwarding.sil-opt>

Thanks,
Johannes

[1]: https://bugs.swift.org/browse/SR-5403

Hi Erik,

Hi Johannes,

great that you want to work on this!

Thanks for your help, without Michael's and your help I wouldn't have been able to do anything here really!

Some ideas:
SideEffectAnalysis currently does not have a notion of “this argument is not modified by the callee” if the callee is unknown or does anything non-trivial.
Therefore I think it’s best to put the in_guarantee check directly into MemoryBehaviorVisitor::visitApplyInst():
If the parameter convention is in_guaranteed and the parameter is V, then the behavior can be MemBehavior::MayRead

Thanks, that actually makes a lot of sense. Here's my diff right now

diff --git a/lib/SILOptimizer/Analysis/MemoryBehavior.cpp b/lib/SILOptimizer/Analysis/MemoryBehavior.cpp
index b1fe7fa665..c44cc64f94 100644
--- a/lib/SILOptimizer/Analysis/MemoryBehavior.cpp
+++ b/lib/SILOptimizer/Analysis/MemoryBehavior.cpp
@@ -245,6 +245,23 @@ MemBehavior MemoryBehaviorVisitor::visitApplyInst(ApplyInst *AI) {
       (InspectionMode == RetainObserveKind::ObserveRetains &&
        ApplyEffects.mayAllocObjects())) {
     Behavior = MemBehavior::MayHaveSideEffects;

···

On 17 Jul 2017, at 10:26 pm, Erik Eckstein <eeckstein@apple.com> wrote:

+
+ unsigned Idx = 0;
+ bool AllReadOnly = false;
+ for (Operand &operand : AI->getArgumentOperands()) {
+ if (operand.get() == V && AI->getOrigCalleeType()->getParameters()[Idx].isIndirectInGuaranteed()) {
+ AllReadOnly = true;
+ } else {
+ AllReadOnly = false;
+ break;
+ }
+
+ Idx++;
+ }
+
+ if (AllReadOnly) {
+ Behavior = MemBehavior::MayRead;
+ }
   } else {
     auto &GlobalEffects = ApplyEffects.getGlobalEffects();
     Behavior = GlobalEffects.getMemBehavior(InspectionMode);

which indeed turns

--- SNIP ---
sil @bar : $@convention(thin) (@in Int) -> () {
bb0(%0 : $*Int):
  %value_raw = integer_literal $Builtin.Int64, 42
  %value = struct $Int (%value_raw : $Builtin.Int64)
  store %value to %0 : $*Int

  %f_buz = function_ref @buz : $@convention(thin) (@in_guaranteed Int) -> ()
  %r1 = apply %f_buz(%0) : $@convention(thin) (@in_guaranteed Int) -> ()

  %value_again = load %0 : $*Int
  %f_test = function_ref @test : $@convention(thin) (Int) -> ()
  %r2 = apply %f_test(%value_again) : $@convention(thin) (Int) -> ()

  /*
  %f_bad = function_ref @bad : $@convention(thin) (@in_guaranteed Int) -> ()
  %r3 = apply %f_bad(%0) : $@convention(thin) (@in_guaranteed Int) -> ()

  %value_again2 = load %0 : $*Int
  %r4 = apply %f_test(%value_again2) : $@convention(thin) (Int) -> ()
  */

  %9999 = tuple()
  return %9999 : $()
}
--- SNAP ---

into

--- SNIP ---
bb0(%0 : $*Int):
  %1 = integer_literal $Builtin.Int64, 42 // user: %2
  %2 = struct $Int (%1 : $Builtin.Int64) // users: %7, %3
  store %2 to %0 : $*Int // id: %3
  // function_ref buz
  %4 = function_ref @buz : $@convention(thin) (@in_guaranteed Int) -> () // user: %5
  %5 = apply %4(%0) : $@convention(thin) (@in_guaranteed Int) -> ()
  // function_ref test
  %6 = function_ref @test : $@convention(thin) (Int) -> () // user: %7
  %7 = apply %6(%2) : $@convention(thin) (Int) -> ()
  %8 = tuple () // user: %9
  return %8 : $() // id: %9
} // end sil function 'bar'
--- SNAP ---

so the load has successfully been eliminated. Also taking my initial repro [1], the retain, the load, and the release are now gone :smiley:.

Is that roughly what you were thinking of?

Many thanks,
  Johannes

[1]: https://bugs.swift.org/secure/attachment/12378/test.swift

Erik

On Jul 17, 2017, at 9:23 AM, Johannes Weiß <johannesweiss@apple.com> wrote:

Thanks Michael!

Erik, I hope what I wrote makes some sense. Any questions or suggestions, please let me know.

On 14 Jul 2017, at 7:30 pm, Michael Gottesman <mgottesman@apple.com> wrote:

On Jul 12, 2017, at 9:53 AM, Johannes Weiß <johannesweiss@apple.com> wrote:

Hi Michael,

[...]

Long story short, I think the RLE actually works for the test case I created. It's even clever enough to see through my invalid function bad() which modified the storage despite its claim that it doesn't. I might also be misunderstanding something.

When something is marked as in_guaranteed, it should be immutable. If the callee violates that, then the SIL is malformed. Perhaps, we can add some sort of verification check.

Right, yes I was aware that that'd be illegal but I added it as a way to check whether this optimisation is 'looking into' the called function.

That being said, I have a good feeling that there is some sort of analysis occuring here since you provided enough information to the optimizer. The optimization here is regardless of whether or not we can see the body of a function, we know that it is safe to optimize this just based off the @in_guaranteed. This implies using a declaration, not a definition of the bad function.

makes sense, didn't think about just only declaring it...

When I said write the SIL by hand, what I meant was writing the whole program by hand. In general, we prefer SIL programs that do not have extraneous stuff that is added by the compiler (for instance debug_value). Additionally, it is important for SIL files to not have dependencies on the stdlib unless absolutely necessary (i.e. your usage of Int). This prevents the stdlib maintainers from having to update these tests given chances to the stdlib. Below is a cleaned up version that shows the problem. Look at how small it is and how it tests /exactly/ what we are trying to test and via the use of declarations and the like we are able to exclude other optimizations:

That makes a lot of sense, thank you. I wasn't yet that familiar with SIL so I thought I start from a program generated by the compiler and then replace the guts with handwritten SIL. But your version is clearly a lot easier to understand and shows what precisely we want to see!

Today, I looked into why this is happening more precisely.

So we don't get the RLE because in this code

if (isComputeAvailValue(Kind) || isPerformingRLE(Kind)) {
for (unsigned i = 0; i < Locs.size(); ++i) {
   if (isTrackingLocation(ForwardSetIn, Ctx.getLocationBit(Locs[i])))
     continue;
   updateForwardSetAndValForRead(Ctx, Ctx.getLocationBit(Locs[i]),
                                 Ctx.getValueBit(Vals[i]));
   // We can not perform the forwarding as we are at least missing
   // some pieces of the read location.
   CanForward = false;

(https://github.com/apple/swift/blob/86620aaa7ebd32d33f4cdf61add5c63a72d3f02a/lib/SILOptimizer/Transforms/RedundantLoadElimination.cpp#L917)

we're not taking the `continue` for the call to `buz()`. The reason why is that here

if (!AA->mayWriteToMemory(I, R.getBase()))
   continue;
// MayAlias.
stopTrackingLocation(ForwardSetIn, i);
stopTrackingValue(ForwardValIn, i);

(https://github.com/apple/swift/blob/86620aaa7ebd32d33f4cdf61add5c63a72d3f02a/lib/SILOptimizer/Transforms/RedundantLoadElimination.cpp#L972)

we're not taking the `continue`, ie. `AA->mayWriteToMemory(I, R.getBase())` is true. The reason for that is that the `SILFunction` for `buz` has

EffectsKindAttr = Unspecified

which equates to `MayHaveSideEffects`, that's also what `-debug-only=sil-redundant-load-elim,sil-membehavior` outputs:

GET MEMORY BEHAVIOR FOR:
   %5 = apply %4(%0) : $@convention(thin) (@in_guaranteed Int) -> ()
   %0 = argument of bb0 : $*Int // users: %6, %5, %3
Found apply, returning MayHaveSideEffects

So where I'm stuck today is that I'm not sure how `EffectsKindAttr` is actually defined. Sure, `$@convention(thin) (@in_guaranteed Int) -> ()` doesn't actually write to the `@in_guaranteed Int` (as that'd be illegal) but it may have other side effects. So I'm not sure if we can just create the function differently if we find only "read-only" kind of parameters. That'd be I think in

auto *fn = SILMod.createFunction(SILLinkage::Private, Name.str(), Ty,
                                nullptr, loc, IsNotBare,
                                IsNotTransparent, IsNotSerialized);

(https://github.com/apple/swift/blob/ec6fc4d54db95f78ae72dab29734533f709ea2d7/lib/Parse/ParseSIL.cpp#L508 -> https://github.com/apple/swift/blob/157db57506b813837481b574a9d38e806bf954b6/lib/SIL/SILModule.cpp#L249)

which doesn't specify any EffectsAttrKind and therefore it defaults to `Unspecified`.

Just as a test, I did put a `[readonly]` in `sil @buz : $@convention(thin) (@in_guaranteed Int) -> ()` and as expected everything propagates through correctly and we get a successful RLE.

So yes, maybe you have some pointers on where to best educate the compiler that the `buz` function won't write to that bit of memory.

I have a few ideas of where to put it, but really the person to bring in here is Erik. He is the one who wrote the side-effect part of the optimizer. Keep in mind he is on vacation right now until next week. So I wouldn't expect a response until then.

Michael

Many thanks,
Johannes

----
sil_stage canonical

import Builtin

struct Int {
var _value : Builtin.Int64
}

sil @test : $@convention(thin) (Int) -> ()
sil @buz : $@convention(thin) (@in_guaranteed Int) -> ()
sil @bad : $@convention(thin) (@in_guaranteed Int) -> ()

sil @bar : $@convention(thin) (@in Int) -> () {
bb0(%0 : $*Int):
%value_raw = integer_literal $Builtin.Int64, 42
%value = struct $Int (%value_raw : $Builtin.Int64)
store %value to %0 : $*Int

%f_buz = function_ref @buz : $@convention(thin) (@in_guaranteed Int) -> ()
%r1 = apply %f_buz(%0) : $@convention(thin) (@in_guaranteed Int) -> ()

%value_again = load %0 : $*Int
%f_test = function_ref @test : $@convention(thin) (Int) -> ()
%r2 = apply %f_test(%value_again) : $@convention(thin) (Int) -> ()

%f_bad = function_ref @bad : $@convention(thin) (@in_guaranteed Int) -> ()
%r3 = apply %f_bad(%0) : $@convention(thin) (@in_guaranteed Int) -> ()

%value_again2 = load %0 : $*Int
%r4 = apply %f_test(%value_again2) : $@convention(thin) (Int) -> ()

%9999 = tuple()
return %9999 : $()
}
----

When I run this test file through rle, I get:

----
sil_stage canonical

import Builtin
import Swift
import SwiftShims

struct Int {
@sil_stored var _value: Builtin.Int64
init(_value: Builtin.Int64)
}

// test
sil @test : $@convention(thin) (Int) -> ()

// buz
sil @buz : $@convention(thin) (@in_guaranteed Int) -> ()

// bad
sil @bad : $@convention(thin) (@in_guaranteed Int) -> ()

// bar
sil @bar : $@convention(thin) (@in Int) -> () {
// %0 // users: %11, %10, %6, %5, %3
bb0(%0 : $*Int):
%1 = integer_literal $Builtin.Int64, 42 // user: %2
%2 = struct $Int (%1 : $Builtin.Int64) // user: %3
store %2 to %0 : $*Int // id: %3
// function_ref buz
%4 = function_ref @buz : $@convention(thin) (@in_guaranteed Int) -> () // user: %5
%5 = apply %4(%0) : $@convention(thin) (@in_guaranteed Int) -> ()
%6 = load %0 : $*Int // user: %8
// function_ref test
%7 = function_ref @test : $@convention(thin) (Int) -> () // users: %12, %8
%8 = apply %7(%6) : $@convention(thin) (Int) -> ()
// function_ref bad
%9 = function_ref @bad : $@convention(thin) (@in_guaranteed Int) -> () // user: %10
%10 = apply %9(%0) : $@convention(thin) (@in_guaranteed Int) -> ()
%11 = load %0 : $*Int // user: %12
%12 = apply %7(%11) : $@convention(thin) (Int) -> ()
%13 = tuple () // user: %14
return %13 : $() // id: %14
} // end sil function 'bar'
----

Michael

Does that all make sense?

Thanks,
Johannes
<test-load-forwarding.sil><test-load-forwarding.sil-opt>

Thanks,
Johannes

[1]: https://bugs.swift.org/browse/SR-5403

Hi Erik,

Hi Johannes,

great that you want to work on this!

Thanks for your help, without Michael's and your help I wouldn't have been able to do anything here really!

Some ideas:
SideEffectAnalysis currently does not have a notion of “this argument is not modified by the callee” if the callee is unknown or does anything non-trivial.
Therefore I think it’s best to put the in_guarantee check directly into MemoryBehaviorVisitor::visitApplyInst():
If the parameter convention is in_guaranteed and the parameter is V, then the behavior can be MemBehavior::MayRead

Thanks, that actually makes a lot of sense. Here's my diff right now

diff --git a/lib/SILOptimizer/Analysis/MemoryBehavior.cpp b/lib/SILOptimizer/Analysis/MemoryBehavior.cpp
index b1fe7fa665..c44cc64f94 100644
--- a/lib/SILOptimizer/Analysis/MemoryBehavior.cpp
+++ b/lib/SILOptimizer/Analysis/MemoryBehavior.cpp
@@ -245,6 +245,23 @@ MemBehavior MemoryBehaviorVisitor::visitApplyInst(ApplyInst *AI) {
      (InspectionMode == RetainObserveKind::ObserveRetains &&
       ApplyEffects.mayAllocObjects())) {
    Behavior = MemBehavior::MayHaveSideEffects;
+
+ unsigned Idx = 0;
+ bool AllReadOnly = false;
+ for (Operand &operand : AI->getArgumentOperands()) {
+ if (operand.get() == V && AI->getOrigCalleeType()->getParameters()[Idx].isIndirectInGuaranteed()) {
+ AllReadOnly = true;
+ } else {
+ AllReadOnly = false;
+ break;
+ }
+
+ Idx++;
+ }
+
+ if (AllReadOnly) {
+ Behavior = MemBehavior::MayRead;
+ }

Suggestion:

if (all_of(enumerate(AI->getArgumentOperands()),
              [&](std::pair<unsigned, SILValue> pair) -> bool {
                 return pair.second.get() == V && AI->getOrigCalleeType()->getParameters()[Idx].isIndirectInGuaranteed()
              })) {
   Behavior = MemBehavior::MayRead;
}

I may have gotten the order of the pair templates wrong. But something like this is a little cleaner.

Michael

···

On Jul 18, 2017, at 8:39 AM, Johannes Weiß <johannesweiss@apple.com> wrote:

On 17 Jul 2017, at 10:26 pm, Erik Eckstein <eeckstein@apple.com> wrote:

  } else {
    auto &GlobalEffects = ApplyEffects.getGlobalEffects();
    Behavior = GlobalEffects.getMemBehavior(InspectionMode);

which indeed turns

--- SNIP ---
sil @bar : $@convention(thin) (@in Int) -> () {
bb0(%0 : $*Int):
%value_raw = integer_literal $Builtin.Int64, 42
%value = struct $Int (%value_raw : $Builtin.Int64)
store %value to %0 : $*Int

%f_buz = function_ref @buz : $@convention(thin) (@in_guaranteed Int) -> ()
%r1 = apply %f_buz(%0) : $@convention(thin) (@in_guaranteed Int) -> ()

%value_again = load %0 : $*Int
%f_test = function_ref @test : $@convention(thin) (Int) -> ()
%r2 = apply %f_test(%value_again) : $@convention(thin) (Int) -> ()

/*
%f_bad = function_ref @bad : $@convention(thin) (@in_guaranteed Int) -> ()
%r3 = apply %f_bad(%0) : $@convention(thin) (@in_guaranteed Int) -> ()

%value_again2 = load %0 : $*Int
%r4 = apply %f_test(%value_again2) : $@convention(thin) (Int) -> ()
*/

%9999 = tuple()
return %9999 : $()
}
--- SNAP ---

into

--- SNIP ---
bb0(%0 : $*Int):
%1 = integer_literal $Builtin.Int64, 42 // user: %2
%2 = struct $Int (%1 : $Builtin.Int64) // users: %7, %3
store %2 to %0 : $*Int // id: %3
// function_ref buz
%4 = function_ref @buz : $@convention(thin) (@in_guaranteed Int) -> () // user: %5
%5 = apply %4(%0) : $@convention(thin) (@in_guaranteed Int) -> ()
// function_ref test
%6 = function_ref @test : $@convention(thin) (Int) -> () // user: %7
%7 = apply %6(%2) : $@convention(thin) (Int) -> ()
%8 = tuple () // user: %9
return %8 : $() // id: %9
} // end sil function 'bar'
--- SNAP ---

so the load has successfully been eliminated. Also taking my initial repro [1], the retain, the load, and the release are now gone :smiley:.

Is that roughly what you were thinking of?

Many thanks,
Johannes

[1]: https://bugs.swift.org/secure/attachment/12378/test.swift

Erik

On Jul 17, 2017, at 9:23 AM, Johannes Weiß <johannesweiss@apple.com> wrote:

Thanks Michael!

Erik, I hope what I wrote makes some sense. Any questions or suggestions, please let me know.

On 14 Jul 2017, at 7:30 pm, Michael Gottesman <mgottesman@apple.com> wrote:

On Jul 12, 2017, at 9:53 AM, Johannes Weiß <johannesweiss@apple.com> wrote:

Hi Michael,

[...]

Long story short, I think the RLE actually works for the test case I created. It's even clever enough to see through my invalid function bad() which modified the storage despite its claim that it doesn't. I might also be misunderstanding something.

When something is marked as in_guaranteed, it should be immutable. If the callee violates that, then the SIL is malformed. Perhaps, we can add some sort of verification check.

Right, yes I was aware that that'd be illegal but I added it as a way to check whether this optimisation is 'looking into' the called function.

That being said, I have a good feeling that there is some sort of analysis occuring here since you provided enough information to the optimizer. The optimization here is regardless of whether or not we can see the body of a function, we know that it is safe to optimize this just based off the @in_guaranteed. This implies using a declaration, not a definition of the bad function.

makes sense, didn't think about just only declaring it...

When I said write the SIL by hand, what I meant was writing the whole program by hand. In general, we prefer SIL programs that do not have extraneous stuff that is added by the compiler (for instance debug_value). Additionally, it is important for SIL files to not have dependencies on the stdlib unless absolutely necessary (i.e. your usage of Int). This prevents the stdlib maintainers from having to update these tests given chances to the stdlib. Below is a cleaned up version that shows the problem. Look at how small it is and how it tests /exactly/ what we are trying to test and via the use of declarations and the like we are able to exclude other optimizations:

That makes a lot of sense, thank you. I wasn't yet that familiar with SIL so I thought I start from a program generated by the compiler and then replace the guts with handwritten SIL. But your version is clearly a lot easier to understand and shows what precisely we want to see!

Today, I looked into why this is happening more precisely.

So we don't get the RLE because in this code

if (isComputeAvailValue(Kind) || isPerformingRLE(Kind)) {
for (unsigned i = 0; i < Locs.size(); ++i) {
  if (isTrackingLocation(ForwardSetIn, Ctx.getLocationBit(Locs[i])))
    continue;
  updateForwardSetAndValForRead(Ctx, Ctx.getLocationBit(Locs[i]),
                                Ctx.getValueBit(Vals[i]));
  // We can not perform the forwarding as we are at least missing
  // some pieces of the read location.
  CanForward = false;

(https://github.com/apple/swift/blob/86620aaa7ebd32d33f4cdf61add5c63a72d3f02a/lib/SILOptimizer/Transforms/RedundantLoadElimination.cpp#L917)

we're not taking the `continue` for the call to `buz()`. The reason why is that here

if (!AA->mayWriteToMemory(I, R.getBase()))
  continue;
// MayAlias.
stopTrackingLocation(ForwardSetIn, i);
stopTrackingValue(ForwardValIn, i);

(https://github.com/apple/swift/blob/86620aaa7ebd32d33f4cdf61add5c63a72d3f02a/lib/SILOptimizer/Transforms/RedundantLoadElimination.cpp#L972)

we're not taking the `continue`, ie. `AA->mayWriteToMemory(I, R.getBase())` is true. The reason for that is that the `SILFunction` for `buz` has

EffectsKindAttr = Unspecified

which equates to `MayHaveSideEffects`, that's also what `-debug-only=sil-redundant-load-elim,sil-membehavior` outputs:

GET MEMORY BEHAVIOR FOR:
  %5 = apply %4(%0) : $@convention(thin) (@in_guaranteed Int) -> ()
  %0 = argument of bb0 : $*Int // users: %6, %5, %3
Found apply, returning MayHaveSideEffects

So where I'm stuck today is that I'm not sure how `EffectsKindAttr` is actually defined. Sure, `$@convention(thin) (@in_guaranteed Int) -> ()` doesn't actually write to the `@in_guaranteed Int` (as that'd be illegal) but it may have other side effects. So I'm not sure if we can just create the function differently if we find only "read-only" kind of parameters. That'd be I think in

auto *fn = SILMod.createFunction(SILLinkage::Private, Name.str(), Ty,
                               nullptr, loc, IsNotBare,
                               IsNotTransparent, IsNotSerialized);

(https://github.com/apple/swift/blob/ec6fc4d54db95f78ae72dab29734533f709ea2d7/lib/Parse/ParseSIL.cpp#L508 -> https://github.com/apple/swift/blob/157db57506b813837481b574a9d38e806bf954b6/lib/SIL/SILModule.cpp#L249)

which doesn't specify any EffectsAttrKind and therefore it defaults to `Unspecified`.

Just as a test, I did put a `[readonly]` in `sil @buz : $@convention(thin) (@in_guaranteed Int) -> ()` and as expected everything propagates through correctly and we get a successful RLE.

So yes, maybe you have some pointers on where to best educate the compiler that the `buz` function won't write to that bit of memory.

I have a few ideas of where to put it, but really the person to bring in here is Erik. He is the one who wrote the side-effect part of the optimizer. Keep in mind he is on vacation right now until next week. So I wouldn't expect a response until then.

Michael

Many thanks,
Johannes

----
sil_stage canonical

import Builtin

struct Int {
var _value : Builtin.Int64
}

sil @test : $@convention(thin) (Int) -> ()
sil @buz : $@convention(thin) (@in_guaranteed Int) -> ()
sil @bad : $@convention(thin) (@in_guaranteed Int) -> ()

sil @bar : $@convention(thin) (@in Int) -> () {
bb0(%0 : $*Int):
%value_raw = integer_literal $Builtin.Int64, 42
%value = struct $Int (%value_raw : $Builtin.Int64)
store %value to %0 : $*Int

%f_buz = function_ref @buz : $@convention(thin) (@in_guaranteed Int) -> ()
%r1 = apply %f_buz(%0) : $@convention(thin) (@in_guaranteed Int) -> ()

%value_again = load %0 : $*Int
%f_test = function_ref @test : $@convention(thin) (Int) -> ()
%r2 = apply %f_test(%value_again) : $@convention(thin) (Int) -> ()

%f_bad = function_ref @bad : $@convention(thin) (@in_guaranteed Int) -> ()
%r3 = apply %f_bad(%0) : $@convention(thin) (@in_guaranteed Int) -> ()

%value_again2 = load %0 : $*Int
%r4 = apply %f_test(%value_again2) : $@convention(thin) (Int) -> ()

%9999 = tuple()
return %9999 : $()
}
----

When I run this test file through rle, I get:

----
sil_stage canonical

import Builtin
import Swift
import SwiftShims

struct Int {
@sil_stored var _value: Builtin.Int64
init(_value: Builtin.Int64)
}

// test
sil @test : $@convention(thin) (Int) -> ()

// buz
sil @buz : $@convention(thin) (@in_guaranteed Int) -> ()

// bad
sil @bad : $@convention(thin) (@in_guaranteed Int) -> ()

// bar
sil @bar : $@convention(thin) (@in Int) -> () {
// %0 // users: %11, %10, %6, %5, %3
bb0(%0 : $*Int):
%1 = integer_literal $Builtin.Int64, 42 // user: %2
%2 = struct $Int (%1 : $Builtin.Int64) // user: %3
store %2 to %0 : $*Int // id: %3
// function_ref buz
%4 = function_ref @buz : $@convention(thin) (@in_guaranteed Int) -> () // user: %5
%5 = apply %4(%0) : $@convention(thin) (@in_guaranteed Int) -> ()
%6 = load %0 : $*Int // user: %8
// function_ref test
%7 = function_ref @test : $@convention(thin) (Int) -> () // users: %12, %8
%8 = apply %7(%6) : $@convention(thin) (Int) -> ()
// function_ref bad
%9 = function_ref @bad : $@convention(thin) (@in_guaranteed Int) -> () // user: %10
%10 = apply %9(%0) : $@convention(thin) (@in_guaranteed Int) -> ()
%11 = load %0 : $*Int // user: %12
%12 = apply %7(%11) : $@convention(thin) (Int) -> ()
%13 = tuple () // user: %14
return %13 : $() // id: %14
} // end sil function 'bar'
----

Michael

Does that all make sense?

Thanks,
Johannes
<test-load-forwarding.sil><test-load-forwarding.sil-opt>

Thanks,
Johannes

[1]: https://bugs.swift.org/browse/SR-5403

Hi Erik,

Hi Johannes,

great that you want to work on this!

Thanks for your help, without Michael's and your help I wouldn't have been able to do anything here really!

Some ideas:
SideEffectAnalysis currently does not have a notion of “this argument is not modified by the callee” if the callee is unknown or does anything non-trivial.
Therefore I think it’s best to put the in_guarantee check directly into MemoryBehaviorVisitor::visitApplyInst():
If the parameter convention is in_guaranteed and the parameter is V, then the behavior can be MemBehavior::MayRead

Thanks, that actually makes a lot of sense. Here's my diff right now

diff --git a/lib/SILOptimizer/Analysis/MemoryBehavior.cpp b/lib/SILOptimizer/Analysis/MemoryBehavior.cpp
index b1fe7fa665..c44cc64f94 100644
--- a/lib/SILOptimizer/Analysis/MemoryBehavior.cpp
+++ b/lib/SILOptimizer/Analysis/MemoryBehavior.cpp
@@ -245,6 +245,23 @@ MemBehavior MemoryBehaviorVisitor::visitApplyInst(ApplyInst *AI) {
     (InspectionMode == RetainObserveKind::ObserveRetains &&
      ApplyEffects.mayAllocObjects())) {
   Behavior = MemBehavior::MayHaveSideEffects;
+
+ unsigned Idx = 0;
+ bool AllReadOnly = false;
+ for (Operand &operand : AI->getArgumentOperands()) {
+ if (operand.get() == V && AI->getOrigCalleeType()->getParameters()[Idx].isIndirectInGuaranteed()) {
+ AllReadOnly = true;
+ } else {
+ AllReadOnly = false;
+ break;
+ }
+
+ Idx++;
+ }
+
+ if (AllReadOnly) {
+ Behavior = MemBehavior::MayRead;
+ }

Suggestion:

if (all_of(enumerate(AI->getArgumentOperands()),
             [&](std::pair<unsigned, SILValue> pair) -> bool {
                return pair.second.get() == V && AI->getOrigCalleeType()->getParameters()[Idx].isIndirectInGuaranteed()
             })) {
  Behavior = MemBehavior::MayRead;
}

I may have gotten the order of the pair templates wrong. But something like this is a little cleaner.

Also, I think you want to use the SubstCalleeType, not the original callee type. The difference is that orig callee type can refer to the base unspecialized type of a specialized function. You always want to use the specialized function if you have it (which is the subst callee type.

···

On Jul 18, 2017, at 9:53 AM, Michael Gottesman via swift-dev <swift-dev@swift.org> wrote:

On Jul 18, 2017, at 8:39 AM, Johannes Weiß <johannesweiss@apple.com> wrote:

On 17 Jul 2017, at 10:26 pm, Erik Eckstein <eeckstein@apple.com> wrote:

Michael

} else {
   auto &GlobalEffects = ApplyEffects.getGlobalEffects();
   Behavior = GlobalEffects.getMemBehavior(InspectionMode);

which indeed turns

--- SNIP ---
sil @bar : $@convention(thin) (@in Int) -> () {
bb0(%0 : $*Int):
%value_raw = integer_literal $Builtin.Int64, 42
%value = struct $Int (%value_raw : $Builtin.Int64)
store %value to %0 : $*Int

%f_buz = function_ref @buz : $@convention(thin) (@in_guaranteed Int) -> ()
%r1 = apply %f_buz(%0) : $@convention(thin) (@in_guaranteed Int) -> ()

%value_again = load %0 : $*Int
%f_test = function_ref @test : $@convention(thin) (Int) -> ()
%r2 = apply %f_test(%value_again) : $@convention(thin) (Int) -> ()

/*
%f_bad = function_ref @bad : $@convention(thin) (@in_guaranteed Int) -> ()
%r3 = apply %f_bad(%0) : $@convention(thin) (@in_guaranteed Int) -> ()

%value_again2 = load %0 : $*Int
%r4 = apply %f_test(%value_again2) : $@convention(thin) (Int) -> ()
*/

%9999 = tuple()
return %9999 : $()
}
--- SNAP ---

into

--- SNIP ---
bb0(%0 : $*Int):
%1 = integer_literal $Builtin.Int64, 42 // user: %2
%2 = struct $Int (%1 : $Builtin.Int64) // users: %7, %3
store %2 to %0 : $*Int // id: %3
// function_ref buz
%4 = function_ref @buz : $@convention(thin) (@in_guaranteed Int) -> () // user: %5
%5 = apply %4(%0) : $@convention(thin) (@in_guaranteed Int) -> ()
// function_ref test
%6 = function_ref @test : $@convention(thin) (Int) -> () // user: %7
%7 = apply %6(%2) : $@convention(thin) (Int) -> ()
%8 = tuple () // user: %9
return %8 : $() // id: %9
} // end sil function 'bar'
--- SNAP ---

so the load has successfully been eliminated. Also taking my initial repro [1], the retain, the load, and the release are now gone :smiley:.

Is that roughly what you were thinking of?

Many thanks,
Johannes

[1]: https://bugs.swift.org/secure/attachment/12378/test.swift

Erik

On Jul 17, 2017, at 9:23 AM, Johannes Weiß <johannesweiss@apple.com> wrote:

Thanks Michael!

Erik, I hope what I wrote makes some sense. Any questions or suggestions, please let me know.

On 14 Jul 2017, at 7:30 pm, Michael Gottesman <mgottesman@apple.com> wrote:

On Jul 12, 2017, at 9:53 AM, Johannes Weiß <johannesweiss@apple.com> wrote:

Hi Michael,

[...]

Long story short, I think the RLE actually works for the test case I created. It's even clever enough to see through my invalid function bad() which modified the storage despite its claim that it doesn't. I might also be misunderstanding something.

When something is marked as in_guaranteed, it should be immutable. If the callee violates that, then the SIL is malformed. Perhaps, we can add some sort of verification check.

Right, yes I was aware that that'd be illegal but I added it as a way to check whether this optimisation is 'looking into' the called function.

That being said, I have a good feeling that there is some sort of analysis occuring here since you provided enough information to the optimizer. The optimization here is regardless of whether or not we can see the body of a function, we know that it is safe to optimize this just based off the @in_guaranteed. This implies using a declaration, not a definition of the bad function.

makes sense, didn't think about just only declaring it...

When I said write the SIL by hand, what I meant was writing the whole program by hand. In general, we prefer SIL programs that do not have extraneous stuff that is added by the compiler (for instance debug_value). Additionally, it is important for SIL files to not have dependencies on the stdlib unless absolutely necessary (i.e. your usage of Int). This prevents the stdlib maintainers from having to update these tests given chances to the stdlib. Below is a cleaned up version that shows the problem. Look at how small it is and how it tests /exactly/ what we are trying to test and via the use of declarations and the like we are able to exclude other optimizations:

That makes a lot of sense, thank you. I wasn't yet that familiar with SIL so I thought I start from a program generated by the compiler and then replace the guts with handwritten SIL. But your version is clearly a lot easier to understand and shows what precisely we want to see!

Today, I looked into why this is happening more precisely.

So we don't get the RLE because in this code

if (isComputeAvailValue(Kind) || isPerformingRLE(Kind)) {
for (unsigned i = 0; i < Locs.size(); ++i) {
if (isTrackingLocation(ForwardSetIn, Ctx.getLocationBit(Locs[i])))
   continue;
updateForwardSetAndValForRead(Ctx, Ctx.getLocationBit(Locs[i]),
                               Ctx.getValueBit(Vals[i]));
// We can not perform the forwarding as we are at least missing
// some pieces of the read location.
CanForward = false;

(https://github.com/apple/swift/blob/86620aaa7ebd32d33f4cdf61add5c63a72d3f02a/lib/SILOptimizer/Transforms/RedundantLoadElimination.cpp#L917)

we're not taking the `continue` for the call to `buz()`. The reason why is that here

if (!AA->mayWriteToMemory(I, R.getBase()))
continue;
// MayAlias.
stopTrackingLocation(ForwardSetIn, i);
stopTrackingValue(ForwardValIn, i);

(https://github.com/apple/swift/blob/86620aaa7ebd32d33f4cdf61add5c63a72d3f02a/lib/SILOptimizer/Transforms/RedundantLoadElimination.cpp#L972)

we're not taking the `continue`, ie. `AA->mayWriteToMemory(I, R.getBase())` is true. The reason for that is that the `SILFunction` for `buz` has

EffectsKindAttr = Unspecified

which equates to `MayHaveSideEffects`, that's also what `-debug-only=sil-redundant-load-elim,sil-membehavior` outputs:

GET MEMORY BEHAVIOR FOR:
%5 = apply %4(%0) : $@convention(thin) (@in_guaranteed Int) -> ()
%0 = argument of bb0 : $*Int // users: %6, %5, %3
Found apply, returning MayHaveSideEffects

So where I'm stuck today is that I'm not sure how `EffectsKindAttr` is actually defined. Sure, `$@convention(thin) (@in_guaranteed Int) -> ()` doesn't actually write to the `@in_guaranteed Int` (as that'd be illegal) but it may have other side effects. So I'm not sure if we can just create the function differently if we find only "read-only" kind of parameters. That'd be I think in

auto *fn = SILMod.createFunction(SILLinkage::Private, Name.str(), Ty,
                              nullptr, loc, IsNotBare,
                              IsNotTransparent, IsNotSerialized);

(https://github.com/apple/swift/blob/ec6fc4d54db95f78ae72dab29734533f709ea2d7/lib/Parse/ParseSIL.cpp#L508 -> https://github.com/apple/swift/blob/157db57506b813837481b574a9d38e806bf954b6/lib/SIL/SILModule.cpp#L249)

which doesn't specify any EffectsAttrKind and therefore it defaults to `Unspecified`.

Just as a test, I did put a `[readonly]` in `sil @buz : $@convention(thin) (@in_guaranteed Int) -> ()` and as expected everything propagates through correctly and we get a successful RLE.

So yes, maybe you have some pointers on where to best educate the compiler that the `buz` function won't write to that bit of memory.

I have a few ideas of where to put it, but really the person to bring in here is Erik. He is the one who wrote the side-effect part of the optimizer. Keep in mind he is on vacation right now until next week. So I wouldn't expect a response until then.

Michael

Many thanks,
Johannes

----
sil_stage canonical

import Builtin

struct Int {
var _value : Builtin.Int64
}

sil @test : $@convention(thin) (Int) -> ()
sil @buz : $@convention(thin) (@in_guaranteed Int) -> ()
sil @bad : $@convention(thin) (@in_guaranteed Int) -> ()

sil @bar : $@convention(thin) (@in Int) -> () {
bb0(%0 : $*Int):
%value_raw = integer_literal $Builtin.Int64, 42
%value = struct $Int (%value_raw : $Builtin.Int64)
store %value to %0 : $*Int

%f_buz = function_ref @buz : $@convention(thin) (@in_guaranteed Int) -> ()
%r1 = apply %f_buz(%0) : $@convention(thin) (@in_guaranteed Int) -> ()

%value_again = load %0 : $*Int
%f_test = function_ref @test : $@convention(thin) (Int) -> ()
%r2 = apply %f_test(%value_again) : $@convention(thin) (Int) -> ()

%f_bad = function_ref @bad : $@convention(thin) (@in_guaranteed Int) -> ()
%r3 = apply %f_bad(%0) : $@convention(thin) (@in_guaranteed Int) -> ()

%value_again2 = load %0 : $*Int
%r4 = apply %f_test(%value_again2) : $@convention(thin) (Int) -> ()

%9999 = tuple()
return %9999 : $()
}
----

When I run this test file through rle, I get:

----
sil_stage canonical

import Builtin
import Swift
import SwiftShims

struct Int {
@sil_stored var _value: Builtin.Int64
init(_value: Builtin.Int64)
}

// test
sil @test : $@convention(thin) (Int) -> ()

// buz
sil @buz : $@convention(thin) (@in_guaranteed Int) -> ()

// bad
sil @bad : $@convention(thin) (@in_guaranteed Int) -> ()

// bar
sil @bar : $@convention(thin) (@in Int) -> () {
// %0 // users: %11, %10, %6, %5, %3
bb0(%0 : $*Int):
%1 = integer_literal $Builtin.Int64, 42 // user: %2
%2 = struct $Int (%1 : $Builtin.Int64) // user: %3
store %2 to %0 : $*Int // id: %3
// function_ref buz
%4 = function_ref @buz : $@convention(thin) (@in_guaranteed Int) -> () // user: %5
%5 = apply %4(%0) : $@convention(thin) (@in_guaranteed Int) -> ()
%6 = load %0 : $*Int // user: %8
// function_ref test
%7 = function_ref @test : $@convention(thin) (Int) -> () // users: %12, %8
%8 = apply %7(%6) : $@convention(thin) (Int) -> ()
// function_ref bad
%9 = function_ref @bad : $@convention(thin) (@in_guaranteed Int) -> () // user: %10
%10 = apply %9(%0) : $@convention(thin) (@in_guaranteed Int) -> ()
%11 = load %0 : $*Int // user: %12
%12 = apply %7(%11) : $@convention(thin) (Int) -> ()
%13 = tuple () // user: %14
return %13 : $() // id: %14
} // end sil function 'bar'
----

Michael

Does that all make sense?

Thanks,
Johannes
<test-load-forwarding.sil><test-load-forwarding.sil-opt>

Thanks,
Johannes

[1]: https://bugs.swift.org/browse/SR-5403

_______________________________________________
swift-dev mailing list
swift-dev@swift.org <mailto:swift-dev@swift.org>
https://lists.swift.org/mailman/listinfo/swift-dev

Thanks, both suggestions look great. Will work them in tomorrow and will also try to add a test for the whole thing.

···

On 18 Jul 2017, at 5:53 pm, Michael Gottesman <mgottesman@apple.com> wrote:

On Jul 18, 2017, at 8:39 AM, Johannes Weiß <johannesweiss@apple.com> wrote:

Hi Erik,

On 17 Jul 2017, at 10:26 pm, Erik Eckstein <eeckstein@apple.com> wrote:

Hi Johannes,

great that you want to work on this!

Thanks for your help, without Michael's and your help I wouldn't have been able to do anything here really!

Some ideas:
SideEffectAnalysis currently does not have a notion of “this argument is not modified by the callee” if the callee is unknown or does anything non-trivial.
Therefore I think it’s best to put the in_guarantee check directly into MemoryBehaviorVisitor::visitApplyInst():
If the parameter convention is in_guaranteed and the parameter is V, then the behavior can be MemBehavior::MayRead

Thanks, that actually makes a lot of sense. Here's my diff right now

diff --git a/lib/SILOptimizer/Analysis/MemoryBehavior.cpp b/lib/SILOptimizer/Analysis/MemoryBehavior.cpp
index b1fe7fa665..c44cc64f94 100644
--- a/lib/SILOptimizer/Analysis/MemoryBehavior.cpp
+++ b/lib/SILOptimizer/Analysis/MemoryBehavior.cpp
@@ -245,6 +245,23 @@ MemBehavior MemoryBehaviorVisitor::visitApplyInst(ApplyInst *AI) {
     (InspectionMode == RetainObserveKind::ObserveRetains &&
      ApplyEffects.mayAllocObjects())) {
   Behavior = MemBehavior::MayHaveSideEffects;
+
+ unsigned Idx = 0;
+ bool AllReadOnly = false;
+ for (Operand &operand : AI->getArgumentOperands()) {
+ if (operand.get() == V && AI->getOrigCalleeType()->getParameters()[Idx].isIndirectInGuaranteed()) {
+ AllReadOnly = true;
+ } else {
+ AllReadOnly = false;
+ break;
+ }
+
+ Idx++;
+ }
+
+ if (AllReadOnly) {
+ Behavior = MemBehavior::MayRead;
+ }

Suggestion:

if (all_of(enumerate(AI->getArgumentOperands()),
             [&](std::pair<unsigned, SILValue> pair) -> bool {
                return pair.second.get() == V && AI->getOrigCalleeType()->getParameters()[Idx].isIndirectInGuaranteed()
             })) {
  Behavior = MemBehavior::MayRead;
}

I may have gotten the order of the pair templates wrong. But something like this is a little cleaner.

Michael

} else {
   auto &GlobalEffects = ApplyEffects.getGlobalEffects();
   Behavior = GlobalEffects.getMemBehavior(InspectionMode);

which indeed turns

--- SNIP ---
sil @bar : $@convention(thin) (@in Int) -> () {
bb0(%0 : $*Int):
%value_raw = integer_literal $Builtin.Int64, 42
%value = struct $Int (%value_raw : $Builtin.Int64)
store %value to %0 : $*Int

%f_buz = function_ref @buz : $@convention(thin) (@in_guaranteed Int) -> ()
%r1 = apply %f_buz(%0) : $@convention(thin) (@in_guaranteed Int) -> ()

%value_again = load %0 : $*Int
%f_test = function_ref @test : $@convention(thin) (Int) -> ()
%r2 = apply %f_test(%value_again) : $@convention(thin) (Int) -> ()

/*
%f_bad = function_ref @bad : $@convention(thin) (@in_guaranteed Int) -> ()
%r3 = apply %f_bad(%0) : $@convention(thin) (@in_guaranteed Int) -> ()

%value_again2 = load %0 : $*Int
%r4 = apply %f_test(%value_again2) : $@convention(thin) (Int) -> ()
*/

%9999 = tuple()
return %9999 : $()
}
--- SNAP ---

into

--- SNIP ---
bb0(%0 : $*Int):
%1 = integer_literal $Builtin.Int64, 42 // user: %2
%2 = struct $Int (%1 : $Builtin.Int64) // users: %7, %3
store %2 to %0 : $*Int // id: %3
// function_ref buz
%4 = function_ref @buz : $@convention(thin) (@in_guaranteed Int) -> () // user: %5
%5 = apply %4(%0) : $@convention(thin) (@in_guaranteed Int) -> ()
// function_ref test
%6 = function_ref @test : $@convention(thin) (Int) -> () // user: %7
%7 = apply %6(%2) : $@convention(thin) (Int) -> ()
%8 = tuple () // user: %9
return %8 : $() // id: %9
} // end sil function 'bar'
--- SNAP ---

so the load has successfully been eliminated. Also taking my initial repro [1], the retain, the load, and the release are now gone :smiley:.

Is that roughly what you were thinking of?

Many thanks,
Johannes

[1]: https://bugs.swift.org/secure/attachment/12378/test.swift

Erik

On Jul 17, 2017, at 9:23 AM, Johannes Weiß <johannesweiss@apple.com> wrote:

Thanks Michael!

Erik, I hope what I wrote makes some sense. Any questions or suggestions, please let me know.

On 14 Jul 2017, at 7:30 pm, Michael Gottesman <mgottesman@apple.com> wrote:

On Jul 12, 2017, at 9:53 AM, Johannes Weiß <johannesweiss@apple.com> wrote:

Hi Michael,

[...]

Long story short, I think the RLE actually works for the test case I created. It's even clever enough to see through my invalid function bad() which modified the storage despite its claim that it doesn't. I might also be misunderstanding something.

When something is marked as in_guaranteed, it should be immutable. If the callee violates that, then the SIL is malformed. Perhaps, we can add some sort of verification check.

Right, yes I was aware that that'd be illegal but I added it as a way to check whether this optimisation is 'looking into' the called function.

That being said, I have a good feeling that there is some sort of analysis occuring here since you provided enough information to the optimizer. The optimization here is regardless of whether or not we can see the body of a function, we know that it is safe to optimize this just based off the @in_guaranteed. This implies using a declaration, not a definition of the bad function.

makes sense, didn't think about just only declaring it...

When I said write the SIL by hand, what I meant was writing the whole program by hand. In general, we prefer SIL programs that do not have extraneous stuff that is added by the compiler (for instance debug_value). Additionally, it is important for SIL files to not have dependencies on the stdlib unless absolutely necessary (i.e. your usage of Int). This prevents the stdlib maintainers from having to update these tests given chances to the stdlib. Below is a cleaned up version that shows the problem. Look at how small it is and how it tests /exactly/ what we are trying to test and via the use of declarations and the like we are able to exclude other optimizations:

That makes a lot of sense, thank you. I wasn't yet that familiar with SIL so I thought I start from a program generated by the compiler and then replace the guts with handwritten SIL. But your version is clearly a lot easier to understand and shows what precisely we want to see!

Today, I looked into why this is happening more precisely.

So we don't get the RLE because in this code

if (isComputeAvailValue(Kind) || isPerformingRLE(Kind)) {
for (unsigned i = 0; i < Locs.size(); ++i) {
if (isTrackingLocation(ForwardSetIn, Ctx.getLocationBit(Locs[i])))
   continue;
updateForwardSetAndValForRead(Ctx, Ctx.getLocationBit(Locs[i]),
                               Ctx.getValueBit(Vals[i]));
// We can not perform the forwarding as we are at least missing
// some pieces of the read location.
CanForward = false;

(https://github.com/apple/swift/blob/86620aaa7ebd32d33f4cdf61add5c63a72d3f02a/lib/SILOptimizer/Transforms/RedundantLoadElimination.cpp#L917)

we're not taking the `continue` for the call to `buz()`. The reason why is that here

if (!AA->mayWriteToMemory(I, R.getBase()))
continue;
// MayAlias.
stopTrackingLocation(ForwardSetIn, i);
stopTrackingValue(ForwardValIn, i);

(https://github.com/apple/swift/blob/86620aaa7ebd32d33f4cdf61add5c63a72d3f02a/lib/SILOptimizer/Transforms/RedundantLoadElimination.cpp#L972)

we're not taking the `continue`, ie. `AA->mayWriteToMemory(I, R.getBase())` is true. The reason for that is that the `SILFunction` for `buz` has

EffectsKindAttr = Unspecified

which equates to `MayHaveSideEffects`, that's also what `-debug-only=sil-redundant-load-elim,sil-membehavior` outputs:

GET MEMORY BEHAVIOR FOR:
%5 = apply %4(%0) : $@convention(thin) (@in_guaranteed Int) -> ()
%0 = argument of bb0 : $*Int // users: %6, %5, %3
Found apply, returning MayHaveSideEffects

So where I'm stuck today is that I'm not sure how `EffectsKindAttr` is actually defined. Sure, `$@convention(thin) (@in_guaranteed Int) -> ()` doesn't actually write to the `@in_guaranteed Int` (as that'd be illegal) but it may have other side effects. So I'm not sure if we can just create the function differently if we find only "read-only" kind of parameters. That'd be I think in

auto *fn = SILMod.createFunction(SILLinkage::Private, Name.str(), Ty,
                              nullptr, loc, IsNotBare,
                              IsNotTransparent, IsNotSerialized);

(https://github.com/apple/swift/blob/ec6fc4d54db95f78ae72dab29734533f709ea2d7/lib/Parse/ParseSIL.cpp#L508 -> https://github.com/apple/swift/blob/157db57506b813837481b574a9d38e806bf954b6/lib/SIL/SILModule.cpp#L249)

which doesn't specify any EffectsAttrKind and therefore it defaults to `Unspecified`.

Just as a test, I did put a `[readonly]` in `sil @buz : $@convention(thin) (@in_guaranteed Int) -> ()` and as expected everything propagates through correctly and we get a successful RLE.

So yes, maybe you have some pointers on where to best educate the compiler that the `buz` function won't write to that bit of memory.

I have a few ideas of where to put it, but really the person to bring in here is Erik. He is the one who wrote the side-effect part of the optimizer. Keep in mind he is on vacation right now until next week. So I wouldn't expect a response until then.

Michael

Many thanks,
Johannes

----
sil_stage canonical

import Builtin

struct Int {
var _value : Builtin.Int64
}

sil @test : $@convention(thin) (Int) -> ()
sil @buz : $@convention(thin) (@in_guaranteed Int) -> ()
sil @bad : $@convention(thin) (@in_guaranteed Int) -> ()

sil @bar : $@convention(thin) (@in Int) -> () {
bb0(%0 : $*Int):
%value_raw = integer_literal $Builtin.Int64, 42
%value = struct $Int (%value_raw : $Builtin.Int64)
store %value to %0 : $*Int

%f_buz = function_ref @buz : $@convention(thin) (@in_guaranteed Int) -> ()
%r1 = apply %f_buz(%0) : $@convention(thin) (@in_guaranteed Int) -> ()

%value_again = load %0 : $*Int
%f_test = function_ref @test : $@convention(thin) (Int) -> ()
%r2 = apply %f_test(%value_again) : $@convention(thin) (Int) -> ()

%f_bad = function_ref @bad : $@convention(thin) (@in_guaranteed Int) -> ()
%r3 = apply %f_bad(%0) : $@convention(thin) (@in_guaranteed Int) -> ()

%value_again2 = load %0 : $*Int
%r4 = apply %f_test(%value_again2) : $@convention(thin) (Int) -> ()

%9999 = tuple()
return %9999 : $()
}
----

When I run this test file through rle, I get:

----
sil_stage canonical

import Builtin
import Swift
import SwiftShims

struct Int {
@sil_stored var _value: Builtin.Int64
init(_value: Builtin.Int64)
}

// test
sil @test : $@convention(thin) (Int) -> ()

// buz
sil @buz : $@convention(thin) (@in_guaranteed Int) -> ()

// bad
sil @bad : $@convention(thin) (@in_guaranteed Int) -> ()

// bar
sil @bar : $@convention(thin) (@in Int) -> () {
// %0 // users: %11, %10, %6, %5, %3
bb0(%0 : $*Int):
%1 = integer_literal $Builtin.Int64, 42 // user: %2
%2 = struct $Int (%1 : $Builtin.Int64) // user: %3
store %2 to %0 : $*Int // id: %3
// function_ref buz
%4 = function_ref @buz : $@convention(thin) (@in_guaranteed Int) -> () // user: %5
%5 = apply %4(%0) : $@convention(thin) (@in_guaranteed Int) -> ()
%6 = load %0 : $*Int // user: %8
// function_ref test
%7 = function_ref @test : $@convention(thin) (Int) -> () // users: %12, %8
%8 = apply %7(%6) : $@convention(thin) (Int) -> ()
// function_ref bad
%9 = function_ref @bad : $@convention(thin) (@in_guaranteed Int) -> () // user: %10
%10 = apply %9(%0) : $@convention(thin) (@in_guaranteed Int) -> ()
%11 = load %0 : $*Int // user: %12
%12 = apply %7(%11) : $@convention(thin) (Int) -> ()
%13 = tuple () // user: %14
return %13 : $() // id: %14
} // end sil function 'bar'
----

Michael

Does that all make sense?

Thanks,
Johannes
<test-load-forwarding.sil><test-load-forwarding.sil-opt>

Thanks,
Johannes

[1]: https://bugs.swift.org/browse/SR-5403

Thanks, both suggestions look great. Will work them in tomorrow and will also try to add a test for the whole thing.

Hi Erik,

Hi Johannes,

great that you want to work on this!

Thanks for your help, without Michael's and your help I wouldn't have been able to do anything here really!

Some ideas:
SideEffectAnalysis currently does not have a notion of “this argument is not modified by the callee” if the callee is unknown or does anything non-trivial.
Therefore I think it’s best to put the in_guarantee check directly into MemoryBehaviorVisitor::visitApplyInst():
If the parameter convention is in_guaranteed and the parameter is V, then the behavior can be MemBehavior::MayRead

Thanks, that actually makes a lot of sense. Here's my diff right now

diff --git a/lib/SILOptimizer/Analysis/MemoryBehavior.cpp b/lib/SILOptimizer/Analysis/MemoryBehavior.cpp
index b1fe7fa665..c44cc64f94 100644
--- a/lib/SILOptimizer/Analysis/MemoryBehavior.cpp
+++ b/lib/SILOptimizer/Analysis/MemoryBehavior.cpp
@@ -245,6 +245,23 @@ MemBehavior MemoryBehaviorVisitor::visitApplyInst(ApplyInst *AI) {
    (InspectionMode == RetainObserveKind::ObserveRetains &&
     ApplyEffects.mayAllocObjects())) {
  Behavior = MemBehavior::MayHaveSideEffects;

You should move your new code out of the if (ApplyEffects.mayReadRC() ...
Otherwise it will not be executed if the called function does not read a reference count.

Beside that it looks good to me.

···

On Jul 18, 2017, at 10:40 AM, Johannes Weiß <johannesweiss@apple.com> wrote:

On 18 Jul 2017, at 5:53 pm, Michael Gottesman <mgottesman@apple.com> wrote:

On Jul 18, 2017, at 8:39 AM, Johannes Weiß <johannesweiss@apple.com> wrote:

On 17 Jul 2017, at 10:26 pm, Erik Eckstein <eeckstein@apple.com> wrote:

+
+ unsigned Idx = 0;
+ bool AllReadOnly = false;
+ for (Operand &operand : AI->getArgumentOperands()) {
+ if (operand.get() == V && AI->getOrigCalleeType()->getParameters()[Idx].isIndirectInGuaranteed()) {
+ AllReadOnly = true;
+ } else {
+ AllReadOnly = false;
+ break;
+ }
+
+ Idx++;
+ }
+
+ if (AllReadOnly) {
+ Behavior = MemBehavior::MayRead;
+ }

Suggestion:

if (all_of(enumerate(AI->getArgumentOperands()),
            [&](std::pair<unsigned, SILValue> pair) -> bool {
               return pair.second.get() == V && AI->getOrigCalleeType()->getParameters()[Idx].isIndirectInGuaranteed()
            })) {
Behavior = MemBehavior::MayRead;
}

I may have gotten the order of the pair templates wrong. But something like this is a little cleaner.

Michael

} else {
  auto &GlobalEffects = ApplyEffects.getGlobalEffects();
  Behavior = GlobalEffects.getMemBehavior(InspectionMode);

which indeed turns

--- SNIP ---
sil @bar : $@convention(thin) (@in Int) -> () {
bb0(%0 : $*Int):
%value_raw = integer_literal $Builtin.Int64, 42
%value = struct $Int (%value_raw : $Builtin.Int64)
store %value to %0 : $*Int

%f_buz = function_ref @buz : $@convention(thin) (@in_guaranteed Int) -> ()
%r1 = apply %f_buz(%0) : $@convention(thin) (@in_guaranteed Int) -> ()

%value_again = load %0 : $*Int
%f_test = function_ref @test : $@convention(thin) (Int) -> ()
%r2 = apply %f_test(%value_again) : $@convention(thin) (Int) -> ()

/*
%f_bad = function_ref @bad : $@convention(thin) (@in_guaranteed Int) -> ()
%r3 = apply %f_bad(%0) : $@convention(thin) (@in_guaranteed Int) -> ()

%value_again2 = load %0 : $*Int
%r4 = apply %f_test(%value_again2) : $@convention(thin) (Int) -> ()
*/

%9999 = tuple()
return %9999 : $()
}
--- SNAP ---

into

--- SNIP ---
bb0(%0 : $*Int):
%1 = integer_literal $Builtin.Int64, 42 // user: %2
%2 = struct $Int (%1 : $Builtin.Int64) // users: %7, %3
store %2 to %0 : $*Int // id: %3
// function_ref buz
%4 = function_ref @buz : $@convention(thin) (@in_guaranteed Int) -> () // user: %5
%5 = apply %4(%0) : $@convention(thin) (@in_guaranteed Int) -> ()
// function_ref test
%6 = function_ref @test : $@convention(thin) (Int) -> () // user: %7
%7 = apply %6(%2) : $@convention(thin) (Int) -> ()
%8 = tuple () // user: %9
return %8 : $() // id: %9
} // end sil function 'bar'
--- SNAP ---

so the load has successfully been eliminated. Also taking my initial repro [1], the retain, the load, and the release are now gone :smiley:.

Is that roughly what you were thinking of?

Many thanks,
Johannes

[1]: https://bugs.swift.org/secure/attachment/12378/test.swift

Erik

On Jul 17, 2017, at 9:23 AM, Johannes Weiß <johannesweiss@apple.com> wrote:

Thanks Michael!

Erik, I hope what I wrote makes some sense. Any questions or suggestions, please let me know.

On 14 Jul 2017, at 7:30 pm, Michael Gottesman <mgottesman@apple.com> wrote:

On Jul 12, 2017, at 9:53 AM, Johannes Weiß <johannesweiss@apple.com> wrote:

Hi Michael,

[...]

Long story short, I think the RLE actually works for the test case I created. It's even clever enough to see through my invalid function bad() which modified the storage despite its claim that it doesn't. I might also be misunderstanding something.

When something is marked as in_guaranteed, it should be immutable. If the callee violates that, then the SIL is malformed. Perhaps, we can add some sort of verification check.

Right, yes I was aware that that'd be illegal but I added it as a way to check whether this optimisation is 'looking into' the called function.

That being said, I have a good feeling that there is some sort of analysis occuring here since you provided enough information to the optimizer. The optimization here is regardless of whether or not we can see the body of a function, we know that it is safe to optimize this just based off the @in_guaranteed. This implies using a declaration, not a definition of the bad function.

makes sense, didn't think about just only declaring it...

When I said write the SIL by hand, what I meant was writing the whole program by hand. In general, we prefer SIL programs that do not have extraneous stuff that is added by the compiler (for instance debug_value). Additionally, it is important for SIL files to not have dependencies on the stdlib unless absolutely necessary (i.e. your usage of Int). This prevents the stdlib maintainers from having to update these tests given chances to the stdlib. Below is a cleaned up version that shows the problem. Look at how small it is and how it tests /exactly/ what we are trying to test and via the use of declarations and the like we are able to exclude other optimizations:

That makes a lot of sense, thank you. I wasn't yet that familiar with SIL so I thought I start from a program generated by the compiler and then replace the guts with handwritten SIL. But your version is clearly a lot easier to understand and shows what precisely we want to see!

Today, I looked into why this is happening more precisely.

So we don't get the RLE because in this code

if (isComputeAvailValue(Kind) || isPerformingRLE(Kind)) {
for (unsigned i = 0; i < Locs.size(); ++i) {
if (isTrackingLocation(ForwardSetIn, Ctx.getLocationBit(Locs[i])))
  continue;
updateForwardSetAndValForRead(Ctx, Ctx.getLocationBit(Locs[i]),
                              Ctx.getValueBit(Vals[i]));
// We can not perform the forwarding as we are at least missing
// some pieces of the read location.
CanForward = false;

(https://github.com/apple/swift/blob/86620aaa7ebd32d33f4cdf61add5c63a72d3f02a/lib/SILOptimizer/Transforms/RedundantLoadElimination.cpp#L917)

we're not taking the `continue` for the call to `buz()`. The reason why is that here

if (!AA->mayWriteToMemory(I, R.getBase()))
continue;
// MayAlias.
stopTrackingLocation(ForwardSetIn, i);
stopTrackingValue(ForwardValIn, i);

(https://github.com/apple/swift/blob/86620aaa7ebd32d33f4cdf61add5c63a72d3f02a/lib/SILOptimizer/Transforms/RedundantLoadElimination.cpp#L972)

we're not taking the `continue`, ie. `AA->mayWriteToMemory(I, R.getBase())` is true. The reason for that is that the `SILFunction` for `buz` has

EffectsKindAttr = Unspecified

which equates to `MayHaveSideEffects`, that's also what `-debug-only=sil-redundant-load-elim,sil-membehavior` outputs:

GET MEMORY BEHAVIOR FOR:
%5 = apply %4(%0) : $@convention(thin) (@in_guaranteed Int) -> ()
%0 = argument of bb0 : $*Int // users: %6, %5, %3
Found apply, returning MayHaveSideEffects

So where I'm stuck today is that I'm not sure how `EffectsKindAttr` is actually defined. Sure, `$@convention(thin) (@in_guaranteed Int) -> ()` doesn't actually write to the `@in_guaranteed Int` (as that'd be illegal) but it may have other side effects. So I'm not sure if we can just create the function differently if we find only "read-only" kind of parameters. That'd be I think in

auto *fn = SILMod.createFunction(SILLinkage::Private, Name.str(), Ty,
                             nullptr, loc, IsNotBare,
                             IsNotTransparent, IsNotSerialized);

(https://github.com/apple/swift/blob/ec6fc4d54db95f78ae72dab29734533f709ea2d7/lib/Parse/ParseSIL.cpp#L508 -> https://github.com/apple/swift/blob/157db57506b813837481b574a9d38e806bf954b6/lib/SIL/SILModule.cpp#L249)

which doesn't specify any EffectsAttrKind and therefore it defaults to `Unspecified`.

Just as a test, I did put a `[readonly]` in `sil @buz : $@convention(thin) (@in_guaranteed Int) -> ()` and as expected everything propagates through correctly and we get a successful RLE.

So yes, maybe you have some pointers on where to best educate the compiler that the `buz` function won't write to that bit of memory.

I have a few ideas of where to put it, but really the person to bring in here is Erik. He is the one who wrote the side-effect part of the optimizer. Keep in mind he is on vacation right now until next week. So I wouldn't expect a response until then.

Michael

Many thanks,
Johannes

----
sil_stage canonical

import Builtin

struct Int {
var _value : Builtin.Int64
}

sil @test : $@convention(thin) (Int) -> ()
sil @buz : $@convention(thin) (@in_guaranteed Int) -> ()
sil @bad : $@convention(thin) (@in_guaranteed Int) -> ()

sil @bar : $@convention(thin) (@in Int) -> () {
bb0(%0 : $*Int):
%value_raw = integer_literal $Builtin.Int64, 42
%value = struct $Int (%value_raw : $Builtin.Int64)
store %value to %0 : $*Int

%f_buz = function_ref @buz : $@convention(thin) (@in_guaranteed Int) -> ()
%r1 = apply %f_buz(%0) : $@convention(thin) (@in_guaranteed Int) -> ()

%value_again = load %0 : $*Int
%f_test = function_ref @test : $@convention(thin) (Int) -> ()
%r2 = apply %f_test(%value_again) : $@convention(thin) (Int) -> ()

%f_bad = function_ref @bad : $@convention(thin) (@in_guaranteed Int) -> ()
%r3 = apply %f_bad(%0) : $@convention(thin) (@in_guaranteed Int) -> ()

%value_again2 = load %0 : $*Int
%r4 = apply %f_test(%value_again2) : $@convention(thin) (Int) -> ()

%9999 = tuple()
return %9999 : $()
}
----

When I run this test file through rle, I get:

----
sil_stage canonical

import Builtin
import Swift
import SwiftShims

struct Int {
@sil_stored var _value: Builtin.Int64
init(_value: Builtin.Int64)
}

// test
sil @test : $@convention(thin) (Int) -> ()

// buz
sil @buz : $@convention(thin) (@in_guaranteed Int) -> ()

// bad
sil @bad : $@convention(thin) (@in_guaranteed Int) -> ()

// bar
sil @bar : $@convention(thin) (@in Int) -> () {
// %0 // users: %11, %10, %6, %5, %3
bb0(%0 : $*Int):
%1 = integer_literal $Builtin.Int64, 42 // user: %2
%2 = struct $Int (%1 : $Builtin.Int64) // user: %3
store %2 to %0 : $*Int // id: %3
// function_ref buz
%4 = function_ref @buz : $@convention(thin) (@in_guaranteed Int) -> () // user: %5
%5 = apply %4(%0) : $@convention(thin) (@in_guaranteed Int) -> ()
%6 = load %0 : $*Int // user: %8
// function_ref test
%7 = function_ref @test : $@convention(thin) (Int) -> () // users: %12, %8
%8 = apply %7(%6) : $@convention(thin) (Int) -> ()
// function_ref bad
%9 = function_ref @bad : $@convention(thin) (@in_guaranteed Int) -> () // user: %10
%10 = apply %9(%0) : $@convention(thin) (@in_guaranteed Int) -> ()
%11 = load %0 : $*Int // user: %12
%12 = apply %7(%11) : $@convention(thin) (Int) -> ()
%13 = tuple () // user: %14
return %13 : $() // id: %14
} // end sil function 'bar'
----

Michael

Does that all make sense?

Thanks,
Johannes
<test-load-forwarding.sil><test-load-forwarding.sil-opt>

Thanks,
Johannes

[1]: https://bugs.swift.org/browse/SR-5403

great, thank you. I think I have worked all the suggestions in, let's do the rest in this PR: https://github.com/apple/swift/pull/11040

It's getting late here so I'll probably to the test tomorrow (but marked the patch as 'do not merge' & added that a test is still missing).

···

On 18 Jul 2017, at 7:29 pm, Erik Eckstein <eeckstein@apple.com> wrote:

On Jul 18, 2017, at 10:40 AM, Johannes Weiß <johannesweiss@apple.com> wrote:

Thanks, both suggestions look great. Will work them in tomorrow and will also try to add a test for the whole thing.

On 18 Jul 2017, at 5:53 pm, Michael Gottesman <mgottesman@apple.com> wrote:

On Jul 18, 2017, at 8:39 AM, Johannes Weiß <johannesweiss@apple.com> wrote:

Hi Erik,

On 17 Jul 2017, at 10:26 pm, Erik Eckstein <eeckstein@apple.com> wrote:

Hi Johannes,

great that you want to work on this!

Thanks for your help, without Michael's and your help I wouldn't have been able to do anything here really!

Some ideas:
SideEffectAnalysis currently does not have a notion of “this argument is not modified by the callee” if the callee is unknown or does anything non-trivial.
Therefore I think it’s best to put the in_guarantee check directly into MemoryBehaviorVisitor::visitApplyInst():
If the parameter convention is in_guaranteed and the parameter is V, then the behavior can be MemBehavior::MayRead

Thanks, that actually makes a lot of sense. Here's my diff right now

diff --git a/lib/SILOptimizer/Analysis/MemoryBehavior.cpp b/lib/SILOptimizer/Analysis/MemoryBehavior.cpp
index b1fe7fa665..c44cc64f94 100644
--- a/lib/SILOptimizer/Analysis/MemoryBehavior.cpp
+++ b/lib/SILOptimizer/Analysis/MemoryBehavior.cpp
@@ -245,6 +245,23 @@ MemBehavior MemoryBehaviorVisitor::visitApplyInst(ApplyInst *AI) {
    (InspectionMode == RetainObserveKind::ObserveRetains &&
     ApplyEffects.mayAllocObjects())) {
  Behavior = MemBehavior::MayHaveSideEffects;

You should move your new code out of the if (ApplyEffects.mayReadRC() ...
Otherwise it will not be executed if the called function does not read a reference count.

Beside that it looks good to me.

+
+ unsigned Idx = 0;
+ bool AllReadOnly = false;
+ for (Operand &operand : AI->getArgumentOperands()) {
+ if (operand.get() == V && AI->getOrigCalleeType()->getParameters()[Idx].isIndirectInGuaranteed()) {
+ AllReadOnly = true;
+ } else {
+ AllReadOnly = false;
+ break;
+ }
+
+ Idx++;
+ }
+
+ if (AllReadOnly) {
+ Behavior = MemBehavior::MayRead;
+ }

Suggestion:

if (all_of(enumerate(AI->getArgumentOperands()),
            [&](std::pair<unsigned, SILValue> pair) -> bool {
               return pair.second.get() == V && AI->getOrigCalleeType()->getParameters()[Idx].isIndirectInGuaranteed()
            })) {
Behavior = MemBehavior::MayRead;
}

I may have gotten the order of the pair templates wrong. But something like this is a little cleaner.

Michael

} else {
  auto &GlobalEffects = ApplyEffects.getGlobalEffects();
  Behavior = GlobalEffects.getMemBehavior(InspectionMode);

which indeed turns

--- SNIP ---
sil @bar : $@convention(thin) (@in Int) -> () {
bb0(%0 : $*Int):
%value_raw = integer_literal $Builtin.Int64, 42
%value = struct $Int (%value_raw : $Builtin.Int64)
store %value to %0 : $*Int

%f_buz = function_ref @buz : $@convention(thin) (@in_guaranteed Int) -> ()
%r1 = apply %f_buz(%0) : $@convention(thin) (@in_guaranteed Int) -> ()

%value_again = load %0 : $*Int
%f_test = function_ref @test : $@convention(thin) (Int) -> ()
%r2 = apply %f_test(%value_again) : $@convention(thin) (Int) -> ()

/*
%f_bad = function_ref @bad : $@convention(thin) (@in_guaranteed Int) -> ()
%r3 = apply %f_bad(%0) : $@convention(thin) (@in_guaranteed Int) -> ()

%value_again2 = load %0 : $*Int
%r4 = apply %f_test(%value_again2) : $@convention(thin) (Int) -> ()
*/

%9999 = tuple()
return %9999 : $()
}
--- SNAP ---

into

--- SNIP ---
bb0(%0 : $*Int):
%1 = integer_literal $Builtin.Int64, 42 // user: %2
%2 = struct $Int (%1 : $Builtin.Int64) // users: %7, %3
store %2 to %0 : $*Int // id: %3
// function_ref buz
%4 = function_ref @buz : $@convention(thin) (@in_guaranteed Int) -> () // user: %5
%5 = apply %4(%0) : $@convention(thin) (@in_guaranteed Int) -> ()
// function_ref test
%6 = function_ref @test : $@convention(thin) (Int) -> () // user: %7
%7 = apply %6(%2) : $@convention(thin) (Int) -> ()
%8 = tuple () // user: %9
return %8 : $() // id: %9
} // end sil function 'bar'
--- SNAP ---

so the load has successfully been eliminated. Also taking my initial repro [1], the retain, the load, and the release are now gone :smiley:.

Is that roughly what you were thinking of?

Many thanks,
Johannes

[1]: https://bugs.swift.org/secure/attachment/12378/test.swift

Erik

On Jul 17, 2017, at 9:23 AM, Johannes Weiß <johannesweiss@apple.com> wrote:

Thanks Michael!

Erik, I hope what I wrote makes some sense. Any questions or suggestions, please let me know.

On 14 Jul 2017, at 7:30 pm, Michael Gottesman <mgottesman@apple.com> wrote:

On Jul 12, 2017, at 9:53 AM, Johannes Weiß <johannesweiss@apple.com> wrote:

Hi Michael,

[...]

Long story short, I think the RLE actually works for the test case I created. It's even clever enough to see through my invalid function bad() which modified the storage despite its claim that it doesn't. I might also be misunderstanding something.

When something is marked as in_guaranteed, it should be immutable. If the callee violates that, then the SIL is malformed. Perhaps, we can add some sort of verification check.

Right, yes I was aware that that'd be illegal but I added it as a way to check whether this optimisation is 'looking into' the called function.

That being said, I have a good feeling that there is some sort of analysis occuring here since you provided enough information to the optimizer. The optimization here is regardless of whether or not we can see the body of a function, we know that it is safe to optimize this just based off the @in_guaranteed. This implies using a declaration, not a definition of the bad function.

makes sense, didn't think about just only declaring it...

When I said write the SIL by hand, what I meant was writing the whole program by hand. In general, we prefer SIL programs that do not have extraneous stuff that is added by the compiler (for instance debug_value). Additionally, it is important for SIL files to not have dependencies on the stdlib unless absolutely necessary (i.e. your usage of Int). This prevents the stdlib maintainers from having to update these tests given chances to the stdlib. Below is a cleaned up version that shows the problem. Look at how small it is and how it tests /exactly/ what we are trying to test and via the use of declarations and the like we are able to exclude other optimizations:

That makes a lot of sense, thank you. I wasn't yet that familiar with SIL so I thought I start from a program generated by the compiler and then replace the guts with handwritten SIL. But your version is clearly a lot easier to understand and shows what precisely we want to see!

Today, I looked into why this is happening more precisely.

So we don't get the RLE because in this code

if (isComputeAvailValue(Kind) || isPerformingRLE(Kind)) {
for (unsigned i = 0; i < Locs.size(); ++i) {
if (isTrackingLocation(ForwardSetIn, Ctx.getLocationBit(Locs[i])))
  continue;
updateForwardSetAndValForRead(Ctx, Ctx.getLocationBit(Locs[i]),
                              Ctx.getValueBit(Vals[i]));
// We can not perform the forwarding as we are at least missing
// some pieces of the read location.
CanForward = false;

(https://github.com/apple/swift/blob/86620aaa7ebd32d33f4cdf61add5c63a72d3f02a/lib/SILOptimizer/Transforms/RedundantLoadElimination.cpp#L917)

we're not taking the `continue` for the call to `buz()`. The reason why is that here

if (!AA->mayWriteToMemory(I, R.getBase()))
continue;
// MayAlias.
stopTrackingLocation(ForwardSetIn, i);
stopTrackingValue(ForwardValIn, i);

(https://github.com/apple/swift/blob/86620aaa7ebd32d33f4cdf61add5c63a72d3f02a/lib/SILOptimizer/Transforms/RedundantLoadElimination.cpp#L972)

we're not taking the `continue`, ie. `AA->mayWriteToMemory(I, R.getBase())` is true. The reason for that is that the `SILFunction` for `buz` has

EffectsKindAttr = Unspecified

which equates to `MayHaveSideEffects`, that's also what `-debug-only=sil-redundant-load-elim,sil-membehavior` outputs:

GET MEMORY BEHAVIOR FOR:
%5 = apply %4(%0) : $@convention(thin) (@in_guaranteed Int) -> ()
%0 = argument of bb0 : $*Int // users: %6, %5, %3
Found apply, returning MayHaveSideEffects

So where I'm stuck today is that I'm not sure how `EffectsKindAttr` is actually defined. Sure, `$@convention(thin) (@in_guaranteed Int) -> ()` doesn't actually write to the `@in_guaranteed Int` (as that'd be illegal) but it may have other side effects. So I'm not sure if we can just create the function differently if we find only "read-only" kind of parameters. That'd be I think in

auto *fn = SILMod.createFunction(SILLinkage::Private, Name.str(), Ty,
                             nullptr, loc, IsNotBare,
                             IsNotTransparent, IsNotSerialized);

(https://github.com/apple/swift/blob/ec6fc4d54db95f78ae72dab29734533f709ea2d7/lib/Parse/ParseSIL.cpp#L508 -> https://github.com/apple/swift/blob/157db57506b813837481b574a9d38e806bf954b6/lib/SIL/SILModule.cpp#L249)

which doesn't specify any EffectsAttrKind and therefore it defaults to `Unspecified`.

Just as a test, I did put a `[readonly]` in `sil @buz : $@convention(thin) (@in_guaranteed Int) -> ()` and as expected everything propagates through correctly and we get a successful RLE.

So yes, maybe you have some pointers on where to best educate the compiler that the `buz` function won't write to that bit of memory.

I have a few ideas of where to put it, but really the person to bring in here is Erik. He is the one who wrote the side-effect part of the optimizer. Keep in mind he is on vacation right now until next week. So I wouldn't expect a response until then.

Michael

Many thanks,
Johannes

----
sil_stage canonical

import Builtin

struct Int {
var _value : Builtin.Int64
}

sil @test : $@convention(thin) (Int) -> ()
sil @buz : $@convention(thin) (@in_guaranteed Int) -> ()
sil @bad : $@convention(thin) (@in_guaranteed Int) -> ()

sil @bar : $@convention(thin) (@in Int) -> () {
bb0(%0 : $*Int):
%value_raw = integer_literal $Builtin.Int64, 42
%value = struct $Int (%value_raw : $Builtin.Int64)
store %value to %0 : $*Int

%f_buz = function_ref @buz : $@convention(thin) (@in_guaranteed Int) -> ()
%r1 = apply %f_buz(%0) : $@convention(thin) (@in_guaranteed Int) -> ()

%value_again = load %0 : $*Int
%f_test = function_ref @test : $@convention(thin) (Int) -> ()
%r2 = apply %f_test(%value_again) : $@convention(thin) (Int) -> ()

%f_bad = function_ref @bad : $@convention(thin) (@in_guaranteed Int) -> ()
%r3 = apply %f_bad(%0) : $@convention(thin) (@in_guaranteed Int) -> ()

%value_again2 = load %0 : $*Int
%r4 = apply %f_test(%value_again2) : $@convention(thin) (Int) -> ()

%9999 = tuple()
return %9999 : $()
}
----

When I run this test file through rle, I get:

----
sil_stage canonical

import Builtin
import Swift
import SwiftShims

struct Int {
@sil_stored var _value: Builtin.Int64
init(_value: Builtin.Int64)
}

// test
sil @test : $@convention(thin) (Int) -> ()

// buz
sil @buz : $@convention(thin) (@in_guaranteed Int) -> ()

// bad
sil @bad : $@convention(thin) (@in_guaranteed Int) -> ()

// bar
sil @bar : $@convention(thin) (@in Int) -> () {
// %0 // users: %11, %10, %6, %5, %3
bb0(%0 : $*Int):
%1 = integer_literal $Builtin.Int64, 42 // user: %2
%2 = struct $Int (%1 : $Builtin.Int64) // user: %3
store %2 to %0 : $*Int // id: %3
// function_ref buz
%4 = function_ref @buz : $@convention(thin) (@in_guaranteed Int) -> () // user: %5
%5 = apply %4(%0) : $@convention(thin) (@in_guaranteed Int) -> ()
%6 = load %0 : $*Int // user: %8
// function_ref test
%7 = function_ref @test : $@convention(thin) (Int) -> () // users: %12, %8
%8 = apply %7(%6) : $@convention(thin) (Int) -> ()
// function_ref bad
%9 = function_ref @bad : $@convention(thin) (@in_guaranteed Int) -> () // user: %10
%10 = apply %9(%0) : $@convention(thin) (@in_guaranteed Int) -> ()
%11 = load %0 : $*Int // user: %12
%12 = apply %7(%11) : $@convention(thin) (Int) -> ()
%13 = tuple () // user: %14
return %13 : $() // id: %14
} // end sil function 'bar'
----

Michael

Does that all make sense?

Thanks,
Johannes
<test-load-forwarding.sil><test-load-forwarding.sil-opt>

Thanks,
Johannes

[1]: https://bugs.swift.org/browse/SR-5403

Thanks very much Eric & Michael for your help! And thanks for merging it. Will this automatically be part of Swift 4 or do I need to make another PR against a swift 4 branch?

Thanks,
  Johannes

···

On 18 Jul 2017, at 9:21 pm, Johannes Weiß via swift-dev <swift-dev@swift.org> wrote:

great, thank you. I think I have worked all the suggestions in, let's do the rest in this PR: https://github.com/apple/swift/pull/11040

It's getting late here so I'll probably to the test tomorrow (but marked the patch as 'do not merge' & added that a test is still missing).

On 18 Jul 2017, at 7:29 pm, Erik Eckstein <eeckstein@apple.com> wrote:

On Jul 18, 2017, at 10:40 AM, Johannes Weiß <johannesweiss@apple.com> wrote:

Thanks, both suggestions look great. Will work them in tomorrow and will also try to add a test for the whole thing.

On 18 Jul 2017, at 5:53 pm, Michael Gottesman <mgottesman@apple.com> wrote:

On Jul 18, 2017, at 8:39 AM, Johannes Weiß <johannesweiss@apple.com> wrote:

Hi Erik,

On 17 Jul 2017, at 10:26 pm, Erik Eckstein <eeckstein@apple.com> wrote:

Hi Johannes,

great that you want to work on this!

Thanks for your help, without Michael's and your help I wouldn't have been able to do anything here really!

Some ideas:
SideEffectAnalysis currently does not have a notion of “this argument is not modified by the callee” if the callee is unknown or does anything non-trivial.
Therefore I think it’s best to put the in_guarantee check directly into MemoryBehaviorVisitor::visitApplyInst():
If the parameter convention is in_guaranteed and the parameter is V, then the behavior can be MemBehavior::MayRead

Thanks, that actually makes a lot of sense. Here's my diff right now

diff --git a/lib/SILOptimizer/Analysis/MemoryBehavior.cpp b/lib/SILOptimizer/Analysis/MemoryBehavior.cpp
index b1fe7fa665..c44cc64f94 100644
--- a/lib/SILOptimizer/Analysis/MemoryBehavior.cpp
+++ b/lib/SILOptimizer/Analysis/MemoryBehavior.cpp
@@ -245,6 +245,23 @@ MemBehavior MemoryBehaviorVisitor::visitApplyInst(ApplyInst *AI) {
   (InspectionMode == RetainObserveKind::ObserveRetains &&
    ApplyEffects.mayAllocObjects())) {
Behavior = MemBehavior::MayHaveSideEffects;

You should move your new code out of the if (ApplyEffects.mayReadRC() ...
Otherwise it will not be executed if the called function does not read a reference count.

Beside that it looks good to me.

+
+ unsigned Idx = 0;
+ bool AllReadOnly = false;
+ for (Operand &operand : AI->getArgumentOperands()) {
+ if (operand.get() == V && AI->getOrigCalleeType()->getParameters()[Idx].isIndirectInGuaranteed()) {
+ AllReadOnly = true;
+ } else {
+ AllReadOnly = false;
+ break;
+ }
+
+ Idx++;
+ }
+
+ if (AllReadOnly) {
+ Behavior = MemBehavior::MayRead;
+ }

Suggestion:

if (all_of(enumerate(AI->getArgumentOperands()),
           [&](std::pair<unsigned, SILValue> pair) -> bool {
              return pair.second.get() == V && AI->getOrigCalleeType()->getParameters()[Idx].isIndirectInGuaranteed()
           })) {
Behavior = MemBehavior::MayRead;
}

I may have gotten the order of the pair templates wrong. But something like this is a little cleaner.

Michael

} else {
auto &GlobalEffects = ApplyEffects.getGlobalEffects();
Behavior = GlobalEffects.getMemBehavior(InspectionMode);

which indeed turns

--- SNIP ---
sil @bar : $@convention(thin) (@in Int) -> () {
bb0(%0 : $*Int):
%value_raw = integer_literal $Builtin.Int64, 42
%value = struct $Int (%value_raw : $Builtin.Int64)
store %value to %0 : $*Int

%f_buz = function_ref @buz : $@convention(thin) (@in_guaranteed Int) -> ()
%r1 = apply %f_buz(%0) : $@convention(thin) (@in_guaranteed Int) -> ()

%value_again = load %0 : $*Int
%f_test = function_ref @test : $@convention(thin) (Int) -> ()
%r2 = apply %f_test(%value_again) : $@convention(thin) (Int) -> ()

/*
%f_bad = function_ref @bad : $@convention(thin) (@in_guaranteed Int) -> ()
%r3 = apply %f_bad(%0) : $@convention(thin) (@in_guaranteed Int) -> ()

%value_again2 = load %0 : $*Int
%r4 = apply %f_test(%value_again2) : $@convention(thin) (Int) -> ()
*/

%9999 = tuple()
return %9999 : $()
}
--- SNAP ---

into

--- SNIP ---
bb0(%0 : $*Int):
%1 = integer_literal $Builtin.Int64, 42 // user: %2
%2 = struct $Int (%1 : $Builtin.Int64) // users: %7, %3
store %2 to %0 : $*Int // id: %3
// function_ref buz
%4 = function_ref @buz : $@convention(thin) (@in_guaranteed Int) -> () // user: %5
%5 = apply %4(%0) : $@convention(thin) (@in_guaranteed Int) -> ()
// function_ref test
%6 = function_ref @test : $@convention(thin) (Int) -> () // user: %7
%7 = apply %6(%2) : $@convention(thin) (Int) -> ()
%8 = tuple () // user: %9
return %8 : $() // id: %9
} // end sil function 'bar'
--- SNAP ---

so the load has successfully been eliminated. Also taking my initial repro [1], the retain, the load, and the release are now gone :smiley:.

Is that roughly what you were thinking of?

Many thanks,
Johannes

[1]: https://bugs.swift.org/secure/attachment/12378/test.swift

Erik

On Jul 17, 2017, at 9:23 AM, Johannes Weiß <johannesweiss@apple.com> wrote:

Thanks Michael!

Erik, I hope what I wrote makes some sense. Any questions or suggestions, please let me know.

On 14 Jul 2017, at 7:30 pm, Michael Gottesman <mgottesman@apple.com> wrote:

On Jul 12, 2017, at 9:53 AM, Johannes Weiß <johannesweiss@apple.com> wrote:

Hi Michael,

[...]

Long story short, I think the RLE actually works for the test case I created. It's even clever enough to see through my invalid function bad() which modified the storage despite its claim that it doesn't. I might also be misunderstanding something.

When something is marked as in_guaranteed, it should be immutable. If the callee violates that, then the SIL is malformed. Perhaps, we can add some sort of verification check.

Right, yes I was aware that that'd be illegal but I added it as a way to check whether this optimisation is 'looking into' the called function.

That being said, I have a good feeling that there is some sort of analysis occuring here since you provided enough information to the optimizer. The optimization here is regardless of whether or not we can see the body of a function, we know that it is safe to optimize this just based off the @in_guaranteed. This implies using a declaration, not a definition of the bad function.

makes sense, didn't think about just only declaring it...

When I said write the SIL by hand, what I meant was writing the whole program by hand. In general, we prefer SIL programs that do not have extraneous stuff that is added by the compiler (for instance debug_value). Additionally, it is important for SIL files to not have dependencies on the stdlib unless absolutely necessary (i.e. your usage of Int). This prevents the stdlib maintainers from having to update these tests given chances to the stdlib. Below is a cleaned up version that shows the problem. Look at how small it is and how it tests /exactly/ what we are trying to test and via the use of declarations and the like we are able to exclude other optimizations:

That makes a lot of sense, thank you. I wasn't yet that familiar with SIL so I thought I start from a program generated by the compiler and then replace the guts with handwritten SIL. But your version is clearly a lot easier to understand and shows what precisely we want to see!

Today, I looked into why this is happening more precisely.

So we don't get the RLE because in this code

if (isComputeAvailValue(Kind) || isPerformingRLE(Kind)) {
for (unsigned i = 0; i < Locs.size(); ++i) {
if (isTrackingLocation(ForwardSetIn, Ctx.getLocationBit(Locs[i])))
continue;
updateForwardSetAndValForRead(Ctx, Ctx.getLocationBit(Locs[i]),
                             Ctx.getValueBit(Vals[i]));
// We can not perform the forwarding as we are at least missing
// some pieces of the read location.
CanForward = false;

(https://github.com/apple/swift/blob/86620aaa7ebd32d33f4cdf61add5c63a72d3f02a/lib/SILOptimizer/Transforms/RedundantLoadElimination.cpp#L917)

we're not taking the `continue` for the call to `buz()`. The reason why is that here

if (!AA->mayWriteToMemory(I, R.getBase()))
continue;
// MayAlias.
stopTrackingLocation(ForwardSetIn, i);
stopTrackingValue(ForwardValIn, i);

(https://github.com/apple/swift/blob/86620aaa7ebd32d33f4cdf61add5c63a72d3f02a/lib/SILOptimizer/Transforms/RedundantLoadElimination.cpp#L972)

we're not taking the `continue`, ie. `AA->mayWriteToMemory(I, R.getBase())` is true. The reason for that is that the `SILFunction` for `buz` has

EffectsKindAttr = Unspecified

which equates to `MayHaveSideEffects`, that's also what `-debug-only=sil-redundant-load-elim,sil-membehavior` outputs:

GET MEMORY BEHAVIOR FOR:
%5 = apply %4(%0) : $@convention(thin) (@in_guaranteed Int) -> ()
%0 = argument of bb0 : $*Int // users: %6, %5, %3
Found apply, returning MayHaveSideEffects

So where I'm stuck today is that I'm not sure how `EffectsKindAttr` is actually defined. Sure, `$@convention(thin) (@in_guaranteed Int) -> ()` doesn't actually write to the `@in_guaranteed Int` (as that'd be illegal) but it may have other side effects. So I'm not sure if we can just create the function differently if we find only "read-only" kind of parameters. That'd be I think in

auto *fn = SILMod.createFunction(SILLinkage::Private, Name.str(), Ty,
                            nullptr, loc, IsNotBare,
                            IsNotTransparent, IsNotSerialized);

(https://github.com/apple/swift/blob/ec6fc4d54db95f78ae72dab29734533f709ea2d7/lib/Parse/ParseSIL.cpp#L508 -> https://github.com/apple/swift/blob/157db57506b813837481b574a9d38e806bf954b6/lib/SIL/SILModule.cpp#L249)

which doesn't specify any EffectsAttrKind and therefore it defaults to `Unspecified`.

Just as a test, I did put a `[readonly]` in `sil @buz : $@convention(thin) (@in_guaranteed Int) -> ()` and as expected everything propagates through correctly and we get a successful RLE.

So yes, maybe you have some pointers on where to best educate the compiler that the `buz` function won't write to that bit of memory.

I have a few ideas of where to put it, but really the person to bring in here is Erik. He is the one who wrote the side-effect part of the optimizer. Keep in mind he is on vacation right now until next week. So I wouldn't expect a response until then.

Michael

Many thanks,
Johannes

----
sil_stage canonical

import Builtin

struct Int {
var _value : Builtin.Int64
}

sil @test : $@convention(thin) (Int) -> ()
sil @buz : $@convention(thin) (@in_guaranteed Int) -> ()
sil @bad : $@convention(thin) (@in_guaranteed Int) -> ()

sil @bar : $@convention(thin) (@in Int) -> () {
bb0(%0 : $*Int):
%value_raw = integer_literal $Builtin.Int64, 42
%value = struct $Int (%value_raw : $Builtin.Int64)
store %value to %0 : $*Int

%f_buz = function_ref @buz : $@convention(thin) (@in_guaranteed Int) -> ()
%r1 = apply %f_buz(%0) : $@convention(thin) (@in_guaranteed Int) -> ()

%value_again = load %0 : $*Int
%f_test = function_ref @test : $@convention(thin) (Int) -> ()
%r2 = apply %f_test(%value_again) : $@convention(thin) (Int) -> ()

%f_bad = function_ref @bad : $@convention(thin) (@in_guaranteed Int) -> ()
%r3 = apply %f_bad(%0) : $@convention(thin) (@in_guaranteed Int) -> ()

%value_again2 = load %0 : $*Int
%r4 = apply %f_test(%value_again2) : $@convention(thin) (Int) -> ()

%9999 = tuple()
return %9999 : $()
}
----

When I run this test file through rle, I get:

----
sil_stage canonical

import Builtin
import Swift
import SwiftShims

struct Int {
@sil_stored var _value: Builtin.Int64
init(_value: Builtin.Int64)
}

// test
sil @test : $@convention(thin) (Int) -> ()

// buz
sil @buz : $@convention(thin) (@in_guaranteed Int) -> ()

// bad
sil @bad : $@convention(thin) (@in_guaranteed Int) -> ()

// bar
sil @bar : $@convention(thin) (@in Int) -> () {
// %0 // users: %11, %10, %6, %5, %3
bb0(%0 : $*Int):
%1 = integer_literal $Builtin.Int64, 42 // user: %2
%2 = struct $Int (%1 : $Builtin.Int64) // user: %3
store %2 to %0 : $*Int // id: %3
// function_ref buz
%4 = function_ref @buz : $@convention(thin) (@in_guaranteed Int) -> () // user: %5
%5 = apply %4(%0) : $@convention(thin) (@in_guaranteed Int) -> ()
%6 = load %0 : $*Int // user: %8
// function_ref test
%7 = function_ref @test : $@convention(thin) (Int) -> () // users: %12, %8
%8 = apply %7(%6) : $@convention(thin) (Int) -> ()
// function_ref bad
%9 = function_ref @bad : $@convention(thin) (@in_guaranteed Int) -> () // user: %10
%10 = apply %9(%0) : $@convention(thin) (@in_guaranteed Int) -> ()
%11 = load %0 : $*Int // user: %12
%12 = apply %7(%11) : $@convention(thin) (Int) -> ()
%13 = tuple () // user: %14
return %13 : $() // id: %14
} // end sil function 'bar'
----

Michael

Does that all make sense?

Thanks,
Johannes
<test-load-forwarding.sil><test-load-forwarding.sil-opt>

Thanks,
Johannes

[1]: https://bugs.swift.org/browse/SR-5403

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

Thanks very much Eric & Michael for your help! And thanks for merging it. Will this automatically be part of Swift 4 or do I need to make another PR against a swift 4 branch?

It's very hard to imagine we would take any optimizer work this late for Swift 4.

John.

···

On Jul 25, 2017, at 12:55 PM, Johannes Weiß via swift-dev <swift-dev@swift.org> wrote:

Thanks,
Johannes

On 18 Jul 2017, at 9:21 pm, Johannes Weiß via swift-dev <swift-dev@swift.org> wrote:

great, thank you. I think I have worked all the suggestions in, let's do the rest in this PR: https://github.com/apple/swift/pull/11040

It's getting late here so I'll probably to the test tomorrow (but marked the patch as 'do not merge' & added that a test is still missing).

On 18 Jul 2017, at 7:29 pm, Erik Eckstein <eeckstein@apple.com> wrote:

On Jul 18, 2017, at 10:40 AM, Johannes Weiß <johannesweiss@apple.com> wrote:

Thanks, both suggestions look great. Will work them in tomorrow and will also try to add a test for the whole thing.

On 18 Jul 2017, at 5:53 pm, Michael Gottesman <mgottesman@apple.com> wrote:

On Jul 18, 2017, at 8:39 AM, Johannes Weiß <johannesweiss@apple.com> wrote:

Hi Erik,

On 17 Jul 2017, at 10:26 pm, Erik Eckstein <eeckstein@apple.com> wrote:

Hi Johannes,

great that you want to work on this!

Thanks for your help, without Michael's and your help I wouldn't have been able to do anything here really!

Some ideas:
SideEffectAnalysis currently does not have a notion of “this argument is not modified by the callee” if the callee is unknown or does anything non-trivial.
Therefore I think it’s best to put the in_guarantee check directly into MemoryBehaviorVisitor::visitApplyInst():
If the parameter convention is in_guaranteed and the parameter is V, then the behavior can be MemBehavior::MayRead

Thanks, that actually makes a lot of sense. Here's my diff right now

diff --git a/lib/SILOptimizer/Analysis/MemoryBehavior.cpp b/lib/SILOptimizer/Analysis/MemoryBehavior.cpp
index b1fe7fa665..c44cc64f94 100644
--- a/lib/SILOptimizer/Analysis/MemoryBehavior.cpp
+++ b/lib/SILOptimizer/Analysis/MemoryBehavior.cpp
@@ -245,6 +245,23 @@ MemBehavior MemoryBehaviorVisitor::visitApplyInst(ApplyInst *AI) {
  (InspectionMode == RetainObserveKind::ObserveRetains &&
   ApplyEffects.mayAllocObjects())) {
Behavior = MemBehavior::MayHaveSideEffects;

You should move your new code out of the if (ApplyEffects.mayReadRC() ...
Otherwise it will not be executed if the called function does not read a reference count.

Beside that it looks good to me.

+
+ unsigned Idx = 0;
+ bool AllReadOnly = false;
+ for (Operand &operand : AI->getArgumentOperands()) {
+ if (operand.get() == V && AI->getOrigCalleeType()->getParameters()[Idx].isIndirectInGuaranteed()) {
+ AllReadOnly = true;
+ } else {
+ AllReadOnly = false;
+ break;
+ }
+
+ Idx++;
+ }
+
+ if (AllReadOnly) {
+ Behavior = MemBehavior::MayRead;
+ }

Suggestion:

if (all_of(enumerate(AI->getArgumentOperands()),
          [&](std::pair<unsigned, SILValue> pair) -> bool {
             return pair.second.get() == V && AI->getOrigCalleeType()->getParameters()[Idx].isIndirectInGuaranteed()
          })) {
Behavior = MemBehavior::MayRead;
}

I may have gotten the order of the pair templates wrong. But something like this is a little cleaner.

Michael

} else {
auto &GlobalEffects = ApplyEffects.getGlobalEffects();
Behavior = GlobalEffects.getMemBehavior(InspectionMode);

which indeed turns

--- SNIP ---
sil @bar : $@convention(thin) (@in Int) -> () {
bb0(%0 : $*Int):
%value_raw = integer_literal $Builtin.Int64, 42
%value = struct $Int (%value_raw : $Builtin.Int64)
store %value to %0 : $*Int

%f_buz = function_ref @buz : $@convention(thin) (@in_guaranteed Int) -> ()
%r1 = apply %f_buz(%0) : $@convention(thin) (@in_guaranteed Int) -> ()

%value_again = load %0 : $*Int
%f_test = function_ref @test : $@convention(thin) (Int) -> ()
%r2 = apply %f_test(%value_again) : $@convention(thin) (Int) -> ()

/*
%f_bad = function_ref @bad : $@convention(thin) (@in_guaranteed Int) -> ()
%r3 = apply %f_bad(%0) : $@convention(thin) (@in_guaranteed Int) -> ()

%value_again2 = load %0 : $*Int
%r4 = apply %f_test(%value_again2) : $@convention(thin) (Int) -> ()
*/

%9999 = tuple()
return %9999 : $()
}
--- SNAP ---

into

--- SNIP ---
bb0(%0 : $*Int):
%1 = integer_literal $Builtin.Int64, 42 // user: %2
%2 = struct $Int (%1 : $Builtin.Int64) // users: %7, %3
store %2 to %0 : $*Int // id: %3
// function_ref buz
%4 = function_ref @buz : $@convention(thin) (@in_guaranteed Int) -> () // user: %5
%5 = apply %4(%0) : $@convention(thin) (@in_guaranteed Int) -> ()
// function_ref test
%6 = function_ref @test : $@convention(thin) (Int) -> () // user: %7
%7 = apply %6(%2) : $@convention(thin) (Int) -> ()
%8 = tuple () // user: %9
return %8 : $() // id: %9
} // end sil function 'bar'
--- SNAP ---

so the load has successfully been eliminated. Also taking my initial repro [1], the retain, the load, and the release are now gone :smiley:.

Is that roughly what you were thinking of?

Many thanks,
Johannes

[1]: https://bugs.swift.org/secure/attachment/12378/test.swift

Erik

On Jul 17, 2017, at 9:23 AM, Johannes Weiß <johannesweiss@apple.com> wrote:

Thanks Michael!

Erik, I hope what I wrote makes some sense. Any questions or suggestions, please let me know.

On 14 Jul 2017, at 7:30 pm, Michael Gottesman <mgottesman@apple.com> wrote:

On Jul 12, 2017, at 9:53 AM, Johannes Weiß <johannesweiss@apple.com> wrote:

Hi Michael,

[...]

Long story short, I think the RLE actually works for the test case I created. It's even clever enough to see through my invalid function bad() which modified the storage despite its claim that it doesn't. I might also be misunderstanding something.

When something is marked as in_guaranteed, it should be immutable. If the callee violates that, then the SIL is malformed. Perhaps, we can add some sort of verification check.

Right, yes I was aware that that'd be illegal but I added it as a way to check whether this optimisation is 'looking into' the called function.

That being said, I have a good feeling that there is some sort of analysis occuring here since you provided enough information to the optimizer. The optimization here is regardless of whether or not we can see the body of a function, we know that it is safe to optimize this just based off the @in_guaranteed. This implies using a declaration, not a definition of the bad function.

makes sense, didn't think about just only declaring it...

When I said write the SIL by hand, what I meant was writing the whole program by hand. In general, we prefer SIL programs that do not have extraneous stuff that is added by the compiler (for instance debug_value). Additionally, it is important for SIL files to not have dependencies on the stdlib unless absolutely necessary (i.e. your usage of Int). This prevents the stdlib maintainers from having to update these tests given chances to the stdlib. Below is a cleaned up version that shows the problem. Look at how small it is and how it tests /exactly/ what we are trying to test and via the use of declarations and the like we are able to exclude other optimizations:

That makes a lot of sense, thank you. I wasn't yet that familiar with SIL so I thought I start from a program generated by the compiler and then replace the guts with handwritten SIL. But your version is clearly a lot easier to understand and shows what precisely we want to see!

Today, I looked into why this is happening more precisely.

So we don't get the RLE because in this code

if (isComputeAvailValue(Kind) || isPerformingRLE(Kind)) {
for (unsigned i = 0; i < Locs.size(); ++i) {
if (isTrackingLocation(ForwardSetIn, Ctx.getLocationBit(Locs[i])))
continue;
updateForwardSetAndValForRead(Ctx, Ctx.getLocationBit(Locs[i]),
                            Ctx.getValueBit(Vals[i]));
// We can not perform the forwarding as we are at least missing
// some pieces of the read location.
CanForward = false;

(https://github.com/apple/swift/blob/86620aaa7ebd32d33f4cdf61add5c63a72d3f02a/lib/SILOptimizer/Transforms/RedundantLoadElimination.cpp#L917)

we're not taking the `continue` for the call to `buz()`. The reason why is that here

if (!AA->mayWriteToMemory(I, R.getBase()))
continue;
// MayAlias.
stopTrackingLocation(ForwardSetIn, i);
stopTrackingValue(ForwardValIn, i);

(https://github.com/apple/swift/blob/86620aaa7ebd32d33f4cdf61add5c63a72d3f02a/lib/SILOptimizer/Transforms/RedundantLoadElimination.cpp#L972)

we're not taking the `continue`, ie. `AA->mayWriteToMemory(I, R.getBase())` is true. The reason for that is that the `SILFunction` for `buz` has

EffectsKindAttr = Unspecified

which equates to `MayHaveSideEffects`, that's also what `-debug-only=sil-redundant-load-elim,sil-membehavior` outputs:

GET MEMORY BEHAVIOR FOR:
%5 = apply %4(%0) : $@convention(thin) (@in_guaranteed Int) -> ()
%0 = argument of bb0 : $*Int // users: %6, %5, %3
Found apply, returning MayHaveSideEffects

So where I'm stuck today is that I'm not sure how `EffectsKindAttr` is actually defined. Sure, `$@convention(thin) (@in_guaranteed Int) -> ()` doesn't actually write to the `@in_guaranteed Int` (as that'd be illegal) but it may have other side effects. So I'm not sure if we can just create the function differently if we find only "read-only" kind of parameters. That'd be I think in

auto *fn = SILMod.createFunction(SILLinkage::Private, Name.str(), Ty,
                           nullptr, loc, IsNotBare,
                           IsNotTransparent, IsNotSerialized);

(https://github.com/apple/swift/blob/ec6fc4d54db95f78ae72dab29734533f709ea2d7/lib/Parse/ParseSIL.cpp#L508 -> https://github.com/apple/swift/blob/157db57506b813837481b574a9d38e806bf954b6/lib/SIL/SILModule.cpp#L249)

which doesn't specify any EffectsAttrKind and therefore it defaults to `Unspecified`.

Just as a test, I did put a `[readonly]` in `sil @buz : $@convention(thin) (@in_guaranteed Int) -> ()` and as expected everything propagates through correctly and we get a successful RLE.

So yes, maybe you have some pointers on where to best educate the compiler that the `buz` function won't write to that bit of memory.

I have a few ideas of where to put it, but really the person to bring in here is Erik. He is the one who wrote the side-effect part of the optimizer. Keep in mind he is on vacation right now until next week. So I wouldn't expect a response until then.

Michael

Many thanks,
Johannes

----
sil_stage canonical

import Builtin

struct Int {
var _value : Builtin.Int64
}

sil @test : $@convention(thin) (Int) -> ()
sil @buz : $@convention(thin) (@in_guaranteed Int) -> ()
sil @bad : $@convention(thin) (@in_guaranteed Int) -> ()

sil @bar : $@convention(thin) (@in Int) -> () {
bb0(%0 : $*Int):
%value_raw = integer_literal $Builtin.Int64, 42
%value = struct $Int (%value_raw : $Builtin.Int64)
store %value to %0 : $*Int

%f_buz = function_ref @buz : $@convention(thin) (@in_guaranteed Int) -> ()
%r1 = apply %f_buz(%0) : $@convention(thin) (@in_guaranteed Int) -> ()

%value_again = load %0 : $*Int
%f_test = function_ref @test : $@convention(thin) (Int) -> ()
%r2 = apply %f_test(%value_again) : $@convention(thin) (Int) -> ()

%f_bad = function_ref @bad : $@convention(thin) (@in_guaranteed Int) -> ()
%r3 = apply %f_bad(%0) : $@convention(thin) (@in_guaranteed Int) -> ()

%value_again2 = load %0 : $*Int
%r4 = apply %f_test(%value_again2) : $@convention(thin) (Int) -> ()

%9999 = tuple()
return %9999 : $()
}
----

When I run this test file through rle, I get:

----
sil_stage canonical

import Builtin
import Swift
import SwiftShims

struct Int {
@sil_stored var _value: Builtin.Int64
init(_value: Builtin.Int64)
}

// test
sil @test : $@convention(thin) (Int) -> ()

// buz
sil @buz : $@convention(thin) (@in_guaranteed Int) -> ()

// bad
sil @bad : $@convention(thin) (@in_guaranteed Int) -> ()

// bar
sil @bar : $@convention(thin) (@in Int) -> () {
// %0 // users: %11, %10, %6, %5, %3
bb0(%0 : $*Int):
%1 = integer_literal $Builtin.Int64, 42 // user: %2
%2 = struct $Int (%1 : $Builtin.Int64) // user: %3
store %2 to %0 : $*Int // id: %3
// function_ref buz
%4 = function_ref @buz : $@convention(thin) (@in_guaranteed Int) -> () // user: %5
%5 = apply %4(%0) : $@convention(thin) (@in_guaranteed Int) -> ()
%6 = load %0 : $*Int // user: %8
// function_ref test
%7 = function_ref @test : $@convention(thin) (Int) -> () // users: %12, %8
%8 = apply %7(%6) : $@convention(thin) (Int) -> ()
// function_ref bad
%9 = function_ref @bad : $@convention(thin) (@in_guaranteed Int) -> () // user: %10
%10 = apply %9(%0) : $@convention(thin) (@in_guaranteed Int) -> ()
%11 = load %0 : $*Int // user: %12
%12 = apply %7(%11) : $@convention(thin) (Int) -> ()
%13 = tuple () // user: %14
return %13 : $() // id: %14
} // end sil function 'bar'
----

Michael

Does that all make sense?

Thanks,
Johannes
<test-load-forwarding.sil><test-load-forwarding.sil-opt>

Thanks,
Johannes

[1]: https://bugs.swift.org/browse/SR-5403

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

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

As John said, this is out of scope for swift 4.
I think it’s find to just have it in master.

Thanks again for your work!

···

On Jul 25, 2017, at 10:00 AM, John McCall via swift-dev <swift-dev@swift.org> wrote:

On Jul 25, 2017, at 12:55 PM, Johannes Weiß via swift-dev <swift-dev@swift.org> wrote:

Thanks very much Eric & Michael for your help! And thanks for merging it. Will this automatically be part of Swift 4 or do I need to make another PR against a swift 4 branch?

It's very hard to imagine we would take any optimizer work this late for Swift 4.

John.

Thanks,
Johannes

On 18 Jul 2017, at 9:21 pm, Johannes Weiß via swift-dev <swift-dev@swift.org> wrote:

great, thank you. I think I have worked all the suggestions in, let's do the rest in this PR: https://github.com/apple/swift/pull/11040

It's getting late here so I'll probably to the test tomorrow (but marked the patch as 'do not merge' & added that a test is still missing).

On 18 Jul 2017, at 7:29 pm, Erik Eckstein <eeckstein@apple.com> wrote:

On Jul 18, 2017, at 10:40 AM, Johannes Weiß <johannesweiss@apple.com> wrote:

Thanks, both suggestions look great. Will work them in tomorrow and will also try to add a test for the whole thing.

On 18 Jul 2017, at 5:53 pm, Michael Gottesman <mgottesman@apple.com> wrote:

On Jul 18, 2017, at 8:39 AM, Johannes Weiß <johannesweiss@apple.com> wrote:

Hi Erik,

On 17 Jul 2017, at 10:26 pm, Erik Eckstein <eeckstein@apple.com> wrote:

Hi Johannes,

great that you want to work on this!

Thanks for your help, without Michael's and your help I wouldn't have been able to do anything here really!

Some ideas:
SideEffectAnalysis currently does not have a notion of “this argument is not modified by the callee” if the callee is unknown or does anything non-trivial.
Therefore I think it’s best to put the in_guarantee check directly into MemoryBehaviorVisitor::visitApplyInst():
If the parameter convention is in_guaranteed and the parameter is V, then the behavior can be MemBehavior::MayRead

Thanks, that actually makes a lot of sense. Here's my diff right now

diff --git a/lib/SILOptimizer/Analysis/MemoryBehavior.cpp b/lib/SILOptimizer/Analysis/MemoryBehavior.cpp
index b1fe7fa665..c44cc64f94 100644
--- a/lib/SILOptimizer/Analysis/MemoryBehavior.cpp
+++ b/lib/SILOptimizer/Analysis/MemoryBehavior.cpp
@@ -245,6 +245,23 @@ MemBehavior MemoryBehaviorVisitor::visitApplyInst(ApplyInst *AI) {
(InspectionMode == RetainObserveKind::ObserveRetains &&
  ApplyEffects.mayAllocObjects())) {
Behavior = MemBehavior::MayHaveSideEffects;

You should move your new code out of the if (ApplyEffects.mayReadRC() ...
Otherwise it will not be executed if the called function does not read a reference count.

Beside that it looks good to me.

+
+ unsigned Idx = 0;
+ bool AllReadOnly = false;
+ for (Operand &operand : AI->getArgumentOperands()) {
+ if (operand.get() == V && AI->getOrigCalleeType()->getParameters()[Idx].isIndirectInGuaranteed()) {
+ AllReadOnly = true;
+ } else {
+ AllReadOnly = false;
+ break;
+ }
+
+ Idx++;
+ }
+
+ if (AllReadOnly) {
+ Behavior = MemBehavior::MayRead;
+ }

Suggestion:

if (all_of(enumerate(AI->getArgumentOperands()),
         [&](std::pair<unsigned, SILValue> pair) -> bool {
            return pair.second.get() == V && AI->getOrigCalleeType()->getParameters()[Idx].isIndirectInGuaranteed()
         })) {
Behavior = MemBehavior::MayRead;
}

I may have gotten the order of the pair templates wrong. But something like this is a little cleaner.

Michael

} else {
auto &GlobalEffects = ApplyEffects.getGlobalEffects();
Behavior = GlobalEffects.getMemBehavior(InspectionMode);

which indeed turns

--- SNIP ---
sil @bar : $@convention(thin) (@in Int) -> () {
bb0(%0 : $*Int):
%value_raw = integer_literal $Builtin.Int64, 42
%value = struct $Int (%value_raw : $Builtin.Int64)
store %value to %0 : $*Int

%f_buz = function_ref @buz : $@convention(thin) (@in_guaranteed Int) -> ()
%r1 = apply %f_buz(%0) : $@convention(thin) (@in_guaranteed Int) -> ()

%value_again = load %0 : $*Int
%f_test = function_ref @test : $@convention(thin) (Int) -> ()
%r2 = apply %f_test(%value_again) : $@convention(thin) (Int) -> ()

/*
%f_bad = function_ref @bad : $@convention(thin) (@in_guaranteed Int) -> ()
%r3 = apply %f_bad(%0) : $@convention(thin) (@in_guaranteed Int) -> ()

%value_again2 = load %0 : $*Int
%r4 = apply %f_test(%value_again2) : $@convention(thin) (Int) -> ()
*/

%9999 = tuple()
return %9999 : $()
}
--- SNAP ---

into

--- SNIP ---
bb0(%0 : $*Int):
%1 = integer_literal $Builtin.Int64, 42 // user: %2
%2 = struct $Int (%1 : $Builtin.Int64) // users: %7, %3
store %2 to %0 : $*Int // id: %3
// function_ref buz
%4 = function_ref @buz : $@convention(thin) (@in_guaranteed Int) -> () // user: %5
%5 = apply %4(%0) : $@convention(thin) (@in_guaranteed Int) -> ()
// function_ref test
%6 = function_ref @test : $@convention(thin) (Int) -> () // user: %7
%7 = apply %6(%2) : $@convention(thin) (Int) -> ()
%8 = tuple () // user: %9
return %8 : $() // id: %9
} // end sil function 'bar'
--- SNAP ---

so the load has successfully been eliminated. Also taking my initial repro [1], the retain, the load, and the release are now gone :smiley:.

Is that roughly what you were thinking of?

Many thanks,
Johannes

[1]: https://bugs.swift.org/secure/attachment/12378/test.swift

Erik

On Jul 17, 2017, at 9:23 AM, Johannes Weiß <johannesweiss@apple.com> wrote:

Thanks Michael!

Erik, I hope what I wrote makes some sense. Any questions or suggestions, please let me know.

On 14 Jul 2017, at 7:30 pm, Michael Gottesman <mgottesman@apple.com> wrote:

On Jul 12, 2017, at 9:53 AM, Johannes Weiß <johannesweiss@apple.com> wrote:

Hi Michael,

[...]

Long story short, I think the RLE actually works for the test case I created. It's even clever enough to see through my invalid function bad() which modified the storage despite its claim that it doesn't. I might also be misunderstanding something.

When something is marked as in_guaranteed, it should be immutable. If the callee violates that, then the SIL is malformed. Perhaps, we can add some sort of verification check.

Right, yes I was aware that that'd be illegal but I added it as a way to check whether this optimisation is 'looking into' the called function.

That being said, I have a good feeling that there is some sort of analysis occuring here since you provided enough information to the optimizer. The optimization here is regardless of whether or not we can see the body of a function, we know that it is safe to optimize this just based off the @in_guaranteed. This implies using a declaration, not a definition of the bad function.

makes sense, didn't think about just only declaring it...

When I said write the SIL by hand, what I meant was writing the whole program by hand. In general, we prefer SIL programs that do not have extraneous stuff that is added by the compiler (for instance debug_value). Additionally, it is important for SIL files to not have dependencies on the stdlib unless absolutely necessary (i.e. your usage of Int). This prevents the stdlib maintainers from having to update these tests given chances to the stdlib. Below is a cleaned up version that shows the problem. Look at how small it is and how it tests /exactly/ what we are trying to test and via the use of declarations and the like we are able to exclude other optimizations:

That makes a lot of sense, thank you. I wasn't yet that familiar with SIL so I thought I start from a program generated by the compiler and then replace the guts with handwritten SIL. But your version is clearly a lot easier to understand and shows what precisely we want to see!

Today, I looked into why this is happening more precisely.

So we don't get the RLE because in this code

if (isComputeAvailValue(Kind) || isPerformingRLE(Kind)) {
for (unsigned i = 0; i < Locs.size(); ++i) {
if (isTrackingLocation(ForwardSetIn, Ctx.getLocationBit(Locs[i])))
continue;
updateForwardSetAndValForRead(Ctx, Ctx.getLocationBit(Locs[i]),
                           Ctx.getValueBit(Vals[i]));
// We can not perform the forwarding as we are at least missing
// some pieces of the read location.
CanForward = false;

(https://github.com/apple/swift/blob/86620aaa7ebd32d33f4cdf61add5c63a72d3f02a/lib/SILOptimizer/Transforms/RedundantLoadElimination.cpp#L917)

we're not taking the `continue` for the call to `buz()`. The reason why is that here

if (!AA->mayWriteToMemory(I, R.getBase()))
continue;
// MayAlias.
stopTrackingLocation(ForwardSetIn, i);
stopTrackingValue(ForwardValIn, i);

(https://github.com/apple/swift/blob/86620aaa7ebd32d33f4cdf61add5c63a72d3f02a/lib/SILOptimizer/Transforms/RedundantLoadElimination.cpp#L972)

we're not taking the `continue`, ie. `AA->mayWriteToMemory(I, R.getBase())` is true. The reason for that is that the `SILFunction` for `buz` has

EffectsKindAttr = Unspecified

which equates to `MayHaveSideEffects`, that's also what `-debug-only=sil-redundant-load-elim,sil-membehavior` outputs:

GET MEMORY BEHAVIOR FOR:
%5 = apply %4(%0) : $@convention(thin) (@in_guaranteed Int) -> ()
%0 = argument of bb0 : $*Int // users: %6, %5, %3
Found apply, returning MayHaveSideEffects

So where I'm stuck today is that I'm not sure how `EffectsKindAttr` is actually defined. Sure, `$@convention(thin) (@in_guaranteed Int) -> ()` doesn't actually write to the `@in_guaranteed Int` (as that'd be illegal) but it may have other side effects. So I'm not sure if we can just create the function differently if we find only "read-only" kind of parameters. That'd be I think in

auto *fn = SILMod.createFunction(SILLinkage::Private, Name.str(), Ty,
                          nullptr, loc, IsNotBare,
                          IsNotTransparent, IsNotSerialized);

(https://github.com/apple/swift/blob/ec6fc4d54db95f78ae72dab29734533f709ea2d7/lib/Parse/ParseSIL.cpp#L508 -> https://github.com/apple/swift/blob/157db57506b813837481b574a9d38e806bf954b6/lib/SIL/SILModule.cpp#L249)

which doesn't specify any EffectsAttrKind and therefore it defaults to `Unspecified`.

Just as a test, I did put a `[readonly]` in `sil @buz : $@convention(thin) (@in_guaranteed Int) -> ()` and as expected everything propagates through correctly and we get a successful RLE.

So yes, maybe you have some pointers on where to best educate the compiler that the `buz` function won't write to that bit of memory.

I have a few ideas of where to put it, but really the person to bring in here is Erik. He is the one who wrote the side-effect part of the optimizer. Keep in mind he is on vacation right now until next week. So I wouldn't expect a response until then.

Michael

Many thanks,
Johannes

----
sil_stage canonical

import Builtin

struct Int {
var _value : Builtin.Int64
}

sil @test : $@convention(thin) (Int) -> ()
sil @buz : $@convention(thin) (@in_guaranteed Int) -> ()
sil @bad : $@convention(thin) (@in_guaranteed Int) -> ()

sil @bar : $@convention(thin) (@in Int) -> () {
bb0(%0 : $*Int):
%value_raw = integer_literal $Builtin.Int64, 42
%value = struct $Int (%value_raw : $Builtin.Int64)
store %value to %0 : $*Int

%f_buz = function_ref @buz : $@convention(thin) (@in_guaranteed Int) -> ()
%r1 = apply %f_buz(%0) : $@convention(thin) (@in_guaranteed Int) -> ()

%value_again = load %0 : $*Int
%f_test = function_ref @test : $@convention(thin) (Int) -> ()
%r2 = apply %f_test(%value_again) : $@convention(thin) (Int) -> ()

%f_bad = function_ref @bad : $@convention(thin) (@in_guaranteed Int) -> ()
%r3 = apply %f_bad(%0) : $@convention(thin) (@in_guaranteed Int) -> ()

%value_again2 = load %0 : $*Int
%r4 = apply %f_test(%value_again2) : $@convention(thin) (Int) -> ()

%9999 = tuple()
return %9999 : $()
}
----

When I run this test file through rle, I get:

----
sil_stage canonical

import Builtin
import Swift
import SwiftShims

struct Int {
@sil_stored var _value: Builtin.Int64
init(_value: Builtin.Int64)
}

// test
sil @test : $@convention(thin) (Int) -> ()

// buz
sil @buz : $@convention(thin) (@in_guaranteed Int) -> ()

// bad
sil @bad : $@convention(thin) (@in_guaranteed Int) -> ()

// bar
sil @bar : $@convention(thin) (@in Int) -> () {
// %0 // users: %11, %10, %6, %5, %3
bb0(%0 : $*Int):
%1 = integer_literal $Builtin.Int64, 42 // user: %2
%2 = struct $Int (%1 : $Builtin.Int64) // user: %3
store %2 to %0 : $*Int // id: %3
// function_ref buz
%4 = function_ref @buz : $@convention(thin) (@in_guaranteed Int) -> () // user: %5
%5 = apply %4(%0) : $@convention(thin) (@in_guaranteed Int) -> ()
%6 = load %0 : $*Int // user: %8
// function_ref test
%7 = function_ref @test : $@convention(thin) (Int) -> () // users: %12, %8
%8 = apply %7(%6) : $@convention(thin) (Int) -> ()
// function_ref bad
%9 = function_ref @bad : $@convention(thin) (@in_guaranteed Int) -> () // user: %10
%10 = apply %9(%0) : $@convention(thin) (@in_guaranteed Int) -> ()
%11 = load %0 : $*Int // user: %12
%12 = apply %7(%11) : $@convention(thin) (Int) -> ()
%13 = tuple () // user: %14
return %13 : $() // id: %14
} // end sil function 'bar'
----

Michael

Does that all make sense?

Thanks,
Johannes
<test-load-forwarding.sil><test-load-forwarding.sil-opt>

Thanks,
Johannes

[1]: https://bugs.swift.org/browse/SR-5403

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

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

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

+1!

···

On Jul 26, 2017, at 8:29 AM, Erik Eckstein via swift-dev <swift-dev@swift.org> wrote:

As John said, this is out of scope for swift 4.
I think it’s find to just have it in master.

Thanks again for your work!

On Jul 25, 2017, at 10:00 AM, John McCall via swift-dev <swift-dev@swift.org> wrote:

On Jul 25, 2017, at 12:55 PM, Johannes Weiß via swift-dev <swift-dev@swift.org> wrote:

Thanks very much Eric & Michael for your help! And thanks for merging it. Will this automatically be part of Swift 4 or do I need to make another PR against a swift 4 branch?

It's very hard to imagine we would take any optimizer work this late for Swift 4.

John.

Thanks,
Johannes

On 18 Jul 2017, at 9:21 pm, Johannes Weiß via swift-dev <swift-dev@swift.org> wrote:

great, thank you. I think I have worked all the suggestions in, let's do the rest in this PR: https://github.com/apple/swift/pull/11040

It's getting late here so I'll probably to the test tomorrow (but marked the patch as 'do not merge' & added that a test is still missing).

On 18 Jul 2017, at 7:29 pm, Erik Eckstein <eeckstein@apple.com> wrote:

On Jul 18, 2017, at 10:40 AM, Johannes Weiß <johannesweiss@apple.com> wrote:

Thanks, both suggestions look great. Will work them in tomorrow and will also try to add a test for the whole thing.

On 18 Jul 2017, at 5:53 pm, Michael Gottesman <mgottesman@apple.com> wrote:

On Jul 18, 2017, at 8:39 AM, Johannes Weiß <johannesweiss@apple.com> wrote:

Hi Erik,

On 17 Jul 2017, at 10:26 pm, Erik Eckstein <eeckstein@apple.com> wrote:

Hi Johannes,

great that you want to work on this!

Thanks for your help, without Michael's and your help I wouldn't have been able to do anything here really!

Some ideas:
SideEffectAnalysis currently does not have a notion of “this argument is not modified by the callee” if the callee is unknown or does anything non-trivial.
Therefore I think it’s best to put the in_guarantee check directly into MemoryBehaviorVisitor::visitApplyInst():
If the parameter convention is in_guaranteed and the parameter is V, then the behavior can be MemBehavior::MayRead

Thanks, that actually makes a lot of sense. Here's my diff right now

diff --git a/lib/SILOptimizer/Analysis/MemoryBehavior.cpp b/lib/SILOptimizer/Analysis/MemoryBehavior.cpp
index b1fe7fa665..c44cc64f94 100644
--- a/lib/SILOptimizer/Analysis/MemoryBehavior.cpp
+++ b/lib/SILOptimizer/Analysis/MemoryBehavior.cpp
@@ -245,6 +245,23 @@ MemBehavior MemoryBehaviorVisitor::visitApplyInst(ApplyInst *AI) {
(InspectionMode == RetainObserveKind::ObserveRetains &&
ApplyEffects.mayAllocObjects())) {
Behavior = MemBehavior::MayHaveSideEffects;

You should move your new code out of the if (ApplyEffects.mayReadRC() ...
Otherwise it will not be executed if the called function does not read a reference count.

Beside that it looks good to me.

+
+ unsigned Idx = 0;
+ bool AllReadOnly = false;
+ for (Operand &operand : AI->getArgumentOperands()) {
+ if (operand.get() == V && AI->getOrigCalleeType()->getParameters()[Idx].isIndirectInGuaranteed()) {
+ AllReadOnly = true;
+ } else {
+ AllReadOnly = false;
+ break;
+ }
+
+ Idx++;
+ }
+
+ if (AllReadOnly) {
+ Behavior = MemBehavior::MayRead;
+ }

Suggestion:

if (all_of(enumerate(AI->getArgumentOperands()),
        [&](std::pair<unsigned, SILValue> pair) -> bool {
           return pair.second.get() == V && AI->getOrigCalleeType()->getParameters()[Idx].isIndirectInGuaranteed()
        })) {
Behavior = MemBehavior::MayRead;
}

I may have gotten the order of the pair templates wrong. But something like this is a little cleaner.

Michael

} else {
auto &GlobalEffects = ApplyEffects.getGlobalEffects();
Behavior = GlobalEffects.getMemBehavior(InspectionMode);

which indeed turns

--- SNIP ---
sil @bar : $@convention(thin) (@in Int) -> () {
bb0(%0 : $*Int):
%value_raw = integer_literal $Builtin.Int64, 42
%value = struct $Int (%value_raw : $Builtin.Int64)
store %value to %0 : $*Int

%f_buz = function_ref @buz : $@convention(thin) (@in_guaranteed Int) -> ()
%r1 = apply %f_buz(%0) : $@convention(thin) (@in_guaranteed Int) -> ()

%value_again = load %0 : $*Int
%f_test = function_ref @test : $@convention(thin) (Int) -> ()
%r2 = apply %f_test(%value_again) : $@convention(thin) (Int) -> ()

/*
%f_bad = function_ref @bad : $@convention(thin) (@in_guaranteed Int) -> ()
%r3 = apply %f_bad(%0) : $@convention(thin) (@in_guaranteed Int) -> ()

%value_again2 = load %0 : $*Int
%r4 = apply %f_test(%value_again2) : $@convention(thin) (Int) -> ()
*/

%9999 = tuple()
return %9999 : $()
}
--- SNAP ---

into

--- SNIP ---
bb0(%0 : $*Int):
%1 = integer_literal $Builtin.Int64, 42 // user: %2
%2 = struct $Int (%1 : $Builtin.Int64) // users: %7, %3
store %2 to %0 : $*Int // id: %3
// function_ref buz
%4 = function_ref @buz : $@convention(thin) (@in_guaranteed Int) -> () // user: %5
%5 = apply %4(%0) : $@convention(thin) (@in_guaranteed Int) -> ()
// function_ref test
%6 = function_ref @test : $@convention(thin) (Int) -> () // user: %7
%7 = apply %6(%2) : $@convention(thin) (Int) -> ()
%8 = tuple () // user: %9
return %8 : $() // id: %9
} // end sil function 'bar'
--- SNAP ---

so the load has successfully been eliminated. Also taking my initial repro [1], the retain, the load, and the release are now gone :smiley:.

Is that roughly what you were thinking of?

Many thanks,
Johannes

[1]: https://bugs.swift.org/secure/attachment/12378/test.swift

Erik

On Jul 17, 2017, at 9:23 AM, Johannes Weiß <johannesweiss@apple.com> wrote:

Thanks Michael!

Erik, I hope what I wrote makes some sense. Any questions or suggestions, please let me know.

On 14 Jul 2017, at 7:30 pm, Michael Gottesman <mgottesman@apple.com> wrote:

On Jul 12, 2017, at 9:53 AM, Johannes Weiß <johannesweiss@apple.com> wrote:

Hi Michael,

[...]

Long story short, I think the RLE actually works for the test case I created. It's even clever enough to see through my invalid function bad() which modified the storage despite its claim that it doesn't. I might also be misunderstanding something.

When something is marked as in_guaranteed, it should be immutable. If the callee violates that, then the SIL is malformed. Perhaps, we can add some sort of verification check.

Right, yes I was aware that that'd be illegal but I added it as a way to check whether this optimisation is 'looking into' the called function.

That being said, I have a good feeling that there is some sort of analysis occuring here since you provided enough information to the optimizer. The optimization here is regardless of whether or not we can see the body of a function, we know that it is safe to optimize this just based off the @in_guaranteed. This implies using a declaration, not a definition of the bad function.

makes sense, didn't think about just only declaring it...

When I said write the SIL by hand, what I meant was writing the whole program by hand. In general, we prefer SIL programs that do not have extraneous stuff that is added by the compiler (for instance debug_value). Additionally, it is important for SIL files to not have dependencies on the stdlib unless absolutely necessary (i.e. your usage of Int). This prevents the stdlib maintainers from having to update these tests given chances to the stdlib. Below is a cleaned up version that shows the problem. Look at how small it is and how it tests /exactly/ what we are trying to test and via the use of declarations and the like we are able to exclude other optimizations:

That makes a lot of sense, thank you. I wasn't yet that familiar with SIL so I thought I start from a program generated by the compiler and then replace the guts with handwritten SIL. But your version is clearly a lot easier to understand and shows what precisely we want to see!

Today, I looked into why this is happening more precisely.

So we don't get the RLE because in this code

if (isComputeAvailValue(Kind) || isPerformingRLE(Kind)) {
for (unsigned i = 0; i < Locs.size(); ++i) {
if (isTrackingLocation(ForwardSetIn, Ctx.getLocationBit(Locs[i])))
continue;
updateForwardSetAndValForRead(Ctx, Ctx.getLocationBit(Locs[i]),
                          Ctx.getValueBit(Vals[i]));
// We can not perform the forwarding as we are at least missing
// some pieces of the read location.
CanForward = false;

(https://github.com/apple/swift/blob/86620aaa7ebd32d33f4cdf61add5c63a72d3f02a/lib/SILOptimizer/Transforms/RedundantLoadElimination.cpp#L917)

we're not taking the `continue` for the call to `buz()`. The reason why is that here

if (!AA->mayWriteToMemory(I, R.getBase()))
continue;
// MayAlias.
stopTrackingLocation(ForwardSetIn, i);
stopTrackingValue(ForwardValIn, i);

(https://github.com/apple/swift/blob/86620aaa7ebd32d33f4cdf61add5c63a72d3f02a/lib/SILOptimizer/Transforms/RedundantLoadElimination.cpp#L972)

we're not taking the `continue`, ie. `AA->mayWriteToMemory(I, R.getBase())` is true. The reason for that is that the `SILFunction` for `buz` has

EffectsKindAttr = Unspecified

which equates to `MayHaveSideEffects`, that's also what `-debug-only=sil-redundant-load-elim,sil-membehavior` outputs:

GET MEMORY BEHAVIOR FOR:
%5 = apply %4(%0) : $@convention(thin) (@in_guaranteed Int) -> ()
%0 = argument of bb0 : $*Int // users: %6, %5, %3
Found apply, returning MayHaveSideEffects

So where I'm stuck today is that I'm not sure how `EffectsKindAttr` is actually defined. Sure, `$@convention(thin) (@in_guaranteed Int) -> ()` doesn't actually write to the `@in_guaranteed Int` (as that'd be illegal) but it may have other side effects. So I'm not sure if we can just create the function differently if we find only "read-only" kind of parameters. That'd be I think in

auto *fn = SILMod.createFunction(SILLinkage::Private, Name.str(), Ty,
                         nullptr, loc, IsNotBare,
                         IsNotTransparent, IsNotSerialized);

(https://github.com/apple/swift/blob/ec6fc4d54db95f78ae72dab29734533f709ea2d7/lib/Parse/ParseSIL.cpp#L508 -> https://github.com/apple/swift/blob/157db57506b813837481b574a9d38e806bf954b6/lib/SIL/SILModule.cpp#L249)

which doesn't specify any EffectsAttrKind and therefore it defaults to `Unspecified`.

Just as a test, I did put a `[readonly]` in `sil @buz : $@convention(thin) (@in_guaranteed Int) -> ()` and as expected everything propagates through correctly and we get a successful RLE.

So yes, maybe you have some pointers on where to best educate the compiler that the `buz` function won't write to that bit of memory.

I have a few ideas of where to put it, but really the person to bring in here is Erik. He is the one who wrote the side-effect part of the optimizer. Keep in mind he is on vacation right now until next week. So I wouldn't expect a response until then.

Michael

Many thanks,
Johannes

----
sil_stage canonical

import Builtin

struct Int {
var _value : Builtin.Int64
}

sil @test : $@convention(thin) (Int) -> ()
sil @buz : $@convention(thin) (@in_guaranteed Int) -> ()
sil @bad : $@convention(thin) (@in_guaranteed Int) -> ()

sil @bar : $@convention(thin) (@in Int) -> () {
bb0(%0 : $*Int):
%value_raw = integer_literal $Builtin.Int64, 42
%value = struct $Int (%value_raw : $Builtin.Int64)
store %value to %0 : $*Int

%f_buz = function_ref @buz : $@convention(thin) (@in_guaranteed Int) -> ()
%r1 = apply %f_buz(%0) : $@convention(thin) (@in_guaranteed Int) -> ()

%value_again = load %0 : $*Int
%f_test = function_ref @test : $@convention(thin) (Int) -> ()
%r2 = apply %f_test(%value_again) : $@convention(thin) (Int) -> ()

%f_bad = function_ref @bad : $@convention(thin) (@in_guaranteed Int) -> ()
%r3 = apply %f_bad(%0) : $@convention(thin) (@in_guaranteed Int) -> ()

%value_again2 = load %0 : $*Int
%r4 = apply %f_test(%value_again2) : $@convention(thin) (Int) -> ()

%9999 = tuple()
return %9999 : $()
}
----

When I run this test file through rle, I get:

----
sil_stage canonical

import Builtin
import Swift
import SwiftShims

struct Int {
@sil_stored var _value: Builtin.Int64
init(_value: Builtin.Int64)
}

// test
sil @test : $@convention(thin) (Int) -> ()

// buz
sil @buz : $@convention(thin) (@in_guaranteed Int) -> ()

// bad
sil @bad : $@convention(thin) (@in_guaranteed Int) -> ()

// bar
sil @bar : $@convention(thin) (@in Int) -> () {
// %0 // users: %11, %10, %6, %5, %3
bb0(%0 : $*Int):
%1 = integer_literal $Builtin.Int64, 42 // user: %2
%2 = struct $Int (%1 : $Builtin.Int64) // user: %3
store %2 to %0 : $*Int // id: %3
// function_ref buz
%4 = function_ref @buz : $@convention(thin) (@in_guaranteed Int) -> () // user: %5
%5 = apply %4(%0) : $@convention(thin) (@in_guaranteed Int) -> ()
%6 = load %0 : $*Int // user: %8
// function_ref test
%7 = function_ref @test : $@convention(thin) (Int) -> () // users: %12, %8
%8 = apply %7(%6) : $@convention(thin) (Int) -> ()
// function_ref bad
%9 = function_ref @bad : $@convention(thin) (@in_guaranteed Int) -> () // user: %10
%10 = apply %9(%0) : $@convention(thin) (@in_guaranteed Int) -> ()
%11 = load %0 : $*Int // user: %12
%12 = apply %7(%11) : $@convention(thin) (Int) -> ()
%13 = tuple () // user: %14
return %13 : $() // id: %14
} // end sil function 'bar'
----

Michael

Does that all make sense?

Thanks,
Johannes
<test-load-forwarding.sil><test-load-forwarding.sil-opt>

Thanks,
Johannes

[1]: https://bugs.swift.org/browse/SR-5403

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

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

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

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

:+1:

···

On 26 Jul 2017, at 4:28 pm, Erik Eckstein <eeckstein@apple.com> wrote:

As John said, this is out of scope for swift 4.
I think it’s find to just have it in master.

Thanks again for your work!

On Jul 25, 2017, at 10:00 AM, John McCall via swift-dev <swift-dev@swift.org> wrote:

On Jul 25, 2017, at 12:55 PM, Johannes Weiß via swift-dev <swift-dev@swift.org> wrote:

Thanks very much Eric & Michael for your help! And thanks for merging it. Will this automatically be part of Swift 4 or do I need to make another PR against a swift 4 branch?

It's very hard to imagine we would take any optimizer work this late for Swift 4.

John.

Thanks,
Johannes

On 18 Jul 2017, at 9:21 pm, Johannes Weiß via swift-dev <swift-dev@swift.org> wrote:

great, thank you. I think I have worked all the suggestions in, let's do the rest in this PR: https://github.com/apple/swift/pull/11040

It's getting late here so I'll probably to the test tomorrow (but marked the patch as 'do not merge' & added that a test is still missing).

On 18 Jul 2017, at 7:29 pm, Erik Eckstein <eeckstein@apple.com> wrote:

On Jul 18, 2017, at 10:40 AM, Johannes Weiß <johannesweiss@apple.com> wrote:

Thanks, both suggestions look great. Will work them in tomorrow and will also try to add a test for the whole thing.

On 18 Jul 2017, at 5:53 pm, Michael Gottesman <mgottesman@apple.com> wrote:

On Jul 18, 2017, at 8:39 AM, Johannes Weiß <johannesweiss@apple.com> wrote:

Hi Erik,

On 17 Jul 2017, at 10:26 pm, Erik Eckstein <eeckstein@apple.com> wrote:

Hi Johannes,

great that you want to work on this!

Thanks for your help, without Michael's and your help I wouldn't have been able to do anything here really!

Some ideas:
SideEffectAnalysis currently does not have a notion of “this argument is not modified by the callee” if the callee is unknown or does anything non-trivial.
Therefore I think it’s best to put the in_guarantee check directly into MemoryBehaviorVisitor::visitApplyInst():
If the parameter convention is in_guaranteed and the parameter is V, then the behavior can be MemBehavior::MayRead

Thanks, that actually makes a lot of sense. Here's my diff right now

diff --git a/lib/SILOptimizer/Analysis/MemoryBehavior.cpp b/lib/SILOptimizer/Analysis/MemoryBehavior.cpp
index b1fe7fa665..c44cc64f94 100644
--- a/lib/SILOptimizer/Analysis/MemoryBehavior.cpp
+++ b/lib/SILOptimizer/Analysis/MemoryBehavior.cpp
@@ -245,6 +245,23 @@ MemBehavior MemoryBehaviorVisitor::visitApplyInst(ApplyInst *AI) {
(InspectionMode == RetainObserveKind::ObserveRetains &&
ApplyEffects.mayAllocObjects())) {
Behavior = MemBehavior::MayHaveSideEffects;

You should move your new code out of the if (ApplyEffects.mayReadRC() ...
Otherwise it will not be executed if the called function does not read a reference count.

Beside that it looks good to me.

+
+ unsigned Idx = 0;
+ bool AllReadOnly = false;
+ for (Operand &operand : AI->getArgumentOperands()) {
+ if (operand.get() == V && AI->getOrigCalleeType()->getParameters()[Idx].isIndirectInGuaranteed()) {
+ AllReadOnly = true;
+ } else {
+ AllReadOnly = false;
+ break;
+ }
+
+ Idx++;
+ }
+
+ if (AllReadOnly) {
+ Behavior = MemBehavior::MayRead;
+ }

Suggestion:

if (all_of(enumerate(AI->getArgumentOperands()),
        [&](std::pair<unsigned, SILValue> pair) -> bool {
           return pair.second.get() == V && AI->getOrigCalleeType()->getParameters()[Idx].isIndirectInGuaranteed()
        })) {
Behavior = MemBehavior::MayRead;
}

I may have gotten the order of the pair templates wrong. But something like this is a little cleaner.

Michael

} else {
auto &GlobalEffects = ApplyEffects.getGlobalEffects();
Behavior = GlobalEffects.getMemBehavior(InspectionMode);

which indeed turns

--- SNIP ---
sil @bar : $@convention(thin) (@in Int) -> () {
bb0(%0 : $*Int):
%value_raw = integer_literal $Builtin.Int64, 42
%value = struct $Int (%value_raw : $Builtin.Int64)
store %value to %0 : $*Int

%f_buz = function_ref @buz : $@convention(thin) (@in_guaranteed Int) -> ()
%r1 = apply %f_buz(%0) : $@convention(thin) (@in_guaranteed Int) -> ()

%value_again = load %0 : $*Int
%f_test = function_ref @test : $@convention(thin) (Int) -> ()
%r2 = apply %f_test(%value_again) : $@convention(thin) (Int) -> ()

/*
%f_bad = function_ref @bad : $@convention(thin) (@in_guaranteed Int) -> ()
%r3 = apply %f_bad(%0) : $@convention(thin) (@in_guaranteed Int) -> ()

%value_again2 = load %0 : $*Int
%r4 = apply %f_test(%value_again2) : $@convention(thin) (Int) -> ()
*/

%9999 = tuple()
return %9999 : $()
}
--- SNAP ---

into

--- SNIP ---
bb0(%0 : $*Int):
%1 = integer_literal $Builtin.Int64, 42 // user: %2
%2 = struct $Int (%1 : $Builtin.Int64) // users: %7, %3
store %2 to %0 : $*Int // id: %3
// function_ref buz
%4 = function_ref @buz : $@convention(thin) (@in_guaranteed Int) -> () // user: %5
%5 = apply %4(%0) : $@convention(thin) (@in_guaranteed Int) -> ()
// function_ref test
%6 = function_ref @test : $@convention(thin) (Int) -> () // user: %7
%7 = apply %6(%2) : $@convention(thin) (Int) -> ()
%8 = tuple () // user: %9
return %8 : $() // id: %9
} // end sil function 'bar'
--- SNAP ---

so the load has successfully been eliminated. Also taking my initial repro [1], the retain, the load, and the release are now gone :smiley:.

Is that roughly what you were thinking of?

Many thanks,
Johannes

[1]: https://bugs.swift.org/secure/attachment/12378/test.swift

Erik

On Jul 17, 2017, at 9:23 AM, Johannes Weiß <johannesweiss@apple.com> wrote:

Thanks Michael!

Erik, I hope what I wrote makes some sense. Any questions or suggestions, please let me know.

On 14 Jul 2017, at 7:30 pm, Michael Gottesman <mgottesman@apple.com> wrote:

On Jul 12, 2017, at 9:53 AM, Johannes Weiß <johannesweiss@apple.com> wrote:

Hi Michael,

[...]

Long story short, I think the RLE actually works for the test case I created. It's even clever enough to see through my invalid function bad() which modified the storage despite its claim that it doesn't. I might also be misunderstanding something.

When something is marked as in_guaranteed, it should be immutable. If the callee violates that, then the SIL is malformed. Perhaps, we can add some sort of verification check.

Right, yes I was aware that that'd be illegal but I added it as a way to check whether this optimisation is 'looking into' the called function.

That being said, I have a good feeling that there is some sort of analysis occuring here since you provided enough information to the optimizer. The optimization here is regardless of whether or not we can see the body of a function, we know that it is safe to optimize this just based off the @in_guaranteed. This implies using a declaration, not a definition of the bad function.

makes sense, didn't think about just only declaring it...

When I said write the SIL by hand, what I meant was writing the whole program by hand. In general, we prefer SIL programs that do not have extraneous stuff that is added by the compiler (for instance debug_value). Additionally, it is important for SIL files to not have dependencies on the stdlib unless absolutely necessary (i.e. your usage of Int). This prevents the stdlib maintainers from having to update these tests given chances to the stdlib. Below is a cleaned up version that shows the problem. Look at how small it is and how it tests /exactly/ what we are trying to test and via the use of declarations and the like we are able to exclude other optimizations:

That makes a lot of sense, thank you. I wasn't yet that familiar with SIL so I thought I start from a program generated by the compiler and then replace the guts with handwritten SIL. But your version is clearly a lot easier to understand and shows what precisely we want to see!

Today, I looked into why this is happening more precisely.

So we don't get the RLE because in this code

if (isComputeAvailValue(Kind) || isPerformingRLE(Kind)) {
for (unsigned i = 0; i < Locs.size(); ++i) {
if (isTrackingLocation(ForwardSetIn, Ctx.getLocationBit(Locs[i])))
continue;
updateForwardSetAndValForRead(Ctx, Ctx.getLocationBit(Locs[i]),
                          Ctx.getValueBit(Vals[i]));
// We can not perform the forwarding as we are at least missing
// some pieces of the read location.
CanForward = false;

(https://github.com/apple/swift/blob/86620aaa7ebd32d33f4cdf61add5c63a72d3f02a/lib/SILOptimizer/Transforms/RedundantLoadElimination.cpp#L917)

we're not taking the `continue` for the call to `buz()`. The reason why is that here

if (!AA->mayWriteToMemory(I, R.getBase()))
continue;
// MayAlias.
stopTrackingLocation(ForwardSetIn, i);
stopTrackingValue(ForwardValIn, i);

(https://github.com/apple/swift/blob/86620aaa7ebd32d33f4cdf61add5c63a72d3f02a/lib/SILOptimizer/Transforms/RedundantLoadElimination.cpp#L972)

we're not taking the `continue`, ie. `AA->mayWriteToMemory(I, R.getBase())` is true. The reason for that is that the `SILFunction` for `buz` has

EffectsKindAttr = Unspecified

which equates to `MayHaveSideEffects`, that's also what `-debug-only=sil-redundant-load-elim,sil-membehavior` outputs:

GET MEMORY BEHAVIOR FOR:
%5 = apply %4(%0) : $@convention(thin) (@in_guaranteed Int) -> ()
%0 = argument of bb0 : $*Int // users: %6, %5, %3
Found apply, returning MayHaveSideEffects

So where I'm stuck today is that I'm not sure how `EffectsKindAttr` is actually defined. Sure, `$@convention(thin) (@in_guaranteed Int) -> ()` doesn't actually write to the `@in_guaranteed Int` (as that'd be illegal) but it may have other side effects. So I'm not sure if we can just create the function differently if we find only "read-only" kind of parameters. That'd be I think in

auto *fn = SILMod.createFunction(SILLinkage::Private, Name.str(), Ty,
                         nullptr, loc, IsNotBare,
                         IsNotTransparent, IsNotSerialized);

(https://github.com/apple/swift/blob/ec6fc4d54db95f78ae72dab29734533f709ea2d7/lib/Parse/ParseSIL.cpp#L508 -> https://github.com/apple/swift/blob/157db57506b813837481b574a9d38e806bf954b6/lib/SIL/SILModule.cpp#L249)

which doesn't specify any EffectsAttrKind and therefore it defaults to `Unspecified`.

Just as a test, I did put a `[readonly]` in `sil @buz : $@convention(thin) (@in_guaranteed Int) -> ()` and as expected everything propagates through correctly and we get a successful RLE.

So yes, maybe you have some pointers on where to best educate the compiler that the `buz` function won't write to that bit of memory.

I have a few ideas of where to put it, but really the person to bring in here is Erik. He is the one who wrote the side-effect part of the optimizer. Keep in mind he is on vacation right now until next week. So I wouldn't expect a response until then.

Michael

Many thanks,
Johannes

----
sil_stage canonical

import Builtin

struct Int {
var _value : Builtin.Int64
}

sil @test : $@convention(thin) (Int) -> ()
sil @buz : $@convention(thin) (@in_guaranteed Int) -> ()
sil @bad : $@convention(thin) (@in_guaranteed Int) -> ()

sil @bar : $@convention(thin) (@in Int) -> () {
bb0(%0 : $*Int):
%value_raw = integer_literal $Builtin.Int64, 42
%value = struct $Int (%value_raw : $Builtin.Int64)
store %value to %0 : $*Int

%f_buz = function_ref @buz : $@convention(thin) (@in_guaranteed Int) -> ()
%r1 = apply %f_buz(%0) : $@convention(thin) (@in_guaranteed Int) -> ()

%value_again = load %0 : $*Int
%f_test = function_ref @test : $@convention(thin) (Int) -> ()
%r2 = apply %f_test(%value_again) : $@convention(thin) (Int) -> ()

%f_bad = function_ref @bad : $@convention(thin) (@in_guaranteed Int) -> ()
%r3 = apply %f_bad(%0) : $@convention(thin) (@in_guaranteed Int) -> ()

%value_again2 = load %0 : $*Int
%r4 = apply %f_test(%value_again2) : $@convention(thin) (Int) -> ()

%9999 = tuple()
return %9999 : $()
}
----

When I run this test file through rle, I get:

----
sil_stage canonical

import Builtin
import Swift
import SwiftShims

struct Int {
@sil_stored var _value: Builtin.Int64
init(_value: Builtin.Int64)
}

// test
sil @test : $@convention(thin) (Int) -> ()

// buz
sil @buz : $@convention(thin) (@in_guaranteed Int) -> ()

// bad
sil @bad : $@convention(thin) (@in_guaranteed Int) -> ()

// bar
sil @bar : $@convention(thin) (@in Int) -> () {
// %0 // users: %11, %10, %6, %5, %3
bb0(%0 : $*Int):
%1 = integer_literal $Builtin.Int64, 42 // user: %2
%2 = struct $Int (%1 : $Builtin.Int64) // user: %3
store %2 to %0 : $*Int // id: %3
// function_ref buz
%4 = function_ref @buz : $@convention(thin) (@in_guaranteed Int) -> () // user: %5
%5 = apply %4(%0) : $@convention(thin) (@in_guaranteed Int) -> ()
%6 = load %0 : $*Int // user: %8
// function_ref test
%7 = function_ref @test : $@convention(thin) (Int) -> () // users: %12, %8
%8 = apply %7(%6) : $@convention(thin) (Int) -> ()
// function_ref bad
%9 = function_ref @bad : $@convention(thin) (@in_guaranteed Int) -> () // user: %10
%10 = apply %9(%0) : $@convention(thin) (@in_guaranteed Int) -> ()
%11 = load %0 : $*Int // user: %12
%12 = apply %7(%11) : $@convention(thin) (Int) -> ()
%13 = tuple () // user: %14
return %13 : $() // id: %14
} // end sil function 'bar'
----

Michael

Does that all make sense?

Thanks,
Johannes
<test-load-forwarding.sil><test-load-forwarding.sil-opt>

Thanks,
Johannes

[1]: https://bugs.swift.org/browse/SR-5403

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

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

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

Terms of Service

Privacy Policy

Cookie Policy