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

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>

Thanks for the feedback! I really appreciate it, especially the `don't
show` part :-P

On Wed, Feb 17, 2021 at 6:44 PM Nuno Lopes <nunoplopes at sapo.pt> wrote:
> 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 (吴伟)
>

-- 
Best wishes,
Wei Wu (吴伟)
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20210217/0a0637a6/attachment.html>

Teaching dominators (and relatedly, the terminology related to natural loops) is
critical for compiler developers, but I don’t think the construction algorithms
themselves are particularly worth going through, except maybe as part of the
compile-time tradeoff Nuno mentions.

So far, I haven’t seen any mention of any loop algorithms, but I’m not sure who
is best to include here.

As concepts, covering scalar evolution, dependence analysis, and MemorySSA could
be useful, giving a students a sense of what the tools in the toolbox they have
are. Further, covering what InstCombine does at a high level (rather than
walking through all of its bajillion patterns) can be important.

Echoing Nuno, I worry that a focus on the algorithms may be too narrow for the
goal of bringing up new developers. You’ll especially want to cover the compile
time versus runtime performance tradeoff, and how passes are designed to try to
alleviate compile time performance (e.g., a very strong preference on
maintaining dominator tree/loop info because those are so commonly used that
recalculating them constantly would measurably increase compile time). Another
topic that would be useful is cost models: LLVM IR is not a perfect analogue for
machine hardware, and some transformations that seem beneficial in IR land may
be harmful in actual machine code. You could try collecting some examples where
an optimization helps on one architecture but hurts on another.

From: llvm-dev <llvm-dev-bounces at lists.llvm.org> On Behalf Of Nuno
Lopes via llvm-dev
Sent: Wednesday, February 17, 2021 5:44
To: 'Wei Wu (吴伟)' <lazyparser at gmail.com>; 'llvm-dev'
<llvm-dev at lists.llvm.org>
Subject: Re: [llvm-dev] [Education] Call for suggestion: Which algorithms/passes
you want a new LLVM developer to know

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<mailto: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/9245e536/attachment-0001.html>