Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

cs.cornell.edu

Post reply on HN
Print view View original

21–30 of 63 posts

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

#21

Post by j2kun »

jcranmer wrote: post #7
j2kun wrote: post #5

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.

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 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 comp…

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.

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

#22

Post by j2kun »

vkazanov wrote: post #16
j2kun wrote: post #5

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.

What is advanced then? Good coverage of dce, data flow, ssa, intruction selection and reg alloc is actually like 98% of the backend.

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

I guess garbage collection is pretty advanced in the syllabus.

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

#23

Post by achierius »

titzer wrote: post #20
jlebar wrote: post #14

Earlier quoted context omitted.

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

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 l…

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

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

#25

Post by runevault »

awesomeMilou wrote: post #24

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

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/

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

#26

Post by ebiederm »

jcranmer wrote: post #7
j2kun wrote: post #5

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.

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 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 comp…

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.

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

#27

Post by vkazanov »

j2kun wrote: post #22
vkazanov wrote: post #16

Earlier quoted context omitted.

What is advanced then? Good coverage of dce, data flow, ssa, intruction selection and reg alloc is actually like 98% of the backend.

Perhaps polyhedral optimization, tiling, scalar evolution, vectorization... I guess garbage collection is pretty advanced in the syllabus.

Well there is advanced and there is advanced.

This course is just a second course on compilers for people who had an introduction. And a great one at that.

A good modern, practical and decently optimizing compiler can do just fine without all the things you've mentioned, including vectorization.

Besides, most programming language implementations never go beyond the basic SSA toolkit.

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

#28

Post by saghm »

afdbcreid wrote: post #18
GL26 wrote: post #15

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

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?

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

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

#29

Post by awesomeMilou »

runevault wrote: post #25
awesomeMilou wrote: post #24

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

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/

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!

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

#30

Post by norir »

jcranmer wrote: post #7
j2kun wrote: post #5

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.

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 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 comp…

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.

Post reply on HN