Call design for Tier 2 (uops) interpreter

[gvanrossum]

(Maybe this is tentative enough that it still belongs in the faster-cpython/ideas tracker, but I hope we're close enough that we can hash it out here. CC @markshannon, @brandtbucher)

(This is a WIP until I have looked a bit deeper into this.)

First order of business is splitting some of the CALL specializations into multiple ops satisfying the uop requirement: either use oparg and no cache entries, or don't use oparg and use at most one cache entry. For example, one of the more important ones, CALL_PY_EXACT_ARGS, uses both oparg (the number of arguments) and a cache entry (func_version). Splitting it into a guard and an action op is problematic: even discounting the possibility of encountering a bound method (i.e., assuming method is NULL), it contains the following DEOPT calls:

            // PyObject *callable = stack_pointer[-1-oparg];
            DEOPT_IF(tstate->interp->eval_frame, CALL);
            int argcount = oparg;
            PyFunctionObject *func = (PyFunctionObject *)callable;
            DEOPT_IF(!PyFunction_Check(callable), CALL);
            PyFunctionObject *func = (PyFunctionObject *)callable;
            DEOPT_IF(func->func_version != func_version, CALL);
            PyCodeObject *code = (PyCodeObject *)func->func_code;
            DEOPT_IF(code->co_argcount != argcount, CALL);
            DEOPT_IF(!_PyThreadState_HasStackSpace(tstate, code->co_framesize), CALL);

If we wanted to combine all this in a single guard op, that guard would require access to both oparg (to dig out callable) and func_version. The fundamental problem is that the callable, which needs to be prodded and poked for the guard to pass, is buried under the arguments, and we need to use oparg to know how deep it is buried.

What if we somehow reversed this so that the callable is on top of the stack, after the arguments? We could arrange for this by adding a COPY n+1 opcode just before the CALL opcode (or its specializations). In fact, this could even be a blessing in disguise, since now we would no longer need to push a NULL before the callable to reserve space for self -- instead, if the callable is found to be a bound method, its self can overwrite the original callable (below the arguments) and the function extracted from the bound method can overwrite the copy of the callable above the arguments. This has the advantage of no longer needing to have a "push NULL" bit in several other opcodes (the LOAD_GLOBAL and LOAD_ATTR families -- we'll have to review the logic in LOAD_ATTR a bit more to make sure this can work).

(Note that the key reason why the callable is buried below the arguments is a requirement about evaluation order in expressions -- the language reference requires that in the expression F(X) where F and X themselves are possibly complex expressions, F is evaluated before X.)

Comparing before and after, currently we have the following arrangement on the stack when CALL n or any of its specializations is reached:

    NULL
    callable
    arg[0]
    arg[1]
    ...
    arg[n-1]

This is obtained by e.g.

    PUSH_NULL
    LOAD_FAST callable
    <load n args>
    CALL n

or

    LOAD_GLOBAL (NULL + callable)
    <load n args>
    CALL n

or

    LOAD_ATTR (NULL|self + callable)
    <load n args>
    CALL n

Under my proposal the arrangement would change to

    callable
    arg[0]
    arg[1]
    ...
    arg[n-1]
    callable

and it would be obtained by

    LOAD_FAST callable  /  LOAD_GLOBAL callable  /  LOAD_ATTR callable
    <load n args>
    COPY n+1
    CALL n

It would (perhaps) even be permissible for the guard to overwrite both copies of the callable if a method is detected, since it would change from

    self.func
    <n args>
    self.func

to

    self
    <n args>
    func

where we would be assured that func has type PyFunctionObject *. (However, I think we ought to have separate specializations for the two cases, since the transformation would also require bumping oparg.)

The runtime cost would be an extra COPY instruction before each CALL; however I think this might actually be simpler than the dynamic check for bound methods, at least when using copy-and-patch.

Another cost would be requiring extra specializations for some cases that currently dynamically decide between function and method; but again I think that with copy-and-patch that is probably worth it, given that we expect that dynamic check to always go the same way for a specific location.

Linked PRs

• gh-106581: Add 10 new opcodes by allowing assert(kwnames == NULL) #106707
• gh-106581: Split CALL_PY_EXACT_ARGS into uops #107760
• gh-106581: Start projecting through calls #107793
• gh-106581: Project through calls #108067
• gh-106581: Fix two bugs in the code generator's copy optimization #108380
• gh-106581: Split CALL_BOUND_METHOD_EXACT_ARGS into uops #108462
• GH-106581: Fix instrumentation in tier 2 #108493
• gh-106581: Support multiple uops pushing new values #108895
• gh-106581: Honor 'always_exits' in write_components() #109338

[markshannon]

Splitting it into a guard and an action op is problematic

You can have as many guards as you need. As long as they do not perturb the state of the VM, there can more than one. We have been assuming that there would be one action, but in fact there can be no action (TO_BOOL_BOOL is just a guard with no action, and NOP has no guard or action).

In summary, a straight line instruction should be made up of zero or more guards followed optionally by an action.

[markshannon]

I specifically said "straight line instruction" above, because some conditional branching instructions, like FOR_ITER_LIST are tricky in that they have internal branching. The exhausted branch pops values off the stack, but the non-exhausted branch does not.
Fortunately, calls are unconditional.

[gvanrossum]

In summary, a straight line instruction should be made up of zero or more guards followed optionally by an action.

Sure, but any individual guard cannot use a cache entry and oparg at the same time. So how do you write the guard that checks the version of the callable Python function? It needs oparg to find the callable on the stack, and the function_version cache entry to verify the version. My solution for that is to have the callable duplicated on top of the stack before this uop sequence starts (see above for details). Is that acceptable?

[gvanrossum]

some conditional branching instructions, like FOR_ITER_LIST are tricky in that they have internal branching. The exhausted branch pops values off the stack, but the non-exhausted branch does not.

Please look at my solution in gh-106542. [Now closed in favor of gh-106696 and gh-106638]

[gvanrossum]

Off-line @markshannon proposed a simpler solution, that doesn't require changing all CALL specializations to handle a different stack layout. We will instead add the oparg to the Tier 2 instruction format, so they become (opcode, oparg, operand) where operand is some cache entry (if needed). Given that we currently have a 32-bit opcode and a 64-bit operand, adding a 32-bit oparg doesn't actually increase the size of the instruction. (See issue gh-106603.)

(There's also gh-105848 for reference.)

[gvanrossum]

Irrespective of the stack format, there's a bigger problem with projecting a trace through a call. Suppose we are projecting a trace and we encounter CALL_PY_EXACT_ARGS. We'd like to be able to continue the trace into that call, and back, so that if we're calling something like

def add(x, y):
    return x + y

from e.g.

total = 0
for i in range(1000):
    total = add(total, i)

we can add its translation to the trace, rather than ending the trace, and end up with a closed loop:

FOR_ITER_RANGE
STORE_FAST i
# LOAD_GLOBAL NULL + add
LOAD_FAST total
LOAD_FAST i
# CALL_PY_EXACT_ARGS 2
# RESUME
# LOAD_FAST x
# LOAD_FAST y
BINARY_OP_ADD_INT
# RETURN_VALUE
STORE_FAST total
JUMP_TO_TOP

Where the commented-out lines are redundant because we really inline the call.

Apart from the problem of eliding those call-related instructions, isn't it a problem that when we start projecting we don't (necessarily) have access to the function object being called? The cache associated with CALL just has a 32-bit "func_version" field, which is not enough to recover the actual function object or the code object (which we are really after). Working our way back from the CALL specialization to the place where the function being called is loaded (here LOAD_GLOBAL, but could be anything, really) does not seem feasible.

I guess this is where we stop projecting and come back to improve the projected executor once we are about to execute the specialized call -- at that point the function object should be exactly n deep on the stack and thus we can verify its type and version and then get its code object.

@markshannon Does this seem feasible?

[gvanrossum]

Perhaps when we end a trace with a call to Python code we can insert a special instruction that causes a new executor to be created using the callable (which is now easily found on the stack) as additional input.

[markshannon]

Yes, that should work.

The (slight) downside is that it forces us to execute the superblock in the tier 2 interpreter, which is likely slower than the tier 1 interpreter, as we can't optimize or JIT compile the superblock until it is complete.

We could insert a special instruction in at the start of the function, to potentially resume superblock creation.
That would allow us to keep execution in the (faster) tier 1 interpreter, at the cost of extra work on entering the function.

FTR, the approach I origially had in mind, was some sort of LRU cache mapping version numbers to functions.

[gvanrossum]

Presumably we would execute the first version of the superblock in the Tier 2 interpreter only once. We could also throw away the first version away when the projection reaches a specialized call, and instead insert a special executor type that records the information needed to reconstruct that superblock quickly but incorporating the callable. Then when we reach that executor it finishes the superblock, inserts it where it should go, and it will be reached on the next iteration around the enclosing loop.

[gvanrossum]

I'm still pondering the logistics -- the optimizer receives neither the frame nor the jump origin, so it wouldn't know the location where to plug in the new executor. Updating the existing executor seems iffy, another thread could already have started executing it, and I hope to make uop executors variable-length (see gh-106608). I guess I could search for the current executor in co_executors to recover its index, but that feels expensive (O(N^2), except N is bounded).

Logistics for the cache idea don't look entirely straightforward either. We could specialize a lot of calls before we get to incorporate one into a superblock, so the cache would have to be pretty large. But maybe I should play with this first.

(The logic around _Py_next_func_version seems subtle and undocumented. Ultimately that seems to be zero except in _bootstrap_python.)

(Also, there are two calls to _PyFunction_GetVersionForCurrentState() in specialize.c that look like they could be replaced by the function_get_version() helper.)

[gvanrossum]

I'm looking into an initial step for this -- just adding CALL_PY_EXACT_ARGS to the superblock, assuming that the Tier 2 interpreter will create, initialize and then return the new frame. For this we need to split CALL_PY_EXACT_ARGS into two uops, a guard and an action. But now we run into another yak to shave -- the generator doesn't yet handle variable-sized stack effects (in this case, args[oparg]) in uops: gh-106812.