<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=us-ascii">
<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:"Segoe UI";
panose-1:2 11 5 2 4 2 4 2 2 3;}
/* 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;}
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.js-issue-title
{mso-style-name:js-issue-title;}
span.EmailStyle20
{mso-style-type:personal-reply;
font-family:"Calibri",sans-serif;
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">Alternative 1: Putting the weights directly into the case alternative tuple<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Rather than putting it in the tuple, you could put it in the AltCon<o:p></o:p></p>
<p class="Code">type Alt b = (AltCon, [b], Expr b)<o:p></o:p></p>
<p class="Code">data AltCon = DataAlt Freq DataCon | LitAlt Freq Literal | DEFAULT Freq<o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:12.0pt"><o:p> </o:p></span></p>
<p class="MsoNormal">My guess is that a lot more current code pattern matches on those triples than pattern matches on the AltCon itself. And AltCon isn’t used for anything else<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Simon<o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:12.0pt"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt"><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">From:</span></b><span lang="EN-US"> ghc-devs <ghc-devs-bounces@haskell.org>
<b>On Behalf Of </b>Andreas Klebinger<br>
<b>Sent:</b> 30 November 2018 11:37<br>
<b>To:</b> ghc-devs@haskell.org<br>
<b>Subject:</b> Considerations for Control flow hint implementation.<o:p></o:p></span></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Hello Devs,<br>
<br>
I've started thinking about the implementation of <a href="https://github.com/ghc-proposals/ghc-proposals/pull/182">
https://github.com/ghc-proposals/ghc-proposals/pull/182</a> recently. (<span class="js-issue-title">Add control flow hint pragmas.)</span><br>
<br>
For this purpose I've rebased <b><span style="font-size:10.0pt;font-family:"Segoe UI",sans-serif;color:#464C5C">D4327
</span></b>"WIP: Add likelyhood to alternatives from stg onwards" which already does a lot of the work at the Cmm/Stg level.<br>
<br>
The issue I ask you for feedback now is how to best attach branch weights to case alternatives in core.<br>
<br>
My prefered approach would be to expand core data types to include them unconditionally.
<br>
While this is quite far reaching in the amount of code it touches it would be rather straight forward to implement:<br>
<br>
Alternative 1: Putting the weights directly into the case alternative tuple:<br>
+ It it's trivial to check which places manipulate case alternatives as they will initially fail to compile.<br>
+ It's very mechanical, almost all use sites won't actually change the weight.<br>
+ It's easy to keep this working going forward as any new optimizations can't "forget" they have to consider them.<br>
- It will introduce a cost in compiler performance.<br>
- New optimization who don't have to care about branchweights still have to at least pipe them through.<br>
- While syntactically heavy in terms of real complexity it's a simply approach.<br>
<br>
Alternative 2: Putting the weights into the case constructor.<br>
+ Might give better compiler performance as I expect us to rebuild cases less often than alternatives.<br>
- Seems kind of clunky.<br>
- Weaker coupling between case alternatives and their weights.<br>
<br>
Or we could use ticks:<br>
+ There is some machinery already there<br>
+ Can be turned off for -O0<br>
+ Can be ignored when convenient.<br>
- Can be ignored when convenient.<br>
- Very weak coupling between case alternatives and their weights.<br>
- The existing machinery doesn't exactly match the needs of this.<br>
- We would have to extend tick semantics to a degree where complexity might grow too large<br>
for me to successfully implement this.<br>
- If new optimizations end up just removing these ticks because they are allowed to then<br>
the whole exercise becomes rather pointless.<br>
- Makes it harder to ensure all relevant code paths in GHC are actually updated. <br>
<br>
In particular there is currently no tick category which can stick to case alternatives but just get's removed in case<br>
it get's in the way of optimizations.<br>
The closest match is SoftScope which allows ticks to be floated up, something that could impact performance quite badly<br>
in this case. As then we might float something intended to mark a branch as unlikely into another branch that is actually<br>
along the hot path.<br>
<br>
I think the core variant(s) mostly stand and fall with the actual compile time impact. For -O0 the impact<br>
would be negligible as the compile time is already dominated by codegen and typechecking. For the rest<br>
it's hard to say.<br>
<br>
So I'm looking for feedback on this. Maybe you have other suggestions I haven't considered?<br>
How much compile time cost increase would be acceptable for what kind of performance boost?<br>
<br>
Cheers,<br>
Andreas Klebinger<o:p></o:p></p>
</div>
</div>
</body>
</html>