A working compiler for a C language subset

This project, USCC, builds out a working compiler for a C language subset called USC (language reference). USCC uses the LLVM framework as its code generation engine.

Project 1: Recursive Descent Parsing

Implemented a LL(1) parser that parses the program into AST. [Handout] [Report]

Project 2: Semantic Analysis

Implemented scoped symbol table that enable scoped identifier declarations, and type checking/conversion that enables conversion between char and int. [Handout] [Report].

Project 3: LLVM IR Generation

Implemented an IREmitter that lowers various types of AST node (e.g., While statement, If statement) to LLVM IR using llvm::IRBuilder. [Handout] [Report]

Project 4: Static Single Assignment (SSA) generation

Implemented a fairly new approach to generate SSA form as outlined in this paper, which directly generate SSA form from the high-level AST, without generating non-SSA form first as in Clang/LLVM. [Handout] [Report]

Project 5: LLVM Optimization Passes

Implemented three LLVM optimization passes, including constant branch folding, dead block removal and loop invariant code motion (LICM).

Project 6: Register Allocation (via graph-coloring)

Implemented a graph-coloring register allocator with LLVM infrastructure (using RegAllocBase interface), following this helpful tutorial. The algorithm is described in the Chatin-Brigg’s paper.