[LLVMdev] RFC - Improvements to PGO profile support

Xinliang David Li davidxl at google.com
Wed Mar 25 22:47:13 PDT 2015


> Which workload is better? I don’t at all trust users to get this right, at
> least for real, non-benchmark code.

We do have a lot of users (real world apps) who can get this right --
I am not joking ;)

> Without the rule, the two workload at least produces consistent
> profile data.  With the Laplace rule, you get 50 in one case, and 66
> in the other.
> Yes, but you’ve got more information in one case than the other. This is a
> feature IMO, not a bug. It’s entirely possible that with workload 2, the
> loop may have executed for a drastically different number of iterations. The
> fact that it did not, i.e., that it was consistent with workload 1, is more
> information that you did not have before. It makes sense for the compiler to
> be more aggressive when it has more data.

But the decision by the compiler is arbitrary and not necessarily
correct.  For instance, the single run used in the training may have
actually executed much fewer number of iterations than average. With
Laplace rule, the iteration count becomes even smaller. My point is
that there is no way for compiler to tell how good the data is nor is
the compiler in a good position to make that judgement.  By so doing,
the users who carefully prune their workload to reduce runtime gets
punished for no reason.

> Having some technology to improve confidence of the profile data is
> fine, but I don't see
> 1) how laplace rule is good for it
> What do you not understand about it? As the counts get larger, LaPlace’s
> rule fades into the noise. It only makes a difference for cases where some
> of the counts are *very* small, and in those cases, it very simply adjust
> the weights to make optimizations less aggressive.

Strictly speaking, in loop context, it just makes optimizations to
assume shorter trip counts.

> 2) why this can not be done in the consumer side (i.e., faithfully
> record the profile data).
> What does this have to do with how faithfully the profile is recorded? We’ve
> got fully accurate data, but if the profiling inputs are too small or not
> representative, you may still get poor optimization choices.

The point is that there is no need to adjust the weights. It is very
easy to check the loop header's profile count to determine how much
confidence you want to give (and possibly controlled with flag). The
control in this way is more fine grained than blindly changing the
weight right after reading the profile data.

> 2) result in bad inlining decisions. For instance:
>   for (...)
>       bar();  // (1)
> where (1) is the only callsite to bar().   Using the rule, BB count
> enclosing the call to bar() can be as low as half of the entry count
> of bar().  Inliner will get confused and think there are more hot
> callsites to 'bar' and  make suboptimal decisions ..
> Also if bar has calls to other functions, those callsites will look
> hotter than the call to 'bar' …
> Your own proposal for recording entry counts is to record “relative
> hotness”, not absolute profile counts.
> The proposal is to record 'global hotness' that can used to compare
> relative hotness across procedural boundaries (e.g. callsites in
> different callers). Profile counts satisfies this condition.
> On the caller’s side, we’ve got a branch weight influenced by LaPlace’s rule
> that is then used to compute BlockFrequency and you’re concerned about a
> mismatch between that the “relative hotness” recorded for the callee??
> Basically, say the caller is test()
> bar(){
>  // ENTRY count =  100 (from profile data)
>  // ENTRY freq = 1
>  // BB2: Freq(BB2) = 1, count = 100
>  foo ();              (2)
> }
> test() {
>   // ENTRY count = 1 (from profile data)
>   // Entry Freq = 1
>   for (i = 0; i < 100; i++) {
>       // BB1: Freq(BB1) = 50 due to Laplace rule
>       bar();  // Freq = 50, count = 50    (1)
>    }
> }
> With laplace rule, the block freq computed for bar's enclosing BB will
> be wrong -- as a result, the bar's enclosing BB's count will  be wrong
> too: 50*1/1 = 50.
> The global hotness of call site (1) & (2) should be the same, but
> distorted when Laplace rule is used.
> Yes, we care about using PGO across routine boundaries for IPO.
> I understand the issue, but my point was that you should simply not do that.
> You’re objecting to LaPlace’s rule based on a hypothetical comparison of
> block frequencies vs. entry counts. There is nothing in LLVM that does that
> now. We don’t even have entry counts.

I am not sure what you mean by 'hypothetical comparison of block
frequencies vs entry counts', but it does not seem to be what I mean.
What I mean is that

1) We need a metric to represent global hotness. Profile (execution)
count fits the bill
2) There are two ways to compute profile count for BBs
   a) directly compute it from the edge count recorded in profile data
(and BB Frequency can be directly scaled from it), but this change
requires slightly changing MD_prof's meaning or introducing MD_count
to record edge count without capping/scaling.

   b) Just recording the entry profile count (minimal change), but do
not change MD_prof. This approach will reuse block frequency
propagation, but the later relies on unaltered branch
probability/weight in order to recompute precisely the count (combined
with entry count).

Since people have concerns on a), we chose b). For b), I merely
pointed out in the above example that with Laplace rule, the
recomputed profile count at the only callsite of 'Bar' can be greatly
different from the recorded entry profile count Bar.  Incoming
callsite's profile distribution can be good signal for inlining
decisions. Such difference will be bad.

> I don’t see how you can argue that LaPlace’s rule is bad because it could
> affect an apples vs. oranges comparison of something that does not even
> exist yet.

Of course, PGO for IPA support is exactly the missing (and very
important) piece we plan to add -- if it already existed, there will
be no problems.



> The attached are two cases as well as the frequency graph computed
> today (with the laplace rule) and the correct frequency expected.
> I’d be a lot more interested to see a real-world example.
> See my reply above. On the other hand, I'd like to see examples where
> LaPlace Rule can actually help improve the profile data quality.
> It’s not about improving the results — it’s about preventing clang from
> being overly aggressive about optimizing based on limited profile data.

More information about the llvm-dev mailing list