VM Execution

This page details how the GLaDOS Virtual Machine executes IR bytecode. The VM is implemented in src/VM/ modules.

Overview

The GLaDOS VM is a stack-based virtual machine that executes the IR instructions generated by the compiler. Key characteristics:

• Stack-based architecture: Operands pushed/popped from value stack
• Indexed local variables: Fast array-based local storage
• Type-specific operations: Runtime type checking for safety
• Function call frames: Proper call/return mechanism
• Offset-based control flow: Relative jumps for branches/loops

VM State Structure

The VM maintains execution state in VMState:

data VMState = VMState
    { stack :: [Value]
    , locals :: [Value]
    , pc :: Int
    , callStack :: [CallFrame]
    }

Stack

The value stack holds:

• Operands for operations
• Intermediate computation results
• Function arguments
• Return values

Operations:

• push :: Value -> VMState -> VMState
• pop :: VMState -> VMResult (Value, VMState)

Locals

Indexed local variables stored as a list (array):

locals :: [Value]

Indexing:

• Parameters occupy indices 0 to paramCount - 1
• Local variables occupy indices paramCount to localVarCount - 1

Example for int add(int a, int b):

locals[0] = a (parameter)
locals[1] = b (parameter)

Example for int sum(int n):

locals[0] = n (parameter)
locals[1] = total (local variable)
locals[2] = i (local variable)

Operations:

• getLocal :: Int -> VMState -> VMResult Value
• setLocal :: Int -> Value -> VMState -> VMResult VMState

Program Counter

The PC tracks the current instruction index:

pc :: Int

• Starts at 0 for each function
• Incremented after each instruction (unless instruction modifies it)
• Modified by Jump, JumpIfFalse for control flow
• Must be within bounds [0, length code - 1]

Call Stack

The call stack stores information for function returns:

callStack :: [CallFrame]

data CallFrame = CallFrame
    { returnPC :: Int
    , returnFuncIdx :: Int
    , savedLocals :: [Value]
    }

Purpose:

• Save return address when calling function
• Restore caller's locals after return
• Enable recursive calls

Value Types

Runtime values are tagged:

data Value
  = VInt Int
  | VBool Bool
  | VFloat Double

Type checking happens at runtime when instructions expect specific types.

Execution Model

Fetch-Decode-Execute Loop

The VM uses a classic fetch-decode-execute cycle:

runLoop :: IRProgram -> Int -> CompiledFunction -> VMState -> VMResult Value
runLoop program funcIdx func state
    | pc state < 0 = Left "PC became negative"
    | pc state >= length (code func) = Left "PC out of bounds"
    | otherwise =
        let instruction = code func !! pc state
            oldPC = pc state
        in case executeInstruction program instruction state of
            Left err -> Left err
            Right newState ->
                case instruction of
                    Halt -> -- return result
                    Return -> -- return result
                    _ -> -- continue loop

Steps:

1. Fetch: Get instruction at code[pc]
2. Decode: Pattern match on instruction type
3. Execute: Dispatch to appropriate handler
4. Increment: pc = pc + 1 (unless instruction modified PC)
5. Repeat: Loop until Return or Halt

Initialization

When calling a function:

execute :: IRProgram -> Int -> [Value] -> VMResult Value
execute program funcIdx args =
    let func = functions program !! funcIdx
        initialLocals = args ++ replicate (localVarCount func) (VInt 0)
        initialState = VMState {
            stack = [],
            locals = initialLocals,
            pc = 0,
            callStack = []
        }
    in runLoop program funcIdx func initialState

Initialization:

• Locals: Parameters first, then uninitialized locals (default VInt 0)
• Stack: Empty
• PC: 0
• CallStack: Empty for main, populated for nested calls

Instruction Execution

Stack Operations

PushInt n:

push (VInt n) state

Stack: [...] → [n, ...]

PushBool b:

push (VBool b) state

Stack: [...] → [b, ...]

PushFloat f:

push (VFloat f) state

Stack: [...] → [f, ...]

Pop:

case pop state of
    Right (_, newState) -> Right newState

Stack: [x, ...] → [...] (discard x)

Local Variable Operations

GetLocal idx:

case getLocal idx state of
    Right val -> Right (push val state)

• Loads locals[idx]
• Pushes value onto stack
• Error if index out of bounds

Stack: [...] → [locals[idx], ...]

SetLocal idx:

case pop state of
    Right (val, newState) -> setLocal idx val newState

• Pops value from stack
• Stores into locals[idx]
• Error if index out of bounds

Stack: [val, ...] → [...]

Integer Arithmetic

AddInt, SubInt, MulInt:

binaryIntOp :: (Int -> Int -> Int) -> VMState -> VMResult VMState
binaryIntOp op state =
    case popInt state of
        Right (b, state1) -> case popInt state1 of
            Right (a, state2) -> Right (push (VInt (a `op` b)) state2)

Stack: [a, b, ...] → [a op b, ...]

DivInt:

case popInt state of
    Right (b, state1) ->
        if b == 0
        then Left "Runtime error: Division by zero"
        else case popInt state1 of
            Right (a, state2) -> Right (push (VInt (a `div` b)) state2)

Stack: [a, b, ...] → [a / b, ...] (or error if b == 0)

Float Arithmetic

AddFloat, SubFloat, MulFloat:

binaryFloatOp :: (Double -> Double -> Double) -> VMState -> VMResult VMState

Stack: [a, b, ...] → [a op b, ...]

DivFloat:

• Check for division by 0.0
• Otherwise same as integer division

Stack: [a, b, ...] → [a / b, ...] (or error)

Unary Operations

NegInt:

case popInt state of
    Right (n, newState) -> Right (push (VInt (-n)) newState)

Stack: [n, ...] → [-n, ...]

NegFloat:

case popFloat state of
    Right (n, newState) -> Right (push (VFloat (-n)) newState)

Stack: [n, ...] → [-n, ...]

NotBool:

case popBool state of
    Right (b, newState) -> Right (push (VBool (not b)) newState)

Stack: [b, ...] → [!b, ...]

Integer Comparison

EqInt, NeqInt, LtInt, GtInt, LeInt, GeInt:

compareInts :: (Int -> Int -> Bool) -> VMState -> VMResult VMState
compareInts cmp state =
    case popInt state of
        Right (b, state1) -> case popInt state1 of
            Right (a, state2) -> Right (push (VBool (a `cmp` b)) state2)

Stack: [a, b, ...] → [a cmp b, ...] (boolean result)

Float Comparison

EqFloat, NeqFloat, LtFloat, GtFloat, LeFloat, GeFloat:

compareFloats :: (Double -> Double -> Bool) -> VMState -> VMResult VMState

Stack: [a, b, ...] → [a cmp b, ...] (boolean result)

Logical Operations

AndBool, OrBool:

binaryBoolOp :: (Bool -> Bool -> Bool) -> VMState -> VMResult VMState
binaryBoolOp op state =
    case popBool state of
        Right (b, state1) -> case popBool state1 of
            Right (a, state2) -> Right (push (VBool (a `op` b)) state2)

Stack: [a, b, ...] → [a op b, ...]

Note: Both operands are always evaluated (no short-circuit at VM level).

Control Flow

Jump offset:

Right (state {pc = pc state + offset})

• Adds offset to PC
• No stack change
• PC is not auto-incremented after this instruction

JumpIfFalse offset:

case popBool state of
    Right (condition, newState) ->
        if condition
        then Right newState
        else Right (newState {pc = pc newState + offset})

• Pops boolean from stack
• If false: jump by offset
• If true: continue to next instruction

Stack: [bool, ...] → [...]

Call funcIdx:

case getFunctionAt program funcIdx of
    Right targetFunc ->
        let argCount = paramCount targetFunc
        in case popNValues argCount [] state of
            Right (args, stateAfterPop) ->
                case executeFunc program funcIdx args of
                    Right result -> Right $ push result stateAfterPop

Process:

1. Get function from program by index
2. Pop paramCount arguments from stack
3. Execute function with arguments
4. Push return value onto stack

Stack: [arg1, arg2, ..., argN, ...] → [result, ...]

Return:

• Returns control to caller (or ends execution)
• Top of stack is return value
• Execution loop exits

Halt:

• Ends program execution
• Top of stack is program result
• Execution loop exits

Type Checking

The VM performs runtime type checking:

popInt:

popInt :: VMState -> VMResult (Int, VMState)
popInt state = case pop state of
    Right (VInt n, newState) -> Right (n, newState)
    Right (VBool _, _) -> Left "Type error: expected Int, got Bool"
    Right (VFloat _, _) -> Left "Type error: expected Int, got Float"

popBool:

popBool :: VMState -> VMResult (Bool, VMState)
popBool state = case pop state of
    Right (VBool b, newState) -> Right (b, newState)
    Right (VInt _, _) -> Left "Type error: expected Bool, got Int"
    Right (VFloat _, _) -> Left "Type error: expected Bool, got Float"

popFloat:

popFloat :: VMState -> VMResult (Double, VMState)
popFloat state = case pop state of
    Right (VFloat f, newState) -> Right (f, newState)
    Right (VInt _, _) -> Left "Type error: expected Float, got Int"
    Right (VBool _, _) -> Left "Type error: expected Float, got Bool"

These ensure type safety even though IR is type-erased at the value level.

Execution Examples

Example 1: Simple Arithmetic

Source:

int x = 5 + 3;
return x;

IR:

PushInt 5
PushInt 3
AddInt
SetLocal 0
GetLocal 0
Return

Execution Trace:

Result: VInt 8

Example 2: Conditional

Source:

int max(int a, int b) {
    if (a > b) {
        return a;
    } else {
        return b;
    }
}

IR:

0: GetLocal 0
1: GetLocal 1
2: GtInt
3: JumpIfFalse 3
4: GetLocal 0
5: Return
6: GetLocal 1
7: Return

