NCC: Not Complete, but Capable: A C Compiler in Rust

Why Build a Compiler?

I've always been interested in pulling back the layers of abstraction and understanding what my code is really doing under the hood. My day job as a Principal Data Scientist gives me plenty of interesting work but no systems programming, leaving me in need of a personal project. I wanted this project to pose fundamental Computer Science problems, provide an opportunity for programming creativity, and be something that could be meaningfully expanded over time. Putting this all together, I decided to write a compiler. Additionally, I have aspirations of putting some ideas and a lot of strong opinions into practice in the form of a new programming language; implementing a simpler one seemed to be a more logical entry point.

This isn't completely new territory for me; I did take a compilers course (thanks Joe Near) in grad school not to mention core CS classes like Theory of Computation and Programming Languages with my advisor Chris Skalka. That said this project is quite a bit different in scope, and it's been a few years since I was in a classroom.

The Plan

With the decision to implement a compiler made there were two major undecided questions.

1. What resource(s) to use
2. What programming language for implementation

The Book

I didn't specifically start with making a C compiler as my goal; that decision was made by another. I reviewed the many compiler resources out there against my preferences:

• An Iterative Approach
• Targeting ASM (ideally AMD64)
• Focusing on the practical (not academic theory)
• Guiding but not spoon-feeding code
• No Racket or Lisp

These preferences led me to one clear answer: Writing a C Compiler by Nora Sandler. This post is not a review of the book though I will say it is excellent. If you're an experienced programmer looking for a hands-on approach I'd say this book is for you; no existing compiler knowledge required. The book is more of a guide than tutorial; it gives you just enough context for you to figure out the implementation yourself and an itinerary to stay on track. If you want to deep dive on any given topic you'll need to read elsewhere but that's kinda the point: you're given enough to know what you don't know.

More on Preferences

Given my prior experience I did have a solid idea of what I wanted out of a resource. I'll take this opportunity to retro on them in case it helps others making similar decisions.

Iterative Approach: Compilers are large and complex, leading most people who undertake such a project to abandon it. I like an iterative approach where you complete the full implementation of small features and build up the language organically. At the end of each stage you have something you can actually use and demo; plus the sense of accomplishment that comes with it. You know more is coming so your design is flexible, but you have clear opportunities to refactor as you expand and learn more. At risk of ruining the fun, it's as if the approach is Agile.

Targeting ASM: I'm interested in the low-level and believe that going to that level of abstraction (yes even ASM is an abstraction) maximizes learning. I'm simply less interested in targeting byte-code or LLVM, though the latter is almost certainly the correct production choice if making a new language. Given that I program on an X86-64 machine targeting that made sense. ARM is a much cleaner architecture; if I developed primarily on a Mac I would target that.

Practical Focus: Not much to say here except that I had a focus on writing software, not simply learning theory. I don't think one is better than the other; it's just how I wanted to spend my time.

Guiding but not spoon-feeding: I picked this project wanting to write code and solve problems independently. I consider it a plus that the book doesn't give you more than snippets of pseudo code. For completeness, I'll note that the book does a reference implementation in OCaml; I haven't felt the need to look at it.

No Racket or Lisp: These are a common choice for tutorial/hobby programming language development as they make parsing trivial. I've always had a strong distaste for the syntax, and the languages feel disconnected from what most associate with professional programming. To be clear there's nothing wrong with these I just personally wouldn't feel motivated to work on it.

Why implement C

The core of the C language is quite simple with no garbage collector or runtime and meets our requirement of going to ASM. This simplicity supports the incremental approach; other languages have a lot of interconnected features and concepts. C was designed to be portable assembly allowing a clear mental model of the transformation from AST to ASM. Nearly every language leverages C libraries for core functionality and most use C as their Foreign Function Interface for cross-language interoperability.

Overall I'm very happy with the direction I took, but there are a few downsides.

Type Systems: C is a weakly typed language. Strong typing would present much more learning opportunity. Increasingly rigorous type systems (e.g., Rust, Go) are the direction the field is headed. That said Programming Languages is a complex field in its own right distinct from Compilers and you can't do everything. This one can really be a pro or a con depending on your goals.

