[llvm-dev] [BranchProbabilityInfo] The sum of all branch probabilities is not equal to 1

[Serguei Katkov via llvm-dev]

Dear All,

I'd like to get you feedback about change in BranchProbabilityInfo.
Specifically whether the proposed change makes sense and whether it
might cause some negative impact.

Currently the BranchProbabilityInfo contains a bunch of heuristics
which does not follow the restriction that sum of all branch probabilities
are equal to 1. This is due to denominator is fixed to 0x80000000 in
BranchProbability class. As a result the probaility of 1 is expressed as
numerator 0x80000000. If we have three branches with equal weight then
it cannot be represented as integer value due to 0x80000000 / 3 = 0x2AAAAAAA * 3 + 2.
This remainder 2 is always less than number of branches. In all current
heuristics this remainder just ignored.

So the question is whether it makes sense to split this remainder between
first several branches or it is better just to drop it.
Note that if we distribute this remainder between some branches we can loose
the "precise" information that two branches has the same probability.
They will be slightly different due to we add 1 to some branches numerators.
So the second question is whether the loosing information about equality of
probabilities might have some negative impact so we should not do this change.

The second question is as follows: currently BranchProbability operates on
weights but produces probabilites. For me personally it is cleaner if huristics
takes probabilities as input (except metadata heuristic).
Does it make sense to move from weights to probabilities in internal constants
used in BranchProbabilityInfo class. I do not have strong preference here,
so want to get your feedback.

Would appreciate for any feedback.

Thank you,
Serguei.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170523/8954bec3/attachment.html>