<div dir="ltr">Kyle has been looking at these exact kinds of patterns and trying to work out a better model to use that avoids deeply chained things becoming "cold" in weird ways...<br><br><div class="gmail_quote"><div dir="ltr">On Fri, Aug 11, 2017 at 11:45 AM Craig Topper via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">In my original case we we definitely didn't. I sort of made up the numbers in the example.<div><br></div><div>I think in the original code the first range was from 390-450. The second range was from 840-900. Then 1290-1350, etc. There is a multiply by 60 proceeding the compares. But as you can see not all of the ranges start at a multiple of 60. Though they are 60 entries wide.</div></div><div class="gmail_extra"></div><div class="gmail_extra"><br clear="all"><div><div class="m_-9164918471806450899gmail_signature" data-smartmail="gmail_signature">~Craig</div></div></div><div class="gmail_extra">
<br><div class="gmail_quote">On Fri, Aug 11, 2017 at 11:31 AM, Philip Reames <span dir="ltr"><<a href="mailto:listmail@philipreames.com" target="_blank">listmail@philipreames.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div text="#000000" bgcolor="#FFFFFF">
<p>Slightly OT for the original question, but do we manage to factor
out the common factor here and actually form the switch?</p>
<p>This could be rewritten as:</p>
<div>int tmp = a/10;<br>
switch(tmp) {<br>
case 1: ...<br>
case 3: ...<br>
case 5: ...<br>
case 7: ...<br>
}<br>
<br>
Do we do so?<span class="m_-9164918471806450899HOEnZb"><font color="#888888"><br>
<br>
Philip<br>
<br>
</font></span></div><div><div class="m_-9164918471806450899h5">
<div class="m_-9164918471806450899m_-4127354802273372663moz-cite-prefix">On 08/04/2017 04:10 PM, Craig Topper
via llvm-dev wrote:<br>
</div>
</div></div><blockquote type="cite"><div><div class="m_-9164918471806450899h5">
<div dir="ltr">
<div>I'm look at some code that does something roughly like this</div>
<div><br>
</div>
<div>if (a >= 10 && a < 20) {</div>
<div> // do calculation</div>
<div>} else if (a >= 30 && a < 40) {</div>
<div> // do calculation</div>
<div>} else if (a >= 50 && a < 60) {</div>
<div> // do something</div>
<div>
<div>} else if (a >= 70 && a < 80) {</div>
<div> // do something</div>
</div>
<div>}</div>
<div><br>
</div>
<div>// some other code that got split based on whether we
entered any of the 'if' bodies. So each if body merges to a
slightly different spot than the not taken side of the final
if.<br>
</div>
<div><br>
</div>
<div>In my specific case there are really 8 specific range
checks.</div>
<div><br>
</div>
<div>Without profile data it seems branch probability assumes
the branch of each 'if' has 50% probability. Due to the way
the ifs are cascaded this causes block frequency to think the
final 'if' body can only execute some really small percentage
of the time. Similarly it thinks that less than %1 of the time
will we enter the code path that occurs if none of the ifs are
taken.</div>
<div><br>
</div>
<div>In reality in my specific case we end up executing none of
the ifs most often. But I think i'd settle for all bodies and
the no ifs taken path having equal weighting</div>
<div><br>
</div>
<div>The bad block frequency and the fact that we have a split
path for merging the ifs versus not going into any ifs at all
seems to be causing block placement to create a layout that
pessimizes the real common case.</div>
<div><br>
</div>
<div>Since all the compares are on the same variable, the
originally code is kinda like a switch and as such we should
maybe give each possible path equal weighting.</div>
<div><br>
</div>
<div>Is there somewhere we can apply a heuristic to the branch
probability so that it can provide a better answer here?</div>
<br clear="all">
<div>
<div class="m_-9164918471806450899m_-4127354802273372663gmail_signature">~Craig</div>
</div>
</div>
<br>
<fieldset class="m_-9164918471806450899m_-4127354802273372663mimeAttachmentHeader"></fieldset>
<br>
</div></div><span><pre>_______________________________________________
LLVM Developers mailing list
<a class="m_-9164918471806450899m_-4127354802273372663moz-txt-link-abbreviated" href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>
<a class="m_-9164918471806450899m_-4127354802273372663moz-txt-link-freetext" href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a>
</pre>
</span></blockquote>
<br>
</div>
</blockquote></div><br></div>
_______________________________________________<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" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
</blockquote></div></div>