[LLVMdev] Path forward on profile guided inlining?

[Philip Reames]

I would like to start prototyping changes towards profile guided 
inlining.  Before doing so, I wanted to get feedback from the community 
on the appropriate approach.  I'm going to layout a strawman proposal, 
but I'm open to other ideas on how to approach the problem.

Depending on what approach we settle on, I *may* be able to commit 
resources to actually implement this in the near term.  I can't commit 
to too much work here, so if we settle on something which will need a 
lot of enabling infrastructure work first, I'm likely going to need to 
just hack this within my local tree.  I'm hoping to avoid that, but I 
want to be up front about the practicalities here.

Now, on to the strawman proposal...

This proposal is intended to not be dependent on the ongoing pass manger 
changes by Chandler.  It's intended to be compatible with that work, but 
not reliant on it.

Background
One of the problems we have today is that we can't ask for information 
about the frequency of the call site we're examining within the inlining 
iteration loop.  We can get at this information from normal transform 
passes run within the outer inlining loop (CallGraphSCCPass), but the 
inner loop does not have the ability to keep function analysis up to 
date while inlining.

We have an existing piece of metadata on functions which record the 
function entry count.  This is not currently kept up to date in any way; 
it records the entry count of the function w/o.r.t. to inlining.  This 
metadata was only recently added and doesn't effect optimization today.

Objective
I'm looking to be able to implement two key inlining heuristics.

The first is to recognize when we have the last remaining *actual* call 
to a callee.  If we can prove there's a single caller today, we 
essentially just assume it's profitable to inline.  I want to extend 
this logic to the case where we have a single call site which dominates 
the caller profile for a given callee.  We might need to still keep 
around a copy of the callee (external, or rare callers), but the 
remaining callee definition will be a cold function, can be optimized 
for size, and can be placed far from hot code.

Second, I would like to use the frequency of the call site to adjust the 
inline threshold within the inliner.  This basically means that we 
become more willing to inline hot functions (and probably less willing 
to inline cold ones).

At least to start with, both of these optimizations would be off by 
default under a flag.  I figure there's a lot to be discussed here, but 
I'd prefer to defer that a bit.  We need to get the enabling parts in 
place before worrying too much about the heuristics.


The Ideal Answer
If we had the pass manager changes done, we'd be able to just ask BFI to 
compute an estimated execution count for the call site.  Both of the 
inliner heuristics I'm interested in could be implemented using that 
information combined with an up to date estimate of the function entry 
count.

If we had the pass manager changes, the only thing we'd need to do is 
update InlineFunction to subtract the estimated call count from the 
entry count of the remaining callee definition.  This would result in 
the entry count of B reflecting the estimated entry count from the 
remaining callers of B.  (Given the call site count is an estimate, this 
implies that entry counts are also now approximate. Given typical 
profiling mechanisms are lossy, that's not a big deal, but is worth 
noting explicitly.)

(See also my note at the bottom about iteration order.  I consider that 
somewhat out of scope for this proposal, but it effects both the ideal 
and practical sections herein.)


The Practical Answer
Essentially, the remainder of this is an approximation of the pass 
manager based solution which let's us start experimenting with the 
inliner changes while waiting for the pass manager.  At least in theory, 
when we have the pass manager in place, we can simply drop most of this.

The basic idea is to use metadata to effectively cache the estimated 
frequency for a given call site.  We can use BFI to generate/update this 
information once per iteration of the outer inlining loop.  As a result, 
we only need to keep it reasonably up to date within the inner inlining 
loop.  (See note below about alternate approaches.)

The metadata on the call site would look something like:
call void @foo() !prof !"estimated_execution_count" 2000 (where 2000 is 
the estimated count)

We'd have a new FunctionPass which removes any existing metadata and 
adds new metadata which basically comes down to a product of the 
functions entry count and the estimated block frequency (provided by 
BFI) of the block containing the call site.  This would run as the last 
FunctionPass within the outer inlining loop.  Assuming that the entry 
counts are kept reasonably up to date, the resulting estimated call site 
counts should be reasonable.

Within the inliner itself, we'd need to update InlineFunction to keep 
the estimated counts in sync:
- When inlining B into A, split the estimated call counts on the calls 
within B between the remaining instance of B and the newly created call 
sites within A.  I plan to split the estimated count in roughly the 
ratio of the entries into B.  As a result, a given call site BC 
(originally from B into C) would be split into two sites AC, and BC with 
estimated counts (AB.count/B.entry_count * OrigBC.count) and 
((1-AB.count/B.entry_count) * OrigBC.count).  This does require updating 
the body of the callee, not just the caller when inlining.

It's important to note that the resulting estimated call counts can be 
just flat out wrong.  As the easiest example, consider a case where B 
called C, but only when a boolean parameter was set to true.  If we 
split the count of BC into AC, BC and then drop the call site AC, we've 
essentially lost information about the frequency of the remaining BC 
w.r.t. any other callers of C.  We could try to adjust for this by only 
updating calls which don't get pruned away by constant propagation 
within InlineFunction, but I'm not sure how worthwhile it is trying to 
be smart here given the information will be roughly restored once we're 
out of the inner loop again.

What we can assume (and thus make inlining decisions on), is that a) a 
given call sites count is a reasonable approximation of it's actual 
execution count and b) that the sum of the call site counts for a given 
callee is less than or equal to the callee's entry count.  What we can't 
do is compare two call sites counts for the same callee within two 
different functions and decide with high confidence which is more frequent.


Alternate Approaches:
1) We could just recompute BFI explicitly in the inliner right before 
passing the result to ICA for the purposes of prototyping. If this was 
off by default, this might be a reasonable scheme for investigation.  
This could likely never be enabled for real uses.
2) We could pre-compute BFI once per function within a given SCC and 
then try to keep it up to date during inlining.  If we cached the call 
frequencies for the initial call sites, we could adjust the visit order 
to minimize the number of times we need to recompute a given functions 
block frequencies.  (e.g. we can look at all the original call sites 
within a function before looking at newly inlined ones)

For the record, it's not clear that the bottom up inlining approach 
works anywhere near as well once you starting using profiling 
information about the caller/callee pair.  You would seem to end up with 
cases where inlining BC makes it more likely you'll inline DC, but if 
you visited them in the other order you wouldn't inline DC. Consider the 
case where BC is a hot call site, and DC is the only other caller of C.  
I have no plans to actually tackle this problem.