> On Jul 18, 2017, at 8:39 AM, Johannes Weiß <[email protected]> wrote:
>
> Hi Erik,
>
>> On 17 Jul 2017, at 10:26 pm, Erik Eckstein <[email protected]> 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ß <[email protected]> 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 <[email protected]> wrote:
>>>>
>>>>>
>>>>> On Jul 12, 2017, at 9:53 AM, Johannes Weiß <[email protected]>
>>>>> 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
[email protected]
https://lists.swift.org/mailman/listinfo/swift-dev
