> 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; > + > + 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