[swift-dev] SR-5403 / Memory Optimization Opportunity (Load/Store forwarding)
Michael Gottesman
mgottesman at apple.com
Wed Jul 12 11:39:24 CDT 2017
> On Jul 11, 2017, at 4:21 PM, Michael Gottesman via swift-dev <swift-dev at swift.org> wrote:
>
>>
>> On Jul 11, 2017, at 10:16 AM, Johannes Weiß <johannesweiss at apple.com <mailto:johannesweiss at apple.com>> wrote:
>>
>> 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 :) ]
>> *** 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.
>
> 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 <https://bugs.swift.org/browse/SR-5403>
>>
>
> _______________________________________________
> swift-dev mailing list
> swift-dev at swift.org <mailto:swift-dev at swift.org>
> https://lists.swift.org/mailman/listinfo/swift-dev <https://lists.swift.org/mailman/listinfo/swift-dev>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-dev/attachments/20170712/84cb7bdb/attachment.html>
More information about the swift-dev
mailing list