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

[Xinliang David Li via llvm-dev]

While it is possible that all the value ranges are equally likely, the
opposite situation may be true too.   It is reasonable to assume that if
the developer knows the program behavior, he/she will choose to test  the
most likely range first .This can be used by the compiler as a heuristic to
make it more likely (not that LLVM is doing it today).  The 50% BP is a
sign that there is no known heuristic applied.

For better performance, using PGO or sample PGO is the best possible way.
Another direction is to use source annotation. Unfortunately,
builtin_expect is too strong for many cases. One enhancement that can be
done is to teach this builtin to take an additional likelihood parameter.
Restructuring the code is also possible, e.g.  by compressing the range and
using a switch ..

David


On Fri, Aug 4, 2017 at 4:10 PM, Craig Topper via llvm-dev <
llvm-dev at lists.llvm.org> 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/20170804/09bf212f/attachment.html>