jserv
commented
1 year ago Mike Pall, creator of LuaJIT, talked about writing a fast interpreter with control-flow graph optimization.
The control-flow graph of an interpreter with C switch-based dispatch looks like this:
.------.
V |
| |
L | L = instruction load
D | D = instruction dispatch
/ /|\ \ |
/ / | \ \ |
C C C C C | C = operand decode
X X X X X | X = instruction execution
\ \ | / / |
\ \|/ / |
| |
V |
`------'Each individual instruction execution looks like this:
......V......
:X | :
: |\ \ :
: F S S : F = fast path
: |/ / : S = slow paths
: | :
:.....V.....:We're talking here about dozens of instructions and hundreds of slow paths. The compiler has to deal with the whole mess and gets into trouble:
- Diamond-shaped control-flow is known to be the worst-case scenario for most optimizations and for register allocation. Nested diamond-shaped control-flow is even worse.
- The compiler doesn't have enough hints to see what the fast paths and what the slow paths are. Even if you'd be able to tell it, it still sees this as a single giant control-flow graph. Anything in this loop could potentially influence anything else, so almost nothing can be hoisted or eliminated. The slow paths kill the opportunities for the fast paths and the complex instructions kill the opportunities for the simpler instructions.
- The standard register allocation heuristics fail at this scale, so the compiler has trouble keeping important variables in registers.
We can use a direct or indirect-threaded interpreter even in C, e.g. with the computed 'goto &' feature of GCC:
* * * * *
| | | | |
C C C C C C = operand decode
X X X X X X = instruction execution
L L L L L L = next instruction load
D D D D D D = next instruction dispatch
| | | | |
V V V V VThis effectively replicates the load and the dispatch, which helps the CPU branch predictors. But it has its own share of problems:
- There's no loop the compiler could recognize. And all of those gotos can jump to pretty much anywhere in the code. Therefore the compiler is unable to hoist anything, because there will be a slow path where an aliasing store kills all opportunities.
- The register allocator can only treat each of these segments separately and will do a real bad job. There's just no way to give it a goal function like "I want the same register assignment before each goto".
- Tail-merging and CSE will happily join all these common tails of each instruction and generate a single dispatch point. Ick. You can try to disable some optimizations for this piece of code, but this will negatively impact all paths.
- There's a point where you start to fight the compiler and this is a game you cannot win.
If you write an interpreter loop in assembler, you can do much better:
- Keep a fixed register assignment for all instructions.
- Keep everything in registers for the fast paths. Spill/reload only in the slow paths.
- Move the slow paths elsewhere, to help with I-Cache density.
- Pre-load instructions and pre-decode operands.
Here's how this would look like:
* * * * *
| | | | |
C C C C C C = partial operand decode for this instruction
F> F> F> F> F> F = fast path, > = exit to slow path
L L L L L L = next instruction load
C C C C C C = partial operand decode for the next instruction
D D D D D D = next instruction dispatch
| | | | |
V V V V VYou can get this down to just a few machine code instructions. LuaJIT's interpreter is fast, because
qwe661234
It would still make sense to consolidate the existing interpreter as the foundation of tiered compilation before we actually develop JIT compiler (#81). See A look at the internals of 'Tiered JIT Compilation' in .NET Core for context. Although #95 uses tail-cail optimization (TCO) to reduce interpreter dispatch cost, we still need to investigate at several interpreter dispatch techniques before deciding how to move forward with more performance improvements and code maintenance.
The author of wasm3 provides an interesting project interp, which implements the following methods:
Preliminary experiments on Intel Xeon CPU E5-2650 v4 @ 2.20GHz with bench.
[ Calls Loop ]
[ Switching ]
[ Direct Threaded Code ]
[ Token (Indirect) Threaded Code ]
[ Tail Calls ]
[ machine code Inlining ]
After #95 is merged, we are concerned about
Reference: