r/Compilers • u/vmcrash • 4d ago
Papers for new compiler devs
What papers do you suggest for new compiler developers to read for different parts of a compiler?
My most important recommendation would be Linear Scan Register Allocation for the Java HotSpot™ Client Compiler, the master thesis of Christian Wimmer. It is very well written, easy to understand, and covers a lot of practical details.
22
u/NXDLang 4d ago
If your goal is to become a better compiler engineer rather than just collect papers, I'd recommend focusing on the papers that introduced ideas you're actually going to implement. A lot of new compiler developers jump straight into the latest PLDI papers and end up drowning in details. The classics are classics for a reason. 1. SSA (Static Single Assignment) Cytron et al. (1991) Efficiently Computing Static Single Assignment Form and the Control Dependence Graph This is probably the single most important compiler paper you'll ever read if you're interested in optimization. Modern compiler infrastructures such as LLVM are heavily SSA-based. Paper: SSA Paper (Cytron et al.) 1
Data Flow Analysis Kildall (1973) A Unified Approach to Global Program Optimization This paper laid the foundation for a huge amount of modern compiler optimization work, including constant propagation, liveness analysis, and many dataflow techniques. Paper: Kildall's Dataflow Paper 2
Register Allocation Chaitin et al. (1981) Register Allocation via Coloring One of the most influential backend papers ever written. It introduces graph-coloring register allocation, which still shows up in compiler courses today. Paper: Register Allocation via Coloring 3
LR Parsing Knuth (1965) On the Translation of Languages from Left to Right This is the paper that introduced LR parsing. Even if you end up using recursive descent, Pratt parsing, or PEGs, it's worth understanding where modern parsing theory came from. Reference: Knuth LR Parsing Paper 4
PEG Parsing Bryan Ford (2004) Parsing Expression Grammars: A Recognition-Based Syntactic Foundation If you're interested in modern parser design, PEGs are worth learning. They influenced numerous language implementations and tooling ecosystems. Paper: PEG Paper
LLVM Lattner & Adve (2004) LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation Even if you never use LLVM directly, understanding why LLVM was designed the way it was will teach you a tremendous amount about IR design. Paper: LLVM Paper
After reading those, start browsing papers from: • PLDI • POPL • CGO • CC (Compiler Construction) • OOPSLA But honestly, I'd rank implementing a compiler and reading LLVM/Rust/Go/Zig source code above reading most research papers. The papers teach the ideas. Real compiler code teaches how those ideas survive contact with reality.
3
u/splicer13 4d ago
Almost all your recs seem dated
- Cytron: No, dude. It's 40 pages long and notable because it was first-ish not because it explains anything well or simply. When you get SSA, everything is obvious and simple in retrospect. Cytron as a paper reflects all the work that went into 'getting it.' Just now it's just needless punishment. There's a paper from ETH that does it in like 3 pages if control flow is structured.
1a. Maybe Chow or another paper on various variants of SSA
Kildall: Very important historical interest, debatable if anyone would remember it if it wasn't by "the guy who wasn't bill gates."
Not preston briggs? Chaitan came first obviously but almost all first papers are crappy learning resources for practicing engineers.
3
u/EggplantExtra4946 4d ago
Alan C. Lawrence, 2007, Optimizing compilation with the Value State Dependence Graph https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-705.pdf
I only read the first 2 chapters but I found it illuminating, that the IR is that much a central piece of optimizing compilers. It made me understand what the fuss was all about concerning SSA.
2
u/splicer13 4d ago
Wimmer paper is good. We (mostly Carol Eidt) based the .NET JIT compiler on it.
Wegman and Zadek "Constant Propagation with Conditional Branches" I like and the descendant: Combining Analyses, Combining Optimizations
HOWEVER do not take that to mean I endorse sea of nodes representation. Everyone except for Cliff Click that I know regards SoN as a mistake both in Hotspot and Turbofan. And not just because Cliff Click makes himself very hard to like, which he does.
1
u/umlcat 4d ago
Before you start, as a friendly disclaimer.
As it occurs with other software, there are several ways to built the same thing, so if you take a look at several compiler design sources, you may find that there are different, and may confuse you.
Take the one that suits you more.
Some questions that may affect the compiler design sources you choose:
Which is the programming language and programming framework you are used to work with ?
Which programming paradigm are you more used to, procedural, object oriented, functional ?
Are you already interested in some existing Compiler Design Framework, such as GCC, LLVM, ANTLR, Gold, or another ?
As an example, I will mention that I learned a lot of procedural pascal and object and class oriented pascal at college, and I also learned C and object and class oriented C++, at college.
My compiler related classes were using "Plain C" style, but there were already object and class oriented C++ techniques for programming design.
Speaking of Functional Programming, Python, neither Haskell did exist. There were some LISP compilers, but I didn't learned about it, until later.
I ended doing a small compiler design related project in procedural pascal in purpouse. It could done it object and class oriented, and in C or C++, but I choose procedural pascal as an alternative to commonly used "Plain C" compiler design techniques.
Sometimes, a Compiler Design student is used to work with a programming language, but needs to learn another one, used in some compiler design sources.
Good Luck, Good Work.
Note, this applies to interpreters and virtual machines, as well.
2
u/Hot-Landscape9837 3d ago
Hey can I get some advice? I was interested in compiler engineering but with the way things are going, I am also scared of not finding a job. Some argue how it is a safer path in this age of AI while others argue that ofc compiler engineers are just not needed that much. I am from a third world country so I would have to try my luck at remote roles, not anything here
14
u/cxzuk 4d ago
Hi VMCrash,
The knowledge pool is deep, and you can easily rabbit hole on one topic. Sometimes you want the theory side of things, sometimes the practical side of things.
While I believe there are some essential topics to know, ultimately everything in a compiler is based on the requirements of the work it has to do.
So I think I would encourage a new dev to consider reading the "A Survey of" or "landscape" papers - ones which give a broad stroke understanding of the options available such as:
Gabriel Blindell 2016 "Instruction Selection" - https://www.cs.tufts.edu/~nr/cs257/archive/gabriel-hjort-blindell/monograph.pdf
Cooper & Torczon 2023 "Engineering A Compiler: Chapter 12 - Instruction Scheduling" (cant link)
Jonathan Protzenko 2009 "A Survey Of Register Allocation Techniques" https://jonathan.protzenko.fr/papers/register09.pdf
Stanier & Watson 2013 "Intermediate Representations in Imperative Compilers" https://dl.acm.org/doi/epdf/10.1145/2480741.2480743
Keith Cooper 1998 "Compiler-Based Code-Improvement Techniques" https://www.cs.tufts.edu/~nr/cs257/archive/keith-cooper/survey.pdf
You might not be able to make a compiler after, but I think they can help give a better understanding of what's going on inside them, and to see some of the beauty of the domain subject.
M ✌