[llvm-dev] RFC: Add guard intrinsics to LLVM

[Philip Reames via llvm-dev]

On 02/17/2016 09:59 PM, Sanjoy Das wrote:
> On Wed, Feb 17, 2016 at 8:53 PM, Philip Reames
> <listmail at philipreames.com> wrote:
>
>> I think you're jumping ahead a bit here.  I'm not sure the semantics are
>> anywhere near as weird as you're framing them to be.  :)
> I now think this weirdness actually does not have to do anything with
> guard_on or bail_to_interpeter, but it has to do with deopt bundles
> itself.  Our notion of of "deopt bundles are readonly" is broken to
> begin with, and that is what's manifesting as the complication we're
> seeing here.
>
> Consider something like
>
> ```
> declare @foo() readonly
> def @bar() { call @foo() [ "deopt"(XXX) ] }
> def @baz() { call @bar() [ "deopt"(YYY) ] }
> ```
>
> Right now according to the semantics of "deopt" operand bundles as in
> the LangRef, every call site above is readonly.  However, it is
> possible for @baz() to write to memory if @bar is deoptimized at the
> call site with the call to @foo.
>
> You could say that it isn't legal to mark @foo as readonly, since the
> action of deoptimizing one's caller is not a readonly operation.  But
> that doesn't work in cases like this:
>
> ```
> global *ptr
> declare @foo() readwrite
> def @bar() { call @foo() [ "deopt"(XXX) ]; *ptr = 42 }
> def @baz() { call @bar() [ "deopt"(YYY) ]; int v0 = *ptr }
> ```
>
> Naively, it looks like an inter-proc CSE can forward 42 to v0, but
> that's unsound, since @bar could get deoptimized at the call to
> @foo(), and then who knows what'll get written to *ptr.
Ok, I think this example does a good job of getting at the root issue.  
You claim this is not legal, I claim it is.  :) Specifically, because 
the use of the inferred information will never be executed in baz.  (see 
below)

Specifically, I think the problem here is that we're mixing a couple of 
notions.  First, we've got the state required for the deoptimization to 
occur (i.e. deopt information).  Second, we've got the actual 
deoptimization mechanism.  Third, we've got the *policy* under which 
deoptimization occurs.

The distinction between the later two is subtle and important.  The 
*mechanism* of exiting the callee and replacing it with an arbitrary 
alternate implementation could absolutely break the deopt semantics as 
you've pointed out.  The policy we actually use does not. Specifically, 
we've got the following restrictions:
1) We only replace callees with more general versions of themselves.  
Given we might be invalidating a speculative assumption, this could be a 
*much* more general version which includes actions and control flow 
invalidate any attribute inference done over the callee.
2) We invalidate all callers of @foo which could have observed the 
incorrect inference.  (This is required to preserve correctness.)

I think we probably need to separate out something to represent the 
interposition/replacement semantics implied by invalidation 
deoptimization.  In it's most generic form, this would model the full 
generality of the mechanism and thus prevent nearly all inference.  We 
could then clearly express our *policy* as a restriction over that full 
generality.

Another interesting case to consider:

global *ptr
declare @foo() readwrite
def @bar() { call @foo() [ "deopt"(XXX) ]; *ptr = 42 }
def @baz() {
   v0 = 42;
   while (C) {
     call @bar() [ "deopt"(v0) ];
     int v0 = *ptr
   }
}

Could we end up deoptimization with an incorrect deopt value for v0 
based on circular logic?  We can infer that v0 is always 42 in this 
example.  I claim that's legal precisely up to the point at which we 
deoptimize @bar and @baz together.  If we deoptimized @bar, let @baz run 
another loop iteration, then invalidated @baz, that would be incorrect.



>
> My interpretation here is that we're not modeling the deopt
> continuations correctly.  Above, the XXX continuation is a delimited
> continuation that terminates at the boundary of @bar, and seen from
> its caller, the memory effect (and any other effect) of @bar has to
> take into account that the "remainder" of @bar() after @foo has
> returned is either what it can see in the IR, or the XXX continuation
> (which it //could// analyze in theory, but in practice is unlikely
> to).
>
> This is kind of a bummer since what I said above directly contradicts
> the "As long as the behavior of an operand bundle is describable
> within these restrictions, LLVM does not need to have special
> knowledge of the operand bundle to not miscompile programs containing
> it." bit in the LangRef.  :(
Per above, I think we're fine for invalidation deoptimization.

For side exits, the runtime function called can never be marked readonly 
(or just about any other restricted semantics) precisely because it can 
execute an arbitrary continuation.  In principle, we could do bytecode 
inference to establish restricted semantics per call site.

Philip