A Bril to x86 Compiler
Goal
The goal of the project was to build a Bril compiler targeting x86_64. The priority of the project was to implement something working, and not necessarily something optimal. So for this project, things like register allocation were out of scope.
Design and Implementation
The current implementation was done in Python and it supports all the core features of Bril. I decided to go with Python despite its slowness because it’s fast to iterate with, but I would expect the process of converting it to another language to be extremely smooth.
The overall design of the compiler at a high-level is relatively simple. The design of Bril resembles assembly, so the compiler just needs to do linera passes converting each instruction at a time to the relevant code. The program does two main passes: first it converts all the Bril instructions into another intermediate representation that is a one-to-one correspondence to an x86 instruction. Then the second pass will actually produce the assembly program and format it. The reason I decided to go with splitting it into two passes as opposed to printing the program directly was because there are multiple different syntaxes for x86, so the intention was if different syntax styles were to be supported, the changes would be more isolated. For the project, I implemented support for Intel syntax.
The Tricky Parts
Although at a high level, things were simple, the details were tricky to get right. The first big hurdle was actually getting a compiled program to run. This required support for several Bril instructions, you would need to support constants, and either printing or returning in order to observe that some changes had happened. But it also required support for some calling conventions to be supported, otherwise the program wouldn’t terminate. What helped got me over this hurdle proved to be quite useful in general for developing this compiler, which was modeling Bril programs as C programs and comparing my Bril -> x86 results with Clang’s C -> x86 results. This helped me find stuff like the following snippet of text, which I would include at the beginning of every file for generating code targeting MacOS:
.section __TEXT,__text,regular,pure_instructions
.build_version macos, 15, 0 sdk_version 15, 2
These directives seemed to vary quite a bit device-to-device; but I found comparing with a reference compiler was a reliable way of finding out what directives are necessary. Online sources often lack the specific things you need for your own device.
It was also quite tricky to get printing right. I implemented Prof. Sampson’s suggestion of linking the printing with a helper rt.c file to avoid printing Booleans by hand. To get linking right, again it helped a lot to model the behavior I would expect in an equivalent C program, and guide my implementation to match that output.
Another tricky part was getting command line arguments handled correctly. A particularly trick case is the following Bril program:
@main(x: int) {
n: int = const 10;
b: bool = lt x n;
br b .loop .done;
.loop:
one: int = const 1;
print x;
y: int = add x one;
call @main y;
.done:
ret;
}
This program takes in a single int as a command line argument, and keeps printing its value and incrementing it until it hits 10. The tricky part comes from the fact that this function also calls itself. So this means the assembly code for this function must somehow handle both command line parsing and support proper calling conventions when it’s called as a normal function. More concretely, in x86, it’s expected that the main function’s first and second parameters are argc and argv respectively. But we also want the main function’s first function to be x.
The solution to this problem was to wrap the main function with a separate function that first handles command line arguments, and then calls the real main function with the proper arguments. However, the current implementation for this might cause bugs for 0.1% of Bril programs because it creates another function called “main_main”, so any Bril programs with such a function name might run into some issues.
However, one big downside of this compiler is that it doesn’t work for plenty of devices. There are more cases that need to be hard-coded differently for different devices. For example, MacOS starts their program with the _main label, but for Linux it looks for a _start label. Since I primarily developed this on a Mac, it was hard to get support for more devices working. Extending support to different devices doesn’t seem too hard, it seems like a matter of adding different formatting and wrapping the program with different assembly programs, but this is seems hard to do without multiple devices.
What wasn’t tricky
It was nice to see how smooth most instructions were to convert to x86. Most instructions were a very close correspondence, with the only exception being the boolean comparison operators. But that seemed to be because x86 doesn’t have instructions for things like less than, unlike RISC-V, but this wasn’t too bad overall to implement.
Evaluation
I had wanted to evaluate on several things, like comparing this compiler to other aot compilers like Brilift, but I didn’t end up with enough time for that.
To test for correctness, I have an automated script that interprets every core benchmark against brili and uses that as a reference. And fortunately, every output matches! It checks for both matching standard outs and matching exit codes. I can confidently say this compiler preserves correctness in 95% of programs, the estimated missing 5% being from programs that start have a “main_main” function and functions with more than 6 arguments. The current implementation does not support more than 6 arguments since calling conventions only reserve 6 registers for function calls.
Overall, this was a pretty fun project and I definitely learned a lot about x86 and am glad I don’t normally program at such a low level.