1-register stack caching test for stack-based interpreters.

stack_machine.cpp

//
// 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
}