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

[Craig Topper via llvm-dev]

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