This repo contains various reference implementations of compiler related data structures and algorithms.
Most of the following was initially done while working through Cornell's CS6120 course from the course assignments, reading papers, LLVM's codebase and various books.
The objective is to create a sort of cookbook of reference implementations that focus on clarity, simplicity and hopefully correctness.
The repository contains a complete implementation of the Bril intermediate language with several analyses, optimizations and various compiler related data structures e.g control flow graphs, SSA representation, dominance graphs...
I hope you enjoy hacking on it as much as I enjoyed writing.
The repository is designed to allow you to hack on things as much as possible.
The core implementation revolves around bril.ir where most
of the core intermediate language is implemented, the tools directory
contains small utilities that can be used to parse and manipulate Bril programs.
For testing, a custom built tool inspired by llvm-lit called turnstile
is provided. turnstile runs snapshot testing of input vs outputs, it's both a
testing framework and a library that can be used to write expect style tests.
turnstile is how we test all program transformations especially when it comes
to optimization passes and so on.
If you don't like turnstile which is just a lighter, basic version of turnt
then you can use turnt instead which supports configuration via TOML and better
CLI integration.
This is a non-exhaustive list of things that are currently implemented :
- Various mini tools to work with the IR in tools folder.
- Instructions and Basic Blocks see ir.py
- Control Flow Graph construction, predecessors and successors computation.. see cfg.py
- Scalar optimizations like dead code elimination, redundant store elimination, local value numbering with constant propagation and constant folding see transform.py.
- Program analyses (without the data flow framework) like liveness analysis and available expressions see analyses.py .
- Data-flow analysis, with a data-flow framework see df.py