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