6 ms·

CS 6120: Advanced Compilers: The Self-Guided Online Course (2020)

454 points by ibobev 4mo ago

titzer 4mo ago
The section on dynamic compilers is more or less all about trace compilation. Generally, trace compilation is a dead end and has been abandoned repeatedly. The more important concepts here are type feedback and speculation and deoptimization, as well as making fast compilers and tiering. The course overall looks good, and it's great that so much is available online, so well done, Adrian.
- giancarlostoro 4mo ago
  Got any other recommended resources on building compilers?
- samps 4mo ago
  Thanks, Ben. I admit I mostly think tracing is just a mind-expanding concept to learn about, even if history has proven it’s not very practical as an organizing principle. But as you say, I’d love to offer more context on “what actually seems to work” industrially.
  - titzer 4mo ago
    Yeah, it is conceptually interesting. I like giving students perspective and in 770 (https://www.cs.cmu.edu/~wasm/cs17-770/fall2025/ https://www.cs.cmu.edu/~wasm/cs17-770/fall2025/) I might spend half or less of a lecture on tracing and I don't pull punches on how I think it ends up not really working well in real systems. It's a good opportunity to talk about program behavior and the cost/benefit of speculation. We spend a lot more time on type feedback, ICs, and deoptimization which are the more universal concepts that can be applied to multiple different compiler designs.
    - vsmenon 4mo ago
      To be fair, the listed Self paper did age quite well!
- jcranmer 4mo ago
  The TraceMonkey paper was on my qual reading list, and my quals happened to be around the time TraceMonkey was ripped out of SpiderMonkey. I was talking with one of the developers at the time (I think it was Jason Orendorff?), who said that tracing just doesn't work out, but there was limited circumstances where he thought it might work out... but I've completely forgotten what those circumstances were.
- abecedarius 4mo ago
  Has LuaJIT been superseded?
- jlebar 4mo ago
  > Generally, trace compilation is a dead end and has been abandoned repeatedly. JAX is a tracing compiler! (I know, I know, it sits in an extremely different part of the problem space than TraceMonkey or LuaJIT. Still.)
  - zipy124 4mo ago
    and PyPy right?
  - titzer 4mo ago
    Interesting. I think numerical computing is a narrow enough domain where programs have very well-behaved control flow, which avoids most of the problems of trace compilation. Loops over branchy code, which are really common in general programs, are very difficult to make work well with tracing. Numerical programs being very stable in terms of control is what enables GPU parallelization and loop optimizations in the long tradition of Fortran compilers. Optimizations like loop tiling, interchange, strip mining, etc aren't going to be easy to do with trace compilation. Anyway my comment was more directed toward trace compilation in the context of dynamic languages, and there I think it's pretty well established it only works well for small programs.
    - achierius 4mo ago
      ML compilers in particular go beyond even the level of stability you would expect from numerical programs. Due to how the SIMT model of thread/warp divergence works, the hardware heavily punishes unstable branches. E.g. if you have 32 threads taking a branch then recoalescing on a barrier -- if they all go the same direction then they can go down the execution pipe as a single bundle, but if 1 takes it while 31 don't, then that's 2x the ex-pipe usage by default (and if you have e.g. a computed-branch, performance goes out the window). Consequently, the whole stack is built around the expectation of stable control flow, even to the detriment of performance (from a local perspective). ML frameworks even take advantage of this to compute, ahead-of-time, how much memory will be used at different points in the program graph, and thereafter schedule memcpy's to make space as necessary. Of course this only works for well-behaved program classes, but e.g. most LLM architectures fit into that category. Interestingly MoE models don't, since they require data-dependent control flow, thus the recent push towards accommodating dynamism in frameworks (like JAX, which until ~recently couldn't handle it at all).
- yu3zhou4 4mo ago
  PyTorch?
- mlazos 4mo ago
  I work on PyTorch torch.compile and it’s a tracing compiler as well. Perhaps this domain is very narrow though; it is also a very not conventional compiler, you’d probably be deeply offended by some of the stuff we do! ;)
- mikemike 4mo ago
  Trace compilation is NOT a dead end. LuaJIT works just fine. On big programs. On hundreds of millions of servers and devices. I find it deeply saddening that even scholars keep repeating this trope. Ignorance is bliss.
  - titzer 4mo ago
    Hi Mike, I think your work on luajit is really cool. I worked on JavaScript for some time and among all of the JS engines out there, a lot of ideas were tried. TraceMonkey in particular did explore trace compilation for JavaScript and benefited from a lot of fundamental research into trace compilation from Michael Franz's group and others. I've talked to many of those people. It just didn't work out for JS as there are too many diverse programs out there that aren't well-behaved. It's not enough to get great performance on some programs (and hopefully good performance on average programs) if there are pathological cases that ruin user experience. The internet is the greatest VM fuzzer yet invented and produces some stunningly awful things that present constant challenges to speculative dynamic optimization. It's well accepted in the JS space that method JITs have more stable, understandable performance, though they too can get into trouble. Best of luck.
    - panick21_ 4mo ago
      Didn't you guys have this discussion like 10 years ago in Lambda the Ultimate comments?
    - mikemike 4mo ago
      I'm not sure one can infer anything from a single failed Mozilla project. 'Real-world' JavaScript is a challenge for any compiler, no matter the underlying technology. The technical debt in SpiderMonkey (at that time, anyway) was eye-watering. Grafting anything on top of that was hard. They haven't even gotten to the point of implementing the crucial pieces of a trace compiler before the project folded. Trace compilers make nice textbook exercises. Getting them into production is a different matter: region selection, side-exit handling, trace graph evolution, deep VM integration, code generation adapted to all of this … far from trivial, but doable. Neither is it trivial to create a production-quality method-at-a-time JIT compiler and VM for a dynamic language. Ceterum censeo: The fundamental papers on trace compilation are from Fisher (1981) and the teams around Multiflow (1990) and Dynamo (1999). Franz, Gal, et al can be credited for later re-popularizing the idea, but they haven't added anything of note.
- revengerwizard 4mo ago
  Tracing JIT compilers are very interesting, and there definitely needs to be more resources on such complex topic.
j2kun 4mo ago
I'm a bit confused about what makes this course "advanced." Most of the topics (dead code elimination, data flow, dominator analysis, SSA form) seem like they belong in a first course on compilers.
- ferguess_k 4mo ago
  I think a lot of the non-professionals start with parsing and do not get exposed to backend. I have read two books about interpreters/compilers and they don't touch the backend very much. Maybe this is introductory for backend?
  - DonaldPShimoda 4mo ago
    That's part of it. I think another part is that it seems like the students are asked to read the papers behind a lot of the concepts, and academic literature is not generally very accessible to undergrads. (Not that they can't read it, but without someone guiding you through at least the first few papers, it can be a frustrating experience for many.)
