[llvm-dev] BranchProbability/BlockFrequency for a chain of ifs

[Chandler Carruth via llvm-dev]

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...

On Fri, Aug 11, 2017 at 11:45 AM Craig Topper via llvm-dev <
llvm-dev at lists.llvm.org> wrote:

> In my original case we we definitely didn't. I sort of made up the numbers
> in the example.
>
> 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.
>
> ~Craig
>
> On Fri, Aug 11, 2017 at 11:31 AM, Philip Reames <listmail at philipreames.com
> > wrote:
>
>> Slightly OT for the original question, but do we manage to factor out the
>> common factor here and actually form the switch?
>>
>> This could be rewritten as:
>> int tmp = a/10;
>> switch(tmp) {
>> case 1: ...
>> case 3: ...
>> case 5: ...
>> case 7: ...
>> }
>>
>> Do we do so?
>>
>> Philip
>>
>> On 08/04/2017 04:10 PM, Craig Topper via llvm-dev wrote:
>>
>> I'm look at some code that does something roughly like this
>>
>> if (a >= 10 && a < 20) {
>>   // do calculation
>> } else if (a >= 30 && a < 40) {
>>   // do calculation
>> } else if (a >= 50 && a < 60) {
>>   // do something
>> } else if (a >= 70 && a < 80) {
>>   // do something
>> }
>>
>> // 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.
>>
>> In my specific case there are really 8 specific range checks.
>>
>> 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.
>>
>> 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
>>
>> 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.
>>
>> 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.
>>
>> Is there somewhere we can apply a heuristic to the branch probability so
>> that it can provide a better answer here?
>>
>> ~Craig
>>
>>
>> _______________________________________________
>> LLVM Developers mailing listllvm-dev at lists.llvm.orghttp://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>
>>
>>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170811/c256e9ad/attachment.html>