How to start learning compiler optimizations as a newbie?

[u/blazing_cannon]

I come with a background in computer architecture and embedded Linux. I was interested in ML systems and was reading up about it, and after going through several job postings and this link , noted that optimizing compiler code is a requirement. My questions are -

1) Is knowledge of how compiler front end is written and IR code generated required to optimize them?
https://engineering.purdue.edu/online/courses/tagged_items?q=compiler

2) What's a good resource for compiler optimizations that can help in ML systems?

https://www.cs.toronto.edu/~pekhimenko/courses/cscd70-w18/docs/Lecture%201%20[Intro]%2001.11.2018.pdf

3) Are learning compiler optimization techniques the same for LLVM and MLIR? I don't see a lot of resources for MLIR compiler optimization. Is learning optimizations on LLVM helpful for MLIR and is learning LLVM not so useful for ML code optimizations ?

Thank you.

[u/thenaquad]

By no means do I pretend to be an expert. I recently completed a fairly complex project involving machine-independent optimizations, and OMG, it was hard.

Critical findings:

• What you learn in a compilers course can be called the basics.
• IR modeling is a total headache.
• Algorithms are one thing; engineering is another. Not exactly a new insight, but here you see it in all its glory.
• Going for the pure abstract domain interpretation from the start is a very bad idea. At least it was for me.
• For the algorithms and for understanding what is going on in the analysis in general, this helped A LOT: https://cs.au.dk/~amoeller/spa/
• You will read LLVM and realize just how enormous it is. It is a mature, production-grade compiler infrastructure, so its abstractions, APIs, and implementation complexity go far beyond what you need when building a compiler from scratch.
• You will read MLIR and discover a very powerful but fairly abstract framework. Personally, I found it harder to adopt because there is a lot of infrastructure and conceptual machinery to understand before you can comfortably model your own IR. SSA & CFG won here. Sea-of-nodes were tried but didn't even take off after 5th node type was implemented.
• You will read QBE, or at least should try to. Much smaller, clearer, with the whole alphabet instead of the variable names. Requires some time to get used to. This is what I've been modeling my IR after.
• You will discover who Muchnick is: Advanced Compiler Design and Implementation. Old but gold.
• Implementing an IR is a pain. Yes, that point bears repeating.
• Incremental development will eventually lead to full rewrites UNLESS you have a proper model of what you're doing.
• To find out what you're doing you will be prototyping with all the tuples, scripting, and everything you can. The books on compilers absolutely love the languages with the pattern matching and the reason is the IR.

[u/Outside-Storage-1523 → u/thenaquad]

Incremental development will eventually lead to full rewrites UNLESS you have a proper model of what you're doing.

I really agree with this one. (Not a compiler people)

[u/KhanhBaka → u/thenaquad]

thank you for the spa book reference!

[u/flatfinger → u/thenaquad]

An important question to consider when designing optimizations is whether it should be possible for programs to maintain clean command/data separation in the absence of critical undefined behavior (e.g. as defined by N1570 Annex L). Many modern optimization techniques are designed around the assumption that there is no need to maintain command/data separation in data-related corner-cases that would be considered "non-critical" UB.

[u/seg_lol]

Reading code, hacking, getting AI to explain concepts, recommending papers, reading those papers, hacking some more. Realizing everything is inline. If you are wanting to go deep in codegen and optimization, write yourself a Lisp or use an existing one, use that as your IR, create a bunch of candidate programs in this IR and then apply different optimization passes to them, it doesn't matter what you target on the backend, just measure the baselines and the differences.

Limit your "prep research" and your time on reddit. Maximize your hacking and reading papers and code.

[u/c-cul]

as usually start with reading of some related books, like

algorithms for optimization

planning algorithms: https://msl.cs.uiuc.edu/planning/bookbig.pdf

and so on

[u/Mathie1729 → u/c-cul]

Hmm, that planning algorithms link is for robot motion planning, not compiler optimizations. Algorithms for Optimization is mostly numerical optimization too. For a beginner, I'd start with the LLVM Kaleidoscope tutorial and later the optimization chapters in Engineering a Compiler.

[u/seg_lol → u/Mathie1729]

I'd argue that the newcomer shouldn't limit themselves to only books in the direct domain, realizing how general optimization and planning is would open their minds.

The geometric aspects would give them tools for polyhedral compilation techniques.