Trap and OSR

Created by: wks

This ticket tracks the design of trap handling, stack introspection and OSR API.

Overview

There are three flavours of stack usage.

The first case is using TRAP to compute some value (or change some µVM states)

Enter the handle_trap call-back from a TRAP instruction, leaving the stack in the READY<T> state. The current thread is unbound and suspended.
The Client compute some value (of type T) and change some µVM states.
Return from the trap and continue normally. That is, re-bind the thread to the stack, passing the value of type T.

The second case is using TRAP for OSR.

Enter the handle_trap call-back from a TRAP instruction, leaving the stack in the READY<T> state. The current thread is unbound and suspended.
The Client queries the current version of function, the current instruction, and the current KEEPALIVE variables of any frame in the current stack.
The Client pops frames. Now the stack is in some inconsistent state.
The Client pushes frames. For each frame, supply the current version of function, the current instruction and the value of any live variables.
The Client re-bind the thread to the stack and return from the TRAP. Just before rebinding, the stack should be in some READY<U> state where U may not be T.

The third case is to manipulate some arbitrary stack in a READY<T> state.

The Client do whatever it wants to the stack.
The stack is in READY<U> state where U may not be T.

Open questions

Is an UNDER_CONSTRUCTION flag needed?

Observed from the previous cases, there are generally two categories:

Do not perform OSR and simply return with some value (or throw exceptions to the stack).
Perform OSR.

The second case may leave the stack temporarily in an inconsistent state. Any attempt to swap-stack to such a stack is meaningless. The UNDER_CONSTRUCTION flag indicates such a state.

This requirement can be interpreted in two ways:

This flag is a physical flag. The Client takes an action to set the flag. After OSR, it clears the flag. This flag can be probed and can be tested during SWAP-STACK. A µVM implementation may implement a mutual-exclusive lock for swap-stack (but may be inefficient).
This flag is only conceptual, that is, it does not physically exist. The Client simply does OSR. There is no way to see whether a stack is "under construction". Swapping to such a stack gives undefined behaviour.

I prefer the second approach. Swapping to an "under construction" stack is never meaningful and always requires extra synchronisation in the program. We may trust the Client to generate correctly synchronised code.

What state is a stack in when some frames are popped?

All frames other than the top frame must be executing the CALL instruction. After popping any frame, the "caller frame" is exposed as the top frame and it may continue with a value or receive an exception just like the TRAP instruction. So it is natural to define that after popping, the stack is in the READY<R> state where R is the return type of the current function.

However, from the implementation point of view, SWAP-STACK must have a different calling convention from ordinary calls (mainly because SWAP-STACK cannot have any callee-saved registers because the callee may not swap back). There must be a "ghost frame" above the current frame with CALL to adapt to the SWAP-STACK calling convention. The value passed by SWAP-STACK will be returned from the "ghost frame" to the CALLer.

We may assume adding the "ghost frame" is cheap. Maybe not.

Hypothetical Client code in Java

This code lets the Client perform some computation.

/* Assume the following µVM IR code:
%bb:
  @current_time_millis_1234567 = TRAP <@i64>
  CALL <...> @print (@current_time_millis_1234567)
  ....
*/
class Client extends MicroVMClient {
    @Override
    public TrapReturnValue handleTrap(ClientAgent ca, int threadHandle, int stackHandle) {
        long time = System.currentTimeMillis();
        ca.putLong("@i64", time);
        return new RebindThreadPassValue(stackHandle, time);
    }
}

This code replaces the top frame:

class Client extends MicroVMClient {
    @Override
    public TrapReturnValue handleTrap(ClientAgent ca, int threadHandle, int stackHandle) {
        // Introspect the frames
        int curInstID = ca.getCurrentInstruction(stackHandle, 0); // 0 = top frame
        int[] keepAlives = ca.dumpKeepAlives(stackHandle, 0); // 0 = top frame

        // Re-compile the function. newFunc also tells the Client where to continue.
        HighLevelFunction newFunc = compileNewFunction(...);

        // Pop a frame
        ca.popFrame();

        // What µVM function is the new high-level function?
        int funcID = newFunc.getUvmFuncID();

        // Where to continue?
        int contInstID = newFunc.getContinuationPoint();

        // What are the values of local variables?
        Map<Integer, Integer> variableToValue = new HashMap<Integer, Integer>();
        for (LocalVariable lv: newFunc.localVariables()) {
            int valHandle = ca.putXxxx(lv.getValue())
            int varID = lv.getUvmVarID();
            variableToValue.put(varID, valHandle)
        }

        // Push the frame
        ca.pushFrame(funcID, contInstID, variableToValue);

        // Return from TRAP, tell the µVM to re-bind the thread with the stack. The trap does not receive values.
        return new RebindThreadPassVoid(stackHandle);
    }
}

This example emulates the JVMTI function ForceEarlyReturnInt (force a function (of int return value) to return early with a specific value, not executing any finalisers).

/*
Assume the following µVM function:
.funcsig @foo_sig = @i32 ()
.funcdef @foo VERSION @foo_v1 () {
  %entry:
    @my_trap_xxxxxx = TRAP <@void>
    THROW @NULLREF
}
*/

class Client extends MicroVMClient {
    @Override
    public TrapReturnValue handleTrap(ClientAgent ca, int threadHandle, int stackHandle) {
        ca.popFrame(stackHandle); // Pop the top frame and expose its caller to the top
        int returnValue = 42;
        int rvHandle = ca.putInt("@i32", returnValue);
        return new RebindThreadPassValue(stackHandle, rvHandle);
    }
}