<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
</head>
<body>
<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.</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.</p>
<p>Philip<br>
</p>
<div class="moz-cite-prefix">On 4/16/21 2:58 PM, Krzysztof Parzyszek
wrote:<br>
</div>
<blockquote type="cite"
cite="mid:DM5PR02MB26035C64B4FE17D2A7CA1DCBDD4C9@DM5PR02MB2603.namprd02.prod.outlook.com">
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<meta name="Generator" content="Microsoft Word 15 (filtered
medium)">
<style>@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:Consolas;
panose-1:2 11 6 9 2 2 4 3 2 4;}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:blue;
text-decoration:underline;}pre
{mso-style-priority:99;
mso-style-link:"HTML Preformatted Char";
margin:0in;
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;
font-size:10.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]-->
<div class="WordSection1">
<p class="MsoNormal">Do you remember what the locality was of
that was the factor?<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">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"><o:p> </o:p></p>
<p class="MsoNormal">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"><o:p> </o:p></p>
<div>
<p class="MsoNormal"><span
style="font-size:9.0pt;font-family:Consolas">-- </span>
<span style="font-size:9.0pt;font-family:Consolas"><o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:8.0pt;font-family:Consolas">Krzysztof
Parzyszek
<a href="mailto:kparzysz@quicinc.com"
moz-do-not-send="true"><span style="color:#0563C1">kparzysz@quicinc.com</span></a>
AI tools development<o:p></o:p></span></p>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<div style="border:none;border-top:solid #E1E1E1
1.0pt;padding:3.0pt 0in 0in 0in">
<p class="MsoNormal"><b>From:</b> Philip Reames
<a class="moz-txt-link-rfc2396E" href="mailto:listmail@philipreames.com"><listmail@philipreames.com></a> <br>
<b>Sent:</b> Friday, April 16, 2021 3:52 PM<br>
<b>To:</b> Krzysztof Parzyszek
<a class="moz-txt-link-rfc2396E" href="mailto:kparzysz@quicinc.com"><kparzysz@quicinc.com></a>; Arthur Eubanks
<a class="moz-txt-link-rfc2396E" href="mailto:aeubanks@google.com"><aeubanks@google.com></a>; Jingu Kang
<a class="moz-txt-link-rfc2396E" href="mailto:Jingu.Kang@arm.com"><Jingu.Kang@arm.com></a><br>
<b>Cc:</b> llvm-dev <a class="moz-txt-link-rfc2396E" href="mailto:llvm-dev@lists.llvm.org"><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"><o:p> </o:p></p>
<p><o:p> </o:p></p>
<div>
<p class="MsoNormal">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">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"> <o:p></o:p></p>
<p class="MsoNormal">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"> <o:p></o:p></p>
<p class="MsoNormal"><span
style="font-size:9.0pt;font-family:Consolas">-- </span>
<o:p></o:p></p>
<p class="MsoNormal"><span
style="font-size:8.0pt;font-family:Consolas">Krzysztof
Parzyszek
<a href="mailto:kparzysz@quicinc.com"
moz-do-not-send="true"><span style="color:#0563C1">kparzysz@quicinc.com</span></a>
AI tools development</span><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> llvm-dev <a
href="mailto:llvm-dev-bounces@lists.llvm.org"
moz-do-not-send="true">
<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"
moz-do-not-send="true"><Jingu.Kang@arm.com></a><br>
<b>Cc:</b> <a href="mailto:llvm-dev@lists.llvm.org"
moz-do-not-send="true">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"> <o:p></o:p></p>
<div>
<p class="MsoNormal">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"> <o:p></o:p></p>
<div>
<div>
<p class="MsoNormal">On Wed, Apr 7, 2021 at 12:36 PM Jingu
Kang via llvm-dev <<a
href="mailto:llvm-dev@lists.llvm.org"
moz-do-not-send="true">llvm-dev@lists.llvm.org</a>>
wrote:<o:p></o:p></p>
</div>
<blockquote style="border:none;border-left:solid #CCCCCC
1.0pt;padding:0in 0in 0in
6.0pt;margin-left:4.8pt;margin-top:5.0pt;margin-right:0in;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" moz-do-not-send="true">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">_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank"
moz-do-not-send="true">llvm-dev@lists.llvm.org</a><br>
<a
href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev"
target="_blank" moz-do-not-send="true">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><o:p></o:p></p>
</blockquote>
</div>
<p class="MsoNormal"><br>
<br>
<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" moz-do-not-send="true">llvm-dev@lists.llvm.org</a><o:p></o:p></pre>
<pre><a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" moz-do-not-send="true">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><o:p></o:p></pre>
</blockquote>
</div>
</blockquote>
</body>
</html>