[llvm-dev] [LLVMdev] Path forward on profile guided inlining?

[Hal Finkel via llvm-dev]

----- Original Message -----
> From: "Philip Reames via llvm-dev" <llvm-dev at lists.llvm.org>
> To: "Xinliang David Li" <davidxl at google.com>
> Cc: "llvm-dev" <llvm-dev at lists.llvm.org>
> Sent: Thursday, December 10, 2015 7:12:50 PM
> Subject: Re: [llvm-dev] [LLVMdev] Path forward on profile guided inlining?
> 
> 
> 
> On 12/10/2015 05:03 PM, Xinliang David Li wrote:
> > On Thu, Dec 10, 2015 at 4:51 PM, Philip Reames
> > <listmail at philipreames.com> wrote:
> >>
> >> On 12/10/2015 04:29 PM, Xinliang David Li wrote:
> >>> On Thu, Dec 10, 2015 at 4:00 PM, Philip Reames
> >>> <listmail at philipreames.com> wrote:
> >>>> Given I didn't get any response to my original query, I chose
> >>>> not to
> >>>> invest
> >>>> time in this at the time.  I am unlikely to get time for this in
> >>>> the near
> >>>> future.
> >>>>
> >>>> On 12/07/2015 03:13 PM, Easwaran Raman wrote:
> >>>>
> >>>> (Resending after  removing llvmdev at cs.uiuc.edu and using
> >>>> llvm-dev at lists.llvm.org)
> >>>>
> >>>> On Mon, Dec 7, 2015 at 3:08 PM, Easwaran Raman
> >>>> <eraman at google.com> wrote:
> >>>>> Hi Philip,
> >>>>>
> >>>>>    Is there any update on this? I've been sending patches to
> >>>>>    get rid of
> >>>>> the
> >>>>> callee hotness based inline hints from the frontend and move
> >>>>> the logic
> >>>>> to
> >>>>> the inliner. The next step is to use the callsite hotness
> >>>>> instead. I
> >>>>> also
> >>>>> want to focus on the infrastructure to enable this and what
> >>>>> I've been
> >>>>> experimenting with is similar to your two alternative
> >>>>> approaches:
> >>>>>
> >>>>>> 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)
> >>>>>>
> >>>>> My proposal is very similar (perhaps identical) to your option
> >>>>> 2 above.
> >>>>> I
> >>>>> don't understand the part where you talk about adjusting the
> >>>>> visit order
> >>>>> to
> >>>>> minimize BFI computation.
> >>>>>
> >>>>> BFI computation:  BFI for a function is computed on demand and
> >>>>> cached.
> >>>> The problem here is that the old pass manager does not have a
> >>>> place/way
> >>>> to
> >>>> cache the function level analysis.  You could do this within the
> >>>> inliner
> >>>> itself, but the function passes run by the SCC pass manager will
> >>>> invalidate
> >>>> everything.  That's the problem I was trying to solve.
> >>> Easwaran's proposal does not rely on the analysis pass framework
> >>> of
> >>> the legacy pass manager -- that is the key idea. BFI info is
> >>> designed
> >>> in a way such that it can be computed on-demand.
> >>>
> >>> BFI for the caller will be incrementally updated during inlining,
> >>> but
> >>> after inlining is done for a node, the BFI info will be
> >>> explicitly
> >>> invalidated for that node due to the function passes run later by
> >>> SCC
> >>> pass manager.  This is expected.
> >> Just to make sure, you're aware this will cost at least one
> >> re-computation
> >> per iteration in CGPassManager::runOnModule right? If that's
> >> expected and
> >> acceptable, then yes, the approach you seem to be describing
> >> should be
> >> workable.
> >>
> > For each leaf node, the number of BFI computation is <= 1. For
> > other
> > nodes, it is <=2 (one as caller, one as callee) -- in other words,
> > it
> > is linear to the number of functions.
> This is not true.
> 
> In CGPassManager::runOnModule, we will iterate on the *same* SCC
> multiple times if we're making progress (i.e. devirtualizing call
> sites)
> on each iteration.  The BFI will be invalidated on each iteration.
>  This
> is caped at 4 iterations, so it's still semi linear, but only because
> there's a cap.
> 
> Examples where this might kick in:
> void bar() {};
> func_ptr foo() { return &bar; }
> void caller() {
>    func_ptr f = foo();
>    f();
> }
> 
> We will visit caller twice so that we can inline both foo and bar.
> 
> I think this iteration is okay for what your proposing - i.e. off by
> default, migration step, etc - but it's important to understand the
> implications of the planned changes.
> 

