<div dir="ltr">Clearly I haven't done a good job explaining my proposal. I don't propose extending the pass manager to provide function level analysis. I proposed to do something like this:<div><br></div><div><div>/// \brief Get BlockFrequencyInfo for a function.</div><div>BlockFrequencyInfo *BlockFrequencyAnalysis::getBlockFrequencyInfo(Function *F) {</div><div> // BFM is a map from Function * to BlockFrequencyInfo * and</div><div> // caches BlockFrequencyInfo *</div><div> auto Iter = BFM.find(F);</div><div> if (Iter != BFM.end()) return Iter->second;</div><div> // We need to create a BlockFrequencyInfo object for F and store it.</div><div> //</div><div> // DominatorTree, LoopInfo and BranchProbabilityInfo can be thrown<br></div><div> // away after BFI is computed.</div><div><br></div><div> // First create a dominator tree<br></div><div> DominatorTree DT;</div><div> DT.recalculate(*F);</div><div><br></div><div> // Then get a LoopInfo object</div><div> LoopInfo LI;</div><div> LI.analyze(DT);</div><div><br></div><div> // Then compute BranchProbabilityInfo</div><div> BranchProbabilityInfo BPI;</div><div> BPI.calculate(*F, LI);</div><div><br></div><div> // Finally compute BlockFrequencyInfo</div><div> BlockFrequencyInfo *BFI = new BlockFrequencyInfo;</div><div> BFI->calculate(*F, BPI, LI);</div><div> BFM[F] = BFI;</div><div> return BFI;</div><div>}</div></div><div><br></div><div><div><br></div></div><div>This recomputes all analysis needed to compute BFI and doesn't depend on the analysis framework. This is likely more computation (no benefit when a dependent analysis is preserved) and is used only by the inliner and not shared by passes like a true analysis. The invalidation needs to be done only once per function after it ceases to be a caller in inlining. Within inliner itself, the BFI data is incrementally updated.</div><div><br></div><div>Thanks,</div><div>Easwaran</div><div><br></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Dec 10, 2015 at 4:00 PM, Philip Reames <span dir="ltr"><<a href="mailto:listmail@philipreames.com" target="_blank">listmail@philipreames.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div text="#000000" bgcolor="#FFFFFF">
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. <br><span class="">
<br>
<div>On 12/07/2015 03:13 PM, Easwaran Raman
wrote:<br>
</div>
<blockquote type="cite">
<div dir="ltr">(Resending after removing <a href="mailto:llvmdev@cs.uiuc.edu" target="_blank"></a><a href="mailto:llvmdev@cs.uiuc.edu" target="_blank">llvmdev@cs.uiuc.edu</a>
and using <a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>)</div>
<div class="gmail_extra"><br>
<div class="gmail_quote">On Mon, Dec 7, 2015 at 3:08 PM,
Easwaran Raman <span dir="ltr"><<a href="mailto:eraman@google.com" target="_blank">eraman@google.com</a>></span>
wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div dir="ltr">Hi Philip,
<div><br>
</div>
<div> 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:</div>
<div class="gmail_extra"><br>
<div class="gmail_quote"><span>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><br>
Alternate Approaches:<br>
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.<br>
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)<br>
<br>
</blockquote>
<div><br>
</div>
</span>
<div>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. </div>
<div><br>
</div>
<div>BFI computation: BFI for a function is computed
on demand and cached. <br>
</div>
</div>
</div>
</div>
</blockquote>
</div>
</div>
</blockquote></span>
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. <br><span class="">
<blockquote type="cite">
<div class="gmail_extra">
<div class="gmail_quote">
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div dir="ltr">
<div class="gmail_extra">
<div class="gmail_quote">
<div><br>
</div>
<div>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. </div>
<div><br>
</div>
<div>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. <br>
</div>
</div>
</div>
</div>
</blockquote>
</div>
</div>
</blockquote></span>
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. <br><span class="">
<blockquote type="cite">
<div class="gmail_extra">
<div class="gmail_quote">
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div dir="ltr">
<div class="gmail_extra">
<div class="gmail_quote">
<div><br>
</div>
<div>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?</div>
<div><br>
</div>
<div><br>
</div>
<div>Thanks,</div>
<div>Easwaran</div>
<span>
<div> <br>
</div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:LLVMdev@cs.uiuc.edu" target="_blank">LLVMdev@cs.uiuc.edu</a> <a href="http://llvm.cs.uiuc.edu" rel="noreferrer" target="_blank"></a><a href="http://llvm.cs.uiuc.edu" target="_blank">http://llvm.cs.uiuc.edu</a><br>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" rel="noreferrer" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
</blockquote>
</span></div>
<br>
</div>
</div>
</blockquote>
</div>
<br>
</div>
</blockquote>
<br>
</span></div>
</blockquote></div><br></div>