Repository navigation
Superoptimize sequences of instructions without observable side-effects in the bytecode compiler. #102869
Description
Sequences of LOAD_FAST, COPY, LOAD_CONST, SWAP, POP_TOP, NOP (and other?) instructions have no observable side-effects as the evaluation stack cannot be observed.
Therefore we can replace any sequence of these instructions with a shorter sequence that has the same effect.
By using a superoptimizer we replace sequences with the optimal equivalent sequence.
In practice we will want to limit the size of lookup tables we generate, but we can generate complete tables for sequences up to 4 or 5.
There is a slight complication of line numbers, but as long the number of line numbers does not exceed the optimal sequence length, we can just allocate instructions line numbers without regard to the original mapping of instructions to line numbers.
Generating and using tables.
During build (or offline), we can generate a table mapping sequences of instructions to the stack, recording the optimum sequence for each stack.
E.g. The sequences LOAD_FAST x; LOAD_FAST y; SWAP 2 and LOAD_FAST y; LOAD_FAST x generate the stack [ y, x ].
So the lookup table maps [ y, x ] to LOAD_FAST y; LOAD_FAST x.
Whenever we see a sequence of instructions without observable side effects, we compute the stack, and look it up. If we find a match, emit the optimal sequence.
Mimimizing the size of tables
We will need to use some sort of numbering scheme for the indexes of LOAD_FAST and LOAD_CONST, and treat LOAD_CONST the same as LOAD_FAST.
So that LOAD_FAST a; LOAD_CONST 1.0 becomes LOAD 1; LOAD 2.
In order to keep the table size down, we should limit the number of distinct locals and constants to 4, and the depth of the stack to something like 7. That way there are only a few thousand possible stacks, and the optimal sequence for each cannot be more than 4 instructions. The entire table should then fit into tens of kbytes of const data.
Handling line numbers.
Since the instructions have no visible side-effects, we can place the line events anywhere in the instruction sequence.
Taking the above sequence with line numbers:
4 LOAD_FAST x
LOAD_FAST y
5 SWAP 2
We can generate:
4 LOAD_FAST y
5 LOAD_FAST x
which is valid as it produces the same sequence of line events and the observable state of the VM is the same in both cases.
Activity
markshannon commentedon Mar 21, 2023
See faster-cpython/ideas#567 for the original motivation for this.
CCLDArjun commentedon Apr 6, 2023
@markshannon why not hardcode these sequences into the peepholer?
something like this: CCLDArjun@22b6aff
Are there enough cases of these that calculating the stack effect and building a lookup table would be worthwhile?
I would imagine finding the stack effect would involve calculating how the stack is before and after all of these operations, right?
brandtbucher commentedon May 2, 2023
Just curious... how is this different from the existing
swaptimizeandapply_static_swapsfunctions inflowgraph.c? If it's similar to what we have there, perhaps those functions could just be taught how to handle more instructions (likeCOPY)?The main idea there is that optimizing runs of
SWAPs is a solved problem (addingCOPYinstructions on top of this would be very easy). Then, instead of copying and swapping things on the stack at runtime, you just copy and swap instructions in the stream at compile time.brandtbucher commentedon May 2, 2023
3.10:
3.11:
carljm commentedon May 2, 2023
apply_static_swapsonly reordersSWAPand opcodes that pop the TOS (STORE_FASTandPOP_TOP.) This issue proposes to also reorderCOPY,LOAD_FAST, andLOAD_CONST(opcodes that push to stack), but notably doesn't propose to touchSTORE_FAST, since it does have an observable side effect (changes the value of a variable in locals.)I think if
apply_static_swapswere to gain support for opcodes that push to stack (and arbitrary sequences of pushes/pops/swaps), its implementation would have to change quite a bit and it would end up looking pretty similar to what is proposed here.Because
apply_static_swapsreordersSTORE_FAST, it has to be conservative about not optimizing anytime it sees a change in lineno, whereas the proposal here (by avoidingSTORE_FAST) can freely optimize as long as there are enough instructions in the optimal sequence to account for all distinct line numbers seen in the original sequence (and can pad withNOPif not; likely the actual implementation would always pad withNOPto avoid changing block size, and would allow later NOP-removal to remove NOPs that aren't needed for their lineno.)carljm commentedon Jun 2, 2023
Discussion in faster-cpython/ideas#585 suggests that we can't actually move
LOAD_FASTto a different line, because offrame_setlinenoand debuggerjumpinstructions. That makes the line number handling part of this a bit more complex than suggested above.