From 9e5d87d568498db251de19cd3c26d02cc74bb2e1 Mon Sep 17 00:00:00 2001 From: Jakob Stoklund Olesen Date: Tue, 9 Mar 2010 22:17:11 +0000 Subject: [PATCH] Try to keep the cached inliner costs around for a bit longer for big functions. The Caller cost info would be reset everytime a callee was inlined. If the caller has lots of calls and there is some mutual recursion going on, the caller cost info could be calculated many times. This patch reduces inliner runtime from 240s to 0.5s for a function with 20000 small function calls. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@98089 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/InlineCost.h | 5 ++++ include/llvm/Transforms/IPO/InlinerPass.h | 4 +++ lib/Analysis/InlineCost.cpp | 36 +++++++++++++++++++++++ lib/Transforms/IPO/InlineAlways.cpp | 5 +++- lib/Transforms/IPO/InlineSimple.cpp | 3 ++ lib/Transforms/IPO/Inliner.cpp | 10 +++---- 6 files changed, 57 insertions(+), 6 deletions(-) diff --git a/include/llvm/Analysis/InlineCost.h b/include/llvm/Analysis/InlineCost.h index 84acd7d5fee..f0e97d7a181 100644 --- a/include/llvm/Analysis/InlineCost.h +++ b/include/llvm/Analysis/InlineCost.h @@ -179,6 +179,11 @@ namespace llvm { void resetCachedCostInfo(Function* Caller) { CachedFunctionInfo[Caller] = FunctionInfo(); } + + /// growCachedCostInfo - update the cached cost info for Caller after Callee + /// has been inlined. If Callee is NULL it means a dead call has been + /// eliminated. + void growCachedCostInfo(Function* Caller, Function* Callee); }; } diff --git a/include/llvm/Transforms/IPO/InlinerPass.h b/include/llvm/Transforms/IPO/InlinerPass.h index 30ece0eb422..c5be59a8cd7 100644 --- a/include/llvm/Transforms/IPO/InlinerPass.h +++ b/include/llvm/Transforms/IPO/InlinerPass.h @@ -75,6 +75,10 @@ struct Inliner : public CallGraphSCCPass { /// virtual void resetCachedCostInfo(Function* Caller) = 0; + /// growCachedCostInfo - update the cached cost info for Caller after Callee + /// has been inlined. + virtual void growCachedCostInfo(Function* Caller, Function* Callee) = 0; + /// removeDeadFunctions - Remove dead functions that are not included in /// DNR (Do Not Remove) list. bool removeDeadFunctions(CallGraph &CG, diff --git a/lib/Analysis/InlineCost.cpp b/lib/Analysis/InlineCost.cpp index 140e7daa6d3..09e66487c7a 100644 --- a/lib/Analysis/InlineCost.cpp +++ b/lib/Analysis/InlineCost.cpp @@ -383,3 +383,39 @@ float InlineCostAnalyzer::getInlineFudgeFactor(CallSite CS) { Factor += 1.5f; return Factor; } + +/// growCachedCostInfo - update the cached cost info for Caller after Callee has +/// been inlined. +void +InlineCostAnalyzer::growCachedCostInfo(Function* Caller, Function* Callee) { + FunctionInfo &CallerFI = CachedFunctionInfo[Caller]; + + // For small functions we prefer to recalculate the cost for better accuracy. + if (!CallerFI.Metrics.NumBlocks || CallerFI.Metrics.NumInsts < 100) { + resetCachedCostInfo(Caller); + return; + } + + // For large functions, we can save a lot of computation time by skipping + // recalculations. + if (CallerFI.Metrics.NumCalls > 0) + --CallerFI.Metrics.NumCalls; + + if (Callee) { + FunctionInfo &CalleeFI = CachedFunctionInfo[Callee]; + if (!CalleeFI.Metrics.NumBlocks) { + resetCachedCostInfo(Caller); + return; + } + CallerFI.Metrics.NeverInline |= CalleeFI.Metrics.NeverInline; + CallerFI.Metrics.usesDynamicAlloca |= CalleeFI.Metrics.usesDynamicAlloca; + + CallerFI.Metrics.NumInsts += CalleeFI.Metrics.NumInsts; + CallerFI.Metrics.NumBlocks += CalleeFI.Metrics.NumBlocks; + CallerFI.Metrics.NumCalls += CalleeFI.Metrics.NumCalls; + CallerFI.Metrics.NumVectorInsts += CalleeFI.Metrics.NumVectorInsts; + CallerFI.Metrics.NumRets += CalleeFI.Metrics.NumRets; + } + // We are not updating the argumentweights. We have already determined that + // Caller is a fairly large function, so we accept the loss of precision. +} diff --git a/lib/Transforms/IPO/InlineAlways.cpp b/lib/Transforms/IPO/InlineAlways.cpp index f11ecae8dfc..bc8028c020a 100644 --- a/lib/Transforms/IPO/InlineAlways.cpp +++ b/lib/Transforms/IPO/InlineAlways.cpp @@ -45,7 +45,10 @@ namespace { return CA.getInlineFudgeFactor(CS); } void resetCachedCostInfo(Function *Caller) { - return CA.resetCachedCostInfo(Caller); + CA.resetCachedCostInfo(Caller); + } + void growCachedCostInfo(Function* Caller, Function* Callee) { + CA.growCachedCostInfo(Caller, Callee); } virtual bool doFinalization(CallGraph &CG) { return removeDeadFunctions(CG, &NeverInline); diff --git a/lib/Transforms/IPO/InlineSimple.cpp b/lib/Transforms/IPO/InlineSimple.cpp index 598043de694..46cf4b25e42 100644 --- a/lib/Transforms/IPO/InlineSimple.cpp +++ b/lib/Transforms/IPO/InlineSimple.cpp @@ -45,6 +45,9 @@ namespace { void resetCachedCostInfo(Function *Caller) { CA.resetCachedCostInfo(Caller); } + void growCachedCostInfo(Function* Caller, Function* Callee) { + CA.growCachedCostInfo(Caller, Callee); + } virtual bool doInitialization(CallGraph &CG); }; } diff --git a/lib/Transforms/IPO/Inliner.cpp b/lib/Transforms/IPO/Inliner.cpp index 3d0309f87cf..03ec72c0304 100644 --- a/lib/Transforms/IPO/Inliner.cpp +++ b/lib/Transforms/IPO/Inliner.cpp @@ -369,6 +369,8 @@ bool Inliner::runOnSCC(std::vector &SCC) { CG[Caller]->removeCallEdgeFor(CS); CS.getInstruction()->eraseFromParent(); ++NumCallsDeleted; + // Update the cached cost info with the missing call + growCachedCostInfo(Caller, NULL); } else { // We can only inline direct calls to non-declarations. if (Callee == 0 || Callee->isDeclaration()) continue; @@ -382,6 +384,9 @@ bool Inliner::runOnSCC(std::vector &SCC) { if (!InlineCallIfPossible(CS, CG, TD, InlinedArrayAllocas)) continue; ++NumInlined; + + // Update the cached cost info with the inlined call. + growCachedCostInfo(Caller, Callee); } // If we inlined or deleted the last possible call site to the function, @@ -407,11 +412,6 @@ bool Inliner::runOnSCC(std::vector &SCC) { delete CG.removeFunctionFromModule(CalleeNode); ++NumDeleted; } - - // Remove any cached cost info for this caller, as inlining the - // callee has increased the size of the caller (which may be the - // same as the callee). - resetCachedCostInfo(Caller); // Remove this call site from the list. If possible, use // swap/pop_back for efficiency, but do not use it if doing so would -- 2.34.1