[swift-dev] SR-5403 / Memory Optimization Opportunity (Load/Store forwarding)
John McCall
rjmccall at apple.com
Tue Jul 25 12:00:31 CDT 2017
> On Jul 25, 2017, at 12:55 PM, Johannes Weiß via swift-dev <swift-dev at 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 at 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 at apple.com> wrote:
>>>
>>>>
>>>> On Jul 18, 2017, at 10:40 AM, Johannes Weiß <johannesweiss at 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 at apple.com> wrote:
>>>>>
>>>>>>
>>>>>> On Jul 18, 2017, at 8:39 AM, Johannes Weiß <johannesweiss at apple.com> wrote:
>>>>>>
>>>>>> Hi Erik,
>>>>>>
>>>>>>> On 17 Jul 2017, at 10:26 pm, Erik Eckstein <eeckstein at 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 😃.
>>>>>>
>>>>>> 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 at 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 at apple.com> wrote:
>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> On Jul 12, 2017, at 9:53 AM, Johannes Weiß <johannesweiss at 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 at swift.org
>> https://lists.swift.org/mailman/listinfo/swift-dev
>
> _______________________________________________
> swift-dev mailing list
> swift-dev at swift.org
> https://lists.swift.org/mailman/listinfo/swift-dev
More information about the swift-dev
mailing list