> On Jul 18, 2017, at 9:53 AM, Michael Gottesman via swift-dev
> <[email protected]> wrote:
>
>>
>> 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.
Also, I think you want to use the SubstCalleeType, not the original callee
type. The difference is that orig callee type can refer to the base
unspecialized type of a specialized function. You always want to use the
specialized function if you have it (which is the subst callee type.
>
> 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] <mailto:[email protected]>
> https://lists.swift.org/mailman/listinfo/swift-dev
> <https://lists.swift.org/mailman/listinfo/swift-dev>
_______________________________________________
swift-dev mailing list
[email protected]
https://lists.swift.org/mailman/listinfo/swift-dev
