Make all jumps relative

[iritkatriel]

Our stats show that most of the absolute jumps that need EXTENDED_ARGs would not need them if we turn them into relative jumps. To do this we would need a backward jump version for each jump opcode (where the oparg is taken as the absolute value of a negative delta).

Furthermore, there is currently some unnecessary complexity in the compiler because (1) codegen specifies whether jumps are forward or backwards (using absolute for backwards jumps) but this information is not trusted by the assembler, which looks at the target of each jump and corrects the opcode if necessary (this is in compile.c, in normalize_jumps). We might as well emit a virtual jump instruction and let the assembler replace that with an actual jump opcode.

PR 32115: JUMP_ABSOLUTE--> JUMP_BACKWARD

[markshannon]

Here's a few more reasons for doing this:

• It speeds up jumps as we don't need get the address of the first instruction from memory
• Being easily distinguish backwards jumps has advantages for instrumentation (we need to trace backward jumps)
• It helps with hot-spot detection.
• It reduces the number of eval-breaker checks we need to do (no need on forward jumps).

[markshannon]

One minor detail:

It is probably worth making all forward jump opcodes even numbers and all backwards jumps odd numbers (or vice versa).
This helps with any instruction that combines a test and a jump, e.g. COMPARE_OP_INT_JUMP.
If the direction of the branch is encoded in the opcode, we will won't need a forward and backwards version:

     int offset = (nextopcode & 1) ? -nextoparg : nextoparg;

[iritkatriel]

We would still need to call the eval breaker only for the backwards jumps.

[iritkatriel]

Maybe instead of using the sign of the opcode we can just add another bitmap like _PyOpcode_RelativeJump and _PyOpcode_Jump. for the direction of the jump. This bitmap is generated by opcode.py.

I also think that opcode.py should generate the virtual opcodes as well, instead of them being defined in compile.c. I could create a function in opcode.h like make_relative_jump(POP_JUMP_IF_TRUE) which in one go generates POP_JUMP_IF_TRUE_FORWARD, POP_JUMP_IF_TRUE_BACKWARD and the virtual POP_JUMP_IF_TRUE.

[iritkatriel]

https://bugs.python.org/issue47120

And a PR for the first stage (replacing JUMP_ABSOLUTE by JUMP_BACKWARD): PR32115

[iritkatriel]

Maybe instead of using the sign of the opcode we can just add another bitmap like _PyOpcode_RelativeJump and _PyOpcode_Jump. for the direction of the jump. This bitmap is generated by opcode.py.

On second thought mapbe a bitmap wastes a register in the eval loop (the other bitmaps are used in the compiler).

[iritkatriel]

PR for JUMP_IF_TRUE_OR_POP/JUMP_IF_FALSE_OR_POP, which are always forwards.

[iritkatriel]

PR for POP_JUMP_IF_TRUE/FALSE/NONE/NOT_NONE.

As we predicted, this change eliminates 90% of the jumps with extended args:

Static stats

Before:

Total: 81 errors
15,128 files
333,926 code objects
5,336,282 lines
44,626,367 opcodes
2,169,508 total size of co_consts
270,630 number of co_consts
378,034 number of absolute jumps
206,404 number of relative jumps
105,676 number of absolute jumps with extended args
8,898 number of relative jumps with extended args
5,121 number of absolute jumps backwards
433 number of absolute jumps backwards with extended args
375,233 number of absolute jumps with delta < 256

After:

Total: 81 errors
15,128 files
333,926 code objects
5,336,282 lines
44,524,476 opcodes
2,169,508 total size of co_consts
270,630 number of co_consts
7,844 number of absolute jumps
576,594 number of relative jumps
1,257 number of absolute jumps with extended args
11,426 number of relative jumps with extended args
7,834 number of absolute jumps with delta < 256

[iritkatriel]

This is done.