<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:"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:"Malgun Gothic";
panose-1:2 11 5 3 2 0 0 2 0 4;}
@font-face
{font-family:Consolas;
panose-1:2 11 6 9 2 2 4 3 2 4;}
@font-face
{font-family:"\@Malgun Gothic";}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0cm;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
pre
{mso-style-priority:99;
mso-style-link:"HTML Preformatted Char";
margin:0cm;
font-size:10.0pt;
font-family:"Courier New";}
span.HTMLPreformattedChar
{mso-style-name:"HTML Preformatted Char";
mso-style-priority:99;
mso-style-link:"HTML Preformatted";
font-family:Consolas;}
span.EmailStyle22
{mso-style-type:personal-reply;
font-family:"Calibri",sans-serif;
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;}
@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="blue" vlink="purple" style="word-wrap:break-word">
<div class="WordSection1">
<p class="MsoNormal">Hi All,<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">How do you think about new pass manager allows each pass to choose the order of loops on new pass manager?<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">At this moment, some function passes are using `appendLoopsToWorklist` to iterate loops in forward program order. We could provide `appendLoopsToWorklistInReverse` or something like that to iterate loops in reverse program order with keeping
one way as default on new pass manager.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Thanks<o:p></o:p></p>
<p class="MsoNormal">JinGu Kang<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<p class="MsoNormal">From: <strong><span style="font-family:"Calibri",sans-serif">Philip Reames via llvm-dev</span></strong> <<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>><br>
Date: Fri, 16 Apr 2021, 23:26<br>
Subject: Re: [llvm-dev] Question about Traversing Loops in forward or reverse program order on new pass manager<br>
To: Krzysztof Parzyszek <<a href="mailto:kparzysz@quicinc.com">kparzysz@quicinc.com</a>>, Arthur Eubanks <<a href="mailto:aeubanks@google.com">aeubanks@google.com</a>>, Jingu Kang <<a href="mailto:Jingu.Kang@arm.com">Jingu.Kang@arm.com</a>><br>
Cc: llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>><o:p></o:p></p>
</div>
<p class="MsoNormal" style="margin-bottom:12.0pt"><o:p> </o:p></p>
<div>
<p>I meant locality in the memory access patterns. If you have a very large function (e.g. machine generated), you'll get much better memory locality by visiting one loop for all passes instead of for each pass visiting each loop. Think cache working sets.<o:p></o:p></p>
<p>However, the more I think about this, I'm now wondering if I was mixing the IPO case with the loop case. I know IPO matters in practice. I'm not sure the loop case does. I might be misremembering. Should be pretty easy to test if you're interested though.<o:p></o:p></p>
<p>Philip<o:p></o:p></p>
<div>
<p class="MsoNormal">On 4/16/21 2:58 PM, Krzysztof Parzyszek wrote:<o:p></o:p></p>
</div>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto">Do you remember what the locality was of that was the factor?<o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"> <o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto">Right now we’re running a loop pass on each loop, which isn’t very different from running a function pass on each loop in a function, so in that sense we keep the “same code different
data” format. Was it the loop structure that was only computed once-ish that made the difference?<o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"> <o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto">My concern is that there are multiple traversal dimensions, not only forward/backward, but also “innerward”/”outerward”, plus optimizing one loop may affect the next one. I think
that more “holistic” passes would provide better flexibility.<o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"> <o:p></o:p></p>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:9.0pt;font-family:Consolas">--
</span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:8.0pt;font-family:Consolas">Krzysztof Parzyszek
<a href="mailto:kparzysz@quicinc.com" target="_blank"><span style="color:#0563C1">kparzysz@quicinc.com</span></a> AI tools development</span><o:p></o:p></p>
</div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"> <o:p></o:p></p>
<div>
<div style="border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0cm 0cm 0cm">
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><b>From:</b> Philip Reames
<a href="mailto:listmail@philipreames.com" target="_blank"><listmail@philipreames.com></a>
<br>
<b>Sent:</b> Friday, April 16, 2021 3:52 PM<br>
<b>To:</b> Krzysztof Parzyszek <a href="mailto:kparzysz@quicinc.com" target="_blank">
<kparzysz@quicinc.com></a>; Arthur Eubanks <a href="mailto:aeubanks@google.com" target="_blank">
<aeubanks@google.com></a>; Jingu Kang <a href="mailto:Jingu.Kang@arm.com" target="_blank">
<Jingu.Kang@arm.com></a><br>
<b>Cc:</b> llvm-dev <a href="mailto:llvm-dev@lists.llvm.org" target="_blank"><llvm-dev@lists.llvm.org></a><br>
<b>Subject:</b> [EXT] Re: [llvm-dev] Question about Traversing Loops in forward or reverse program order on new pass manager<o:p></o:p></p>
</div>
</div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"> <o:p></o:p></p>
<p> <o:p></o:p></p>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto">On 4/15/21 10:27 AM, Krzysztof Parzyszek via llvm-dev wrote:<o:p></o:p></p>
</div>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto">I think the traversal order may depend on the optimization. I would actually propose to get rid of those fine-grained pass managers altogether. I think they are abstractions taken
too far, to the point of being counter-productive. Instead, loop passes should visit a function at a time, and use utility functions (like iterators of various kinds) to visit loops in the order they want.<o:p></o:p></p>
</blockquote>
<p>JFYI, there are very good compile time reasons to visit each loop with all passes. I don't remember the exact numbers, but I remember last time this was assessed that locality made a very measurable impact. Particularly for large machine generated codebases.
<o:p></o:p></p>
<p>If we do have loop transforms which prefer both, we could do two pass approach. We have something analogous to this for inferring attributes in IPO.
<o:p></o:p></p>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"> <o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto">On the actual issue here, I think we should stick to the old traversal order for the time being. This would reduce the potential for regressions and make it easier to fully transition
to the NPM for everyone.<o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"> <o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:9.0pt;font-family:Consolas">--
</span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:8.0pt;font-family:Consolas">Krzysztof Parzyszek
<a href="mailto:kparzysz@quicinc.com" target="_blank"><span style="color:#0563C1">kparzysz@quicinc.com</span></a> AI tools development</span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"> <o:p></o:p></p>
<div style="border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0cm 0cm 0cm">
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><b>From:</b> llvm-dev
<a href="mailto:llvm-dev-bounces@lists.llvm.org" target="_blank"><llvm-dev-bounces@lists.llvm.org></a>
<b>On Behalf Of </b>Arthur Eubanks via llvm-dev<br>
<b>Sent:</b> Thursday, April 15, 2021 11:59 AM<br>
<b>To:</b> Jingu Kang <a href="mailto:Jingu.Kang@arm.com" target="_blank"><Jingu.Kang@arm.com></a><br>
<b>Cc:</b> <a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
<b>Subject:</b> [EXT] Re: [llvm-dev] Question about Traversing Loops in forward or reverse program order on new pass manager<o:p></o:p></p>
</div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"> <o:p></o:p></p>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto">Ping on loop traversal order. Does anybody have any intuition about which way to traverse loops in a function?<o:p></o:p></p>
</div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"> <o:p></o:p></p>
<div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto">On Wed, Apr 7, 2021 at 12:36 PM Jingu Kang via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>> wrote:<o:p></o:p></p>
</div>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-top:5.0pt;margin-right:0cm;margin-bottom:5.0pt">
<div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto">Hi All,<o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"> <o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="color:black;background:white">I have seen performance regressions from new pass manager against legacy pass manager. One of the issues is the order of populating loops
on pass manager. The legacy pass manager is traversing loops in reverse program order but the new pass manager is traversing in forward program order. It sometimes causes different output. I have created a review
<a href="https://reviews.llvm.org/D99774" target="_blank">https://reviews.llvm.org/D99774</a> for reverse program order on new pass manager and had short discussion with Arthur on it. It is not easy to say the reverse order is better than the forward one or
vice versa. I would like to share this issue with more people on llvm-dev. If you have idea or experience about this issue, please share it.</span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="color:black;background:white"> </span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="color:black;background:white">Thanks</span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="color:black;background:white">JinGu Kang</span><o:p></o:p></p>
</div>
</div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto">_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" target="_blank">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><o:p></o:p></p>
</blockquote>
</div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;margin-bottom:12.0pt"><o:p> </o:p></p>
<pre>_______________________________________________<o:p></o:p></pre>
<pre>LLVM Developers mailing list<o:p></o:p></pre>
<pre><a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><o:p></o:p></pre>
<pre><a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" target="_blank">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><o:p></o:p></pre>
</blockquote>
</div>
</blockquote>
</div>
<p class="MsoNormal">_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" target="_blank">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><o:p></o:p></p>
</div>
</body>
</html>