Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
1-register stack caching test for stack-based interpreters.
//
// Simple stack-based virtual machine tests.
//
// I use two slightly different strategies to manage the
// interpreter stack: First is using the "naive" approach
// of keeping a stack pointer that is bumped/decremented
// for every instruction that has stack operands. The second
// approach uses a "stack cache" register to cache the
// Top-of-Stack (TOS) value.
//
// The 1 register TOS cache will compile to fewer memory
// access instruction (since the compiler can keep it in
// an actual machine register) and also removes some stack
// pointer management code for common instructions (albeit
// possibly adding more code to instructions like Push/Pop).
//
// Overall, this is a simple and easy optimization for
// stack-based virtual machines.
//
#include <cstdint>
#include <cstdlib>
#include <cstdio>
// --------------------------------------------------------
enum class Instruction : std::uint8_t
{
Noop,
Halt,
Push,
PrintTop,
Add,
Sub,
Mul,
Div,
Mod,
// Number of entries in the enum, not an actual instruction.
Count
};
// --------------------------------------------------------
struct VM
{
const Instruction * code;
const int * data;
int * stack;
};
// --------------------------------------------------------
void interpretSimpleStackBased(VM * vm)
{
const Instruction * ip = vm->code; // instruction pointer
const int * dp = vm->data; // data pointer
int * sp = vm->stack; // stack pointer
for (;;)
{
const Instruction instr = *ip++;
switch (instr)
{
case Instruction::Noop: break;
case Instruction::Halt: {
std::printf("Halt\n");
return;
}
case Instruction::Push: {
*sp++ = *dp++;
}
break;
case Instruction::PrintTop: {
std::printf("Top is = %i\n", *(sp - 1));
}
break;
case Instruction::Add: {
int b = *(--sp);
int a = *(--sp);
int c = a + b;
*sp++ = c;
}
break;
case Instruction::Sub: {
int b = *(--sp);
int a = *(--sp);
int c = a - b;
*sp++ = c;
}
break;
case Instruction::Mul: {
int b = *(--sp);
int a = *(--sp);
int c = a * b;
*sp++ = c;
}
break;
case Instruction::Div: {
int b = *(--sp);
int a = *(--sp);
int c = a / b;
*sp++ = c;
}
break;
case Instruction::Mod: {
int b = *(--sp);
int a = *(--sp);
int c = a % b;
*sp++ = c;
}
break;
default: {
std::abort(); // Invalid instruction!
}
} // switch
} // for
}
// --------------------------------------------------------
void interpretStackBasedTOSCache(VM * vm)
{
const Instruction * ip = vm->code; // instruction pointer
const int * dp = vm->data; // data pointer
int * sp = vm->stack; // stack pointer
int r0 = 0; // top-of-stack (TOS) cache register
for (;;)
{
const Instruction instr = *ip++;
switch (instr)
{
case Instruction::Noop: break;
case Instruction::Halt: {
std::printf("Halt\n");
return;
}
case Instruction::Push: {
*sp++ = r0;
r0 = *dp++;
}
break;
case Instruction::PrintTop: {
std::printf("Top is = %i\n", r0);
}
break;
case Instruction::Add: {
int a = *(--sp);
r0 = a + r0;
}
break;
case Instruction::Sub: {
int a = *(--sp);
r0 = a - r0;
}
break;
case Instruction::Mul: {
int a = *(--sp);
r0 = a * r0;
}
break;
case Instruction::Div: {
int a = *(--sp);
r0 = a / r0;
}
break;
case Instruction::Mod: {
int a = *(--sp);
r0 = a % r0;
}
break;
default: {
std::abort(); // Invalid instruction!
}
} // switch
} // for
}
// --------------------------------------------------------
int main()
{
const Instruction code[] = {
Instruction::Noop,
Instruction::Noop,
Instruction::Push,
Instruction::Push,
Instruction::Add,
Instruction::Push,
Instruction::Mul,
Instruction::PrintTop,
Instruction::Push,
Instruction::Mod,
Instruction::PrintTop,
Instruction::Push,
Instruction::Div,
Instruction::PrintTop,
Instruction::Push,
Instruction::Sub,
Instruction::PrintTop,
Instruction::Push,
Instruction::Mul,
Instruction::PrintTop,
Instruction::Noop,
Instruction::Noop,
Instruction::Halt,
};
const int data[] = {
1,
1,
2,
5,
2,
1,
0,
};
int stack[256];
VM vm = { code, data, stack };
std::printf("Running simple stack-based interpreter:\n");
interpretSimpleStackBased(&vm);
std::printf("Running stack-based interpreter with TOS cache:\n");
interpretStackBasedTOSCache(&vm);
// Expected output for both interpreters is:
// Top is = 4
// Top is = 4
// Top is = 2
// Top is = 1
// Top is = 0
// Halt
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment