Lab 8: VM I — Stack Arithmetic and Memory Segments

Week: 8
Points: 20
Time: ~5 hours
Deliverable: toolchain/vm-translator/translator.py + simulation results + diary/week-08.md

What you ship

• toolchain/vm-translator/translator.py — handles stack arithmetic and all memory segments
• vm/week-08/SimpleAdd.vm — your test program (push + add)
• vm/week-08/StackTest.vm — arithmetic and comparison tests
• vm/week-08/SimpleAdd.s — translated assembly
• asm/week-08/simpleadd.hex — hex image for CPU simulation
• diary/week-08.md

Lab 8.1: Stack arithmetic translator

Write toolchain/vm-translator/translator.py. Your translator reads a .vm file and writes a .s file of RV32I-Lite assembly. For this lab, implement:

Memory segment push/pop:

Arithmetic commands:

ARITHMETIC = {
    'add':  ["LW x10, 0(sp)", "ADDI sp, sp, 4",
             "LW x11, 0(sp)", "ADD x11, x11, x10", "SW x11, 0(sp)"],
    'sub':  ["LW x10, 0(sp)", "ADDI sp, sp, 4",
             "LW x11, 0(sp)", "SUB x11, x11, x10", "SW x11, 0(sp)"],
    'neg':  ["LW x10, 0(sp)", "NEG x10, x10", "SW x10, 0(sp)"],
    'and':  ["LW x10, 0(sp)", "ADDI sp, sp, 4",
             "LW x11, 0(sp)", "AND x11, x11, x10", "SW x11, 0(sp)"],
    'or':   ["LW x10, 0(sp)", "ADDI sp, sp, 4",
             "LW x11, 0(sp)", "OR x11, x11, x10", "SW x11, 0(sp)"],
    'not':  ["LW x10, 0(sp)", "NOT x10, x10", "SW x10, 0(sp)"],
}

Comparison commands (each needs a unique label counter to avoid label collisions):

def translate_comparison(command: str, label_counter: int) -> list[str]:
    true_label  = f"CMP_TRUE_{label_counter}"
    end_label   = f"CMP_END_{label_counter}"
    branch_map  = {'eq': 'BEQ', 'gt': 'BGT', 'lt': 'BLT'}
    branch      = branch_map[command]
    return [
        "LW x10, 0(sp)", "ADDI sp, sp, 4",
        "LW x11, 0(sp)",
        f"SUB x12, x11, x10",          # x12 = y - x (top was x, second was y)
        f"{branch} x12, x0, {true_label}",
        "LI x11, 0",                    # false = 0
        f"JAL x0, {end_label}",
        f"{true_label}:",
        "LI x11, -1",                   # true = -1 (all bits set)
        f"{end_label}:",
        "SW x11, 0(sp)",
    ]

Your translator skeleton:

#!/usr/bin/env python3
"""translator.py -- VM I: stack arithmetic + memory segments."""
import sys
from pathlib import Path

class VMTranslator:
    def __init__(self, source_name: str):
        self.source_name = source_name   # used for static segment label prefix
        self.output: list[str] = []
        self._label_counter = 0

    def _emit(self, *lines):
        for line in lines:
            self.output.append(f"    {line}" if not line.endswith(':') else line)

    def translate_push(self, segment: str, index: int):
        if segment == 'constant':
            self._emit(f"LI x10, {index}", "ADDI sp, sp, -4", "SW x10, 0(sp)")
        elif segment in ('local', 'argument', 'this', 'that'):
            reg = {'local': 'x18', 'argument': 'x19', 'this': 'x20', 'that': 'x21'}[segment]
            self._emit(f"LW x10, {index * 4}({reg})",
                       "ADDI sp, sp, -4", "SW x10, 0(sp)")
        elif segment == 'temp':
            addr = 0x0300 + index * 4
            self._emit(f"LI x10, {addr}", "LW x10, 0(x10)",
                       "ADDI sp, sp, -4", "SW x10, 0(sp)")
        elif segment == 'static':
            label = f"{self.source_name}.static.{index}"
            self._emit(f"LA x10, {label}", "LW x10, 0(x10)",
                       "ADDI sp, sp, -4", "SW x10, 0(sp)")
        elif segment == 'pointer':
            reg = 'x20' if index == 0 else 'x21'
            self._emit(f"ADDI sp, sp, -4", f"SW {reg}, 0(sp)")

    def translate_pop(self, segment: str, index: int):
        if segment in ('local', 'argument', 'this', 'that'):
            reg = {'local': 'x18', 'argument': 'x19', 'this': 'x20', 'that': 'x21'}[segment]
            self._emit("LW x10, 0(sp)", "ADDI sp, sp, 4",
                       f"SW x10, {index * 4}({reg})")
        elif segment == 'temp':
            addr = 0x0300 + index * 4
            self._emit("LW x10, 0(sp)", "ADDI sp, sp, 4",
                       f"LI x11, {addr}", "SW x10, 0(x11)")
        elif segment == 'static':
            label = f"{self.source_name}.static.{index}"
            self._emit("LW x10, 0(sp)", "ADDI sp, sp, 4",
                       f"LA x11, {label}", "SW x10, 0(x11)")
        elif segment == 'pointer':
            reg = 'x20' if index == 0 else 'x21'
            self._emit(f"LW {reg}, 0(sp)", "ADDI sp, sp, 4")

    def translate_arithmetic(self, command: str):
        ARITHMETIC = {
            'add': ("LW x10, 0(sp)", "ADDI sp, sp, 4",
                    "LW x11, 0(sp)", "ADD x11, x11, x10", "SW x11, 0(sp)"),
            'sub': ("LW x10, 0(sp)", "ADDI sp, sp, 4",
                    "LW x11, 0(sp)", "SUB x11, x11, x10", "SW x11, 0(sp)"),
            'neg': ("LW x10, 0(sp)", "NEG x10, x10", "SW x10, 0(sp)"),
            'and': ("LW x10, 0(sp)", "ADDI sp, sp, 4",
                    "LW x11, 0(sp)", "AND x11, x11, x10", "SW x11, 0(sp)"),
            'or':  ("LW x10, 0(sp)", "ADDI sp, sp, 4",
                    "LW x11, 0(sp)", "OR x11, x11, x10", "SW x11, 0(sp)"),
            'not': ("LW x10, 0(sp)", "NOT x10, x10", "SW x10, 0(sp)"),
        }
        if command in ARITHMETIC:
            self._emit(*ARITHMETIC[command])
        elif command in ('eq', 'gt', 'lt'):
            n = self._label_counter
            self._label_counter += 1
            true_l = f"CMP_TRUE_{n}"
            end_l  = f"CMP_END_{n}"
            branch = {'eq': 'BEQ', 'gt': 'BGT', 'lt': 'BLT'}[command]
            self._emit("LW x10, 0(sp)", "ADDI sp, sp, 4",
                       "LW x11, 0(sp)",
                       "SUB x12, x11, x10",
                       f"{branch} x12, x0, {true_l}",
                       "LI x11, 0",
                       f"JAL x0, {end_l}")
            self.output.append(f"{true_l}:")
            self._emit("LI x11, -1")
            self.output.append(f"{end_l}:")
            self._emit("SW x11, 0(sp)")

    def translate_file(self, vm_text: str) -> list[str]:
        for raw_line in vm_text.splitlines():
            line = raw_line.split('//')[0].strip()
            if not line:
                continue
            parts = line.split()
            cmd = parts[0]
            if cmd == 'push':
                self.translate_push(parts[1], int(parts[2]))
            elif cmd == 'pop':
                self.translate_pop(parts[1], int(parts[2]))
            elif cmd in ('add','sub','neg','and','or','not','eq','gt','lt'):
                self.translate_arithmetic(cmd)
        return self.output

