Make all jumps relative, and maybe change format.

[markshannon]

Currently JUMP_FORWARD is relative, but all others are absolute.

We should make all jumps relative, because:

1. With inline caches we will no longer need first_instr to find cache entries. With relative jumps we will not need it all, freeing up a register in the interpreter (or saving a memory access).
2. It will allow the compiler to freely re-order basic blocks reducing the number of jumps on the fast path.

Possible designs.

1. Pairs of instructions. A jump instruction, like any other consists of opcode oparg, possibly preceded by EXTENDED_ARG. oparg is unsigned, so if jumps were to be relative, then the direction would have to be encoded in the instruction. So POP_JUMP_IF_TRUE would become POP_JUMP_IF_TRUE_FORWARD and POP_JUMP_IF_TRUE_BACKWARD.
2. Signed operands. This tricky, as we don't know where to sign extend from as we don't know how large the operand is. We could place the direction in the low bit, but that is a bit fiddly.
3. 32 bit instructions. All jump instructions could be followed by a signed 16 bit extension, giving us 23 bit offsets. This requires a bit of a hack to get 31 bit offsets: rely on wrapping and ignore the extension. Since offsets large than 23 bits will be vanishingly rare, it shouldn't be a problem in practice.

Given that inline caches are going spread out the code, jumps of over 255 are going to become more common.

If we use 32 bit instructions, we could also encode the test in the low bit.

TARGET(POP_JUMP_TEST) {
    int extension = *next_instr++;
    PyObject *val = POP();
    int is_true = true_test(val);
    int branch = is_true ^ (oparg & 1);
    int offset = (extension << 7) | (oparg >> 1);
    next_instr += branch *offset; // Use sign preserving shift here
    NEXT_OPARG();
    DISPATCH();
}

[gvanrossum]

Are you thinking we could transition to this new design in time for the feature freeze? Or is this more a 3.12 thing?

[markshannon]

It depends on how everything else goes. I don't see any reason not to do this for 3.11, but we might just run out of time.

[markshannon]

python/cpython#31575 more than doubles the number of EXTENDED_ARG instructions due to inline caches.
We will need to do this for 3.11.

[markshannon]

python/cpython#31575 also reduces the number of POP_JUMP_IF_NONE instructions by about 5%.
Presumably because the sequence isn't merged if there is an EXTENDED_ARG in the middle.

[brandtbucher]

This confuses me. Doesn't this happen during peepholing, before EXTENDED_ARGS are added?

[markshannon]

Indeed. There should be no change.
The stats aren't 100% accurate, but 5% is a surprisingly large change.

[markshannon]

(This is an elaboration of python/cpython#32215 (comment))

There are four jump instructions, JUMP_IF_TRUE_OR_POP, JUMP_IF_FALSE_OR_POP, JUMP_IF_NOT_EXC_MATCH and JUMP_IF_NOT_EG_MATCH that have the following properties:

• They are relatively uncommon.
• They are highly biased in direction, they almost almost always go forward.

Which means that having a forward and backward version of each would be wasteful.
So, let's have the assembler fix it.

By fixing up backwards branches in the assembler, we don't need to bloat the interpreter with two versions of each of these opcodes and we don't need to complicate the optimizer.

JUMP_IF_FALSE_OR_POP and JUMP_IF_TRUE_OR_POP can be fixed as follows:

    JUMP_IF_FALSE_OR_POP backwards

becomes

    COPY 1
    POP_JUMP_IF_FALSE backwards
    POP_TOP

JUMP_IF_NOT_EXC_MATCH and JUMP_IF_NOT_EG_MATCH can be fixed as follows:

    JUMP_IF_NOT_EXC_MATCH backwards

becomes

    JUMP_IF_NOT_EXC_MATCH jump
    JUMP_FORWARD end
jump:
    JUMP_BACKWARD backwards
end:

Hopefully, these cases should be very rare.

[iritkatriel]

I'm not sure that the exception matching opcodes even need to be jumps. See #348.

[markshannon]

Yes, that's probably better.

[markshannon]

Rather than complex bit hacks, we could just have a simple rule:

• All conditional branches must go forwards

The compiler will need to cope with this restriction, in two ways

• The front-end should try to avoid producing conditional backward branches
• The assembler will need to fix them up, by replacing

    POP_JUMP_IF_FALSE backwards

with

    POP_JUMP_IF_TRUE end
    JUMP_BACKWARD backwards
end:

This is a bit less efficient for while and continue as there will be two jumps, not one.
We can mitigate this by unrolling very tight loops.

Only having forward branches makes specialization a lot simpler, and only JUMP_BACKWARD needs a CHECK_EVALBREAKER check.

Another advantage of this is that we only need to handle JUMP_BACKWARD and JUMP_BACKWARD_NO_INTERRUPT when looking for hot code to optimize.

[iritkatriel]

This could be better. But note that it introduces a situation where the optimiser creates a new basicblock, which I think we don't currently have. So we need to think what that means.

[markshannon]

In theory, only the optimizer should care about basic blocks.
All the assembler should need to handle is a list of instructions or superblocks.

[gvanrossum]

Remind me what is the reason a while loop may have a conditional jump back? (I understand the continue situation, presumably it's optimizing if <cond>: continue.)

[markshannon]

Remind me what is the reason a while loop may have a conditional jump back?

One instruction (the conditional branch) per loop instead two (the conditional branch and the unconditional back jump)

[sweeneyde]

Remind me what is the reason a while loop may have a conditional jump back? (I understand the continue situation, presumably it's optimizing if <cond>: continue.)

If evaluating the condition is short, it looks like it might get repeated at the bottom of the loop:

>>> from dis import dis
>>> def f(x):
...     while x:
...         x -= 1
...
>>> dis(f)
  1           0 RESUME                            0

  2           2 LOAD_FAST                         0 (x)
              4 POP_JUMP_FORWARD_IF_FALSE         9 (to 24)

  3     >>    6 LOAD_FAST                         0 (x)
              8 LOAD_CONST                        1 (1)
             10 BINARY_OP                        23 (-=)
             14 STORE_FAST                        0 (x)

  2          16 LOAD_FAST                         0 (x)      <--- repeats instr 2
             18 POP_JUMP_BACKWARD_IF_TRUE         7 (to 6)   <--- equivalent of instr 4
             20 LOAD_CONST                        0 (None)
             22 RETURN_VALUE
        >>   24 LOAD_CONST                        0 (None)
             26 RETURN_VALUE

[sweeneyde]

Actually always, not just when the condition is short: https://github.com/python/cpython/blob/1cd8c29dace2dc6b91503803113fea4288ca842b/Python/compile.c#L3196

[iritkatriel]

Remind me what is the reason a while loop may have a conditional jump back?

One instruction (the conditional branch) per loop instead two (the conditional branch and the unconditional back jump)

But then doesn’t the transformation you’re suggesting here just cancel out that optimisation, and bring us back to two jumps?

[gvanrossum]

But then doesn’t the transformation you’re suggesting here just cancel out that optimisation, and bring us back to two jumps?

Unless the expected number of iterations is 1...

[markshannon]

But then doesn’t the transformation you’re suggesting here just cancel out that optimisation, and bring us back to two jumps?

Yes, it does. But it allows us to skip the eval-breaker check in the conditional branch and simplifies the code in COMPARE_OP_FLOAT_JUMP and COMPARE_OP_INT_JUMP which are somewhat convoluted at the moment. Those improvements might well balance out the extra dispatch.