So You Want to Build a Language VM - Part 04 - Jumps

Covers the jump opcodes

iridium

Jump Around!

When we last left our intrepid tutorial followers, we had a simple VM that could add, subtract, multiply and divide. This is all fine and dandy, but we need more functionality than just that. In this segment, we’ll be adding some jump-related instructions.

Types of Jumps

There’s a few different kinds of jumps that are very common:

  1. Absolute

  2. Relative Forward

  3. Relative Backward

Absolute Jumps

These change the program counter to be whatever the argument is, without regard to anything else. In its simplest form, this instruction often looks like this:

...<instructions>...
JMP 100
...<instructions>...

Whenever the program counter hits the JMP instruction, the program counter is set to 100, and execution continues from there. One problem with this approach is that we cannot jump past the maximum number we can represent with the bits used in the instruction. Since we have a 32-bit instruction and 8 are taken up for the JMP instruction, that gives us 2^24, or 16,777,216.

An alternative to this is to have a jump instruction that reads the destination from a register. This allows a jump to 2^32 addresses. This is the first version of JMP we’ll be implementing.

Relative Jumps

These jump a certain number of instructions forwards or backwards relative to the current program counter. These are useful for implementing loops.

Jumps to Labels

We haven’t talked much about labels. Think of it as tagging a specific byte with a name, and instead of worrying about what number to jump to, you can jump directly to that label. We’ll go more into depth with this one when we write our assembler.

Implementing Absolute Jumps

Let’s do this one first. First, open up instruction.rs file and add the opcode. We’ll call it JMP.

#[derive(PartialEq)]
pub enum Opcode {
    LOAD,
    ADD,
    SUB,
    MUL,
    DIV,
    HLT,
    JMP,
    IGL
}

And now we need some code in the execution function back in vm.rs:

Opcode::JMP => {
    let target = self.registers[self.next_8_bits() as usize];
    self.pc = target as usize;
},

An example of using this might look like:

LOAD $0 #0
JMP $0
This would cause an infinite loop. Oops.

Testing

Let’s add a test for this instruction in vm.rs:

#[test]
fn test_jmp_opcode() {
    let mut test_vm = get_test_vm();
    test_vm.registers[0] = 1;
    test_vm.program = vec![7, 0, 0, 0];
    test_vm.run_once();
    assert_eq!(test_vm.pc, 1);
}

Important
If you have changed the numbers associated with each opcode in instruction.rs, then vec![7, 0, 0, 0]; will not work. Replace the 7 with whatever integer your JMP opcode is.

We get our test VM, set register 0 to hold our JMP target (byte 4), make a small program, run one instruction, and make sure the program counter changed as expected.

Implementing Relative Jumps

The JMP instruction changes the program counter from the perspective of the VM; the relative jump instructions change the program counter relative to the current instruction.

We could implement this in two ways. One possible syntax is: JMP -5 to jump backwards by 5.

Another is: JMPB 5 to jump backwards by 5.

If we make the direction implicit in the instruction, then we of course need two instructions. If we want to go with one opcode, then we have to accept the - sign in our assembler, and express it in our bytecode. Right now, two instructions is easiest, so that’s what we’re going with.

Our two new instructions will be JMPF and JMPB, for jump Forwards and Backwards. They will each be 1 argument Instructions, and that argument is the register number in which the number of bytes to move is stored.

Note
Going forward, I’m not going to detail the repetitious part of adding a new Opcode. Here are the steps as a short list: 1. Add the new Opcode to the enum in instruction.rs 2. Add the new Opcode to the From<u8> implementation in instruction.rs 3. Add the needed code to execute the instruction to the match arm in vm.rs execute_instruction function 4. Add a test in vm.rs

The complete code for both instructions are in the GitLab repo. I’ll show the functional code for JMPF here:

Opcode::JMPF => {
    let value = self.registers[self.next_8_bits() as usize]
    self.pc += value;
}

And then let’s write a test:

#[test]
fn test_jmpf_opcode() {
    let mut test_vm = get_test_vm();
    test_vm.registers[0] = 2;
    test_vm.program = vec![8, 0, 0, 0, 6, 0, 0, 0];
    test_vm.run_once();
    assert_eq!(test_vm.pc, 4);
}

Done!

Now just implement JMPB, and we have a good selection of jumping operations. Next up, we’ll add in some equality test instructions!

If you need some assistance with any of the topics in the tutorials, or just devops and application development in general, we offer consulting services. Check it out over here or click Services along the top.