def main():
    src = Path(sys.argv[1])
    out = Path(sys.argv[sys.argv.index('-o') + 1]) if '-o' in sys.argv else src.with_suffix('.s')
    t = VMTranslator(src.stem)
    lines = t.translate_file(src.read_text())
    out.write_text('\n'.join(lines) + '\n')
    print(f"  {src.name} -> {out.name} ({len(lines)} instructions)")

if __name__ == '__main__':
    main()

Lab 8.2: Translate SimpleAdd.vm

Create vm/week-08/SimpleAdd.vm:

// SimpleAdd.vm
// Computes 7 + 8 and leaves the result on the stack.
push constant 7
push constant 8
add

Translate and simulate:

python3 toolchain/vm-translator/translator.py vm/week-08/SimpleAdd.vm \
    -o vm/week-08/SimpleAdd.s

# Assemble
python3 toolchain/assembler/asm.py vm/week-08/SimpleAdd.s \
    -o asm/week-08/simpleadd.vof

# Link to binary
python3 toolchain/linker/linker.py asm/week-08/simpleadd.vof \
    -o asm/week-08/simpleadd.bin

# Convert to hex and simulate
python3 -c "
import struct
data = open('asm/week-08/simpleadd.bin','rb').read()
with open('/tmp/simpleadd.hex','w') as f:
    for i in range(0, max(len(data), 4), 4):
        word = struct.unpack_from('<I', data, i)[0] if i < len(data) else 0
        f.write(f'{word:08x}\n')
"
cp /tmp/simpleadd.hex verilog/cpu/imem.hex
vvp cpu_sim | grep -E '\[PASS\]|\[FAIL\]|stack'

Expected: the value 15 (0x0F) at the top of stack.

Lab 8.3: Translate StackTest.vm

Create vm/week-08/StackTest.vm:

// StackTest.vm
// Tests all arithmetic and comparison operations.
push constant 17
push constant 17
eq         // true (-1)
push constant 17
push constant 16
eq         // false (0)
push constant 892
push constant 891
gt         // true (-1)
push constant 891
push constant 892
gt         // false (0)
push constant 32767
push constant 32766
lt         // false (0)
push constant 57
push constant 31
add
push constant 53
sub
push constant 112
neg
and
push constant 82
or
not

Translate and simulate. The final stack value must match the reference output. Capture the simulation output to diary/week-08.md.

Lab 8.4: Seeded error drill — segment boundary

Modify SimpleAdd.vm to pop to temp 8 (index 8 of temp, which would write to absolute address 0x0300 + 32 = 0x0320). Verify that your translator emits the correct absolute address. Verify in simulation that the value lands at that address and not at the wrong location.

Then restore SimpleAdd.vm to its original form.

Toolchain Diary — Week 8

Record in diary/week-08.md:

• CSA-102 comparison: Py6502v's flat-address model used named locations; the VM uses a hardware stack. What does the stack model buy the compiler writer that named locations do not?
• The stack pointer protocol: describe in your own words what ADDI sp, sp, -4; SW x10, 0(sp) does and why those two instructions are always paired.
• The comparison result encoding: why does the VM encode true as -1 (all bits set) instead of 1? How does this choice interact with the and and or commands?
• Forward promise: Lab 9.5 asks you to implement mul as shift-and-add. After completing that lab, record the cycle count for mul(5, 7) here.

Grading