<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40"><head><meta http-equiv=Content-Type content="text/html; charset=utf-8"><meta name=Generator content="Microsoft Word 15 (filtered medium)"><style><!--
/* Font Definitions */
@font-face
{font-family:"MS Gothic";
panose-1:2 11 6 9 7 2 5 8 2 4;}
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:"Microsoft JhengHei";
panose-1:2 11 6 4 3 5 4 4 2 4;}
@font-face
{font-family:"\@MS Gothic";
panose-1:2 11 6 9 7 2 5 8 2 4;}
@font-face
{font-family:"\@Microsoft JhengHei";
panose-1:2 11 6 4 3 5 4 4 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0cm;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
.MsoChpDefault
{mso-style-type:export-only;
font-family:"Calibri",sans-serif;}
@page WordSection1
{size:612.0pt 792.0pt;
margin:72.0pt 72.0pt 72.0pt 72.0pt;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]--></head><body lang=EN-US link="#0563C1" vlink="#954F72" style='word-wrap:break-word'><div class=WordSection1><p class=MsoNormal>GVN is super interesting, yes. Well worth the time.<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>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).<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>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.<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>Alias analysis is important. But don<span style='font-family:"Times New Roman",serif'>’</span>t show LLVM<span style='font-family:"Times New Roman",serif'>’</span>s one <span style='font-family:"Segoe UI Emoji",sans-serif'>😅</span> I think gcc<span style='font-family:"Times New Roman",serif'>’</span>s is probably a better example. This combined with some simple optimizations that it enables, like store forwarding.<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>Linear-scan register allocation is simple and I think it<span style='font-family:"Times New Roman",serif'>’</span>s important to see the last mile. As well as a simple instructions election algorithm. The Burg family ones are not complicated.<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>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<span style='font-family:"Times New Roman",serif'>’</span>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<span style='font-family:"Times New Roman",serif'>’</span>s fascinating.<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>If your students learn all of this, please send them in for internships <span style='font-family:"Segoe UI Emoji",sans-serif'>😊</span><o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>Nuno<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><o:p> </o:p></p><div style='border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0cm 0cm 0cm'><p class=MsoNormal><b>From:</b> Wei Wu<o:p></o:p></p><p class=MsoNormal><b>Sent:</b> 17 February 2021 10:22<br><b>To:</b> llvm-dev <llvm-dev@lists.llvm.org><br><b>Subject:</b> [llvm-dev] [Education] Call for suggestion: Which algorithms/passes you want a new LLVM developer to know<o:p></o:p></p></div><p class=MsoNormal><o:p> </o:p></p><div><div><p class=MsoNormal>Hi,<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>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.<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>I appreciate it if you can provide some suggestions. <o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal><br>-- <o:p></o:p></p><div><p class=MsoNormal>Best wishes,<br>Wei Wu (<span style='font-family:"MS Gothic"'>吴</span><span style='font-family:"Microsoft JhengHei",sans-serif'>伟</span>)<o:p></o:p></p></div></div></div></div></body></html>