[LLVMdev] Separating loop nests based on profile information?

[Duncan P. N. Exon Smith]

> On 2015-Jan-08, at 11:37, Philip Reames <listmail at philipreames.com> wrote:
> 
> Let me ask a basic question: what do BlockFrequency and BranchProbability compute and roughly what mental cost model should I have?  Once I have a BlockFrequency, what does it mean?  Some of this is documented in BlockFrequencyImpl.h, but the high level bits are mostly missing.  Particularly for BranchProbability.  

*Branch weight*: An integer attached to an outgoing edge from a basic
block that represents the relative likelihood that it will be taken
over other outgoing edges.

*Branch probability*: Assuming a basic block is executed, what's the
probability it will terminate via a given outgoing edge?  This is the
branch probability for that branch.  Equivalent to the branch weight
divided by the sum of the branch weights for the basic block.

If we don't have profile information, branch weights (and thus,
probabilities) are computed using heuristics in -branch-prob.

*Block frequency*: Assume a function is executed many times -- call this
large number the block frequency of the entry block.  Given that, how
many times is each basic block executed?  This is the block frequency of
each block.  Frequencies are calculated from branch probabilities in
-block-freq.  You can compare relative "hotness" of two basic blocks by
comparing their block frequencies.  (A block frequency means nothing in
isolation -- you need to compare it to a reference block frequency, like
the frequency of a loop header, or of the entry block, or of something
else, for it to have any meaning.)

*Block bias* (PR20316 [1]): Is this basic block more or less likely to
be executed than its "peers"?  The current proposal calculates a
"reference" block frequency by assuming all branch weights are 1 (and,
thus, that all branch probabilities are even), and defines the block
bias to be the ratio of the block frequency to its "reference" block
frequency.  It may have some bitrot, but wouldn't be hard for me to
clean up and commit (if it's even a useful metric).

After I wrote this out, I remembered that I already documented this [2].
(If you think the descriptions I just gave here are more useful than
what's in tree, please improve the in-tree version!)

[1]: http://llvm.org/bugs/show_bug.cgi?id=20316
[2]: http://llvm.org/docs/BlockFrequencyTerminology.html