GeezerVison

Can we leave dispatch to the code generator?
The saved instruction pointer (frame->prev_instr) is part of the VM state like any other, so shouldn't need special casing. Unless the necessary information is not otherwise present. All the information necessary is in JUMPBY(oparg).

Okay, so you're saying that for Tier 2 the code generator should just replace JUMPBY(<expr>) with something Tier-2-appropriate. That could actually work. There are three places where we shouldn't do that, SEND, JUMP_BACKWARD and ENTER_EXECUTOR, we can exclude those by forbidding something they use.

SEND will probably need to be broken up into two micro ops, one that does the send, and another that does the jump. The SEND jump should be a more-or-less normal jump. We also need to track where we are sending from, to handle the matching YIELD_VALUE, so I'd "forbid" SEND for now.

I think you already handle JUMP_BACKWARD and ENTER_EXECUTOR correctly. They complete the loop, or exit.

Set oparg = 0, loop over EXTENDED_ARGS, shifting as you go then shift in the final oparg.
https://github.com/python/cpython/blob/main/Python/instrumentation.c#L1332

Will do.

This turns out more complicated than I expected. The big question is: what IP should SAVE_IP save?

To make my current deopt strategy work (re-execute the specialized bytecode, which will fail the same guard and then deopt to the generic bytecode), the saved IP should point to the EXTENDED_ARG instruction. But the jump offsets are calculated relative to the jumping opcode. I suppose I could add the number of EXTENDED_ARG opcodes to the jump offsets (or subtract, for backward jumps).

But I worry that the error handling code might also need an adjustment -- I don't know if EXTENDED_ARG is included in exception handling ranges or if the error handling looks at the last executed bytecode.

I guess for now I can just treat EXTENDED_ARG as an unsupported opcode and kick this can of worms down the road...

Saving the IP of the start of the instruction (not codeunit) is the correct thing, I think.
On entering the tier 1 interpreter, it will then get the correct oparg as it will execute all the EXTENDED_ARGs.

EXTENDED_ARG can never cause an error, so it doesn't matter whether they are included in the jump tables, although I think they are anyway.

operand = (operand & 0xffffff00) | executor->vm_data.oparg

We don't want unspecialized instructions in the superblocks. I'd treat ENABLE_SPECIALIZATION as one of the forbidden words.
The fix is to improve our specialization, not to handle unspecialized instructions.

That seems a bit harsh. It would mean that if we have a sequence of innocent bytecodes like

LOAD_FAST i
LOAD_CONST j
BINARY_OP (/)
STORE_FAST k
...

we would not be able to include the BINARY_OP and STORE_FAST instructions in a superblock, because the unspecialized BINARY_OP ends the superblock generation.

Harsh, but fair. BINARY_OP needs to work harder at being specialized 🙂

Seriously though, there is no merit in longer superblocks if we can't optimize them well, and the unspecialized forms do not optimize well. They are much slower, and force us to discard a lot of type information.

It is far more profitable to improve the specializer, so that unspecialized instructions are rare.

Rather than special case individual instructions, can we test on flags?
That way, this will continue to work if we add LOAD_FAST_LOAD_CONST.
Something like if (_Py_OpcodeMetadata[opcode].is_super_instruction)

We could do something where the code generator encodes this in the size field of the expansions, in the switch (currently) at line 405 below. E.g. -1 means operand >> 4 and -2 means operand & 0xF. Should probably switch to an enum. The generator would have to work a little harder but that seems doable (e.g. it could detect the use of oparg1 and oparg2 and then parse the instruction name into two pieces).

That should work, although I was thinking of the dumber approach of just annotating LOAD_FAST_LOAD_FAST, etc as a superinstruction in bytecodes.c. Something like adding /* superinstruction */

This seems unnecessary.

The superblock generator should be converting each conditional jump into a conditional exit, followed by an unconditional jump.
Such that:

POP_JUMP_IF_TRUE label

becomes:

False branch more likely

EXIT_IF_TRUE

True branch more likely

EXIT_IF_FALSE
JUMP_FORWARD label

As for which branch is more likely, we will need to record which way branches go.

Okay, just so I understand correctly, the idea is that EXIT_IF_TRUE/FALSE doesn't pop, and continues in the bytecode at the original POP_JUMP_IF_TRUE instruction, which will pop. So the "False branch more likely" (i.e., branch not likely) version will have to actually translate to EXIT_IF_TRUE; POP_TOP. We could special-case this in the translator: it would have put such a list of uops in the expansion for POP_JUMP_IF_TRUE and friends, and we'd have to add hand-written cases to the uop executor for EXIT_IF_TRUE etc.

In the other case (branch likely) the JUMP_FORWARD label could just be SAVE_IP label; superblock generation would then continue from the bytecode at label. That's not something I currently do -- a simplistic approach could do the SAVE_IP followed by EXIT_TRACE, and we can iterate later on continuing from label.

But recording which way branches go is something for a future PR; again the most simplistic thing to do for now is to assume that branching is less likely than not branching (i.e., always generate EXIT_IF_TRUE; POP_TOP for now).

Honestly, for now I think I'll stick to just making the generator explicitly translate JUMPBY(n) into the correct sequence of JUMPBY, STACK_SHRINK and DISPATCH. Nothing should follow JUMPBY then.

I think it makes more sense to consume the condition before exiting

These two instructions, POP_JUMP_IF_TRUE and POP_JUMP_IF_FALSE (the None variants can be broken down into LOAD_CONST None; IS_OP; POP_JUMP...) are special, so don't worry too much about fitting them into the more general framework.

