[Python-Dev] Register-based VM [Was: Possible performance regression]

[Neil Schemenauer]

On 2019-02-27, Victor Stinner wrote:
> The compiler begins with using static single assignment form (SSA) but
> then uses a register allocator to reduce the number of used registers.
> Usually, at the end you have less than 5 registers for a whole
> function.

In case anyone is interested on working on this, I dug up some
discussion from years ago.  Advice from Tim Peters:

    [Python-Dev] Rattlesnake progress
    https://mail.python.org/pipermail/python-dev/2002-February/020172.html
    https://mail.python.org/pipermail/python-dev/2002-February/020182.html
    https://mail.python.org/pipermail/python-dev/2002-February/020146.html

Doing a prototype register-based compiler in Python seems like a
good idea.  Using the 'compiler' package would give you a good
start.  I think this is the most recent version of that package:

    https://github.com/pfalcon/python-compiler

Based on a little poking around, I think it has not been updated for
the 16-bit word code.  Shouldn't be too hard to make it work though.

I was thinking about the code format on the weekend.  Using
three-register opcodes seems a good idea.   We could could retain
the 16-bit word code format.  For opcodes that use three registers,
use a second word for the last two registers.  I.e.

    <8 bit opcode><8 bit register #>
    <8 bit register #><8 bit register #>

Limit the number of registers to 256.  If you run out, just push and
pop from stack.  You want to keep the instruction decode path in the
evaluation loop simple and not confuse the CPU branch predictor.

Regards,

  Neil