llvm dev - Feb 2014 - [LLVMdev] [RFC] BlockFrequency is the wrong metric; we need a new one

On Feb 2, 2014, at 6:18 PM, Andrew Trick <atrick at apple.com> wrote:
>> The result of such a system would produce weights for every block in
the above CFG as '1.0', or equivalent to the entry block weight. This to
me is a really useful metric -- it indicates that no block in the CFG is really
more or less likely than any other. Only *biases* in a specific direction would
cause the block weights to go up or down significantly.
> 
> I don't like this statement, or don't understand it. It is useful
to know a branch is unbiased. Currently we assume branches are unbiased then
optimize conservatively in those cases (do no harm). But if we had greater
confidence in unbiased branches (because the branch was actually profiled), we
could if-convert much more aggressively
As an aside, I’d like to point out that knowing that a branch is unbiased is not
sufficient to know that it is poorly predicted and therefore profitable to
if-convert.   Consider a case where a branch is evaluated 100 times, going to
the true destination 50 times and the false destination 50 times.  If the cases
where it goes each particular direction is strongly correlated with prior
branches in the execution trace, the branch predictor’s history table will pick
up on that and successfully predict this branch despite it being unbiased when
considered in isolation.

—Owen
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20140202/e0247ca0/attachment.html>

On Feb 2, 2014, at 9:02 PM, Owen Anderson <resistor at mac.com> wrote:
> 
> On Feb 2, 2014, at 6:18 PM, Andrew Trick <atrick at apple.com> wrote:
> 
>>> The result of such a system would produce weights for every block
in the above CFG as '1.0', or equivalent to the entry block weight. This
to me is a really useful metric -- it indicates that no block in the CFG is
really more or less likely than any other. Only *biases* in a specific direction
would cause the block weights to go up or down significantly.
>> 
>> I don't like this statement, or don't understand it. It is
useful to know a branch is unbiased. Currently we assume branches are unbiased
then optimize conservatively in those cases (do no harm). But if we had greater
confidence in unbiased branches (because the branch was actually profiled), we
could if-convert much more aggressively
> 
> As an aside, I’d like to point out that knowing that a branch is unbiased
is not sufficient to know that it is poorly predicted and therefore profitable
to if-convert.   Consider a case where a branch is evaluated 100 times, going to
the true destination 50 times and the false destination 50 times.  If the cases
where it goes each particular direction is strongly correlated with prior
branches in the execution trace, the branch predictor’s history table will pick
up on that and successfully predict this branch despite it being unbiased when
considered in isolation.
That’s a good point. We could profile misprediction, but we have no way to
express that either in the current BranchProbability/BlockFrequency API or in
Chandler’s variant.
-Andy

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20140202/6643ef10/attachment.html>

On Sun, Feb 2, 2014 at 9:07 PM, Andrew Trick <atrick at apple.com> wrote:
> That’s a good point. We could profile misprediction, but we have no way to
> express that either in the current BranchProbability/BlockFrequency API or
> in Chandler’s variant.
>
But I don't think we *need* to profile misprediction at all. It simply
isn't a problem that PGO needs to solve. The problems we're looking at
for
PGO to help with are:

- i-cache locality / general code layout
- spill placement / live range splitting
- loop vectorization and unrolling[1]
- inlining[1]

For all of these, we're really looking at hot or cold region
identification, and clustering. I don't think that in these cases it is
perfectly reasonable to model "hot" and "cold" (in the
branch probability
sense) as both heavily biased and high confidence in that bias, and
"not-hot" or "not-cold" as either not heavily biased *or*
low confidence in
any indicated bias.

This gives us a simple linear model.


[1]: Note that even these are merely *speculative* use cases based on
experience with other systems. I'm not really trying to make sweeping
claims about *how* effective PGO will be here, only that it is an area that
various folks are looking at improving with PGO based on experience in
other system.s
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20140202/d8edbc8f/attachment.html>