Writing a VM Part Three

Filed under vms on December 20, 2022

Welcome to part 3 of this blog series. We’ll be adding instructions to allow us to better control the flow of our code, as well as adding in comparison instructions. Code for this blog entry will be available here.

I’d recommend reading part one and part two before reading this part.

Overview

We’re going add new instructions to control the flow of our executing code:

Hex Value	Mnemonic	Description
0x0A	PUSH	Push the value of I1 onto the stack
0x0B	POP	Pop a value off the stack and into I2
0x0C	JMP	Set PC to the address in I1
0x0D	LESS	Run the next instruction only if I1 < I2
0x0E	LTE	Run the next instruction only if I1 <= I2
0x0F	GT	Run the next instruction only if I1 > I2
0x10	GTE	Run the next instruction only if I1 >= I2
0x11	EQ	Run the next instruction only if I1 = I2
0x12	CALL	Set the PC to the address in I1
0x13	RETURN	Return to the last `CALL` location

To facilitate these changes, we’ll be adding a new register to the machine.

Hardware Changes

We’ll be adding a new stack pointer (SP) register, which will start at the last physical addressable memory address. We will use this to push and pop data off the stack. It will initially be set to 0xFFE0.

New Instructions

Stack operations

To move data on and off the stack, we’ll use the PUSH and POP. PUSH will do the following:

sp -= 1
mem[sp] = I1

While POP will do the opposite

I2 = mem[sp]
sp += 1

Comparators

The comparison operations will all work in similar ways, running a comparison and if the comparison fails adding 1 to the program counter to skip the next instruction:

if !cmp(i1, i2) {
  pc += 1
}

Jumping to different addresses

CALL will push the current program counter value onto the stack and jump to the address in I1

sp -= 1
mem[sp] = pc

RETURN will pop an address from the stack and set the program counter

pc = mem[sp]
sp += 1

In practice, this will mean we need to be careful of stack data if we wish to RETURN an address.

JMP will jump to an address in memory, can’t get much simpler than that.

pc = I1

Implementation

The stack pointer

Let’s start by adding in the new register, replacing __reserved8:

// register.go
const (
//...
	__reserved7
	SP
	SR
//...
)

And adding it into our register map when we initialise our registers:

registerMap: map[uint8]*Register{
  //...
  SP: {0xFFE0},
  //...
},

We initialise the stack pointer at 0xFFE0 and it will grow “up” in the memory space as we push more items into it.

Adding the instruction constants

We’ll add the new instructions into the constants in cpu.go

const (
	HALT = iota
  //...
	PUSH
	POP
	JMP
	LESS
	LTE
	GT
	GTE
	EQ
	CALL
	RETURN
)

Stack operations

PUSH and POP, as mentioned before, are mirror images of each other. Implementing this also exposed a bug in my memory implementation that I hadn’t hit as of yet, in that my maximum address of 0xFFE0 wasn’t an addressable location. I fixed this by making the memory 1 word larger.

// cpu.go
func (c *CPU) push(i1, _ *Register) {
	sp, err := c.registers.GetRegister(SP)
	if err != nil {
		panic(err)
	}

	sp.Value--
	err = c.bus.Write(sp.Value, i1.Value)
	if err != nil {
		sr, err := c.registers.GetRegister(SR)
		if err != nil {
			panic(err)
		}
		sr.Value = sr.Value | STATUS_MEMORY_ERROR
		return
	}
}

func (c *CPU) pop(_, i2 *Register) {
	sp, err := c.registers.GetRegister(SP)
	if err != nil {
		panic(err)
	}

	v, err := c.bus.Read(sp.Value)
	if err != nil {
		sr, err := c.registers.GetRegister(SR)
		if err != nil {
			panic(err)
		}
		sr.Value = sr.Value | STATUS_MEMORY_ERROR
		return
	}
	i2.Value = v
	sp.Value++
}

Notice that we’re also using our status register that we implemented last time. This will be important, since it’s the only way to tell if the machine is in an error state.

Jump instruction

The JMP instruction is pretty easy to implement

// cpu.go
func (c *CPU) jmp(i1, _ *Register) {
	pc, err := c.registers.GetRegister(PC)

	if err != nil {
		panic(err)
	}
	pc.Value = i1.Value
}

Comparators

As stated before, the comparators are all pretty similar

// cpu.go
func (c *CPU) less(i1, i2 *Register) {
	if !(i1.Value < i2.Value) {
		pc, err := c.registers.GetRegister(PC)
		if err != nil {
			panic(err)
		}
		pc.Value++
	}
}

func (c *CPU) lte(i1, i2 *Register) {
	if !(i1.Value <= i2.Value) {
		pc, err := c.registers.GetRegister(PC)
		if err != nil {
			panic(err)
		}
		pc.Value++
	}
}

