Majority of the resources I used to build Tucan, my toy optimizing compiler in Rust. This list is not complete but most of the things listed here are things I really read through and used.
- Engineering a compiler (I use this a lot! For SSA, dominance and optimizations)
- Static Single Assignment Book (I use this a lot!)
- Types And Programming Languages
- Abdulaziz Ghuloum - An Incremental Approach to Compiler Construction
- Abdulaziz Ghuloum - Compilers: Backend to Frontend and Back To Front Again
- Simple Generation of Static Single-Assignment Form
- Simple and Efficient Construction of Static Single Assignment Form
- A Simple, Fast Dominance Algorithm (heavily used this to implement dominators & dominance frontier)
- Efficiently Computing Static Single Assignment Form and the Control Dependence Graph
- Eric Fritz - Waddle – Always-Canonical Intermediate Representation
- Cliff Click - A Simple Graph-Based Intermediate Representation
- Cliff Click - From Quads to Graphs: An Intermediate Representation's Journey
- Linear Scan Register Allocation in the Context of SSA Form and Register Constraints (I used this to implement reg alloc)
- Linear Scan Register Allocation on SSA form
- Optimized Interval Splitting in a Linear Scan Register Allocator
- Linear Scan Register Allocation for the Java HotSpot™ Client Compiler
- Computing Liveness Sets for SSA-Form Programs (I used this to implement liveness analysis)
- Linear Scan Register Allocation in the Context of SSA Form and Register Constraints
- R. E. Tarjan - Testing Flow Graph Reducibility
- Paul Havlak - Nesting of Reducible and Irreducible Loops
- G. Ramalingam - Identifying loops in almost linear time
- Presentation on LLVM's IR
- Markus Denker Presentation
- Slides on dominance frontier
- Slides on liveness analysis
- Wasmtime Cranelift docs on IR: https://github.com/bytecodealliance/wasmtime/blob/main/cranelift/docs/ir.md
- Rust's MIR:
- https://blog.rust-lang.org/2016/04/19/MIR.html
- https://rustc-dev-guide.rust-lang.org/mir/index.html
- https://github.com/nikomatsakis/rfcs/blob/mir/text/0000-mir.md
- Here are the type definitions: https://github.com/rust-lang/rust/blob/f7ec6873ccfbf7dcdbd1908c0857c866b3e7087a/src/librustc/mir/repr.rs
- This is a good idea: https://rustc-dev-guide.rust-lang.org/mir/construction.html#unpack-all-the-things
- This shows how to generate three-address code (TAC) from an AST:
- This shows how both blocks in a conditional write results to a temp:
- The Go source code also has conversion from AST to SSA and this is the entry point: https://sourcegraph.com/github.com/golang/go@master/-/blob/src/cmd/compile/internal/gc/ssa.go#L1106-1113
- @mraleph's irhydra: https://github.com/mraleph/irhydra/blob/master/saga/lib/src/flow/ssa.dart
- [This comment][https://twitter.com/mraleph/status/1343907821495181313?s=20] by him is also interesting
- Cranelift's README on SSA-based regalloc: craneliftregalloc
- Mike Pall on LuaJIT's "reverse linear scan" algorithm: mikepallreverselinearscan
- Blog post from one of the author's of MoarVM on "reverse linear scan": reverselinearscanblogpost
- Slides: https://ethz.ch/content/dam/ethz/special-interest/infk/inst-cs/lst-dam/documents/Education/Classes/Spring2018/210_Compiler_Design/Slides/w14_01-register-allocation_18.pdf
- https://stackoverflow.com/questions/23793366/simple-register-allocation-scheme-for-x86
- https://stackoverflow.com/questions/1960888/register-allocation-and-spilling-the-easy-way
- https://web.stanford.edu/class/archive/cs/cs143/cs143.1128/lectures/17/Slides17.pdf
- https://twitter.com/rsms/status/1326924181317931009
- https://rsms.me/co/doc/chaitin/?input=slc&enable-briggs=1®count=3&slc=a%20%3D%201%0Ab%20%3D%202%0Ac%20%3D%203%0Ad%20%3D%20b%20%2B%20a%0Ae%20%3D%20b%20%2B%20c%0Af%20%3D%20e%20%2B%20b%0Ag%20%3D%20d%20%2B%20c%0A%2F%2Fg%20%3D%20d%20%2B%20f&ifg=a%20--%20b%0Aa%20--%20c%0Ab%20--%20c%0Ab%20--%20d%0Ab%20--%20e%0Ac%20--%20d%0Ac%20--%20e%0Ad%20--%20e
- https://github.com/rsms/co/blob/master/src/ir/regalloc.ts
- See the commit message on this one: https://github.com/pbiggar/phc/blob/master/misc/old_comments/sccp.txt#L9
- Good blog post on value numbering
- Wikipedia entry on Value Numbering is good
- x64 cheat sheet
- another cheat sheet
- The dora Cannon compiler
- Explaining argc, argv in ASM
- Stack frame layout on x86-64
- Guide to x86 Assembly
- The Go source code also has conversion from AST to SSA and this is the entry point: https://sourcegraph.com/github.com/golang/go@master/-/blob/src/cmd/compile/internal/gc/ssa.go#L1106-1113
- Here is the part of the code that handles assignment: https://sourcegraph.com/github.com/golang/go@95ce805d14642a8e8e40fe1f8f50b9b5a2c4e38b/-/blob/src/cmd/compile/internal/gc/ssa.go#L1254
- This is the most important file:
src/cmd/compile/internal/gc/ssa.go
Rust compiler has some good code to read:
- Traversal iterators https://github.com/rust-lang/rust/blob/master/compiler/rustc_middle/src/mir/traversal.rs
- Walking up a tree iterator https://github.com/rust-lang/rust/blob/fe1bf8e05c39bdcc73fc09e246b7209444e389bc/compiler/rustc_middle/src/hir/map/mod.rs#L108-L138
- Defining the
Indexis also interesting: https://github.com/rust-lang/rust/blob/fe1bf8e05c39bdcc73fc09e246b7209444e389bc/compiler/rustc_middle/src/mir/mod.rs#L494-L509 - These small closure-based iterators are also cool: https://github.com/rust-lang/rust/blob/fe1bf8e05c39bdcc73fc09e246b7209444e389bc/compiler/rustc_middle/src/mir/mod.rs#L382-L389
- Here's how they implement dominators: https://github.com/rust-lang/rust/blob/fe1bf8e05c39bdcc73fc09e246b7209444e389bc/compiler/rustc_data_structures/src/graph/dominators/mod.rs
- Interesting: https://github.com/rust-lang/rust/blob/130b2ab0ed272f93dd5d019e72ac1fd4b4a77323/compiler/rustc_mir/src/transform/remove_noop_landing_pads.rs#L102-L103
- They don't compute the complete set of dominators, but instead only the immediate dominator, which they then use to to iterate over all dominators: https://github.com/rust-lang/rust/blob/fe1bf8e05c39bdcc73fc09e246b7209444e389bc/compiler/rustc_data_structures/src/graph/dominators/mod.rs#L120-L141
- This repository is gold: https://github.com/aprell/compiler-potpourri