Compiler for a Simple Language in OCaml

An end-to-end compiler toolchain for a small C-like language (Oat), implemented in OCaml.

It covers the full pipeline from parsing to LLVM IR and x86 code generation, and includes a set of classic static analyses and optimizations.

What I built

• Type system / typechecking
  • Implemented a specification-driven typechecker (contexts, subtyping, and full expression/statement checking) to enforce type safety.
  • Added structured context building for globals, structs, and function declarations.
• Frontend compilation (language features)
  • Extended the frontend to support structs and function pointers.
  • Implemented array length and array initializers.
  • Added checked cast support via null-pointer checking with correct scoping for the “not-null” branch.
• Generic dataflow framework
  • Implemented a reusable worklist solver (as an OCaml functor) that computes fixpoints over CFG-like graphs.
  • Used analysis-specific lattice operations (combine, equality/ordering) and flow functions.
• Analyses and optimizations
  • Liveness analysis (dataflow) as a baseline analysis and a backend input.
  • Alias analysis to determine when a pointer uniquely names a stack slot.
  • Dead code elimination (DCE) with store elimination when the destination is proven non-aliased and dead.
  • Constant propagation + constant folding, then iterative constprop → dce optimization (O1-style).
• Backend: register allocation
  • Implemented an improved register allocation strategy leveraging liveness information, outperforming a greedy baseline on provided quality tests.
• Experimentation / validation
  • Benchmarked multiple configurations (baseline, greedy, better, clang) with and without -O1, using time on representative programs.

Repositories

• Optimization + analyses: opt
• Typechecking: type-check