- jcranmer 4mo ago
  Well, course numbers are regular enough that you can look up what the "intro compilers" course is: https://www.cs.cornell.edu/courses/cs4120/2026sp/?schedule https://www.cs.cornell.edu/courses/cs4120/2026sp/?schedule The short answer is that compilers is basically broken up into two courses, with the first course largely being the minimum necessary to build a compiler (lexing, parsing, codegen, register allocation), and the second course being how to build an optimizing compiler.
  - j2kun 4mo ago
    Looks like there is quite a bit of overlap with regards to the optimizing parts between these two courses. I guess it's switching from the dragon book to academic papers that makes it advanced.
  - ebiederm 4mo ago
    The academic literature on register allocation is scary. First is presented a linear time optimal algorithm for graph coloring then it is claimed better can be done by a O(N^2) algorithm that uses a heuristic. I do believe the dragon book got caught with the emperor's new register allocator and the literature hasn't really recovered yet.
gaze 4mo ago
I'm super curious what alexia massalin is up to these days, besides collecting microunity patent royalties
GL26 4mo ago
Saw a podcast that talked about the rust compiler, which apparently included machine learning algorithms at some points to determine whether or not you had code that could crash your system
- afdbcreid 4mo ago
  I've never heard about that and I'm pretty sure it's incorrect (although "machine learning" is a wide term), do you have a source for that?
  - saghm 4mo ago
    I've also never heard this before. The closest I can think of is fuzzing test suites used to find panics in various crates, but that's neither machine learning nor in the compiler itself. I know that datalog is used for the borrow checking logic, so I could also maybe imagine someone describing something like that in some hand wavy way like "proof by machine to detect up front whether the program is safe or might crash" and that getting misinterpreted, but that seems like a stretch
    - afdbcreid 4mo ago
      Datalog is not used for borrow checking. It was used in old versions of the experimental next-gen borrow checker, Polonius. Current versions of Polonius (which is still experimental) are coded in Rust.
      - saghm 4mo ago
        Oh interesting, I'm not sure why I misunderstood that. Thanks for the correction!
