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 inJUMPBY(oparg).

Okay, so you're saying that for Tier 2 the code generator should just replaceJUMPBY(<expr>) with something Tier-2-appropriate. That could actually work. There are three places where we shouldn't do that,SEND,JUMP_BACKWARD andENTER_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. TheSEND jump should be a more-or-less normal jump. We also need to track where we are sending from, to handle the matchingYIELD_VALUE, so I'd "forbid"SEND for now.

I think you already handleJUMP_BACKWARD andENTER_EXECUTOR correctly. They complete the loop, or exit.

Setoparg = 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 shouldSAVE_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 theEXTENDED_ARG instruction. But the jump offsets are calculated relative to the jumping opcode. I suppose I could add the number ofEXTENDED_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 ifEXTENDED_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 treatEXTENDED_ARG as an unsupported opcode and kick this can of worms down the road...

Saving the IP of the start of theinstruction (not codeunit) is the correct thing, I think.
On entering the tier 1 interpreter, it will then get the correctoparg as it will execute all theEXTENDED_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 treatENABLE_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 iLOAD_CONST jBINARY_OP (/)STORE_FAST k...

we would not be able to include theBINARY_OP andSTORE_FAST instructions in a superblock, because the unspecializedBINARY_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 addLOAD_FAST_LOAD_CONST.
Something likeif (_Py_OpcodeMetadata[opcode].is_super_instruction)

We could do something where the code generator encodes this in thesize field of the expansions, in the switch (currently) at line 405 below. E.g.-1 meansoperand >> 4 and-2 meansoperand & 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 ofoparg1 andoparg2 and then parse the instruction name into two pieces).

That should work, although I was thinking of the dumber approach of just annotatingLOAD_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_FALSEJUMP_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 thatEXIT_IF_TRUE/FALSE doesn't pop, and continues in the bytecode at the originalPOP_JUMP_IF_TRUE instruction, which will pop. So the "False branch more likely" (i.e., branch not likely) version will have to actually translate toEXIT_IF_TRUE; POP_TOP. We could special-case this in the translator: it would have put such a list of uops in the expansion forPOP_JUMP_IF_TRUE and friends, and we'd have to add hand-written cases to the uop executor forEXIT_IF_TRUE etc.

In the other case (branch likely) theJUMP_FORWARD label could just beSAVE_IP label; superblock generation would then continue from the bytecode atlabel. That's not something I currently do -- a simplistic approach could do theSAVE_IP followed byEXIT_TRACE, and we can iterate later on continuing fromlabel.

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 generateEXIT_IF_TRUE; POP_TOP for now).

Honestly, for now I think I'll stick to just making the generator explicitly translateJUMPBY(n) into the correct sequence ofJUMPBY,STACK_SHRINK andDISPATCH. Nothing should followJUMPBY then.

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

These two instructions,POP_JUMP_IF_TRUE andPOP_JUMP_IF_FALSE (theNone variants can be broken down intoLOAD_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 thePOP_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 theEXIT 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 oneEXIT 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 ofPOP_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 replaceJUMPBY(<expr>) with something Tier-2-appropriate. That could actually work. There are three places where we shouldn't do that,SEND,JUMP_BACKWARD andENTER_EXECUTOR, we can exclude those by forbidding something they use.

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

In the other case (branch likely) theJUMP_FORWARD label could just beSAVE_IP label; superblock generation would then continue from the bytecode atlabel. That's not something I currently do -- a simplistic approach could do theSAVE_IP followed byEXIT_TRACE, and we can iterate later on continuing fromlabel.

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 generateEXIT_IF_TRUE; POP_TOP for now).

Honestly, for now I think I'll stick to just making the generator explicitly translateJUMPBY(n) into the correct sequence ofJUMPBY,STACK_SHRINK andDISPATCH. Nothing should followJUMPBY then.

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

LOAD_FAST iLOAD_CONST jBINARY_OP (/)STORE_FAST k...

we would not be able to include theBINARY_OP andSTORE_FAST instructions in a superblock, because the unspecializedBINARY_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 thesize field of the expansions, in the switch (currently) at line 405 below. E.g.-1 meansoperand >> 4 and-2 meansoperand & 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 ofoparg1 andoparg2 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. TheSEND jump should be a more-or-less normal jump. We also need to track where we are sending from, to handle the matchingYIELD_VALUE, so I'd "forbid"SEND for now.

I think you already handleJUMP_BACKWARD andENTER_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 andPOP_JUMP_IF_FALSE (theNone variants can be broken down intoLOAD_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 thePOP_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 theEXIT 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 oneEXIT 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 ofPOP_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 annotatingLOAD_FAST_LOAD_FAST, etc as a superinstruction in bytecodes.c. Something like adding/* superinstruction */