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

[Craig Topper via llvm-dev]

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
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170811/5a8f9ced/attachment.html>