<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:Consolas;
panose-1:2 11 6 9 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0cm;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri",sans-serif;
color:black;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
pre
{mso-style-priority:99;
mso-style-link:"HTML Preformatted Char";
margin:0cm;
margin-bottom:.0001pt;
font-size:10.0pt;
font-family:"Courier New";
color:black;}
p.Code, li.Code, div.Code
{mso-style-name:Code;
margin-top:0cm;
margin-right:0cm;
margin-bottom:0cm;
margin-left:36.0pt;
margin-bottom:.0001pt;
font-size:9.0pt;
font-family:"Courier New";
color:black;}
p.msonormal0, li.msonormal0, div.msonormal0
{mso-style-name:msonormal;
mso-margin-top-alt:auto;
margin-right:0cm;
mso-margin-bottom-alt:auto;
margin-left:0cm;
font-size:11.0pt;
font-family:"Calibri",sans-serif;
color:black;}
span.HTMLPreformattedChar
{mso-style-name:"HTML Preformatted Char";
mso-style-priority:99;
mso-style-link:"HTML Preformatted";
font-family:Consolas;
color:black;}
span.EmailStyle21
{mso-style-type:personal-reply;
font-family:"Calibri",sans-serif;
color:windowtext;
font-weight:normal;
font-style:normal;
text-decoration:none none;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;}
@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 bgcolor="white" lang="EN-GB" link="blue" vlink="purple">
<div class="WordSection1">
<p class="MsoNormal"><span style="font-size:12.0pt;color:windowtext">There is good info in this thread … do add it to the ticket #15124<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt;color:windowtext"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt;color:windowtext">Simon<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt;color:windowtext"><o:p> </o:p></span></p>
<div style="border:none;border-left:solid blue 1.5pt;padding:0cm 0cm 0cm 4.0pt">
<div>
<div style="border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0cm 0cm 0cm">
<p class="MsoNormal"><b><span lang="EN-US" style="color:windowtext">From:</span></b><span lang="EN-US" style="color:windowtext"> ghc-devs <ghc-devs-bounces@haskell.org>
<b>On Behalf Of </b>Andreas Klebinger<br>
<b>Sent:</b> 06 May 2018 20:59<br>
<b>To:</b> Kavon Farvardin <kavon@farvard.in><br>
<b>Cc:</b> ghc-devs@haskell.org<br>
<b>Subject:</b> Re: Basic Block Layout in the NCG<o:p></o:p></span></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<pre>On branch probability:<o:p></o:p></pre>
<p class="MsoNormal">I've actually created a patch to add more probabilities in the recent past which included<br>
probabilities on CmmSwitches. Although it made little difference when only tagging error<br>
branches.<br>
<br>
Partially that also run into issues with code layout which is why I put that on ice for now.<br>
<br>
The full patch is here:<br>
<a href="https://phabricator.haskell.org/D4327">https://phabricator.haskell.org/D4327</a><br>
<br>
I think this really has to be done back to front as GHC currently throws<br>
away all likelyhood information before we get to block layout.<br>
Which makes it very hard to take advantage of this information.<br>
<br>
Code Layout:<br>
<br>
That seems exactly like the kind of pointers I was looking for! <br>
I do wonder how well some of them aged. For example [5] and [6] use at most two way associative cache.
<br>
But as you said it should be at least a good starting point.<br>
<br>
I will put your links into the ticket so they are easily found once I (or someone else!) has time to look<br>
deeper into this.<br>
<br>
Cheers<br>
Andreas<br>
<br>
<br>
<br>
<o:p></o:p></p>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div style="margin-left:18.75pt;margin-top:22.5pt;margin-right:18.75pt;margin-bottom:7.5pt">
<div style="border:none;border-top:solid #EDEEF0 1.0pt;padding:4.0pt 0cm 0cm 0cm">
<div>
<p class="MsoNormal" style="vertical-align:middle"><a href="mailto:kavon@farvard.in"><b>Kavon Farvardin</b></a><o:p></o:p></p>
</div>
<p class="MsoNormal" align="right" style="text-align:right;vertical-align:middle">
<span style="color:#9FA2A5">Sonntag, 6. Mai 2018 20:17</span><o:p></o:p></p>
</div>
</div>
<div style="margin-left:18.0pt;margin-right:18.0pt">
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<pre><span style="color:#888888">Does anyone have good hints for literature on basic block layout<o:p></o:p></span></pre>
<pre><span style="color:#888888">algorithms?<o:p></o:p></span></pre>
</blockquote>
<pre><span style="color:#888888"><o:p> </o:p></span></pre>
<pre><span style="color:#888888">Here are some thoughts:<o:p></o:p></span></pre>
<pre><span style="color:#888888"><o:p> </o:p></span></pre>
<pre><span style="color:#888888">* Branch Probability *<o:p></o:p></span></pre>
<pre><span style="color:#888888"><o:p> </o:p></span></pre>
<pre><span style="color:#888888">Any good code layout algorithm should take branch probabilities into<o:p></o:p></span></pre>
<pre><span style="color:#888888">account. From what I've seen, we already have a few likely-branch<o:p></o:p></span></pre>
<pre><span style="color:#888888">heuristics baked into the generation/transformation of Cmm, though<o:p></o:p></span></pre>
<pre><span style="color:#888888">perhaps it's worth doing more to add probabilities as in [1,3]. The<o:p></o:p></span></pre>
<pre><span style="color:#888888">richer type information in STG could come in handy.<o:p></o:p></span></pre>
<pre><span style="color:#888888"><o:p> </o:p></span></pre>
<pre><span style="color:#888888">I think the first step in leveraging branch proability information is<o:p></o:p></span></pre>
<pre><span style="color:#888888">to use a Float to represent the magnitude of likeliness instead of a<o:p></o:p></span></pre>
<pre><span style="color:#888888">Bool.<o:p></o:p></span></pre>
<pre><span style="color:#888888"><o:p> </o:p></span></pre>
<pre><span style="color:#888888">Target probabilities on CmmSwitches could also help create smarter<o:p></o:p></span></pre>
<pre><span style="color:#888888">SwitchPlans. Slides 20-21 in [2] demonstrate a lower-cost decision tree<o:p></o:p></span></pre>
<pre><span style="color:#888888">based on these probabilities.<o:p></o:p></span></pre>
<pre><span style="color:#888888"><o:p> </o:p></span></pre>
<pre><span style="color:#888888"><o:p> </o:p></span></pre>
<pre><span style="color:#888888">* Code Layout *<o:p></o:p></span></pre>
<pre><span style="color:#888888"><o:p> </o:p></span></pre>
<pre><span style="color:#888888">The best all-in-one source for static code positioning I've seen is in<o:p></o:p></span></pre>
<pre><span style="color:#888888">[5], and might be a good starting point for exploring that space. More<o:p></o:p></span></pre>
<pre><span style="color:#888888">importantly, [5] talks about function positioning, which is something I<o:p></o:p></span></pre>
<pre><span style="color:#888888">think we're missing. A more sophisticated extension to [5]'s function<o:p></o:p></span></pre>
<pre><span style="color:#888888">positioning can be found in [6].<o:p></o:p></span></pre>
<pre><span style="color:#888888"><o:p> </o:p></span></pre>
<pre><span style="color:#888888">Keeping in mind that LLVM is tuned to optimize loops within functions,<o:p></o:p></span></pre>
<pre><span style="color:#888888">at at high-level LLVM does the following [4]:<o:p></o:p></span></pre>
<pre><span style="color:#888888"><o:p> </o:p></span></pre>
<pre><span style="color:#888888"> The algorithm works from the inner-most loop within a <o:p></o:p></span></pre>
<pre><span style="color:#888888"> function outward, and at each stage walks through the<o:p></o:p></span></pre>
<pre><span style="color:#888888"> basic blocks, trying to coalesce them into sequential<o:p></o:p></span></pre>
<pre><span style="color:#888888"> chains where allowed by the CFG (or demanded by heavy<o:p></o:p></span></pre>
<pre><span style="color:#888888"> probabilities). Finally, it walks the blocks in <o:p></o:p></span></pre>
<pre><span style="color:#888888"> topological order, and the first time it reaches a <o:p></o:p></span></pre>
<pre><span style="color:#888888"> chain of basic blocks, it schedules them in the <o:p></o:p></span></pre>
<pre><span style="color:#888888"> function in-order.<o:p></o:p></span></pre>
<pre><span style="color:#888888"><o:p> </o:p></span></pre>
<pre><span style="color:#888888">There are also plenty of heuristics such as "tail duplication" to deal<o:p></o:p></span></pre>
<pre><span style="color:#888888">with diamonds and other odd cases in the CFG that are harder to layout.<o:p></o:p></span></pre>
<pre><span style="color:#888888"> Unfortunately, there don't seem to be any sources cited. We may want<o:p></o:p></span></pre>
<pre><span style="color:#888888">to develop our own heuristics to modify the CFG for better layout as<o:p></o:p></span></pre>
<pre><span style="color:#888888">well.<o:p></o:p></span></pre>
<pre><span style="color:#888888"><o:p> </o:p></span></pre>
<pre><span style="color:#888888"><o:p> </o:p></span></pre>
<pre><span style="color:#888888"><o:p> </o:p></span></pre>
<pre><span style="color:#888888">[1] Thomas Ball, James R. Larus. Branch Prediction for Free (<a href="https://do">https://do</a><o:p></o:p></span></pre>
<pre><span style="color:#888888">i.org/10.1145/173262.155119)<o:p></o:p></span></pre>
<pre><span style="color:#888888"><o:p> </o:p></span></pre>
<pre><span style="color:#888888">[2] Hans Wennborg. The recent switch lowering improvements. (<a href="http://llv">http://llv</a><o:p></o:p></span></pre>
<pre><span style="color:#888888">m.org/devmtg/2015-10/slides/Wennborg-SwitchLowering.pdf) See also: http<o:p></o:p></span></pre>
<pre><span style="color:#888888"><a href="file:///s:/www.youtube.com/watch%3fv=gMqSinyL8uk">s://www.youtube.com/watch?v=gMqSinyL8uk</a><o:p></o:p></span></pre>
<pre><span style="color:#888888"><o:p> </o:p></span></pre>
<pre><span style="color:#888888">[3] James E. Smith. A study of branch prediction strategies (<a href="https://dl">https://dl</a><o:p></o:p></span></pre>
<pre><span style="color:#888888">.acm.org/citation.cfm?id=801871)<o:p></o:p></span></pre>
<pre><span style="color:#888888"><o:p> </o:p></span></pre>
<pre><span style="color:#888888">[4] <a href="http://llvm.org/doxygen/MachineBlockPlacement_8cpp_source.html">http://llvm.org/doxygen/MachineBlockPlacement_8cpp_source.html</a><o:p></o:p></span></pre>
<pre><span style="color:#888888"><o:p> </o:p></span></pre>
<pre><span style="color:#888888">[5] Karl Pettis, Robert C. Hansen. Profile guided code positioning. (ht<o:p></o:p></span></pre>
<pre><span style="color:#888888">tps://doi.org/10.1145/93542.93550)<o:p></o:p></span></pre>
<pre><span style="color:#888888"><o:p> </o:p></span></pre>
<pre><span style="color:#888888">[6] Hashemi et al. Efficient procedure mapping using cache line<o:p></o:p></span></pre>
<pre><span style="color:#888888">coloring (<a href="https://doi.org/10.1145/258915.258931">https://doi.org/10.1145/258915.258931</a>)<o:p></o:p></span></pre>
<pre><span style="color:#888888"><o:p> </o:p></span></pre>
<pre><span style="color:#888888"><o:p> </o:p></span></pre>
<pre><span style="color:#888888">~kavon<o:p></o:p></span></pre>
<pre><span style="color:#888888"><o:p> </o:p></span></pre>
<pre><span style="color:#888888"><o:p> </o:p></span></pre>
<pre><span style="color:#888888">On Sat, 2018-05-05 at 21:23 +0200, Andreas Klebinger wrote:<o:p></o:p></span></pre>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<pre><span style="color:#888888">Does anyone have good hints for literature on basic block layout<o:p></o:p></span></pre>
<pre><span style="color:#888888">algorithms?<o:p></o:p></span></pre>
<pre><span style="color:#888888">I've run into a few examples where the current algorithm falls apart <o:p></o:p></span></pre>
<pre><span style="color:#888888">while working on Cmm.<o:p></o:p></span></pre>
<pre><span style="color:#888888"><o:p> </o:p></span></pre>
<pre><span style="color:#888888">There is a trac ticket <a href="https://ghc.haskell.org/trac/ghc/ticket/15124">https://ghc.haskell.org/trac/ghc/ticket/15124#</a><o:p></o:p></span></pre>
<pre><span style="color:#888888">ticket<o:p></o:p></span></pre>
<pre><span style="color:#888888">where I tracked some of the issues I ran into.<o:p></o:p></span></pre>
<pre><span style="color:#888888"><o:p> </o:p></span></pre>
<pre><span style="color:#888888">As it stands some cmm optimizations are far out weighted by<o:p></o:p></span></pre>
<pre><span style="color:#888888">accidental changes they cause in the layout of basic blocks.<o:p></o:p></span></pre>
<pre><span style="color:#888888"><o:p> </o:p></span></pre>
<pre><span style="color:#888888">The main problem seems to be that the current codegen only considers<o:p></o:p></span></pre>
<pre><span style="color:#888888">the <o:p></o:p></span></pre>
<pre><span style="color:#888888">last jump<o:p></o:p></span></pre>
<pre><span style="color:#888888">in a basic block as relevant for code layout.<o:p></o:p></span></pre>
<pre><span style="color:#888888"><o:p> </o:p></span></pre>
<pre><span style="color:#888888">This works well for linear chains of control flow but behaves badly<o:p></o:p></span></pre>
<pre><span style="color:#888888">and <o:p></o:p></span></pre>
<pre><span style="color:#888888">somewhat<o:p></o:p></span></pre>
<pre><span style="color:#888888">unpredictable when dealing with branch heavy code where blocks have<o:p></o:p></span></pre>
<pre><span style="color:#888888">more <o:p></o:p></span></pre>
<pre><span style="color:#888888">than<o:p></o:p></span></pre>
<pre><span style="color:#888888">one successor or calls.<o:p></o:p></span></pre>
<pre><span style="color:#888888"><o:p> </o:p></span></pre>
<pre><span style="color:#888888">In particular if we have a loop<o:p></o:p></span></pre>
<pre><span style="color:#888888"><o:p> </o:p></span></pre>
<pre><span style="color:#888888">A jmp B call C call D<o:p></o:p></span></pre>
<pre><span style="color:#888888"><o:p> </o:p></span></pre>
<pre><span style="color:#888888">which we enter into at block B from Block E<o:p></o:p></span></pre>
<pre><span style="color:#888888">we would like something like:<o:p></o:p></span></pre>
<pre><span style="color:#888888"><o:p> </o:p></span></pre>
<pre><span style="color:#888888">E,B,C,D,A<o:p></o:p></span></pre>
<pre><span style="color:#888888"><o:p> </o:p></span></pre>
<pre><span style="color:#888888">Which means with some luck C/D might be still in cache if we return<o:p></o:p></span></pre>
<pre><span style="color:#888888">from <o:p></o:p></span></pre>
<pre><span style="color:#888888">the call.<o:p></o:p></span></pre>
<pre><span style="color:#888888"><o:p> </o:p></span></pre>
<pre><span style="color:#888888">However we can currently get:<o:p></o:p></span></pre>
<pre><span style="color:#888888"><o:p> </o:p></span></pre>
<pre><span style="color:#888888">E,B,A,X,D,X,C<o:p></o:p></span></pre>
<pre><span style="color:#888888"><o:p> </o:p></span></pre>
<pre><span style="color:#888888">where X are other unrelated blocks. This happens since call edges<o:p></o:p></span></pre>
<pre><span style="color:#888888">are <o:p></o:p></span></pre>
<pre><span style="color:#888888">invisible to the layout algorithm.<o:p></o:p></span></pre>
<pre><span style="color:#888888">It even happens when we have (conditional) jumps from B to C and C<o:p></o:p></span></pre>
<pre><span style="color:#888888">to D <o:p></o:p></span></pre>
<pre><span style="color:#888888">since these are invisible as well!<o:p></o:p></span></pre>
<pre><span style="color:#888888"><o:p> </o:p></span></pre>
<pre><span style="color:#888888">I came across cases where inverting conditions lead to big<o:p></o:p></span></pre>
<pre><span style="color:#888888">performance <o:p></o:p></span></pre>
<pre><span style="color:#888888">losses since suddenly block layout<o:p></o:p></span></pre>
<pre><span style="color:#888888">got all messed up. (~4% slowdown for the worst offenders).<o:p></o:p></span></pre>
<pre><span style="color:#888888"><o:p> </o:p></span></pre>
<pre><span style="color:#888888">So I'm looking for solutions there.<o:p></o:p></span></pre>
<pre><span style="color:#888888"><o:p> </o:p></span></pre>
<pre><span style="color:#888888">_______________________________________________<o:p></o:p></span></pre>
<pre><span style="color:#888888">ghc-devs mailing list<o:p></o:p></span></pre>
<pre><span style="color:#888888"><a href="mailto:ghc-devs@haskell.org">ghc-devs@haskell.org</a><o:p></o:p></span></pre>
<pre><span style="color:#888888"><a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs">http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs</a><o:p></o:p></span></pre>
</blockquote>
</div>
<div style="margin-left:18.75pt;margin-top:22.5pt;margin-right:18.75pt;margin-bottom:7.5pt">
<div style="border:none;border-top:solid #EDEEF0 1.0pt;padding:4.0pt 0cm 0cm 0cm">
<div>
<p class="MsoNormal" style="vertical-align:middle"><a href="mailto:klebinger.andreas@gmx.at"><b>Andreas Klebinger</b></a><o:p></o:p></p>
</div>
<p class="MsoNormal" align="right" style="text-align:right;vertical-align:middle">
<span style="color:#9FA2A5">Samstag, 5. Mai 2018 21:23</span><o:p></o:p></p>
</div>
</div>
<div style="margin-left:18.0pt;margin-right:18.0pt">
<p class="MsoNormal" style="margin-bottom:12.0pt"><span style="color:#888888">Does anyone have good hints for literature on basic block layout algorithms?
<br>
I've run into a few examples where the current algorithm falls apart while working on Cmm.
<br>
<br>
There is a trac ticket <a href="https://ghc.haskell.org/trac/ghc/ticket/15124#ticket">
https://ghc.haskell.org/trac/ghc/ticket/15124#ticket</a> <br>
where I tracked some of the issues I ran into. <br>
<br>
As it stands some cmm optimizations are far out weighted by <br>
accidental changes they cause in the layout of basic blocks. <br>
<br>
The main problem seems to be that the current codegen only considers the last jump
<br>
in a basic block as relevant for code layout. <br>
<br>
This works well for linear chains of control flow but behaves badly and somewhat <br>
unpredictable when dealing with branch heavy code where blocks have more than <br>
one successor or calls. <br>
<br>
In particular if we have a loop <br>
<br>
A jmp B call C call D <br>
<br>
which we enter into at block B from Block E <br>
we would like something like: <br>
<br>
E,B,C,D,A <br>
<br>
Which means with some luck C/D might be still in cache if we return from the call.
<br>
<br>
However we can currently get: <br>
<br>
E,B,A,X,D,X,C <br>
<br>
where X are other unrelated blocks. This happens since call edges are invisible to the layout algorithm.
<br>
It even happens when we have (conditional) jumps from B to C and C to D since these are invisible as well!
<br>
<br>
I came across cases where inverting conditions lead to big performance losses since suddenly block layout
<br>
got all messed up. (~4% slowdown for the worst offenders). <br>
<br>
So I'm looking for solutions there. <o:p></o:p></span></p>
</div>
</blockquote>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
</div>
</body>
</html>