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

[Philip Reames via llvm-dev]

On 02/17/2016 04:41 PM, Sanjoy Das wrote:
> Replies inline.
>
> At a high level, it feels like we'll eventually need a new instruction
> to represent the kind of control flow a guard entails (to be clear: we
> should probably still start with an intrinsic) -- they are fairly
> well-behaved, i.e. readonly, nounwind etc. as far as the immediate
> "physical" caller is concerned, but not so as far as its callers's
> callers are concerned.
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.  :)
>
> On Wed, Feb 17, 2016 at 3:40 PM, Philip Reames
> <listmail at philipreames.com> wrote:
>
>
>> I'd suggest a small change to Sanjoy's declaration.  I think we should allow
>> additional arguments to the guard, not just the condition.  What exactly
>> those arguments mean would be up to the runtime, but various runtimes might
>> want to provide additional arguments to the OSR mechanism.
> We'll still have to make a call on the signature of the intrinsic (or
> are you suggesting a varargs intrinsic)?
>
> I suppose we could also have a family of intrinsics, that take on
> argument of variable type.
I was proposing a varargs _intrinsic_.  (Not varargs as in C/C++, but 
varargs as-in polymorphic over all static signatures.)
>
>>> Bailing out to the interpreter involves re-creating the state of the
>>> interpreter frames as-if the compilee had been executing in the
>>> interpreter all along.  This state is represented and maintained using
>>> a `"deopt"` operand bundle attached to the call to `@llvm.guard_on`.
>>> The verifier will reject calls to `@llvm.guard_on` without a `"deopt"`
>>> operand bundle.
>> This introduces a very subtle point.  The side exit only effects the
>> *function* which contains the guard.  A caller of that function in the same
>> module may be returned to by either the function itself, or the interpreter
>> after running the continuation implied by the guard.  This introduces a
>> complication for IPA/IPO; any guard (really, any side exit, of which guards
>> are one form) has to be treated as a possible return point from the callee
>> with an unknowable return value and memory state.
> This is a really good point.  This has strong implications for the
> guards memory effects as well -- even though a guard can be seen as
> readonly in its containing functions, things that call the containing
> function has to see the guard as read-write.  IOW @foo below is
> read/write, even though v0 can be forwarded to v1:
>
> ```
> int @foo(int cond) {
>    int v0 = this->field;
>    guard_on(cond);
>    int v1 = this->field;
>    return v0 + v1;
> }
> ```
Essentially, we'd be introducing an aliasing rule along the following: 
"reads nothing on normal path, reads/writes world if guard is taken (in 
which case, does not return)."  Yes, implementing that will be a bit 
complicated, but I don't see this as a fundamental issue.

>
> As you point out, we're also introducing a newish kind of control flow
> here.  It is not fundamentally new, since longjmp does something
> similar (but not quite the same).
>
> I hate to say this, but perhaps we're really looking at (eventually) a
> new instruction here, and not just a new intrinsic.
>
>>> `@bail_to_interpreter` does not return to the current compilation, but
>>> it returns to the `"deopt"` continuation that is has been given (once
>>> inlined, the empty "deopt"() continuation will be fixed up to have the
>>> right
>>> continuation).
>> This "bail_to_interpreter" is a the more general form of side exit I
>> mentioned above.
> How is it more general?
You can express a guard as a conditional branch to a 
@bail_to_interpreter construct.  Without the @bail_to_interpreter (which 
is the thing which has those weird aliasing properties we're talking 
about), you're stuck.

(In our tree, we've implemented exactly the "bail_to_interpreter" 
construct under a different name, marked as readonly with an exception 
in FunctionAttrs to resolve the IPO problem.)

What the guard nodes add is a) conciseness, b) potentially better 
optimization, and c) the ability to widen.

Thinking about it further, I think we should probably have started with 
proposing the @bail_to_interpreter construct, gotten that working fully 
upstream, then done the guard, but oh well.  We can do both in parallel 
since we have a working implementation downstream of @b_to_i.
>
>>> ## memory effects (unresolved)
>>>
>>> [I haven't come up with a good model for the memory effects of
>>>    `@llvm.guard_on`, suggestions are very welcome.]
>>>
>>> I'd really like to model `@llvm.guard_on` as a readonly function,
>>> since it does not write to memory if it returns; and e.g. forwarding
>>> loads across a call to `@llvm.guard_on` should be legal.
>>>
>>> However, I'm in a quandary around representing the "may never return"
>>> aspect of `@llvm.guard_on`: I have to make it illegal to, say, hoist a
>>> load form `%ptr` across a guard on `%ptr != null`.
>> Modeling this as memory dependence just seems wrong.  We already have to
>> model control dependence on functions which may throw.  I don't think
>> there's anything new here.
> I am trying to model this as control dependence, but the difficult bit
> is to do that while still maintaining that the call does not clobber
> any memory.  I'm worried that there may be reasons (practical or
> theoretical) why we "readonly" functions always have to terminate and
> be nothrow.
I think we should not bother modeling the call as readonly.  As we've 
seen with @llvm.assume, we can get something which is readonly in 
practice without it being readonly per se.  :)  And, as above, it's not 
clear that readonly is even a correct way to model a guard as all.

>
>> The only unusual bit is that we're going to want to teach AliasAnalysis that
>> the guard does write to any memory location (to allow forwarding) while
>> still preserving the control dependence.
> So you're saying that we model the guard as otherwise read/write (thus
> sidestepping the readonly non-returning quandary) but teach
> AliasAnalysis that it doesn't clobber any memory?  That would work.
Yes.  As we've done for @llvm.assume and a number of other one off 
cases.  Once we've implemented the exact semantics we want, we can 
decide if there's a property lurking which we can extract as a new 
attribute.
>
> We can also use the same tool to solve the "may return to its caller's
> caller with arbitrary heap state" issue by teaching AA that a guard
> does not alias with reads in its own (physical) function, but clobbers
> the heap for other (physical) functions.
I'd have to think about this a bit further before agreeing, but on the 
surface this seems reasonable.
>
> Notation: I'm differentiating between physical functions == functions
> that create actual stack frames and inlined functions == logical Java
> functions that don't create separate physical frames.  Inlining IR
> from one java level function into another usually creates a physical
> function that contains more than one logical function.
>
>>> There are couple
>>> of ways I can think of dealing with this, none of them are both easy
>>> and neat:
>>>
>>>    - State that since `@llvm.guard_on` could have had an infinite loop
>>>      in it, it may never return. Unfortunately, the LLVM IR has some
>>>      rough edges on readonly infinite loops (since C++ disallows that),
>>>      so LLVM will require some preparatory work before we can do this
>>>      soundly.
>>>
>>>    - State that `@llvm.guard_on` can unwind, and thus has non-local
>>>      control flow.  This can actually work (and is pretty close to
>>>      the actual semantics), but is somewhat of hack since
>>>      `@llvm.guard_on` doesn't _really_ throw an exception.
>> Er, careful.  Semantically, the guard *might* throw an exception. It could
>> be that's what the interpreter does when evaluating the continuation implied
>> by the guard and any of our callers have to account for the fact the
>> function which contains the guard might throw.  The easiest way to ensure
>> that is to model the guard call as possibly throwing.
> Yes, it does not throw an exception into its own caller, but may throw
> into its caller's caller.
>
> -- Sanjoy