func (c *CPU) gt(i1, i2 *Register) {
	if !(i1.Value > i2.Value) {
		pc, err := c.registers.GetRegister(PC)
		if err != nil {
			panic(err)
		}
		pc.Value++
	}
}

func (c *CPU) gte(i1, i2 *Register) {
	if !(i1.Value >= i2.Value) {
		pc, err := c.registers.GetRegister(PC)
		if err != nil {
			panic(err)
		}
		pc.Value++
	}
}

func (c *CPU) eq(i1, i2 *Register) {
	if !(i1.Value == i2.Value) {
		pc, err := c.registers.GetRegister(PC)
		if err != nil {
			panic(err)
		}
		pc.Value++
	}
}

CALL and Return

CALL pushes an element onto the stack and then jumps to another address, while RETURN will pop an address off the stack and return there

// cpu.go
func (c *CPU) call(i1, _ *Register) {
	sp, err := c.registers.GetRegister(SP)
	if err != nil {
		panic(err)
	}
	pc, err := c.registers.GetRegister(PC)
	if err != nil {
		panic(err)
	}

	sp.Value--
	err = c.bus.Write(sp.Value, pc.Value)
	if err != nil {
		sr, err := c.registers.GetRegister(SR)
		if err != nil {
			panic(err)
		}
		sr.Value = sr.Value | STATUS_MEMORY_ERROR
		return
	}

	pc.Value = i1.Value
}

func (c *CPU) ret(_, _ *Register) {
	sp, err := c.registers.GetRegister(SP)
	if err != nil {
		panic(err)
	}

	val, err := c.bus.Read(sp.Value)
	sp.Value++
	if err != nil {
		sr, err := c.registers.GetRegister(SR)
		if err != nil {
			panic(err)
		}
		sr.Value = sr.Value | STATUS_MEMORY_ERROR
		return
	}

	pc, err := c.registers.GetRegister(PC)
	if err != nil {
		panic(err)
	}
	pc.Value = val
}

Wiring it all together

Finally, we’ll add our instructions into the switch:

// cpu.go
func (c *CPU) executeInstruction(instruction uint32) error {
	// ...

	switch opcode {
	// ...
	case PUSH:
		c.push(i1, i2)
	case POP:
		c.pop(i1, i2)
	case JMP:
		c.jmp(i1, i2)
	case LESS:
		c.less(i1, i2)
	case LTE:
		c.lte(i1, i2)
	case GT:
		c.gt(i1, i2)
	case GTE:
		c.gte(i1, i2)
	case EQ:
		c.eq(i1, i2)
	case CALL:
		c.call(i1, i2)
	case RETURN:
		c.ret(i1, i2)
  // ...
	}
	return nil
}

Testing a whole program

Now that we have some more instructions to play with, let’s make our program in main.go more interesting by calculating 10 factorial:


func main() {
	// Load this in at mem[0x100]
	// This program will calculate the value of 10! (10*9*8...) and store it at address 0x1000
	program := []uint32{
		0x03F00001, //0x100: COPY 0x01 R0
		0x03F1000A, //0x101: COPY 0x0A R1
		0x03F20001, //0x102: COPY 0x01 R2
		0x06100000, //0x103: MUL R1 R0
		0x11F10001, //0x104: EQ 0x01 R1
		0x0CF0010A, //0x105: JMP 0x10A
		0x05120000, //0x106: SUB R1 R2
		0x03210000, //0x107: COPY R2 R1
		0x03F20001, //0x108: COPY 0x01 R2
		0x0CF00102, //0x109: JMP 0x102
		0x020F1000, //0x10A: WRITE R0 0x1000
		0x00000000, //0x10B: HALT
	}

	registers := internal.NewRegisterBank()
	mem := internal.NewMemory()
	for i, p := range program {
		err := mem.Write(uint32(i+0x100), p)
		if err != nil {
			fmt.Printf("error writing to memory location 0x%x: %v\n",
				i, err)
			return
		}
	}
	bus := internal.NewBus(mem)
	cpu := internal.NewCPU(registers, bus)

	sr, err := registers.GetRegister(internal.SR)
	if err != nil {
		fmt.Printf("Could not get the staus register: %v", err)
		return
	}
	for sr.Value&internal.STATUS_HALT == 0 {
		cpu.Tick()
	}
	val, err := mem.Read(0x1000)
	if err != nil {
		fmt.Printf("could not read memory at 0x1000: %v\n", err)
		return
	}
	// Value in memory should be 3628800
	fmt.Printf("The value at address 0x1000 is %d\n", val)
}

If everything is working correctly, this program will output

The value at address 0x1000 is 3628800

Next time

My hope is to put together an assembler next, because writing out binary instructions is rather tedious. I have never done anything like that before, so we’ll see how long it takes. Take care until next time!