Building a Compiler in Six Parts

Building an actual compiler was one of the most interesting things I've done while learning computer science. I learned to actually think about the project I was architecting instead of just coding away mindlessly.

What made the project interesting was not just that each phase had its own implementation requirements. It was that every phase depended on the previous one being clear enough to extend. A rough decision in the parser could come back during type checking; an awkward AST shape could make IR lowering harder; a convenient assembly strategy could become expensive once we started optimizing.

The first milestone was mostly about getting the compiler infrastructure right. We used JFlex for lexical analysis, Maven for the Java project setup, and a command-line wrapper around the compiler so later stages could reuse the same entry point.

Setup probably took the longest because one of my group members tackled setting up Maven, which was a huge pain. But it was definitely worth doing in the long run, since we could compile and run all of our tests with one simple command in the command line.

The actual lexical analysis wasn't too difficult. I understood regular expressions pretty well, and after reading the JFlex documentation it went by rather quickly. One small thing I would handle differently is that we knew we were going to use CUP for parsing. CUP and JFlex integrate pretty well, so the tokens created by JFlex were easily streamed into CUP. However, I decided to implement a custom token enum that was pretty small, even though I knew it was going to be deprecated. Looking back, I should have just gone ahead and used CUP. For future software projects, this taught me to use the best long-term practice even when there is a more convenient short-term option.

In the second phase, we did parsing (syntactic analysis). This is where our group's whiteboard sessions came to life, and they stayed relevant throughout the rest of the project. We met together to design an initial AST (Abstract Syntax Tree) structure. Probably the biggest design decision was splitting declarations and assignments into two separate nodes, which helped distinguish between the two. We also decided to make the nodes polymorphic records so our tree was immutable, although we eventually had to change away from records after a few realizations.

Aside from the design decisions, we used CUP (Constructor of Useful Parsers) for this. I didn't write the grammar in this part, though I did later, but my groupmates expressed that it was an absolute pain. I would come to realize that later too. The main takeaway from using CUP is that writing a proper grammar is pretty difficult. I mainly worked on testing and printing the AST via S-expressions.

This may have been one of the more fun assignments because I thought writing type checking was exciting. It was cool to see everything go well and get type checked correctly. In practice, I might get annoyed when something doesn't type check in Java or another language, but implementing the checker itself was pretty fun.

After another whiteboard session, we decided to approach type checking in an object-oriented recursive style. This meant annotating our tree with the type of each specific node. That got annoying because, during parsing, we had made the AST immutable, so we had to go back and change everything away from records. Additionally, we had a typecheck method in each node/class, so going through each file to see whether we had finished it, or whether the node needed one, was cumbersome.

For this language, context and scoping were not too bad because there could only be one unique identifier in a specific Eta file. You couldn't have local variables with the same name as a global one, so that made context checking a bit easier. Another interesting thing was that, since we had interface files in Eta, we separated the types for functions implemented in an Eta file from the types for functions declared in interface files. We would replace the interface type (signature) with the Eta type (function) if it was found to be implemented.

One issue we faced again was that I handled the main input of our program in a poorly designed way. There were a lot of interwoven parts: lexing created tokens, parsing turned tokens into an AST, and type checking annotated the AST. I handled that flow and ended up with a bunch of interwoven solutions. Instead of thinking about the design when facing an issue, I would add a function that solved my immediate problem in one place, which led to another issue, and the cycle repeated. I was jokingly "banned" from touching main after this due to my lack of foresight, and a bunch of code had to be cleaned up. I definitely took away from this that, instead of jumping to an immediate fix, I should sit and think about the architecture of the fix and its impacts.

Learning from past assignment mistakes, we decided during our whiteboard meetings to use a visitor pattern when building the IR from the AST instead of an OO-recursive approach. This was a breath of fresh air compared to the previous assignment because IR creation for each node lived in one file and required a lot less boilerplate code.