awesomeMilou 4mo ago
Is there also a self guided course for "basic compilers", before stepping into an advanced level?
- runevault 4mo ago
  I'd say check out Crafting Interpreters [1]. It has 2 parts, the first in Java for doing a treewalk Interpreter in Java before going farther with a version written in C. 1. https://craftinginterpreters.com/ https://craftinginterpreters.com/
  - awesomeMilou 4mo ago
    Hmm I would have hoped for something more formal and that's focused on compiled runtimes, instead of dynamic runtimes Still, I appreciate you replying, I'm sure you meant to be helpful!
  - WJW 4mo ago
    Not GP, but after doing Crafting Interpreters I was kinda left with a gap in my knowledge regarding the conversion of an AST into native code. Also kinda missing was optimization passes over an AST. I somewhat understand the idea, but it would definitely be nice to have a more guided book/article for this. Crafting Interpreters is definitely a recommended read, but it stops at Interpreters (fair enough, the book is thick enough). Crafting Compilers would need at least 4-5 extra chapters IMO.
    - t-3 4mo ago
      Most of the work involved in emitting code deals with somewhat arbitrary hardware details. Pretty much the only way is to get familiar with your target hardware features, instructions, and platform ABIs. ISA manuals all have sections describing these, they're pretty much always very dry and "linguistically rigorous" so it's not easy to read but everything you need is there. Actually emitting instructions is pretty boring and mechanical outside of some considerations and subtleties with hardware-specific optimization, OS calling conventions, register selection, etc.
- 4mo ago
xqb64 4mo ago
How does this compare to Nora Sandler's "Writing a C compiler" in terms of the potential gains for the reader?
- Jtsummers 4mo ago
  Her book sits closer to what you'd get from an undergraduate level compilers course, this course covers more advanced material than she does. If you're a novice or a dabbler, start with her book or something else at that level, then try out this course and fill in the gaps as needed.
- ozgrakkurt 4mo ago
  I found that book to be basically useless as a passive reader. She basically writes "do this" and you are supposed to do it. This course is much more valuable because it actually gives a lot of information. It really feels like most text books on compilers have massive "black hole" sections that pull you in on the technicals that you are not even supposed to use in the end. I found that his course and the LLVM book by Quentin Colombet really useful because they both give easy to understand information that seems to be actually used in real large systems like LLVM/gcc etc. There are also book like SSA-based compiler design that seem to be great but I am not able to read because of lacking prior knowledge. Also thank you to Adrian if he is reading this, he is an amazing teacher and releasing this content is much appreciated
  - xqb64 4mo ago
    The book is very much supposed to not be read passively.
tomhow 4mo ago
Previously... CS 6120: Advanced Compilers: The Self-Guided Online Course - https://news.ycombinator.com/item?id=39577878 https://news.ycombinator.com/item?id=39577878 - March 2024 (102 comments) Advanced Compilers: Self-Guided Online Course - https://news.ycombinator.com/item?id=35130975 https://news.ycombinator.com/item?id=35130975 - March 2023 (82 comments) Advanced Compilers: Self-Guided Online Course - https://news.ycombinator.com/item?id=25386756 https://news.ycombinator.com/item?id=25386756 - Dec 2020 (232 comments)
ken47 4mo ago
Thanks for creating and sharing this.
flash1 4mo ago
Great material! Thank you.
sincerely 4mo ago
Are there any other self-guided online university level CS courses like this?
- howLongHowLong 4mo ago
  There are dozens. Search "mooc". Also some professors will release their lectures and homework outside of a "mooc" framework. I've even had professors respond to questions in the comments. The Internet can still be pretty cool.