Legacy Baggage: Sandler does a good job navigating around this for the most part but C has a lot of baggage. C's design is fundamentally incompatible with safety so a motivated individual can't even attempt to implement them without straying too far off course. Additionally, many of C's design decisions are poor or outdated so learning them to the detail required for implementation doesn't always feel worthwhile. I wouldn't go into a project like this with the goal of making a fully compliant C compiler; there's just too much uninteresting detail and complexity involved (e.g. the preprocessor). Knowing you'll never implement the full language can be a bit demotivating, but you do end up with a sizable subset. Hopefully I can find some real-word programs that fit within it.

All that said, we have to implement something and C is far from a bad choice. For all its faults, C is relevant; it underpins virtually all modern languages and core libraries. In a way, if your goal in building a compiler is to understand how programs really work, you need to understand C: its calling conventions, memory layout, and so on. Perhaps learning C at a deep level will pay direct dividends; time will tell.

The tests

Following Sandler's book has one major advantage I didn't fully appreciate: The test suite. I know everyone says you need to test. You ignore them. The world keeps spinning. That's me too but when writing a compiler, you really need tests. Programming languages especially those with the baggage of C are loaded with edge cases that must be handled correctly. There are infinite combinations of tokens that construct valid programs, and you must handle them all correctly.

The provided test suite allows the reader to follow TDD without the annoying part, writing tests. They were critical in keeping things moving along correctly. NCC passes the full Sandler test suite along with my personal additions that cover additional features and missed cases.

Why Rust?

Rust is a language that I deeply admire but haven't done any complex projects with. I won't go into a pro-Rust rant here except to say it provides incredible safety without compromising performance. A compiler can be written in any language and the best choice is usually the one you know best. In a vacuum OCaml is likely the best fit, though Rust is pretty close and I have both personal interest and professional use cases involving Rust (and neither for OCaml).

Both Rust and OCaml have structural pattern matching, which I consider essential for not hating oneself during compiler development. ASTs are trees of variants: expressions can be binary operations, unary operations, variables, or constants. Pattern matching lets you destructure these cleanly and exhaustively:

match expr {
    Expr::Binary(op, left, right) => { /* handle binary */ }
    Expr::Unary(op, operand) => { /* handle unary */ }
    Expr::Var(name) => { /* handle variable */ }
    Expr::Constant(val) => { /* handle constant */ }
} // Rust ensures you handle every case

The compiler won't let you forget a variant. When you add a new expression type, every match that doesn't handle it becomes a compile error. Compare this to visitor patterns or instanceof chains in languages without pattern matching. It's night and day.

Borrow Checker: The reason one may choose OCaml (or any particular language) over Rust is typically fear of the borrow checker. This has been a non-issue for me thus far. Maybe I have more .clone() than needed, but a garbage-collected language would have that overhead anyway. Recursive types ended up being a breeze with Box<Expr>. Things may become more difficult once I get to optimization passes, but based on my experience so far I'm not too worried. In any case, I firmly believe that the borrow checker's guarantees preventing bugs have saved me far more time than working within its constraints has cost me.

Language Design: The irony isn't lost on me: learning a language designed for memory safety while implementing C, a language famous for letting you shoot yourself in the foot. The contrast between the two has been extremely illustrative and has become my guide in determining what I would want in my own design.

It has not been easy implementing a language I don't know very well, in a language I don't know very well, on a topic I don't know very well. It has, however, been fun. Maybe now I do know some of those things well.

What NCC Can Do Now

After completing Part 1 (Chapters 1-10), NCC compiles a substantial subset of C:

• Expressions: arithmetic, bitwise, comparison, logical (with short-circuit evaluation)
• Variables: local and global, with block scoping and shadowing
• Control flow: if/else, while, do-while, for, switch/case, break/continue, goto
• Functions: definitions, forward declarations, System V AMD64 calling convention
• Storage classes: static (internal linkage), extern (external linkage)
• Operators: compound assignment (+=, -=, *=...), increment/decrement (++x, x++), ternary (?:)

A Real Example

This Collatz Conjecture program demonstrates static variables, functions, loops, bitwise operations, and conditionals:

