> 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 <eeckst...@apple.com> wrote: >>> >>>> >>>> On Jul 18, 2017, at 10:40 AM, Johannes Weiß <johanneswe...@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 <mgottes...@apple.com> >>>>> wrote: >>>>> >>>>>> >>>>>> On Jul 18, 2017, at 8:39 AM, Johannes Weiß <johanneswe...@apple.com> >>>>>> wrote: >>>>>> >>>>>> Hi Erik, >>>>>> >>>>>>> On 17 Jul 2017, at 10:26 pm, Erik Eckstein <eeckst...@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ß <johanneswe...@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 <mgottes...@apple.com> >>>>>>>>> wrote: >>>>>>>>> >>>>>>>>>> >>>>>>>>>> On Jul 12, 2017, at 9:53 AM, Johannes Weiß <johanneswe...@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