ReyX 4mo ago
[dead]

454 points by ibobev 4mo ago

The section on dynamic compilers is more or less all about trace compilation. Generally, trace compilation is a dead end and has been abandoned repeatedly. The more important concepts here are type feedback and speculation and deoptimization, as well as making fast compilers and tiering. The course overall looks good, and it's great that so much is available online, so well done, Adrian.

giancarlostoro 4mo ago
Got any other recommended resources on building compilers?
samps 4mo ago
Thanks, Ben. I admit I mostly think tracing is just a mind-expanding concept to learn about, even if history has proven it’s not very practical as an organizing principle. But as you say, I’d love to offer more context on “what actually seems to work” industrially.
- titzer 4mo ago
  Yeah, it is conceptually interesting. I like giving students perspective and in 770 (https://www.cs.cmu.edu/~wasm/cs17-770/fall2025/ https://www.cs.cmu.edu/~wasm/cs17-770/fall2025/) I might spend half or less of a lecture on tracing and I don't pull punches on how I think it ends up not really working well in real systems. It's a good opportunity to talk about program behavior and the cost/benefit of speculation. We spend a lot more time on type feedback, ICs, and deoptimization which are the more universal concepts that can be applied to multiple different compiler designs.
  - vsmenon 4mo ago
    To be fair, the listed Self paper did age quite well!
jcranmer 4mo ago
The TraceMonkey paper was on my qual reading list, and my quals happened to be around the time TraceMonkey was ripped out of SpiderMonkey. I was talking with one of the developers at the time (I think it was Jason Orendorff?), who said that tracing just doesn't work out, but there was limited circumstances where he thought it might work out... but I've completely forgotten what those circumstances were.
abecedarius 4mo ago
Has LuaJIT been superseded?
jlebar 4mo ago
> Generally, trace compilation is a dead end and has been abandoned repeatedly. JAX is a tracing compiler! (I know, I know, it sits in an extremely different part of the problem space than TraceMonkey or LuaJIT. Still.)
- zipy124 4mo ago
  and PyPy right?
- titzer 4mo ago
  Interesting. I think numerical computing is a narrow enough domain where programs have very well-behaved control flow, which avoids most of the problems of trace compilation. Loops over branchy code, which are really common in general programs, are very difficult to make work well with tracing. Numerical programs being very stable in terms of control is what enables GPU parallelization and loop optimizations in the long tradition of Fortran compilers. Optimizations like loop tiling, interchange, strip mining, etc aren't going to be easy to do with trace compilation. Anyway my comment was more directed toward trace compilation in the context of dynamic languages, and there I think it's pretty well established it only works well for small programs.
  - achierius 4mo ago
    ML compilers in particular go beyond even the level of stability you would expect from numerical programs. Due to how the SIMT model of thread/warp divergence works, the hardware heavily punishes unstable branches. E.g. if you have 32 threads taking a branch then recoalescing on a barrier -- if they all go the same direction then they can go down the execution pipe as a single bundle, but if 1 takes it while 31 don't, then that's 2x the ex-pipe usage by default (and if you have e.g. a computed-branch, performance goes out the window). Consequently, the whole stack is built around the expectation of stable control flow, even to the detriment of performance (from a local perspective). ML frameworks even take advantage of this to compute, ahead-of-time, how much memory will be used at different points in the program graph, and thereafter schedule memcpy's to make space as necessary. Of course this only works for well-behaved program classes, but e.g. most LLM architectures fit into that category. Interestingly MoE models don't, since they require data-dependent control flow, thus the recent push towards accommodating dynamism in frameworks (like JAX, which until ~recently couldn't handle it at all).
yu3zhou4 4mo ago
PyTorch?
mlazos 4mo ago
I work on PyTorch torch.compile and it’s a tracing compiler as well. Perhaps this domain is very narrow though; it is also a very not conventional compiler, you’d probably be deeply offended by some of the stuff we do! ;)
mikemike 4mo ago
Trace compilation is NOT a dead end. LuaJIT works just fine. On big programs. On hundreds of millions of servers and devices. I find it deeply saddening that even scholars keep repeating this trope. Ignorance is bliss.
- titzer 4mo ago
  Hi Mike, I think your work on luajit is really cool. I worked on JavaScript for some time and among all of the JS engines out there, a lot of ideas were tried. TraceMonkey in particular did explore trace compilation for JavaScript and benefited from a lot of fundamental research into trace compilation from Michael Franz's group and others. I've talked to many of those people. It just didn't work out for JS as there are too many diverse programs out there that aren't well-behaved. It's not enough to get great performance on some programs (and hopefully good performance on average programs) if there are pathological cases that ruin user experience. The internet is the greatest VM fuzzer yet invented and produces some stunningly awful things that present constant challenges to speculative dynamic optimization. It's well accepted in the JS space that method JITs have more stable, understandable performance, though they too can get into trouble. Best of luck.
  - panick21_ 4mo ago
    Didn't you guys have this discussion like 10 years ago in Lambda the Ultimate comments?
  - mikemike 4mo ago
    I'm not sure one can infer anything from a single failed Mozilla project. 'Real-world' JavaScript is a challenge for any compiler, no matter the underlying technology. The technical debt in SpiderMonkey (at that time, anyway) was eye-watering. Grafting anything on top of that was hard. They haven't even gotten to the point of implementing the crucial pieces of a trace compiler before the project folded. Trace compilers make nice textbook exercises. Getting them into production is a different matter: region selection, side-exit handling, trace graph evolution, deep VM integration, code generation adapted to all of this … far from trivial, but doable. Neither is it trivial to create a production-quality method-at-a-time JIT compiler and VM for a dynamic language. Ceterum censeo: The fundamental papers on trace compilation are from Fisher (1981) and the teams around Multiflow (1990) and Dynamo (1999). Franz, Gal, et al can be credited for later re-popularizing the idea, but they haven't added anything of note.
revengerwizard 4mo ago
Tracing JIT compilers are very interesting, and there definitely needs to be more resources on such complex topic.

j2kun 4mo ago

I'm a bit confused about what makes this course "advanced." Most of the topics (dead code elimination, data flow, dominator analysis, SSA form) seem like they belong in a first course on compilers.

ferguess_k 4mo ago
I think a lot of the non-professionals start with parsing and do not get exposed to backend. I have read two books about interpreters/compilers and they don't touch the backend very much. Maybe this is introductory for backend?
- DonaldPShimoda 4mo ago
  That's part of it. I think another part is that it seems like the students are asked to read the papers behind a lot of the concepts, and academic literature is not generally very accessible to undergrads. (Not that they can't read it, but without someone guiding you through at least the first few papers, it can be a frustrating experience for many.)
