I Built a Processor for Advent of Code Day 8

It may or may not have been a massive waste of time, but at least I had fun and get to showcase some fun things Spade can do! Especially the new labels that allow the Spade compiler to act as a rudimentary assembler.

Advent of Code is a yearly programming challenge where a new programming problem is unlocked every day starting on December 1. This year, a few of us are doing advent of code in hardware for Advent of FPGA and of course this means I’m using Spade.

I set myself the additional rule that as far as possible, everything should be done in Spade, including input parsing, and until day 8 I had kept that streak up with only minor difficulties. However, day 8 this year was less suited to hardware solutions than previous problems, and honestly, after a week of solving similar problems I was starting to get a bit bored. For a while a thought had been brewing in the back of my mind that it is possible to build a simple CPU for a one-off instruction set using Spade’s enums.

So, armed with a problem being annoying to do in hardware, relatively simple in software, and this latest brainworm, I decided to try my hand at solving day 8 with a custom processor to maintain my 100% Spade streak.

The Initial Processor

I had already prototyped an enum-based processor for a guest lecture I gave in early november.

That meant I could write the insturction set, processor like this:

/// The definition of the instructions that the processor supports.
enum Insn {
    Nop,
    Set{dest: uint<4>, value: uint<16>},
    Add{dest: uint<4>, opa: uint<4>, opb: uint<4>},
    Jump{target: int<16>},
    Out{op: uint<4>}
}

And then write a program for this processor like this

/// The instruction memory containing the program to be executed. To fit in block-ram this
/// has a single cycle read latency.
let mem = inst std::mem::clocked_memory_init(clk, [], [
    Insn::Set$(dest: 0, value: 0),
    Insn::Set$(dest: 1, value: 1),
    Insn::Add$(dest: 0, opa: 1, opb: 0),
    Insn::Out$(op: 0),
    Insn::Jump$(target: 2),
    Insn::Jump$(target: 0)
]);

The processor implementation is another hundred lines, a bit too much for inlining in this blog post.

Turning the Spade Compiler Into an Assembler

However, there was one annoying thing about this: All the jumps need hard-coded offsets and that makes writing any non-trivial program super annoying and error prone. After some brief discussion in the Spade Discord we realized that we can solve that problem by adding labels to arrays. Just like an assembler, you can put a label before an array element, and then use that label to refer to its index later.

Half an hour of implementation and another hour of syntax bike shedding later, Spade had support for this new feature albeit with a placeholder syntax, meaning the previous example program can now be written as

let mem = inst std::mem::clocked_memory_init(clk, [], [
    Insn::Set$(dest: 0, value: 0),
    Insn::Set$(dest: 1, value: 1),
  'loop
    Insn::Add$(dest: 0, opa: 1, opb: 0),
    Insn::Out$(op: 0),
    Insn::Jump$(target: @loop.index),
]);

Fearlessly Extending the Processor

One of my favourite things about Spade is how it enables “fearless refactoring”. If you make a change, the compiler will yell at you to update all the places where the change may affect things. Take for example the instruction set above. It is clearly not enough for any real world tasks, so I had to add quite a few instructions to it.

That means first extending the Insn enum, for example with an Addi{dest: uint<4>, opa: uint<4>, value: uint<32>} instruction

Now the compiler will complain about all the places where this new instruction is not handled, for example, in the ALU:

// Perform any computation the instruction requires
let alu_out = match insn {
    Insn::Nop => std::undef::undef(),
    Insn::Set$(dest: _, value: _) => std::undef::undef(),
    Insn::Add$(opa: _, opb: _, dest: _) => trunc(reg_a + reg_b),
    Insn::Jump(_) => std::undef::undef(),
    Insn::Out(_) => std::undef::undef(),
};

Adding supprt for Addi here is simple, I just had to add an additional branch

    Insn::Add$(opa: _, opb: _, value) => trunc(reg_a + value),

And repeating for the other match expressions in the processor I ended up with a slightly more powerful processor without putting too much thought into it!

This is also very helpful when adjusting instructions. If I realized that the parameters to any instruction were not ideal, I could just change it in the definition, and the compiler would tell me where to update, both in the processor and also in the program thanks to the assembler just being the Spade compiler!

All in all, this worked really well, while I of course had minor bugs from getting things wrong, I was able to build up my processor to quite a few instructions: which s which s

enum Insn {
    Nop,
    Set{dest: uint<5>, value: uint<72>},
    Move{dest: uint<5>, source: uint<5>},
    Add{dest: uint<5>, opa: uint<5>, opb: uint<5>},
    Addi{dest: uint<5>, opa: uint<5>, value: uint<72>},
    Mul{dest: uint<5>, opa: uint<5>, opb: uint<5>},
    Div2{dest: uint<5>, opa: uint<5>},
    Inc{dest: uint<5>},
    Dec{dest: uint<5>},
    ReadCoord{dest: uint<5>, source_addr: uint<5>},
    SqDist3d{dest: uint<5>, opa: uint<5>, opb: uint<5>},
    Jump{target: uint<16>},
    JumpAndLink{target: uint<16>, dest: uint<5>},
    JumpReg{target: uint<5>},
    Branch{target: uint<16>, opa: uint<5>, cmp: Cmp, opb: uint<5>},
    Out{op: uint<5>},
    Outi{value: uint<72>},
    GetNumCoords{dest: uint<5>},
    WaitParsingDone,
    ReadMem{dest: uint<5>, source: uint<5>},
    ReadMemOffset{dest: uint<5>, offset: uint<15>, addr: uint<5>},
    WriteMem{dest_addr: uint<5>, dest_value: uint<5>},
    WriteMemOffset{dest_addr: uint<5>, offset: uint<15>, dest_value: uint<5>},
    Halt,
}

In addition, I was able to make late large scale changes when I realized I had failed to account for some things. For example, I doubled the number of registers in the processor, and increased the native word length from 48 to 72 bits without causing any existing code to fail!

So Far, So Good

Until now, everything has gone well! Spade did what it was supposed to, the new labels meant writing “assembly” in Spade was pretty comfortable, and I didn’t run into any hard to track down bugs in the processor! However, as it turns out solving a second week advent of code problem in assembler comes with some difficulties. Word lengths had to be massive, my naive solution needed N^2 memory and did not end up fitting in block RAM for the ECP5 FPGA I was going to run this on, and I misread the problem description at least twice. In addition, many of these problems only appeared for larger inputs which meant 500k clock cycles of simulation just to reproduce issues. I also uncovered a bug in the Spade Surfer plugin which meant that the instruction decoding that had been extremely pleasant to work with initially broke for long simulations, making debugging quite pleasant.

In the end, through painful debugging and comparing my results to the result of a friend’s python solution I eventually found all the bugs and earned that, sweet sweet silver star.

And the runtime was only around 3 minutes. Here at Spade inc we have gone past hardware accceleration and are fast at work on revolutionary hardware decceleration!

Conclusions

While this is probably not the best way to solve an advent of code problem, being able to define and program an ad-hoc processor like this is something I’m excited to have in the Spade toolbox, and I’m very pleased that the fearless refactoring that Spade provides extended to this technique.

I believe this will come in handy for “management tasks” where the task is “programmatically complicated” but where preformance isn’t top priority.

You can find all the source code for this project in my advent of code repo