1// Which starting number under 100 takes the most steps to reach 1?
2
3static int total_steps = 0;
4
5int collatz(int n) {
6    int steps = 0;
7    while (n != 1) {
8        if (n & 1) {
9            n = 3 * n + 1;    // odd
10        } else {
11            n = n >> 1;       // even: divide by 2
12        }
13        steps++;
14    }
15    total_steps += steps;
16    return steps;
17}
18
19int main(void) {
20    int champion = 1;
21    int max_steps = 0;
22
23    for (int i = 1; i < 100; i++) {
24        int steps = collatz(i);
25        if (steps > max_steps) {
26            max_steps = steps;
27            champion = i;
28        }
29    }
30    return champion;  // Returns 97 (118 steps!)
31}
32

NCC compiles this to working machine code showing that NCC is already capable of handling non-trivial programs.

For completeness, here's the grammar:

1<program> ::= { <declaration> }
2<declaration> ::= <variable-declaration> | <function-declaration>
3<variable-declaration> ::= { <specifier> }+ <identifier> [ "=" <exp> ] ";"
4<function-declaration> ::= { <specifier> }+ <identifier> "(" <param-list> ")" ( <block> | ";" )
5<param-list> ::= "void" | "int" <identifier> { "," "int" <identifier> }
6<specifier> ::= "int" | "static" | "extern"
7<block> ::= "{" { <block-item> } "}"
8<block-item> ::= <statement> | <declaration>
9<for-init> ::= <variable-declaration> | [ <exp> ] ";"
10<statement> ::= "return" <exp> ";"
11            | <exp> ";"
12            | "if" "(" <exp> ")" <statement> [ "else" <statement> ]
13            | "goto" <identifier> ";"
14            | <identifier> ":" <statement>
15            | <block>
16            | "break" ";"
17            | "continue" ";"
18            | "while" "(" <exp> ")" <statement>
19            | "do" <statement> "while" "(" <exp> ")" ";"
20            | "for" "(" <for-init> [ <exp> ] ";" [ <exp> ] ")" <statement>
21            | "switch" "(" <exp> ")" <statement>
22            | "case" <exp> ":" <statement>
23            | "default" ":" <statement>
24            | ";"
25<exp> ::= <factor> | <exp> <binop> <exp> | <exp> <assign-op> <exp>
26       | <exp> "?" <exp> ":" <exp> | <exp> "++" | <exp> "--"
27<factor> ::= <int> | <identifier> | <unop> <factor> | "++" <factor> | "--" <factor> | "(" <exp> ")"
28          | <identifier> "(" [ <argument-list> ] ")"
29<argument-list> ::= <exp> { "," <exp> }
30<unop> ::= "-" | "~" | "!"
31<binop> ::= "-" | "+" | "*" | "/" | "%" | "&" | "|" | "^" | "<<" | ">>" | "&&" | "||"
32         | "==" | "!=" | "<" | "<=" | ">" | ">="
33<assign-op> ::= "=" | "+=" | "-=" | "*=" | "/=" | "%=" | "&=" | "|=" | "^=" | "<<=" | ">>="
34<identifier> ::= ? An identifier token ?
35<int> ::= ? A constant token ?
36

Beyond the Book

Extra Credit

Several features in this list: bitwise operations, compound assignment, increment/decrement, goto, and switch statements were suggested but not covered by the book creating some fun challenges. Thankfully they were included in the test suite. I particularly struggled with switch statements which have, let's call it interesting behaviors, but we'll leave that for another time.

Warnings

Implementing a compiler gives you appreciation for the warnings real compilers provide. Sandler does not cover warnings in the book, compiler tutorials typically don't, though warning quality is typically a discerning feature of production compilers. Warnings can easily be the most complex part of the compiler as they may require detailed tracking and analysis of the program's control flow. As safety was not a consideration in C's design warnings are particularly hard to retro-fit into the language.

NCC implements several:

• -Wshadow: Warns when a variable shadows one from an outer scope
• -Wunused-parameter: Warns about function parameters that are never used
• -Wswitch-unreachable: Warns about code before the first case in a switch

These are pretty basic but still help the programmer catch real bugs. I'll be able to implement more complex warnings after getting into optimization passes as they share a lot of tracking and analysis.

Assembly

