<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:"Segoe UI Emoji";
panose-1:2 11 5 2 4 2 4 2 2 3;}
@font-face
{font-family:"Microsoft JhengHei";
panose-1:2 11 6 4 3 5 4 4 2 4;}
@font-face
{font-family:"\@Microsoft JhengHei";}
@font-face
{font-family:"\@MS Gothic";
panose-1:2 11 6 9 7 2 5 8 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:#0563C1;
text-decoration:underline;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
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">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.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">So far, I haven’t seen any mention of any loop algorithms, but I’m not sure who is best to include here.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">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.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">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.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<div style="border:none;border-left:solid blue 1.5pt;padding:0in 0in 0in 4.0pt">
<div>
<div style="border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0in 0in 0in">
<p class="MsoNormal"><b>From:</b> llvm-dev <llvm-dev-bounces@lists.llvm.org> <b>On Behalf Of
</b>Nuno Lopes via llvm-dev<br>
<b>Sent:</b> Wednesday, February 17, 2021 5:44<br>
<b>To:</b> 'Wei Wu (<span style="font-family:"MS Gothic"">吴</span><span style="font-family:"Microsoft JhengHei",sans-serif">伟</span>)' <lazyparser@gmail.com>; 'llvm-dev' <llvm-dev@lists.llvm.org><br>
<b>Subject:</b> Re: [llvm-dev] [Education] Call for suggestion: Which algorithms/passes you want a new LLVM developer to know<o:p></o:p></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<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 0in 0in 0in">
<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 <<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>><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>
</div>
</body>
</html>