[swift-dev] SR-5403 / Memory Optimization Opportunity (Load/Store forwarding)

[Johannes Weiß]

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