Inside the visitor, we came up with a prologue pattern to ensure IR lowering. In expressions, we allowed the creation of e-sequences that sequenced all the commands necessary to create a value, assigned that value to a new unique temporary register, and returned the temporary. We also created a hoist function that took in a list of statements and an expression. If the expression was simple, it just returned itself. If the expression was an e-sequence, all of its statements were appended to the prologue and the function returned the temporary holding the corresponding output.

Although this created new e-sequences, it never allowed the depth in the tree to be more than one. When a statement hoisted an expression, it would be consolidated into a single sequence. Any AST node expecting an IRSeq from one of its children could simply append those statements to its own prologue. This allowed us to consolidate the instructions into a single sequence for each method, and we had the convenience of a mid-level IR while still outputting a lowered one. This did lead to inefficient IR, but most of those problems were fixable through later optimizations.

During our whiteboard sessions for this phase, we decided to reuse the visitor pattern. It had been nice for IR generation, so we continued with it.

We had Tiles and ETiles (expression tiles). ETiles had a temp and cost associated with them by default. We were pretty conservative with tiling, but we still found some nice designs that avoided blowing everything up into lots of classes, mostly around binary operations.

For the actual code generation, we aimed for a simple approach of spilling everything onto the stack so our program was functionally correct, even though it produced a lot of lines. Some of those line counts were absolutely insane. A lot of these decisions were made for the sake of correctness, but unfortunately they did come back to bite us.

Additionally, one thing that came back to haunt us from a previous assignment was IR generation. We spent hours debugging an issue with recursive functions. This was a huge rabbit hole, but one of the key parts was deciding what to do when we had a statement of the form "return foo(x)". I decided that it didn't make sense to have something like MOVE RV1, RV1, with RV being the return value register pseudo name. So foo was moved into a different temporary, and then that temporary was moved into RV1.

Unfortunately, this was a poor decision because it was necessary to know about it during code generation, especially when considering callee/caller-saved registers. A huge takeaway from this nearly day-long debugging session was that not only do the big design decisions matter, like visitor vs. OO pattern, but the small, seemingly minuscule ones can have huge effects too. I did document this small decision in our design overview, but I clearly underestimated its importance.

In this part of the compiler, we were tasked with implementing language features like records, nulls, and break statements, as well as optimizing our compiler with things like register allocation and dead code elimination. I mostly handled the new language features, and they touched pretty much everything we had worked on previously. I was able to reuse much of the existing architecture, which was convenient.

It did get a bit frustrating during type checking and parsing because I had to create a few new AST nodes and update some type-check methods. It was also confusing because there were places I forgot to implement changes, although those were found through thorough testing. This definitely supports our finding that visitor > OO pattern. Additionally, I implemented actual parsing, so I did work with CUP. It was definitely as troublesome as my groupmates said it was, and it took quite a long time to write a proper grammar. Aside from those hiccups, the rest went pretty smoothly for the new features.

Regarding the optimizations, we decided to use an abstract assembler as an intermediary between tiling and assembly code for certain functions. This let us maximize reuse of the old code. It also enabled register allocation, which we did with linear scan instead of Chaitin's algorithm because of time constraints, along with other optimizations.

Obviously this was a project about building a compiler, so I did learn a lot about compilers and what I would do differently next time. But honestly, I also learned a lot of valuable software engineering principles from this project.

I'm just rambling here, but one big takeaway is that the whiteboard sessions were absolutely crucial. Design was a huge time sink because we couldn't really start working until we had a fleshed-out plan for what we were going to do. In retrospect, some of those sessions could have been longer, and maybe we could have saved ourselves the headache of the OO pattern for type checking and realized earlier that visitor was more effective.

Additionally, we could have planned out more of our file structure in those meetings. A lot of the time, we talked about how we would implement the compiler and the technical parts, but talking more about file structure and business-logic classes could have saved us a lot of refactoring in phase 3. I definitely think drawing those things out on a whiteboard and keeping design documents/visuals is super important.

Another takeaway is that any decision, no matter how big or small, is crucial. This mainly comes from the RV1 issue in phases 4 and 5, which was a seemingly minor thing that blew up into a full day, and yes I mean day, not just work day, of debugging.