[analyzer] Implement "do not inline large functions many times"

performance heuristic

After inlining a function with more than 13 basic blocks 32 times, we
are not going to inline it anymore. The idea is that inlining large
functions leads to drastic performance implications. Since the function
has already been inlined, we know that we've analyzed it in many
contexts. 

The following metrics are used:
 - Large function is a function with more than 13 basic blocks (we
should switch to another metric, like cyclomatic complexity)
 - We consider that we've inlined a function many times if it's been
inlined 32 times. This number is configurable with -analyzer-config
max-times-inline-large=xx

This heuristic addresses a performance regression introduced with
inlining on one benchmark. The analyzer on this benchmark became 60
times slower with inlining turned on. The heuristic allows us to analyze
it in 24% of the time. The performance improvements on the other
benchmarks I've tested with are much lower - under 10%, which is
expected.

llvm-svn: 170361

2 files changed, 19 insertions, 2 deletions

diff --git a/clang/lib/StaticAnalyzer/Core/AnalyzerOptions.cpp b/clang/lib/StaticAnalyzer/Core/AnalyzerOptions.cpp
index 8ecbac009d3..b993804afea 100644
--- a/clang/lib/StaticAnalyzer/Core/AnalyzerOptions.cpp
+++ b/clang/lib/StaticAnalyzer/Core/AnalyzerOptions.cpp
@@ -133,6 +133,12 @@ unsigned AnalyzerOptions::getGraphTrimInterval() {
   return GraphTrimInterval.getValue();
 }
 
+unsigned AnalyzerOptions::getMaxTimesInlineLarge() {
+  if (!MaxTimesInlineLarge.hasValue())
+    MaxTimesInlineLarge = getOptionAsInteger("max-times-inline-large", 32);
+  return MaxTimesInlineLarge.getValue();
+}
+
 bool AnalyzerOptions::shouldSynthesizeBodies() {
   return getBooleanOption("faux-bodies", true);
 }
diff --git a/clang/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp b/clang/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp
index d654bb5f707..7c1c26e8f77 100644
--- a/clang/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp
+++ b/clang/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp
@@ -33,6 +33,9 @@ STATISTIC(NumOfDynamicDispatchPathSplits,
 STATISTIC(NumInlinedCalls,
   "The # of times we inlined a call");
 
+STATISTIC(NumReachedInlineCountMax,
+  "The # of times we reached inline count maximum");
+
 void ExprEngine::processCallEnter(CallEnter CE, ExplodedNode *Pred) {
   // Get the entry block in the CFG of the callee.
   const StackFrameContext *calleeCtx = CE.getCalleeContext();
@@ -415,12 +418,12 @@ bool ExprEngine::shouldInlineDecl(const Decl *D, ExplodedNode *Pred) {
   if (getContext().getLangOpts().CPlusPlus) {
     if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) {
       // Conditionally allow the inlining of template functions.
-      if (!getAnalysisManager().options.mayInlineTemplateFunctions())
+      if (!AMgr.options.mayInlineTemplateFunctions())
         if (FD->getTemplatedKind() != FunctionDecl::TK_NonTemplate)
           return false;
 
       // Conditionally allow the inlining of C++ standard library functions.
-      if (!getAnalysisManager().options.mayInlineCXXStandardLibrary())
+      if (!AMgr.options.mayInlineCXXStandardLibrary())
         if (getContext().getSourceManager().isInSystemHeader(FD->getLocation()))
           if (IsInStdNamespace(FD))
             return false;
@@ -432,6 +435,14 @@ bool ExprEngine::shouldInlineDecl(const Decl *D, ExplodedNode *Pred) {
   if (!CalleeADC->getAnalysis<RelaxedLiveVariables>())
     return false;
 
+  if (Engine.FunctionSummaries->getNumTimesInlined(D) >
+        AMgr.options.getMaxTimesInlineLarge() &&
+      CalleeCFG->getNumBlockIDs() > 13) {
+    NumReachedInlineCountMax++;
+    return false;
+  }
+  Engine.FunctionSummaries->bumpNumTimesInlined(D);
+
   return true;
 }