jcranmer 4mo ago
Well, course numbers are regular enough that you can look up what the "intro compilers" course is: https://www.cs.cornell.edu/courses/cs4120/2026sp/?schedule https://www.cs.cornell.edu/courses/cs4120/2026sp/?schedule The short answer is that compilers is basically broken up into two courses, with the first course largely being the minimum necessary to build a compiler (lexing, parsing, codegen, register allocation), and the second course being how to build an optimizing compiler.
- j2kun 4mo ago
  Looks like there is quite a bit of overlap with regards to the optimizing parts between these two courses. I guess it's switching from the dragon book to academic papers that makes it advanced.
- ebiederm 4mo ago
  The academic literature on register allocation is scary. First is presented a linear time optimal algorithm for graph coloring then it is claimed better can be done by a O(N^2) algorithm that uses a heuristic. I do believe the dragon book got caught with the emperor's new register allocator and the literature hasn't really recovered yet.

gaze 4mo ago

I'm super curious what alexia massalin is up to these days, besides collecting microunity patent royalties

GL26 4mo ago

Saw a podcast that talked about the rust compiler, which apparently included machine learning algorithms at some points to determine whether or not you had code that could crash your system

afdbcreid 4mo ago
I've never heard about that and I'm pretty sure it's incorrect (although "machine learning" is a wide term), do you have a source for that?
- saghm 4mo ago
  I've also never heard this before. The closest I can think of is fuzzing test suites used to find panics in various crates, but that's neither machine learning nor in the compiler itself. I know that datalog is used for the borrow checking logic, so I could also maybe imagine someone describing something like that in some hand wavy way like "proof by machine to detect up front whether the program is safe or might crash" and that getting misinterpreted, but that seems like a stretch
  - afdbcreid 4mo ago
    Datalog is not used for borrow checking. It was used in old versions of the experimental next-gen borrow checker, Polonius. Current versions of Polonius (which is still experimental) are coded in Rust.
    - saghm 4mo ago
      Oh interesting, I'm not sure why I misunderstood that. Thanks for the correction!

