Brainfuck Compiler using QBE

Code: https://gitlab.com/leah_u/bfc

Introduction

Brainfuck is one of the most famous esoteric programming languages. It consists of only eight simple commands. While this makes it very difficult to write useful programs, it also means that writing an interpreter is very easy compared to regular languages.

When I came across the QBE compiler backend, I felt inspired to use it to write a compiler. Since I didn’t want the project to get too big, I quickly decided to implement a compiler for Brainfuck. I had already built a simple interpreter a few years ago, so this time I wanted to try to focus on performance.

Implementation

Instead of compiling the Brainfuck commands one by one, I parsed the input into an intermediate representation of operations. These operations map closely to the Brainfuck commands, but each contains an additional argument. Multiple consecutive moves or increments / decrements get reduced to a single operation with a count, for example: >>> becomes OP_MOVE_RIGHT(3). The jump operations have their destination as the argument. A special case is the command sequence [-], which is a loop that sets the current cell to zero. By parsing this into a separate operation, I was able to gain a significant performance boost.

To test the parser, I wrote an interpreter that takes in my intermediate representation of the Brainfuck code. This turned out to be a very good idea, as it led me to find out that I had accidentally switched around the left and right moves. It also allowed me to compare the performance to the final compiled version.

Converting my intermediate representation into QBE was pretty straightforward. All I needed was a chunk of memory for the cells and a pointer into that memory area, as well as a main function. The compiler then loops through the list of operations and emits the corresponding QBE instructions. The most interesting ones are the jumps generated by [ and ]. The operations already contain an index for the destination. Since they can only jump to other loop commands, I simply created a QBE label after each jump operation with its own index, which can then be referenced by the other jump.