So You Want to Build a Language VM - Part 05 - Equality Checks

Covers equality opcodes

iridium

Equality

Hey, you’ve made it this far! Congrats! I wish I could say we’re near the end to give you some hope, but, well…​sorry. =)

Today, we’re going to add some equality and comparison instructions! These will let us test us if the values in two registers are equal, not equal, greater than, or less than. These are easy to implement, so it shouldn’t take us too long. == Opcodes The new Opcodes we’ll be creating are:

  1. EQ (equal)

  2. NEQ (not equal)

  3. GT (greater than)

  4. LT (less than)

  5. GTQ (greater than OR equal to)

  6. LTQ (less than OR equal to)

  7. JEQ (jump if equal)

JEQ is a bit different, and we’ll go into it in more detail later in this post.

Why?

These are the foundation of conditional logic. With these, we can start to implement if-then logic, while loops, for loops, and all that fun stuff!

Implementation

So let’s say that we want to use the EQ Opcode. In our still-fictitious assembly language, it might look like:

EQ $0 $1

And our VM will check if the values in register 0 and register 1 are equal. This leaves us with a question, though…​where does it put the result?

Storing the Result

There’s two options I’ve seen used. One is that we can supply a third register in which to put the result, so the usage would then look like:

EQ $0 $1 $2

and register 2 would then have 0 (false, or not equal) and 1 (true, or equal). This is how MIPS does it.

The other option is a special register dedicated to holding the results of instructions. You can’t LOAD values into it or use it for anything but as an operand for certain instructions, such as JEQ.

MIPS normally uses the first option, and even though our assembly is based heavily on MIPS, we’re going to deviate a bit here and use a dedicated register. This is strictly a personal preference of mine; I find it easier to write assembly if I have one less register to keep track of.

Equal Boolean

The first thing we need to do is add the boolean variable to the VM:

pub struct VM {
    /// Array that simulates having hardware registers
    registers: [i32; 32],
    /// Program counter that tracks which byte is being executed
    pc: usize,
    /// The bytecode of the program being run
    program: Vec<u8>,
    /// Contains the remainder of modulo division ops
    remainder: usize,
    /// Contains the result of the last comparison operation
    equal_flag: bool,
}

And then in our impl block for our VM, we initialize it like so:

pub fn new() -> VM {
    VM {
        registers: [0; 32],
        program: vec![],
        pc: 0,
        remainder: 0,
        equal_flag: false,
    }
}

EQ code

Since the implementation of these opcodes, except JEQ, are almost identical in implementation, I will walk through adding the EQ code and the JEQ code, and leave the rest to you. You can check out the source code to see the details of the rest.

Boilerplate

You should have a good handle on this now: 1. Add EQ to the enum in instruction.rs 2. Add it to the implementation of From<u8> in instruction.rs 3. Implement the instruction in vm.rs 4. Add a test for it

The implementation of EQ looks like:

Opcode::EQ => {
    let register1 = self.registers[self.next_8_bits() as usize];
    let register2 = self.registers[self.next_8_bits() as usize];
    if register1 == register2 {
        self.equal_flag = true;
    } else {
        self.equal_flag = false;
    }
    self.next_8_bits();
},

We get the value of the two registers and set the VM’s equal_flag accordingly, then eat the next 8 bits.

Our test for it looks like:

#[test]
fn test_eq_opcode() {
    let mut test_vm = get_test_vm();
    test_vm.registers[0] = 10;
    test_vm.registers[1] = 10;
    test_vm.program = vec![10, 0, 1, 0, 10, 0, 1, 0];
    test_vm.run_once();
    assert_eq!(test_vm.equal_flag, true);
    test_vm.registers[1] = 20;
    test_vm.run_once();
    assert_eq!(test_vm.equal_flag, false);
}

Important
See how we test both the case where the values are equal and the case where they are not? Its good to always try to test all possible paths.

JEQ

OK, moving on to the non-comparison instruction for this entry: JEQ, or Jump If Equal. It will take one register as an argument, and if equal_flag is true, will jump to the value stored in that register. If false, it will not jump to it.

The implementation for this operation looks like:

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

And our test for it:

#[test]
fn test_jeq_opcode() {
    let mut test_vm = get_test_vm();
    test_vm.registers[0] = 7;
    test_vm.equal_flag = true;
    test_vm.program = vec![16, 0, 0, 0, 17, 0, 0, 0, 17, 0, 0, 0];
    test_vm.run_once();
    assert_eq!(test_vm.pc, 7);
}

And that’s it for JEQ!

Wrap Up

With minimal effort, you can also implement a JNEQ instruction, or jump if not equal. Why have them both? Convience is the principal reason. It will let us write assembly code later that will be easier to follow.

Having a large number of instructions that may do more than one thing is one of the primary differences between a RISC processor and a CISC processor. An even more simplistic processor than our VM might be missing a MUL instruction and require the programmer to use ADD and JMP instructions.

Madness, I know.

Anyway, that’s it for this section! Next up, for a change of pace, we’ll start building a REPL for our VM!

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.