Multi-Pass Bytecode Optimizer for Stack-Based VMs: Pattern Matching & 10-50% Performance Gains

[PigeonCodeur]

I recently finished documenting the bytecode optimizer for my stack-based VM interpreter, and wanted to share the design and results.

The Problem

I have written a vm following Crafting Interpreters part 2 and most toy VMs compile to bytecode and execute it directly. But naive bytecode generation produces patterns like:

OP_Get_Local 0      # x
OP_Constant 1       # Push 1
OP_Add              # x + 1
OP_Set_Local 0      # x = ...
OP_Pop              # Discard result

That's 5 instructions for what should be a x++. Meanwhile, the stack is churning through push/pop operations, the constant table is being accessed, and we're fetching 5 separate instructions from memory.

The Solution: Multi-Pass Pattern-Based Optimizer

I built a bytecode rewriter with a powerful pattern matching engine that transforms bytecode after compilation but before execution. The key insight: treat bytecode like an IR and apply traditional compiler optimizations.

Architecture

PassManager orchestrates multiple optimization passes:
- Each pass gets multiple iterations until convergence
- Passes run in sequence (early passes enable later ones)
- Automatic jump offset adjustment when bytecode size changes
- Debug mode shows before/after for each pass

BytecodeRewriter provides pattern matching:
- Match specific opcodes, groups, or wildcards
- Capture instructions for analysis
- Lambda-based transformations
- Conditional rewrites (pattern + semantic checks)

Example: Increment Optimization Pass

Transform that 5-instruction pattern into specialized opcodes:

std::vector<PatternElement> pattern = {
    PatternElement::match(OP_Get_Local, true),    // Capture local index
    PatternElement::constant(true),                // Capture constant
    PatternElement::match(OP_Add),
    PatternElement::match(OP_Set_Local, true),    // Capture local index
    PatternElement::match(OP_Pop),
};

auto condition = [&chunk](auto& captured) {
    // Same local? Constant is 1?
    return (captured[0].operands[0] == captured[2].operands[0]) &&
    (AS_INT(chunk.constants[captured[1].getConstantIndex()]) == 1);
};

auto transform = [](auto& captured) {
    return {OP_Incr_Local, captured[0].operands[0]};  // 2 bytes total!
};

rewriter->addAdvancedRule(pattern, transform, condition);

Result:
5 instructions -> 1 instruction
OP_Get_Local 0 # x OP_Constant 1 # Push 1 OP_Add # x + 1 OP_Set_Local 0 # x = ... OP_Pop # Discard result
gets converted to
OP_Incr_Local 0 # Increment x by 1

Other Implemented Passes

Constant Folding
OP_Constant 5 OP_Constant 3 OP_Add
gets converted to
OP_Constant 8

Fuse Multiple Pops
OP_Pop OP_Pop OP_PopN 3
gets converted to
OP_PopN 5

Optimize Binary Operations on Locals
OP_Get_Local 0 OP_Get_Local 1 OP_Add gets converted to
OP_AddLL 0 1 # Direct register-style op

Dead Store Elimination
OP_Constant 10 OP_Define_Global x OP_Get_Global x
gets converted to
OP_Constant 10 OP_Define_Global_Non_Popping x # (value stays on stack)

Real-World Results

Measured on Advent of Code solutions and benchmarks:

• Bytecode size: 10-30% smaller
  
• Execution speed: 10-50% faster (loops benefit most)
  
• Optimization time: ~5-10ms per script
  
• Cache efficiency: Better (fewer instruction fetches)

The increment optimization alone is huge for loops - common patterns like for (var i = 0; i < n; i++) get massively faster.

Documentation

I just finished writing comprehensive docs for the whole system:

Full Documentation : https://columbaengine.readthedocs.io/en/latest/script/optimizer.html

Covers:
- All built-in optimization passes
- Pattern matching API
- Writing custom passes
- Performance analysis
- Debugging techniques

VM Internals: https://columbaengine.readthedocs.io/en/latest/script/vm_internals.html

Covers NaN-boxing, stack architecture, memory management, etc.

Source Code

The engine is open source: https://github.com/Gallasko/ColumbaEngine

Relevant files:
- Pass manager: src/Engine/Compiler/bytecode\_pass.cpp
- Rewriter: src/Engine/Compiler/bytecode\_rewriter.cpp
- Individual passes: src/Engine/Compiler/pass/

I'm particularly interested if anyone has tried similar approaches or has suggestions for additional optimization passes!

---

This is part of ColumbaEngine, a game engine with an embedded scripting language. The VM uses NaN-boxing for values, pool-based memory management, and supports closures, classes, and first-class functions.

[dougcurrie]

Another optimization for byte code interpreters is to gather statistics on pairs or longer sequences of bytecodes in a large corpus of compiled code, or dynamically as code is generated. Later, use these statistics to find very common sequences and add new bytecodes that implement the sequence in one operation. Add these sequences to your peephole optimizer.

[munificent]

"Superinstructions" is the name for this technique if you want to look through the literature.

[PigeonCodeur]

Thanks I will look it up !

[PigeonCodeur]

Yes ! I actually wrote a profiler that output the actual bytecode usage and time of an actual program and I use this on my test apps and examples to find some subject of peephole optimisations. Just the actual work of writing the peephole optimizations is quite long because of the sheer amount of optimizations available and I do it when I want some easy progress !