Execution Trace for max(10, 5):

Initial state:

• locals = [10, 5] (a=10, b=5)
• stack = []

Result: VInt 10

Execution Trace for max(3, 8):

Initial state:

• locals = [3, 8] (a=3, b=8)

Result: VInt 8

Example 3: Loop

Source:

int sum = 0;
int i = 0;
while (i < 3) {
    sum = sum + i;
    i = i + 1;
}
return sum;

IR:

0: PushInt 0
1: SetLocal 0
2: PushInt 0
3: SetLocal 1
4: GetLocal 1
5: PushInt 3
6: LtInt
7: JumpIfFalse 10
8: GetLocal 0
9: GetLocal 1
10: AddInt
11: SetLocal 0
12: GetLocal 1
13: PushInt 1
14: AddInt
15: SetLocal 1
16: Jump -12
17: GetLocal 0
18: Return

Abbreviated Execution Trace:

Result: VInt 3

Example 4: Function Call

Source:

int double(int x) {
    return x * 2;
}

int main() {
    return double(21);
}

IR for double:

0: GetLocal 0
1: PushInt 2
2: MulInt
3: Return

IR for main:

0: PushInt 21
1: Call 0
2: Return

Execution Trace:

Starting in main:

Result: VInt 42

Example 5: Float Operations

Source:

float circleArea(float radius) {
    float pi = 3.14;
    return pi * radius * radius;
}

IR:

0: PushFloat 3.14
1: SetLocal 1
2: GetLocal 1
3: GetLocal 0
4: MulFloat
5: GetLocal 0
6: MulFloat
7: Return

Execution Trace for circleArea(2.0):

Initial: locals = [2.0, 0.0] (radius=2.0, pi uninitialized)

Result: VFloat 12.56

Error Handling

The VM returns errors for:

Stack Underflow:

"Stack underflow: tried to pop from empty stack"

Type Mismatch:

"Type error: expected Int, got Bool"
"Type error: expected Float, got Int"

Division by Zero:

"Runtime error: Division by zero"

Invalid Local Index:

"Local index out of bounds: 5 (max: 2)"
"Invalid local index: -1 (negative)"

Invalid Function Index:

"Function index out of bounds: 10"
"Invalid function index: -1 (negative)"

PC Out of Bounds:

"PC out of bounds"
"PC became negative"

Performance Characteristics

Memory Usage

• Stack: Grows with expression nesting depth
• Locals: Fixed size per function (paramCount + localVarCount)
• CallStack: Grows with recursion depth

Instruction Cost

Most instructions are O(1):

• Stack operations: O(1)
• Arithmetic: O(1)
• Comparisons: O(1)
• Local access: O(1) (array indexing)
• Jumps: O(1) (PC update)

Function calls: O(1) + cost of called function

Optimization Opportunities

Current implementation uses lists (linked lists in Haskell):

• Stack: List works well (push/pop at head is O(1))
• Locals: Could use Vector for true O(1) indexing
• Code: Could use Vector for true O(1) instruction fetch

Implementation Notes

Module Structure

VM/HelperFunc.hs:

• VMState and CallFrame definitions
• Basic stack operations (push, pop)
• Local variable operations (getLocal, setLocal)
• Type-safe pop functions (popInt, popBool, popFloat)
• Binary operation helpers

VM/Interpreter.hs:

• Main execution loop (runLoop)
• Instruction dispatcher (executeInstruction)
• Function executor (execute)

VM/InstructionHandlers.hs:

• Individual instruction implementations
• Stack operations handler
• Variable operations handler
• Arithmetic operations handler
• Comparison operations handler
• Logical operations handler
• Control flow handler

Design Decisions

Why Lists for Locals?

• Simple implementation
• Good enough for most functions (few locals)
• Could be optimized to Vector later

Why No Short-Circuit?

• Compiler evaluates both operands before logical ops
• Simplifies VM implementation
• Short-circuiting happens at IR generation level

Why Type-Tagged Values?

• Type safety at runtime
• Catch type errors that shouldn't happen (defensive)
• Clear error messages

Why Offset-Based Jumps?

• No label resolution needed
• Compact representation
• Fast execution (just add to PC)

VM Architecture

The GLaDOS VM design is similar to:

• WebAssembly: Indexed locals, stack-based
• JVM: Stack machine with typed operations
• Python bytecode: Stack-based with locals

But simpler:

• No objects or references
• No garbage collection (values are primitives)
• No exceptions (Either monad for errors)
• Straightforward execution model

Testing the VM

The VM can be tested by:

1. Compiling GLaDOS source → IR
2. Executing IR with test inputs
3. Checking results against expected values

Example test:

let program = compileProgram "int main() { return 42; }"
result = execute program (mainIndex program) []
-- Expected: Right (VInt 42)

Next Steps

After VM execution:

• Results can be inspected
• Error messages help debugging
• Bytecode can be serialized for storage
• Future: JIT compilation or optimization passes