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

Yeah, it is conceptually interesting. I like giving students perspective and in 770 (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.

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.

and PyPy right?

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.

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.

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.

I am actively opposed to this design for a first compiler. There is no need for a lexer with a recursive descent parser. Register allocation is also an unnecessary distraction. It is better for a first compiler to compile to a higher level language in which neither register assignment nor memory management are necessary.

Optimizing compilers are suboptimal in that they waste enormous amount of time optimizing code that can't or needn't be optimized and even where the optimizations are helpful, they are opaque and at risk of unexpectedly regressing both due to small changes at the source code level or changes in the compiler optimizer, both of which are quite insidious.

If instead of optimizing compilers, we had languages that allowed for seamless interop between low level and high level functions, then perhaps an llm becomes the optimizer (or you can invoke the compiler to optimize a specific function by source level rewrite). The benefit of this compared to a traditional optimizing compiler is that the optimization is done once per function and never repeated (until prompted) and the implementation is human readable and not buried in a binary. Moreover, and perhaps even more importantly, by not doing optimizations in the compiler, compilation times can be much faster, easily 100-1000x than state of the art optimizing compiler, while generating equivalent or even better runtime performance. As it has been said: premature optimization is the root of all evil.

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.)

Perhaps polyhedral optimization, tiling, scalar evolution, vectorization...

I guess garbage collection is pretty advanced in the syllabus.

The book is very much supposed to not be read passively.

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.

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!

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