There are a number of approaches, for exits. Here are three:

1. Leave the condition on the stack, and exit to the POP_JUMP... instruction.
   I don't like this approach as it is inefficient and will make trace stitching tricky
2. Pop the condition and exit to the target, or successor, instruction.
   This is better, but means that the EXIT uop needs to handle a jump and the exit.
3. Convert the superblock into a tree, jumping to an exit branch which makes an unconditional exit.
   Definitely my preferred option. Means that there is only one EXIT uop and that it just exits.

Option 3 makes the superblock creation more complex, but simplifies the tier2 interpreter.
We will want to push some operations onto exit branches in the specializer and partial evaluator, so we will need to convert the superblock to a tree at some point.

If option 3 is too complex for this PR, option 2 should work as a temporary step.

So for option 3, using the example above of POP_JUMP_IF_TRUE label we get:

False branch more likely

    POP_JUMP_IF_TRUE_UOP uop_label:
    ...
uop_label:
    SAVE_IP label
    EXIT

True branch more likely

    POP_JUMP_IF_FALSE_UOP uop_label:
    SAVE_IP label
    ...
uop_label:
    EXIT

Okay, so you're saying that for Tier 2 the code generator should just replace JUMPBY(<expr>) with something Tier-2-appropriate. That could actually work. There are three places where we shouldn't do that, SEND, JUMP_BACKWARD and ENTER_EXECUTOR, we can exclude those by forbidding something they use.

Okay, just so I understand correctly, the idea is that EXIT_IF_TRUE/FALSE doesn't pop, and continues in the bytecode at the original POP_JUMP_IF_TRUE instruction, which will pop. So the "False branch more likely" (i.e., branch not likely) version will have to actually translate to EXIT_IF_TRUE; POP_TOP. We could special-case this in the translator: it would have put such a list of uops in the expansion for POP_JUMP_IF_TRUE and friends, and we'd have to add hand-written cases to the uop executor for EXIT_IF_TRUE etc.

In the other case (branch likely) the JUMP_FORWARD label could just be SAVE_IP label; superblock generation would then continue from the bytecode at label. That's not something I currently do -- a simplistic approach could do the SAVE_IP followed by EXIT_TRACE, and we can iterate later on continuing from label.

But recording which way branches go is something for a future PR; again the most simplistic thing to do for now is to assume that branching is less likely than not branching (i.e., always generate EXIT_IF_TRUE; POP_TOP for now).

Honestly, for now I think I'll stick to just making the generator explicitly translate JUMPBY(n) into the correct sequence of JUMPBY, STACK_SHRINK and DISPATCH. Nothing should follow JUMPBY then.

That seems a bit harsh. It would mean that if we have a sequence of innocent bytecodes like

LOAD_FAST i
LOAD_CONST j
BINARY_OP (/)
STORE_FAST k
...

we would not be able to include the BINARY_OP and STORE_FAST instructions in a superblock, because the unspecialized BINARY_OP ends the superblock generation.

Useless diff chunks like this make it harder to review the generated output. I would love to drop the #line directives. (Unsurprisingly, I get a lot of value out of seeing the diff of the generated code when I am fiddling with the code generator.) For debugging you could still generate line numbers using

python3 Tools/cases_generator/generate_cases.py -lPy_BUILD_CORE

We could do something where the code generator encodes this in the size field of the expansions, in the switch (currently) at line 405 below. E.g. -1 means operand >> 4 and -2 means operand & 0xF. Should probably switch to an enum. The generator would have to work a little harder but that seems doable (e.g. it could detect the use of oparg1 and oparg2 and then parse the instruction name into two pieces).

Will do.

SEND will probably need to be broken up into two micro ops, one that does the send, and another that does the jump. The SEND jump should be a more-or-less normal jump. We also need to track where we are sending from, to handle the matching YIELD_VALUE, so I'd "forbid" SEND for now.

I think you already handle JUMP_BACKWARD and ENTER_EXECUTOR correctly. They complete the loop, or exit.

I think it makes more sense to consume the condition before exiting

These two instructions, POP_JUMP_IF_TRUE and POP_JUMP_IF_FALSE (the None variants can be broken down into LOAD_CONST None; IS_OP; POP_JUMP...) are special, so don't worry too much about fitting them into the more general framework.

There are a number of approaches, for exits. Here are three:

1. Leave the condition on the stack, and exit to the POP_JUMP... instruction.
   I don't like this approach as it is inefficient and will make trace stitching tricky
2. Pop the condition and exit to the target, or successor, instruction.
   This is better, but means that the EXIT uop needs to handle a jump and the exit.
3. Convert the superblock into a tree, jumping to an exit branch which makes an unconditional exit.
   Definitely my preferred option. Means that there is only one EXIT uop and that it just exits.

Option 3 makes the superblock creation more complex, but simplifies the tier2 interpreter.
We will want to push some operations onto exit branches in the specializer and partial evaluator, so we will need to convert the superblock to a tree at some point.

If option 3 is too complex for this PR, option 2 should work as a temporary step.

So for option 3, using the example above of POP_JUMP_IF_TRUE label we get:

False branch more likely

    POP_JUMP_IF_TRUE_UOP uop_label:
    ...
uop_label:
    SAVE_IP label
    EXIT

True branch more likely

    POP_JUMP_IF_FALSE_UOP uop_label:
    SAVE_IP label
    ...
uop_label:
    EXIT

That should work, although I was thinking of the dumber approach of just annotating LOAD_FAST_LOAD_FAST, etc as a superinstruction in bytecodes.c. Something like adding /* superinstruction */