[Python-ideas] Exposing flat bytecode representation to optimizers

[Victor Stinner]

2016-02-05 20:58 GMT+01:00 Andrew Barnert via Python-ideas
<python-ideas at python.org>:
> It would break the optimizer APIs, but `PyCode_Optimize` isn't public

Sadly, PyCode_Optimize() is public and part of the stable ABI. But I'm
ok to take the responsability of breaking it if we implement the PEP
511 since we will probably have a much better API to optimize AST and
bytecode, and I would prefer that no one directly uses
PyCode_Optimize()!


> and the API proposed by PEP 511 is public, but that PEP isn't even finalized, much less accepted yet.

To be clear: the PEP 511 is a draft still stuck in python-ideas, it's
not ready for a review on python-dev. I still expect changes on the
API.

I'm very interested by your feedback on the bytecode transformer API :-)


>   [^3]: The compiler doesn't actually have exactly what the optimizers would want, but it's pretty close: it has a linked list of block objects, each of which has an array of instruction objects, with jump targets being pointers to blocks. That's actually even better to work with, but too complicated to expose to optimizers.

The current implementation of the peephole optimizer has a complex
code to update jumps. IMHO it would be simpler if the code would be
blocks of instructions.

My plan is to implement most implementations at AST level and only
optimizer jumps at "bytecode" level. So I don't need much informations
on instructions, just a structure easy to manipulate to optimize
jumps.

For my old "registervm" project, I also wrote my own API to have a
higher level structure for bytecode:
https://hg.python.org/sandbox/registervm/file/tip/Lib/registervm.py

* Block: list of sequential instructions. Blocks are linked together
by jumps (and conditional jumps)
* Instruction
* Instruction argument: Immediate, Immediate8 (8 bits), Label (for
jumps), Register (well, something specific to my register-based
instructions), Local (local variable)

Basically, the code is a list of blocks where a block is a list of
instructions + arguments (in registervm, an instruction can have many
arguments, not only one). In registervm, the Instruction class stores
directly arguments, but that's more an implementation detail ;-)

Do you know if byteplay and other projects have a similar design? It
would be nice to find the root common structure to be a generic API.


> Flattening it would be trivial. Or, if that's too expensive, we could do something almost as simple and much cheaper: convert it in-line to a deque-like linked list of arrays, with jump targets being indices or pointers into that. Or we could just expose the list of blocks as-is, as an opaque thing with a mutable-deque-of-instructions API around it.

For the PEP 511 we can imagine multiple levels for code tranformers:
block of instructions, flatten bytecode, AST, etc.

The cost of the transformation is to convert internal from CPython
objects to Python objects, and then convert the result of the code
transformer back to internal CPython objects. For AST, I expect the
cost of the double conversions to be non-negligible since AST uses a
lot of small objects.

Hopefully, no conversion is needed if no code transformer is registered.

Victor