C Compiler

Description

I built this compiler to understand how C programs become machine instructions. The frontend, semantic analysis, intermediate representation, and optimization passes are written from scratch in C.

It supports a subset of C: integer variables and expressions, local scopes, functions, conditionals, loops, and short-circuit logic. The original backend generates x86-64 assembly using the System V AMD64 calling convention, with GCC handling assembly and linking. Each function allocates its own stack frame to store local variables and temporaries. Stack frame size is determined during semantic analysis and lowering phases.

Development

I started by generating assembly directly from an abstract syntax tree (AST), the parser's structured representation of a program. This gave me a working compiler, but it produced a lot of unnecessary machine code and was not optimized. Additionally, all operations were done by pushing 32 bit integers to the stack, which could lead to stack pointer misalignment issues.

I then introduced a custom three-address intermediate representation (IR). Breaking expressions into small instructions allowed for compiler optimization and simplified what the backend needs to handle.

Original:  C source → Frontend / AST → x86-64 assembly

Redesign:  C source → Frontend / AST → Three-address IR
                                             ↓
                                         Optimizer
                                             ↓
                                  x86-64 backend (in progress)

The Pipeline

Parsing: A recursive-descent parser handles operator precedence and builds the AST.

Semantic Analysis: Semantic analysis resolves variables and functions, tracks block scopes, assigns stack offsets, and checks that statements such as break and continue have valid targets.

IR Lowering: Expressions become operations on constants, resolved variables, and compiler-generated temporaries. Branches and loops become labels and jumps, so later stages can work with a small instruction set.

// C source
return (a + b) * 2;

// Three-address IR
t0 = a + b
t1 = t0 * 2
RETURN t1

Optimization: Constant folding evaluates constant expressions. Propagation carries known values forward. Branch simplification and reachability analysis remove unnecessary jumps and unreachable code. These passes repeat until no further changes occur. These passes are currently conservative, meaning they do not try to optimize across different labels and jumps.

Limitation: Currently variables and temporaries use stack locations, allocated in the stack frame of each function, avoiding a register allocator at this stage. Hopefully, that will change in the future.

Current status

Working: the original AST-to-x86-64 compiler. The custom IR, AST-to-IR lowering, and optimization passes are also implemented.

In progress: completing the optimized IR-to-x86-64 backend. The original backend remains a working reference during the transition.