Sandler follows the typical compiler tutorial pattern of emitting a text representation of assembly which can be passed off to GCC's or Clang's assembler. I decided I really wanted to have the full pipeline complete without calling out to external binaries, which we'll talk about in Pass 6 below.

The Architecture

NCC follows a classic multi-pass compiler pipeline:

• Lexer: Converts source text into tokens using regex patterns with maximal munch. Each token carries a span for error reporting.
• Parser: Recursive descent with precedence climbing. Builds an abstract syntax tree while handling operator precedence.
• Validator: Two-pass semantic analysis: resolves variables to unique names, labels loops/switches, type checks, builds symbol table.
• Tackifier: Lowers the AST to TACKY, a three-address code IR. Flattens nested expressions and makes control flow explicit.
• Codegen: Converts TACKY to x86-64 assembly AST. Assigns pseudo-registers to stack slots and fixes invalid instructions.
• Emitter: Encodes instructions to machine code using iced-x86 and writes ELF/Mach-O object files.
• Linker: Resolves external symbols and produces the final executable. Uses wild on Linux.

To illustrate, we'll trace this small program through each pass, showing how we iteratively transform source code into an executable:

1static int counter = 0;
2
3int next(void) {
4    counter++;
5    return counter;
6}
7
8int main(void) {
9    return next() + next();
10}
11

All representations of this program below share this green-tinted background.

Pass 1: Lexer

The lexer converts source text into tokens using regex patterns. Nothing fancy, just a table of patterns mapped to token types:

const TOKEN_PATTERNS: &[(&str, Token)] = &[
    (r"^int\b", Token::IntKeyword),
    (r"^return\b", Token::ReturnKeyword),
    (r"^[a-zA-Z_]\w*\b", Token::Identifier(String::new())),
    (r"^[0-9]+\b", Token::ConstantInt(String::new())),
    // ... operators, punctuation, etc.
];

The lexer tries all patterns and picks the longest match (maximal munch), so interface matches as an identifier (9 chars), not the int keyword (3 chars). Each token carries a Span (file, line, column) for error messages later.

Our example becomes a flat stream of tokens:

[StaticKeyword, IntKeyword, Identifier("counter"), Assignment, ConstantInt("0"),
 Semicolon, IntKeyword, Identifier("next"), OpenParen, VoidKeyword, CloseParen,
 OpenBrace, Identifier("counter"), Increment, Semicolon, ReturnKeyword,
 Identifier("counter"), Semicolon, CloseBrace, IntKeyword, Identifier("main"),
 OpenParen, VoidKeyword, CloseParen, OpenBrace, ReturnKeyword, Identifier("next"),
 OpenParen, CloseParen, Plus, Identifier("next"), OpenParen, CloseParen,
 Semicolon, CloseBrace]

Pass 2: Parser

The parser transforms the token stream into an Abstract Syntax Tree (AST).

Abstract Syntax Tree: A tree structure representing the program's hierarchical structure where each node corresponds to a construct in the source code.

NCC's parser uses recursive descent with precedence climbing to match the approach of production compilers. It's a common complaint that compiler discussions dedicate too much time to parsing; we'll try to avoid that error. Rolling your own parser is actually quite simple once you understand the core algorithm. The alternative is to use a parser generator like YACC and learn some automata theory. Recursive descent is easier to learn, debug, and reason about, while retaining full control over error messages and AST construction.

For example, NCC peeks ahead to fuse - with integer literals so -2147483648 parses correctly instead of overflowing as -(2147483648). The parser also emits -Wswitch-unreachable when it detects statements before the first case. These context-sensitive behaviors would be awkward to express in a grammar file.

Recursive descent handles statements and declarations. Each grammar rule becomes a function (parse_statement(), parse_declaration(), parse_block()) and parsing a construct means calling the function for that rule. When a rule references other rules, you call those functions, hence "descent." As you descend, you consume tokens from the front of the queue; when you return, the tokens for that construct are gone.

Precedence climbing handles expressions. Instead of writing separate functions for each precedence level (15+ for C's operators), you write one function that takes a minimum precedence parameter. Parse the left operand, then loop: if the next operator's precedence is high enough, consume it and recurse for the right side. Higher-precedence operators bind tighter because they get parsed in deeper recursive calls.

For example, parsing a + b * c: when we see + (precedence 45), we recurse with min_prec=46. The * (precedence 50) is higher, so it gets consumed in that recursive call. The recursion returns b * c, and we build a + (b * c).

Our example program parses to the AST below. Note how our representation now has the structure of the language.

Program
├── VarDeclaration
│   ├── name: counter
│   └── init: Constant(0)
├── FunDeclaration
│   ├── name: next
│   └── body:
│       ├── Expression
│       │   └── PostFix (Increment)
│       │       └── Identifier("counter")
│       └── Return
│           └── Identifier("counter")
└── FunDeclaration
    ├── name: main
    └── body:
        └── Return
            └── Binary (Add)
                ├── FunctionCall: next
                └── FunctionCall: next

Pass 3: Validator (Semantic Analysis)

After parsing, we know the program is syntactically valid. Now we verify its semantics in two passes over the parser's AST.

Resolution pass

Variable resolution: Variables are renamed for uniqueness. Two variables might be syntactically the same (both named x) but semantically refer to different objects.

Loop and switch labeling: Break and continue statements need to know which loop they belong to. The validator annotates each loop with a unique label number, and each break/continue with its target.

goto/label validation: We verify that all goto statements target labels that exist in the same function.

Warnings: NCC provides warnings in select cases of valid but often undesirable programs.

Here's how variable resolution transforms a function with shadowing:

1// Before resolution:
2int foo(int x) {     // -Wunused-parameter: x never used
3    int x = 2;       // -Wshadow: shadows parameter
4    {
5        int x = 3;   // -Wshadow: shadows x from outer scope
6    }
7    return x;
8}
9
10// After resolution:
11int foo(int x.1) {
12    int x.2 = 2;
13    {
14        int x.3 = 3;
15    }
16    return x.2;
17}
18

After this pass, the compiler no longer needs to track scoping; each name is globally unique. The warnings are emitted during resolution as we detect each shadowing occurrence.

Typecheck pass

Type checking: Currently NCC supports a single type, int. Even so, there's work to do. We ensure functions aren't used as variables and vice versa, check that function declarations don't conflict, and verify call sites have the correct number of arguments.

Building the symbol table: Functions and global variables get recorded with their types, linkage (static vs extern), and whether they've been defined. Codegen uses this table to determine which symbols need relocations and which are local to this translation unit.

Constant expression evaluation: Case labels and static variable initializers must be compile-time constants. We recursively evaluate these expressions during validation, folding operations like 1 + 2 into their result.

A note on C's overloaded keywords: static means "internal linkage" at file scope but "static storage duration" inside a function. extern means "defined elsewhere" but can also just be a declaration without definition. Implementing these correctly meant carefully reading the spec and testing against GCC's behavior.

For this simple example the AST structure is unchanged, but loops would be annotated with labels for break/continue resolution and variables renamed. The validator builds a symbol table: counter is marked as static (internal linkage, not visible to other files), while next and main are global. The initializer 0 is evaluated as a constant expression. After passing this stage we know that the program is valid, the AST didn't change much but the work here allows a big leap in the next pass.

Pass 4: Tackifier (AST → TACKY IR)

TACKY is a three-address code IR where complex expressions become sequences of simple operations:

temp.1 = b * c
temp.2 = a + temp.1
Copy temp.2 -> x

Why bother with an IR? Two reasons:

1. Expressions become trivial. The AST has nested expressions; TACKY has flat sequences. Code generation doesn't need to think about operator precedence or temporary management.

2. Control flow becomes explicit. An if statement becomes jumps and labels:

JumpIfZero condition -> else_label
  ... then block ...
Jump -> end_label
Label(else_label)
  ... else block ...
Label(end_label)

The tackifier walks the AST recursively, emitting instructions into a flat list. A NameGenerator produces unique temporary names (temp.1, temp.2, etc.).

Here's our example lowered to TACKY. Notice how nested expressions are now flat sequences of simple operations.

Program
├── FunctionDefinition: next
│   ├── Copy counter -> postfix_org.1
│   ├── Binary Add counter, 1 -> postfix_new.1
│   ├── Copy postfix_new.1 -> counter
│   └── Return counter
│
├── FunctionDefinition: main
│   ├── FunCall next() -> call.1
│   ├── Copy call.1 -> binary_left.1
│   ├── FunCall next() -> call.2
│   ├── Binary Add binary_left.1, call.2 -> temp.1
│   └── Return temp.1
│
└── StaticVariable: counter (init: 0)

The postfix increment counter++ becomes explicit: save the original, compute the new value, store it back. In main, the nested expression next() + next() is flattened and each function call result is captured in a temporary before the add.

Pass 5: Codegen (TACKY → Assembly AST)

This pass converts TACKY instructions to an assembly AST, a structured representation of x86-64 instructions.

The conversion is mostly straightforward: TACKY's Binary { Add, src1, src2, dst } becomes x86's mov src1, dst; add src2, dst. But there are complications:

Pseudo-registers: Initially, all variables are Pseudo("x.1") operands. This lets us generate instructions without knowing the data's canonical location; a later iteration in this pass assigns stack slots or registers:

fn replace_pseudo(&mut self, operand: &Operand) -> Operand {
    match operand {
        Operand::Pseudo(name) => {
            if self.data_vars.contains(name) {
                Operand::Data(name.clone())  // Global: RIP-relative
            } else {
                self.get_stack_location(name)  // Local: stack slot
            }
        }
        _ => operand.clone(),
    }
}

Fixing invalid instructions: x86-64 has restrictions. You can't mov from memory to memory, or idiv an immediate. A fixup pass rewrites these:

// Memory-to-memory move: use R10 as intermediate
Instruction::Mov { src, dst } if src.is_memory() && dst.is_memory() => {
    new_ins.push(Instruction::Mov { src, dst: Operand::Reg(Reg::R10) });
    new_ins.push(Instruction::Mov { src: Operand::Reg(Reg::R10), dst });
}

Calling convention: Function calls follow System V AMD64 ABI. The first six integer arguments go in RDI, RSI, RDX, RCX, R8, R9; the rest go on the stack. The stack must be 16-byte aligned before call.

The next function's assembly AST shows pseudo-registers replaced with stack slots and counter using RIP-relative addressing (accessing data relative to the instruction pointer, required for position-independent code):

Program
├── FunctionDefinition: next
│   ├── AllocateStack 16
│   ├── Mov Data(counter) -> R10
│   ├── Mov R10 -> Stack(-4)
│   ├── Mov Data(counter) -> R10
│   ├── Mov R10 -> Stack(-8)
│   ├── Binary Add Imm(1) -> Stack(-8)
│   ├── Mov Stack(-8) -> R10
│   ├── Mov R10 -> Data(counter)
│   ├── Mov Data(counter) -> AX
│   └── Ret
│
├── FunctionDefinition: main
│   ├── AllocateStack 16
│   ├── Call next
│   ├── Mov AX -> Stack(-4)
│   ├── Mov Stack(-4) -> R10
│   ├── Mov R10 -> Stack(-8)
│   ├── Call next
│   ├── Mov AX -> Stack(-12)
│   ├── Mov Stack(-8) -> R10
│   ├── Mov R10 -> Stack(-16)
│   ├── Mov Stack(-12) -> R10
│   ├── Binary Add R10 -> Stack(-16)
│   ├── Mov Stack(-16) -> AX
│   └── Ret
│
└── StaticVariable: counter (init: 0)

Pass 6: Emitter (Assembly → Machine Code)

This is where NCC diverges from most tutorials. Instead of emitting assembly text and shelling out to as, we use iced-x86 to encode instructions directly:

let mut asm = CodeAssembler::new(64)?;
asm.mov(rax, rbp - 8)?;   // Local variable
asm.add(rax, rcx)?;
asm.mov(rbp - 16, rax)?;
...

For working with X86-64 I recommend using a library or sticking with emitting textual asm as instruction sizes vary making it difficult to encode. In contrast, I've heard assembling ARM is much more straightforward and doable as a hobby project.

The object crate then wraps the machine code in ELF (Linux) or Mach-O (macOS) format, handling relocations for external symbols.

Why do this?

• Single binary: no dependency on external tools
• Faster compilation: no spawning subprocesses
• Educational: you understand exactly what bytes end up in the executable

The tradeoff is complexity. When you emit text assembly, the assembler handles instruction encoding, relocation generation, and symbol table construction. With iced-x86, you handle these yourself: ensuring RIP-relative addressing for static variables, calculating relocation addends based on instruction format, setting correct symbol visibility for cross-file linking, and building object files with proper sections and relocations. (That's a whole other blog post.)

NCC can pretty-print the assembly for debugging, using the symbol table to resolve function and global variable names back to their labels:

1next:
2  push %rbp
3  mov %rsp,%rbp
4  sub $16,%rsp
5  mov counter(%rip),%r10d
6  mov %r10d,-4(%rbp)
7  mov counter(%rip),%r10d
8  mov %r10d,-8(%rbp)
9  addl $1,-8(%rbp)
10  mov -8(%rbp),%r10d
11  mov %r10d,counter(%rip)
12  mov counter(%rip),%eax
13  mov %rbp,%rsp
14  pop %rbp
15  ret
16
17main:
18  push %rbp
19  mov %rsp,%rbp
20  sub $16,%rsp
21  call next
22  mov %eax,-4(%rbp)
23  mov -4(%rbp),%r10d
24  mov %r10d,-8(%rbp)
25  call next
26  mov %eax,-12(%rbp)
27  mov -8(%rbp),%r10d
28  mov %r10d,-16(%rbp)
29  mov -12(%rbp),%r10d
30  add %r10d,-16(%rbp)
31  mov -16(%rbp),%eax
32  mov %rbp,%rsp
33  pop %rbp
34  ret
35
36.bss
37counter:
38  .zero 4
39

We made it from C to x86-64! The observant reader may notice that there's a few unnecessary moves here. This is because NCC uses the load-execute-store pattern which treats the stack as the canonical location only using registers as scratch space for individual operations. This assembly will look a bit different, and be more efficient, once register allocation and copy propagation are implemented.

Pass 7: Linker

On Linux, NCC uses libwild for linking, a Rust linker that can produce executables without calling the system ld. On macOS, we shell out to ld as libwild does not support it.

The linker resolves external symbols (like putchar from libc), combines object files, and produces the final executable.

Why So Many Passes

Each pass should do one thing. Compilers are complex but writing them doesn't have to be. Each pass either transforms the program representation closer to the target or checks it for correctness. As complexity grows so will the number of passes; individual optimizations may even be their own pass.

Lessons Learned

Building a compiler forces you to learn plenty of things; I'll skip the obvious and touch on some high-level concepts.

• Programming Language Design: Seeing the faults of C while working with Rust's constraints and guarantees has shaped my thinking on what makes a good language
• Abstractions: Difficult problems can be more easily handled with layers of abstraction, sometimes you need a few.
• Understanding C: It's not all about ASM. C's standards (e.g. calling convention, stack layout, linking) underpin the modern languages we use daily.
• Have a Plan: Complex hobby projects usually end up abandoned. Having a clear focus can help. The incremental approach is key, picking the project back up after a few months never felt daunting.

If you're interested in compilers, systems programming, or just want to flex your Computer Science skills I recommend you tackle a similar project. The book is excellent, and the learning is unmatched.

What's Next

There are two parts of the book left, making the next step clear. In Part II I'll be adding more complex types including pointers, arrays, and structs. Part III will add register allocation and some optimization passes.

After the book there's a few directions I could go.

Optimizations: I'll likely convert TACKY to Static Single Assignment (SSA) form and add some more complex optimizations like sparse conditional constant propagation (SCCP), loop-invariant code motion, and common subexpression elimination. I've also been interested in auto-vectorization and could see myself implementing it; TSVC (Test Suite for Vectorizing Compilers) would be a good benchmark to work toward.

Language Design: Ultimately I'd like to make my own language and have been firming up exactly what I want that to look like. I would likely implement it using NCC's backend (though learning LLVM would be a practical choice) so it complements the first item.

As far as the blog goes I may do some deeper dives on some of the topics covered here including specific feature implementations (e.g. switch statements), interesting bugs I encountered, and thoughts on language design.

NCC is open source and available on GitHub.