awesomeMilou 4mo ago

Is there also a self guided course for "basic compilers", before stepping into an advanced level?

runevault 4mo ago
I'd say check out Crafting Interpreters [1]. It has 2 parts, the first in Java for doing a treewalk Interpreter in Java before going farther with a version written in C. 1. https://craftinginterpreters.com/ https://craftinginterpreters.com/
- awesomeMilou 4mo ago
  Hmm I would have hoped for something more formal and that's focused on compiled runtimes, instead of dynamic runtimes Still, I appreciate you replying, I'm sure you meant to be helpful!
- WJW 4mo ago
  Not GP, but after doing Crafting Interpreters I was kinda left with a gap in my knowledge regarding the conversion of an AST into native code. Also kinda missing was optimization passes over an AST. I somewhat understand the idea, but it would definitely be nice to have a more guided book/article for this. Crafting Interpreters is definitely a recommended read, but it stops at Interpreters (fair enough, the book is thick enough). Crafting Compilers would need at least 4-5 extra chapters IMO.
  - t-3 4mo ago
    Most of the work involved in emitting code deals with somewhat arbitrary hardware details. Pretty much the only way is to get familiar with your target hardware features, instructions, and platform ABIs. ISA manuals all have sections describing these, they're pretty much always very dry and "linguistically rigorous" so it's not easy to read but everything you need is there. Actually emitting instructions is pretty boring and mechanical outside of some considerations and subtleties with hardware-specific optimization, OS calling conventions, register selection, etc.
4mo ago

xqb64 4mo ago

How does this compare to Nora Sandler's "Writing a C compiler" in terms of the potential gains for the reader?

Jtsummers 4mo ago
Her book sits closer to what you'd get from an undergraduate level compilers course, this course covers more advanced material than she does. If you're a novice or a dabbler, start with her book or something else at that level, then try out this course and fill in the gaps as needed.
ozgrakkurt 4mo ago
I found that book to be basically useless as a passive reader. She basically writes "do this" and you are supposed to do it. This course is much more valuable because it actually gives a lot of information. It really feels like most text books on compilers have massive "black hole" sections that pull you in on the technicals that you are not even supposed to use in the end. I found that his course and the LLVM book by Quentin Colombet really useful because they both give easy to understand information that seems to be actually used in real large systems like LLVM/gcc etc. There are also book like SSA-based compiler design that seem to be great but I am not able to read because of lacking prior knowledge. Also thank you to Adrian if he is reading this, he is an amazing teacher and releasing this content is much appreciated
- xqb64 4mo ago
  The book is very much supposed to not be read passively.

tomhow 4mo ago

Previously... CS 6120: Advanced Compilers: The Self-Guided Online Course - https://news.ycombinator.com/item?id=39577878 https://news.ycombinator.com/item?id=39577878 - March 2024 (102 comments) Advanced Compilers: Self-Guided Online Course - https://news.ycombinator.com/item?id=35130975 https://news.ycombinator.com/item?id=35130975 - March 2023 (82 comments) Advanced Compilers: Self-Guided Online Course - https://news.ycombinator.com/item?id=25386756 https://news.ycombinator.com/item?id=25386756 - Dec 2020 (232 comments)

ken47 4mo ago

Thanks for creating and sharing this.

flash1 4mo ago

Great material! Thank you.

sincerely 4mo ago

Are there any other self-guided online university level CS courses like this?

howLongHowLong 4mo ago
There are dozens. Search "mooc". Also some professors will release their lectures and homework outside of a "mooc" framework. I've even had professors respond to questions in the comments. The Internet can still be pretty cool.

ReyX 4mo ago

[dead]