David Yue

This list is mainly for myself. I'm not going to pretend I know much about compilers, I know close to zero. But someone may find this helpful.

• The infamous "dragon" book

  • Compilers: Principles, Techniques, and Tools by Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman
  • Good for understanding dataflow analysis
  • Missing any mention of SSA

• Engineering a Compiler by Keith Cooper and Linda Torczon

  • This book is a lot more implementation focused than the dragon book
  • I used this book as a reference for implementation at first.
  • Gentle introduction to SSA
  • SSA based transforms: SSCP etc.

For the two textbooks above, I'm not supposed to tell you that there are sites like Library Genesis where you can download them for free. So please don't do that :)

• Dataflow Analysis Additional Resources and Notes

  • Understanding why we use reverse post-order in forward dataflow analysis
    • https://eli.thegreenplace.net/2015/directed-graph-traversal-orderings-and-applications-to-data-flow-analysis/
  • Universal set initialization for computing available expressions. https://cs.stackexchange.com/questions/161114/dataflow-analysis-available-expressions-why-is-outb-initialized-to-universal

• Course pages that provide helpful slides for various compiler topics

  • https://www.cs.princeton.edu/courses/archive/spring22/cos320/
  • https://www.cl.cam.ac.uk/teaching/1718/OptComp/slides.html
  • https://www.cs.cornell.edu/courses/cs6120/2020fa/self-guided/

• Global Value Numbering - Partial Redundancy Elimination

  • Essentially Partial Redundancy Elimination in SSA form
  • https://hosking.github.io/links/VanDrunen+2004CC.pdf

• Simple and Efficient Construction of Single Static Assignment Form

  • State of the art Into-SSA translation algorithm
  • https://c9x.me/compile/bib/braun13cc.pdf

• Static Single Assignment Book

  • Very informative collection of "book excerpts" on SSA form. Especially translation out of SSA form.
  • Register Allocation
  • https://pfalcon.github.io/ssabook/latest/book-full.pdf

• LLVM mem2reg Algorithm

  • https://longfangsong.github.io/en/mem2reg-made-simple/
  • Proof of Correctness? https://langdev.stackexchange.com/questions/3992/ssa-construction-dfs-of-cfg-vs-traversal-of-dominator-tree

• Algorithm for computing immediate dominators

  • https://sbaziotis.com/compilers/visualizing-dominators.html

• Register Allocation

  • George & Appel Iterated Register Coalescing https://dl.acm.org/doi/pdf/10.1145/229542.229546
    • Graph Based Register Allocation, Chaitin-Briggs Algorithm.