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

[Philip Reames via llvm-dev]

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 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/aa191caa/attachment.html>