[llvm-dev] [Education] Call for suggestion: Which algorithms/passes you want a new LLVM developer to know

[Nuno Lopes via llvm-dev]

GVN is super interesting, yes. Well worth the time.

 

I would add an SSA-construction algorithm (SROA in LLVM, but you can go with something simpler). Understanding SSA construction requires other concepts, such as dominators, and is an eye-opener for some of the tradeoffs being done in IR design (caching reaching-defs information).

 

I would also try a simple static analysis, like range analysis, so students understand the concepts of abstract interpretation, abstraction, widening, etc. You can introduce SSI here if you have time.

 

Alias analysis is important. But don’t show LLVM’s one 😅  I think gcc’s is probably a better example. This combined with some simple optimizations that it enables, like store forwarding.

 

Linear-scan register allocation is simple and I think it’s important to see the last mile. As well as a simple instructions election algorithm. The Burg family ones are not complicated.

 

In the end, more than learning many algorithms, I think the point is that they should realize how large programs are and how quick the compiler must be to handle those. So it’s all about doing the right tradeoffs of compilation speed vs benefit in performance/code-size/etc. Spend some time looking at the output of the compiler, both IR & assembly, and discuss in class what could be improved. It’s fascinating.

 

If your students learn all of this, please send them in for internships 😊

 

Nuno

 

 

From: Wei Wu

Sent: 17 February 2021 10:22
To: llvm-dev <llvm-dev at lists.llvm.org>
Subject: [llvm-dev] [Education] Call for suggestion: Which algorithms/passes you want a new LLVM developer to know

 

Hi,

 

I'm preparing a new compiler course which will start in April. The course uses LLVM as the reference compiler and RISC-V as the backend. The goal of the course is to bring up new compiler developers for LLVM and other toolchains. I propose to introduce ten or eleven algorithms that are commonly used in modern compiler systems, and walk-through the source code of these algorithms in LLVM codebase. Although I have several textbooks in my hand, I am not sure which algorithms are expected to be familiar for a new compiler developer. Currently tablegen, GlobalISel, GVN, DCE, and Inlining are in the plan, and there are still a few algorithms to be filled in.

 

I appreciate it if you can provide some suggestions. 

 


-- 

Best wishes,
Wei Wu (吴伟)

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20210217/634cd4d7/attachment.html>