I think it will be interesting to see if this causes a net increase or decrease in compile time. Turning off inlining in regions known (suspected) to be cold should decrease compile time overall, and given that the CodeGen parts involved for large functions are really pretty expensive, I think it is still an open question how this will turn out.

 -Hal

> 
> >
> >
> >> Particularly as an intermediate step to parallelize work with the
> >> new pass
> >> manager, this sounds very much worthwhile.
> > Yes, that is exactly the intention -- it can buy pass manager
> > rework
> > more time while unlock lots of pending performance tuning work we
> > plan
> > to do.
> >
> > thanks,
> >
> > David
> >
> >
> >>>>> Update: When 'bar' gets inlined into 'foo', the BFI for 'foo'
> >>>>> is
> >>>>> updated.
> >>>>> Let OldBB in 'bar' gets cloned as NewBB in 'foo'.  NewBB's
> >>>>> block
> >>>>> frequency
> >>>>> can be incrementally computed from OldBB's block frequency,
> >>>>> entry block
> >>>>> frequency of 'bar' and the frequency of the block containing
> >>>>> the 'foo'
> >>>>> ->
> >>>>> 'bar' callsite. Even when the new CGSCC level BFI analysis is
> >>>>> in place,
> >>>>> this
> >>>>> incremental update is useful to minimize computation.
> >>>>>
> >>>>> Invalidation:  Once inlining is completed in an SCC (at the end
> >>>>> of
> >>>>> runOnSCC), the entries for functions in that SCC are
> >>>>> invalidated since
> >>>>> other
> >>>>> passes run by the CGSCC pass manager (including those run by
> >>>>> the
> >>>>> function
> >>>>> pass manager run under CGSCC pass manager) might affect the
> >>>>> computed BFI
> >>>>> for
> >>>>> the functions in the SCC.
> >>>> This sounds like you're essentially planning to extend the old
> >>>> pass
> >>>> manager
> >>>> with function level analysis support in the SCC pass manager.  I
> >>>> advise
> >>>> against this given the fact that Chandler is actively working on
> >>>> the new
> >>>> one
> >>>> and getting patches reviewed for the old one is "challenging" at
> >>>> best.
> >>>> If
> >>>> you take this approach, make sure Chandler - who is pretty much
> >>>> the only
> >>>> active reviewer in this area - is on-board with your approach
> >>>> before you
> >>>> start.
> >>> There is no plan to extend old pass manager for this capability.
> >>>  The
> >>> proposed solution is intended to work with the new pass manager
> >>> too,
> >>> so there is no conflict here. The BFI book-keeping by inliner can
> >>> be
> >>> removed with pass manager change is in place.
> >> Thanks for the clarification.
> >>
> >>> David
> >>>
> >>>
> >>>>> When the new PM infrastructure and a CGSCC based BFI analysis
> >>>>> is in
> >>>>> place,
> >>>>> the transition should be easy assuming it will provide
> >>>>> getBFI(Function
> >>>>> *)
> >>>>> and invalidateBFI(Function *) interfaces. BFI for a function is
> >>>>> computed
> >>>>> at
> >>>>> most twice in this approach. Thoughts?
> >>>>>
> >>>>>
> >>>>> Thanks,
> >>>>> Easwaran
> >>>>>
> >>>>>> _______________________________________________
> >>>>>> LLVM Developers mailing list
> >>>>>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> >>>>>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> >>>>>
> 
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
> 

-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory