llvm dev - Feb 2021 - [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/fcbbdd1b/attachment-0001.html>

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>