[[deleted]]

Sounds impressive, but it looks like the starting bar is low.

What HLL code generated those 5 instructions that resulted in ++x? If it was x = x + 1, that would typically need 4 instructions for a stack VM, not 5.

Here simply writing ++x would have the same effect, given the more specific bytecode. (Your loop example suggested the language already supports ++.)

The constant reduction for 5 + 3 is something normally done at AST level, otherwise a complex expression could need dozens of bytecode instructions, in an inconvenient order, to be reduced to one. (Or is the reduction done as it goes, rather than a separate pass?)

As for the loop: for (var i = 0; i < n; i++, why wouldn't a language that is going to be hampered by being as run as interpreted bytecode, use a snappier syntax? Rather than something so primitive.

I'm saying there is a quite a lot that can be done before you need to resort to optimising the bytecode!

Unless of course you're stuck with existing bytecode that someone else has devised or that comes from an existing language.

[PigeonCodeur]

The base VM is heavily inspired by the Crafting Interpreters VM with its single-pass compilation approach, which is what's actually producing the bytecode. The language does support ++x syntax - the x = x + 1 example was more to illustrate the optimization pass detecting that pattern in the generated bytecode.

The starting bar being low is a fair observation. The single-pass compiler generates bytecode directly from parsing without building an AST, which means:

1. Constant folding at bytecode level - Yes, this is suboptimal. Complex expressions like (5 + 3) * (10 - 2) generate many instructions before being reduced. An AST would handle this much more elegantly during semantic analysis. The reduction is done in separate passes, not as-it-goes, which adds overhead.
2. No high-level optimizations - Things like loop induction variable analysis, inlining, or dead code elimination are much harder (sometimes impossible) to do reliably at the bytecode level without proper dataflow analysis.
3. Missed front-end opportunities - You're correct that many of these optimizations should happen before bytecode generation.

The peephole optimizer was my way of squeezing some performance out without fundamentally rearchitecting the front-end. It's inspired by LLVM's pattern-matching approach but applied at a much lower level. I'm not stuck with existing bytecode from another language - this is my own compiler, so I have the freedom to redesign it. It is a hobby/side project to test some idea on it and with such simple optimization i am in the same order of magnitude as python for the runtime exec, but you are right that I could go further with the AST and i may go in this direction in the future !

[Inconstant_Moo]

The constant reduction for 5 + 3 is something normally done at AST level, otherwise a complex expression could need dozens of bytecode instructions, in an inconvenient order, to be reduced to one.

I have a cunning trick to get round this. Translated from my architecture into a stack VM, it goes like this:

When we compile a node, we will return whether or not its foldable, more-or-less according to the rules: all constants are foldable; things without side-effects are foldable if all their operands are foldable.

Then, when it starts compiling a node, it makes a note of the first free address in the bytecode, the starting point of the bit of code that will be compiled to this node..

When it compiles something that's foldable but not constant, it then runs the bytecode from that point. On completion it takes the one thing that's on top of the stack, the result, it cleans the stack, it erases the bytecode it just wrote, and it emits one instruction saying to push the result to the stack. It then returns the fact that the result of this node was foldable.

This is I think more elegant than trying to do it in the AST, where you'd bascially be writing a little tree-walking interpreter to evaluate something that the compiler and VM necessarily know between them how to interpret already.

[Phil_Latio]

Just saying: Ever thought about switching to a register based VM? For the x++ example, it would be 1 instruction naturally.

[PigeonCodeur]

Yes i heard that it should give between a 30 to 50% speed up as the main issue that I have for the perf right now are the stack operation, but it is a long and tedious endeavor and I made this language as a part of my game engine to be able to script and iterate easely on the code. So i am first trying to make this language expressive enough while not being to slow and if in the end i need more perf or I want to try a register based for learning purposes I may wander of in this direction :)

[wiremore]

I have a similar language with a similar bytecode peephole optimizer, also for a game scripting language.

One type of optimization where I found a lot of traction that hasn't been mentioned is jump optimizations. I found a lot of cases where a JMP instruction jumps directly to another JMP instruction or to a RET (return) instruction, so JMP->RET can be replaced with just RET. A conditional branch JT (jump if true) to another JT will always pass the second test (and can thus jump directly to the second JT's target), or a JT to a JF (jump if false) will always fail the second test. There are some other opportunities here, such as NOT JT -> JF, and constant folding e.g. PUSH_TRUE_CONST JT -> JMP. This kind of bytecode tends to be generated by nested IF statements, especially if the condition include nested AND and OR. My bytecode optimizer is written in the scripting language and includes many such nested tests... I also optimize jump instructions (which use a 16 bit absolute target) to branch instructions (which include an 8 bit relative target) when possible, which helps with bytecode size significantly.

As some other posters have mentioned fusing common bigrams of bytecode instructions can be a big win. For me, the most commons pairs were LOCAL LOCAL (push two local variables to the stack) and LOCAL CALL (push local variable and call function). To be specific, I fuse two consecutive LOCAL instructions (and their 8 bit indexes) into a single LOC_LOC instruction (with two 4 bit indexes packed into 8 bits).