<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:"Book Antiqua";
panose-1:2 4 6 2 5 3 5 3 3 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0cm;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman",serif;}
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;}
span.EmailStyle17
{mso-style-type:personal-reply;
font-family:"Book Antiqua",serif;
color:#943634;
font-weight:normal;
font-style:normal;
text-decoration:none none;}
.MsoChpDefault
{mso-style-type:export-only;
font-family:"Calibri",sans-serif;
mso-fareast-language:EN-US;}
@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-IE link=blue vlink=purple><div class=WordSection1><p class=MsoNormal><span style='font-family:"Book Antiqua",serif;color:black;mso-fareast-language:EN-US'>Thanks for the clarification Sanjay - I had somehow misunderstood the intent, but your response clear this up.<o:p></o:p></span></p><p class=MsoNormal><span style='font-family:"Book Antiqua",serif;color:black;mso-fareast-language:EN-US'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-family:"Book Antiqua",serif;color:black;mso-fareast-language:EN-US'>Sorry for the confusion,<o:p></o:p></span></p><p class=MsoNormal><span style='font-family:"Book Antiqua",serif;color:black;mso-fareast-language:EN-US'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-family:"Book Antiqua",serif;color:black;mso-fareast-language:EN-US'> MartinO<o:p></o:p></span></p><p class=MsoNormal><span style='font-family:"Book Antiqua",serif;color:#943634;mso-fareast-language:EN-US'><o:p> </o:p></span></p><p class=MsoNormal><b><span lang=EN-US style='font-size:11.0pt;font-family:"Calibri",sans-serif'>From:</span></b><span lang=EN-US style='font-size:11.0pt;font-family:"Calibri",sans-serif'> Sanjay Patel [mailto:spatel@rotateright.com] <br><b>Sent:</b> 22 April 2016 23:46<br><b>To:</b> Martin.ORiordan@movidius.com<br><b>Cc:</b> Xinliang David Li <xinliangli@gmail.com>; llvm-dev <llvm-dev@lists.llvm.org>; David Li <davidxl@google.com>; Nick Lewycky <nicholas@mxc.ca>; cfe-dev <cfe-dev@lists.llvm.org><br><b>Subject:</b> Re: [cfe-dev] [llvm-dev] [RFC] remove the llvm.expect intrinsic<o:p></o:p></span></p><p class=MsoNormal><o:p> </o:p></p><div><div><div><div><p class=MsoNormal style='margin-bottom:12.0pt'>Hi Martin -<o:p></o:p></p></div><p class=MsoNormal style='margin-bottom:12.0pt'>1. Nobody is proposing to remove __builtin_expect(); we're just debating the best way to lower that programmer hint. The question is whether we need an *llvm.expect* intrinsic or if some kind of metadata will be adequate.<o:p></o:p></p></div><p class=MsoNormal style='margin-bottom:12.0pt'>2. The fact that using __builtin_expect() improved perf regardless of whether you chose the right or wrong prediction isn't too far-fetched IMO - it means that a branch (and HW prediction) was the better choice in that situation versus a select / conditional move. The compiler generated the branch, and the HW branch predictor did the rest.<o:p></o:p></p></div><p class=MsoNormal style='margin-bottom:12.0pt'>3. The original motivation for this proposed cleanup is a bug where __builtin_expect() is being ignored:<br><a href="https://llvm.org/bugs/show_bug.cgi?id=27344">https://llvm.org/bugs/show_bug.cgi?id=27344</a><br><br><o:p></o:p></p><div><p class=MsoNormal><o:p> </o:p></p></div></div><div><p class=MsoNormal><o:p> </o:p></p><div><p class=MsoNormal>On Fri, Apr 22, 2016 at 4:18 PM, Martin J. O'Riordan <<a href="mailto:martin.oriordan@movidius.com" target="_blank">martin.oriordan@movidius.com</a>> wrote:<o:p></o:p></p><blockquote style='border:none;border-left:solid #CCCCCC 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-right:0cm'><div><div><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span style='font-family:"Book Antiqua",serif;color:#943634'>Sorry for jumping in so late into this discussion, but I genuinely believe that removing this is a bad idea.</span><o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span style='font-family:"Book Antiqua",serif;color:#943634'> </span><o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span style='font-family:"Book Antiqua",serif;color:#943634'>My reason for saying this is going to sound very strange, but I think that we need to understand a bit more about how this is being handled.</span><o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span style='font-family:"Book Antiqua",serif;color:#943634'> </span><o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span style='font-family:"Book Antiqua",serif;color:#943634'>A while back one of my customers asked me if there was a method for advising the compiler how an </span><i><span style='font-family:"Book Antiqua",serif;color:black'>if-statement</span></i><span style='font-family:"Book Antiqua",serif;color:black'> </span><span style='font-family:"Book Antiqua",serif;color:#943634'>was likely to resolve, and I said “sure” and told them to use ‘</span><span style='font-family:"Courier New";color:black'>__builtin_expect</span><span style='font-family:"Book Antiqua",serif;color:#943634'>’.</span><o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span style='font-family:"Book Antiqua",serif;color:#943634'> </span><o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span style='font-family:"Book Antiqua",serif;color:#943634'>At the time I thought that the compiler was probably predicting a higher probability or true/false than was actually the case for a particular instance, as my customer was telling me that the compiler was optimising in favour of the less probable case (something the customer knew, but the information could not be determined from the code).</span><o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span style='font-family:"Book Antiqua",serif;color:#943634'> </span><o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span style='font-family:"Book Antiqua",serif;color:#943634'>This was fair enough, these things happen and the customer (or profile directed feedback) has more knowledge than the default inferences in the compiler.</span><o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span style='font-family:"Book Antiqua",serif;color:#943634'> </span><o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span style='font-family:"Book Antiqua",serif;color:#943634'>They added the ‘</span><span style='font-family:"Courier New";color:black'>__builtin_expect</span><span style='font-family:"Book Antiqua",serif;color:#943634'>’ to provide their domain specific expert knowledge, and the performance did indeed improve as expected, with the compiler preferring the most likely branch that the programmer had indicated.</span><o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span style='font-family:"Book Antiqua",serif;color:#943634'> </span><o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span style='font-family:"Book Antiqua",serif;color:#943634'>The surprise though, was when we experimentally changed the outcome of the ‘</span><span style='font-family:"Courier New";color:black'>__builtin_expect</span><span style='font-family:"Book Antiqua",serif;color:#943634'>’ to say the exact opposite of what the actual case was. That is, to invert the truth. The program was more performant with the “wrong” truth than it was with no statement of truth. When we told the compiler that a particular outcome was more probable than when in fact it was less, the performance was better than when we said nothing. And when we told it the actual probable outcome, it was more performance still. So telling the outcome of the branch as being more likely true, or more likely false, was better than not telling the compiler anything at all.</span><o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span style='font-family:"Book Antiqua",serif;color:#943634'> </span><o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span style='font-family:"Book Antiqua",serif;color:#943634'>I must admit, this was a considerable surprise for me, but it does mean that there is something changing in that area of the code that responds differently when ‘</span><span style='font-family:"Courier New";color:black'>__builtin_expect</span><span style='font-family:"Book Antiqua",serif;color:#943634'>’ is used versus the inferred probabilities.</span><o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span style='font-family:"Book Antiqua",serif;color:#943634'> </span><o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span style='font-family:"Book Antiqua",serif;color:#943634'>It is not something that I have investigated further as it is not a specific area that I can prioritise my efforts, but I think that it is something I have to raise awareness off in the context of this thread where removing this builtin is being proposed. At the moment I have a lot of programs that are benefitting from the explicit use of this builtin, even when the programmer directed outcome is wrong. So before we can remove this builtin, we need to explain why there is a difference on behaviour when it is present and stating a particular outcome versus it being omitted and the inferred outcome being the same.</span><o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span style='font-family:"Book Antiqua",serif;color:#943634'> </span><o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span style='font-family:"Book Antiqua",serif;color:#943634'> MartinO</span><o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span style='font-family:"Book Antiqua",serif;color:#943634'> </span><o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><b><span lang=EN-US style='font-size:11.0pt;font-family:"Calibri",sans-serif'>From:</span></b><span lang=EN-US style='font-size:11.0pt;font-family:"Calibri",sans-serif'> cfe-dev [mailto:<a href="mailto:cfe-dev-bounces@lists.llvm.org" target="_blank">cfe-dev-bounces@lists.llvm.org</a>] <b>On Behalf Of </b>Xinliang David Li via cfe-dev<br><b>Sent:</b> 22 April 2016 22:49<br><b>To:</b> Sanjay Patel <<a href="mailto:spatel@rotateright.com" target="_blank">spatel@rotateright.com</a>><br><b>Cc:</b> llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>>; cfe-dev <<a href="mailto:cfe-dev@lists.llvm.org" target="_blank">cfe-dev@lists.llvm.org</a>>; David Li <<a href="mailto:davidxl@google.com" target="_blank">davidxl@google.com</a>>; Nick Lewycky <<a href="mailto:nicholas@mxc.ca" target="_blank">nicholas@mxc.ca</a>><br><b>Subject:</b> Re: [cfe-dev] [llvm-dev] [RFC] remove the llvm.expect intrinsic</span><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><div><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'>Your patch does make the handling of __builtin_unpredictable and __builtin_expect 'unified' in some way.<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'>However given the point brought up by Reid, and the rationale by Richard, as well as consideration of the easiness for enhancement in the future, I think keep the current mechanism is a better approach. <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></div><div><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'>The test cases from Richard are broken with current lowering, but it is just bugs to be fixed.<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></div><div><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'>David<o:p></o:p></p></div></div><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'>On Fri, Apr 22, 2016 at 1:50 PM, Sanjay Patel via cfe-dev <<a href="mailto:cfe-dev@lists.llvm.org" target="_blank">cfe-dev@lists.llvm.org</a>> wrote:<o:p></o:p></p><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><div><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'>I, of course, thought the ~100 lines added by D19299 was a reasonable trade for the ~800 lines removed in D19300.<o:p></o:p></p></div><p class=MsoNormal style='mso-margin-top-alt:auto;margin-bottom:12.0pt'><br>David Li (and anyone else following along), do you still like those patches after hearing this objection or should I abandon?<o:p></o:p></p></div></div><div><div><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'>On Fri, Apr 22, 2016 at 11:55 AM, Reid Kleckner <<a href="mailto:rnk@google.com" target="_blank">rnk@google.com</a>> wrote:<o:p></o:p></p><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><div><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'>Sorry, I didn't realize that was the clang side.<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></div><div><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'>I think it's kind of ugly that the frontend has to pattern match and lower this intrinsic in three places: if, switch, and general case. The existing intrinsic is nice because it directly represents what the user can write, and lets the optimizer decide how to best represent it. As David Li mentioned, we may want to do value profiling in the future, and if we remove this intrinsic, we will have to come and revisit this code.<br><br>I think a single early pass to lower this intrinsic is a low cost to pay for that simplicity.<o:p></o:p></p></div><div><div><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 Fri, Apr 22, 2016 at 10:39 AM, Sanjay Patel <<a href="mailto:spatel@rotateright.com" target="_blank">spatel@rotateright.com</a>> wrote:<o:p></o:p></p><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;margin-bottom:12.0pt'>Hi Reid -<o:p></o:p></p></div><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'>The intent of D19299 is to remove all Clang refs to llvm.expect. Do you see any holes after applying that patch? <o:p></o:p></p></div><div><div><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'>On Fri, Apr 22, 2016 at 11:36 AM, Reid Kleckner <<a href="mailto:rnk@google.com" target="_blank">rnk@google.com</a>> wrote:<o:p></o:p></p><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><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'>Clang still appears to use llvm.expect. I think if you can show that it's trivial to update clang with a patch, then yeah, moving back down to one representation for this sounds reasonable.<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><div><div><div><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'>On Fri, Apr 22, 2016 at 9:20 AM, Sanjay Patel 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></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><div><div><div><p class=MsoNormal style='mso-margin-top-alt:auto;margin-bottom:12.0pt'>I've proposed removing the llvm.expect intrinsic:<br><a href="http://reviews.llvm.org/D19300" target="_blank">http://reviews.llvm.org/D19300</a><o:p></o:p></p></div><p class=MsoNormal style='mso-margin-top-alt:auto;margin-bottom:12.0pt'>The motivation for this change is in:<br><a href="http://reviews.llvm.org/D19299" target="_blank">http://reviews.llvm.org/D19299</a><br><br>For reference:<br>1. We created an intrinsic that's only reason for existing is to improve perf, but the intrinsic can harm optimization by interfering with transforms in other passes.<br><br>2. To solve that, we created a pass to always transform the intrinsic into metadata at a very early stage in LLVM. But now every program is paying a compile-time tax (running the LowerExpectIntrinsic pass) for a feature that is rarely used.<br><br>A possible front-end replacement transformation for a source-level "builtin_expect()" is in D19299: I think a front-end can always directly create metadata for this kind of programmer hint rather than using an intermediate representation (the intrinsic). Likewise, if there's some out-of-tree IR pass that is creating an llvm.expect, it should be able to create branch weight metadata directly instead.<br><br>Please let me know if you see any problems with this proposal or the patches.<o:p></o:p></p></div><div><p class=MsoNormal style='mso-margin-top-alt:auto;margin-bottom:12.0pt'>For reference, here's the original post-commit review thread for llvm.expect:<br><a href="https://marc.info/?l=llvm-commits&m=130997676129580&w=4" target="_blank">https://marc.info/?l=llvm-commits&m=130997676129580&w=4</a><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></div></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;margin-bottom:12.0pt'>_______________________________________________<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="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" target="_blank">http://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;mso-margin-bottom-alt:auto'> <o:p></o:p></p></div></blockquote></div><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'> <o:p></o:p></p></div></div></div></blockquote></div><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'> <o:p></o:p></p></div></div></div></div></blockquote></div><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'> <o:p></o:p></p></div></div></div><p class=MsoNormal style='mso-margin-top-alt:auto;margin-bottom:12.0pt'><br>_______________________________________________<br>cfe-dev mailing list<br><a href="mailto:cfe-dev@lists.llvm.org" target="_blank">cfe-dev@lists.llvm.org</a><br><a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev</a><o:p></o:p></p></blockquote></div><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'> <o:p></o:p></p></div></div></div></div></div></blockquote></div><p class=MsoNormal><o:p> </o:p></p></div></div></body></html>