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

[Sanjoy Das via llvm-dev]

On Mon, Feb 22, 2016 at 11:03 AM, Philip Reames
<listmail at philipreames.com> wrote:
>> ```
>> 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.)

Yes.  I think I was too dramatic when I claimed that the
deoptimization model in LLMV is "wrong" -- the real story is more on
the lines of "frontend authors need to be aware of some subtleties".

> 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.

Yes.  LLVM already has a "mayBeOverriden" flag, we should just add a
function attribute, `interposable`, that makes `mayBeOverriden` return
true.

> 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.

The problem is a little easier with side exits, since with side exits,
we will either have them at the tail position, or have them follow an
unreachable (so having them as read/write/may-unwind is not a problem).

With guards, we have to solve a harder problem -- we don't want to
mark the guard as "can read write all memory", since we'd like to
forward `val` to `val1` in the example below:

  int val = *ptr;
  guard_on(arbitrary condition)
  int val1 = *ptr;

But, as discussed earlier, we're probably okay if we mark guard_on as
read/write; and use alias analysis to sneakily make it "practically
readonly".

-- Sanjoy