I-mikan-I/ssa-compiler

Rust 🦀 SSA Compiler

A compiler that uses SSA (single static assignment form) as its definitive IR, written entirely in Rust!

The compiler hosts an optimization pipeline and native assembly generation.

Usage

Show information about available CLI commands:

Display Options:

$ cargo run -- --help

Compile correct3.lang into RISCV assembly:

$ mkdir build
$ cargo run -- examples/correct3.lang -o build

Disable optimization:

$ mkdir build
$ cargo run -- examples/correct3.lang -o build --no-optimize

Use the output to generate a rv64 elf:

$ cargo run --release -- examples/incr-twice.lang examples/incr.lang -o build
$ riscv64-linux-gnu-gcc -mabi=lp64d examples/incr.c build/incrtwice.s build/increment.s build/init.s build/_globals.s -o build/increment.elf
$ qemu-riscv64 build/increment.elf

Roadmap

• Parser (DONE)
• Intermediate Representation (DONE)
  • Definition (DONE)
  • Translation from AST (DONE)
  • CFG construction (DONE)
  • SSA transformation (DONE)
• Optimization passes (DONE)
  • GVN-PRE (DONE)
  • Copy propagation (DONE)
• Backend (DONE)
  • Register allocation (DONE)
  • Instruction selection (DONE)
• Global data (DONE)

Cargo features

Feature	Description
print-cfgs	Displays every constructed CFG as a dot graph.
print-gvn	Displays debug information of the GVN-PRE pass.
print-linear	Displays generated linear code.

Language features

The syntax of the supported language is described in spec.bnf.
Global functions and global variables have to be forward declared, undefined but declared symbols are left to resolve by the linker. You can call your functions from C code, see this example. The compiler generates optimized riscv64 gnu assembly files, which can then be linked with any other objects.

Further reading

I go into some implementation details in my medium article!

Viewing the control flow graphs after each step helps one understand and debug the code:

Initial CFG: SSA CFG: Optimized CFG: Register-allocated CFG: