Add "checker caching" to GRExprEngine::CheckerVisit to progressively build

a winowed list of checkers that actually do something for a given StmtClass.
As the number of checkers grows, this may potentially significantly reduce
the number of checkers called at any one time.  My own measurements show that
for the ~20 registered Checker objects, only ~5 of them respond at any one time
to a give statement.  While this isn't a net performance win right now (there
is a minor slowdown on sqlite.3) this improvement does greatly improve debugging
when stepping through the checkers used to evaluate a given statement.

git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@106884 91177308-0d34-0410-b5e6-96231b3b80d8

4 files changed, 87 insertions, 18 deletions

diff --git a/include/clang/Checker/PathSensitive/Checker.h b/include/clang/Checker/PathSensitive/Checker.h
index 034c305359..8bedd23914 100644
--- a/include/clang/Checker/PathSensitive/Checker.h
+++ b/include/clang/Checker/PathSensitive/Checker.h
@@ -38,16 +38,20 @@ class CheckerContext {
   const unsigned size;
   bool DoneEvaluating; // FIXME: This is not a permanent API change.
 public:
+  bool *respondsToCallback;
+public:
   CheckerContext(ExplodedNodeSet &dst, GRStmtNodeBuilder &builder,
                  GRExprEngine &eng, ExplodedNode *pred,
                  const void *tag, ProgramPoint::Kind K,
+                 bool *respondsToCB = 0,
                  const Stmt *stmt = 0, const GRState *st = 0)
     : Dst(dst), B(builder), Eng(eng), Pred(pred),
       OldSink(B.BuildSinks),
       OldTag(B.Tag, tag),
       OldPointKind(B.PointKind, K),
       OldHasGen(B.HasGeneratedNode),
-      ST(st), statement(stmt), size(Dst.size()) {}
+      ST(st), statement(stmt), size(Dst.size()),
+      respondsToCallback(respondsToCB) {}
 
   ~CheckerContext();
 
@@ -189,10 +193,11 @@ private:
                 GRStmtNodeBuilder &Builder,
                 GRExprEngine &Eng,
                 const Stmt *S,
-                ExplodedNode *Pred, void *tag, bool isPrevisit) {
+                ExplodedNode *Pred, void *tag, bool isPrevisit,
+                bool& respondsToCallback) {
     CheckerContext C(Dst, Builder, Eng, Pred, tag,
                      isPrevisit ? ProgramPoint::PreStmtKind :
-                     ProgramPoint::PostStmtKind, S);
+                     ProgramPoint::PostStmtKind, &respondsToCallback, S);
     if (isPrevisit)
       _PreVisit(C, S);
     else
@@ -203,7 +208,7 @@ private:
                           GRExprEngine &Eng, const ObjCMessageExpr *ME,
                           ExplodedNode *Pred, const GRState *state, void *tag) {
     CheckerContext C(Dst, Builder, Eng, Pred, tag, ProgramPoint::PostStmtKind,
-                     ME, state);
+                     0, ME, state);
     return EvalNilReceiver(C, ME);
   }
 
@@ -211,7 +216,7 @@ private:
                        GRExprEngine &Eng, const CallExpr *CE,
                        ExplodedNode *Pred, void *tag) {
     CheckerContext C(Dst, Builder, Eng, Pred, tag, ProgramPoint::PostStmtKind,
-                     CE);
+                     0, CE);
     return EvalCallExpr(C, CE);
   }
 
@@ -224,7 +229,7 @@ private:
                     bool isPrevisit) {
     CheckerContext C(Dst, Builder, Eng, Pred, tag,
                      isPrevisit ? ProgramPoint::PreStmtKind :
-                     ProgramPoint::PostStmtKind, StoreE);
+                     ProgramPoint::PostStmtKind, 0, StoreE);
     assert(isPrevisit && "Only previsit supported for now.");
     PreVisitBind(C, AssignE, StoreE, location, val);
   }
@@ -239,7 +244,7 @@ private:
                         void *tag, bool isLoad) {
     CheckerContext C(Dst, Builder, Eng, Pred, tag,
                      isLoad ? ProgramPoint::PreLoadKind :
-                     ProgramPoint::PreStoreKind, S, state);
+                     ProgramPoint::PreStoreKind, 0, S, state);
     VisitLocation(C, S, location);
   }
 
@@ -247,7 +252,7 @@ private:
                           GRExprEngine &Eng, const Stmt *S, ExplodedNode *Pred,
                           SymbolReaper &SymReaper, void *tag) {
     CheckerContext C(Dst, Builder, Eng, Pred, tag, 
-                     ProgramPoint::PostPurgeDeadSymbolsKind, S);
+                     ProgramPoint::PostPurgeDeadSymbolsKind, 0, S);
     EvalDeadSymbols(C, S, SymReaper);
   }
 
diff --git a/include/clang/Checker/PathSensitive/CheckerVisitor.h b/include/clang/Checker/PathSensitive/CheckerVisitor.h
index 72f0ae1375..e2ba89bca1 100644
--- a/include/clang/Checker/PathSensitive/CheckerVisitor.h
+++ b/include/clang/Checker/PathSensitive/CheckerVisitor.h
@@ -79,8 +79,13 @@ break;
     }
   }
 
-  void PreVisitStmt(CheckerContext &C, const Stmt *S) {}
-  void PostVisitStmt(CheckerContext &C, const Stmt *S) {}
+  void PreVisitStmt(CheckerContext &C, const Stmt *S) {
+    *C.respondsToCallback = false;
+  }
+
+  void PostVisitStmt(CheckerContext &C, const Stmt *S) {
+    *C.respondsToCallback = false;
+  }
 
   void PreVisitCastExpr(CheckerContext &C, const CastExpr *E) {
     static_cast<ImplClass*>(this)->PreVisitStmt(C, E);
diff --git a/include/clang/Checker/PathSensitive/GRExprEngine.h b/include/clang/Checker/PathSensitive/GRExprEngine.h
index cb5c0a70fc..a302ea4eb0 100644
--- a/include/clang/Checker/PathSensitive/GRExprEngine.h
+++ b/include/clang/Checker/PathSensitive/GRExprEngine.h
@@ -75,14 +75,25 @@ class GRExprEngine : public GRSubEngine {
   llvm::OwningPtr<GRSimpleAPICheck> BatchAuditor;
 
   typedef llvm::DenseMap<void *, unsigned> CheckerMap;
-  CheckerMap CheckerM;
-  
   typedef std::vector<std::pair<void *, Checker*> > CheckersOrdered;
+  typedef llvm::DenseMap<std::pair<unsigned, unsigned>, CheckersOrdered *>
+          CheckersOrderedCache;
+  
+  /// A registration map from checker tag to the index into the
+  ///  ordered checkers vector.
+  CheckerMap CheckerM;
+
+  /// An ordered vector of checkers that are called when evaluating
+  ///  various expressions and statements.
   CheckersOrdered Checkers;
 
-  /// BR - The BugReporter associated with this engine.  It is important that
-  //   this object be placed at the very end of member variables so that its
-  //   destructor is called before the rest of the GRExprEngine is destroyed.
+  /// A map used for caching the checkers that respond to the callback for
+  ///  a particular statement and visitation order.
+  CheckersOrderedCache COCache;
+
+  /// The BugReporter associated with this engine.  It is important that
+  ///  this object be placed at the very end of member variables so that its
+  ///  destructor is called before the rest of the GRExprEngine is destroyed.
   GRBugReporter BR;
   
   llvm::OwningPtr<GRTransferFuncs> TF;
diff --git a/lib/Checker/GRExprEngine.cpp b/lib/Checker/GRExprEngine.cpp
index b7b3502ccc..4c2512dfa4 100644
--- a/lib/Checker/GRExprEngine.cpp
+++ b/lib/Checker/GRExprEngine.cpp
@@ -172,13 +172,37 @@ public:
 void GRExprEngine::CheckerVisit(Stmt *S, ExplodedNodeSet &Dst,
                                 ExplodedNodeSet &Src, bool isPrevisit) {
 
-  if (Checkers.empty()) {
+  // Determine if we already have a cached 'CheckersOrdered' vector
+  // specifically tailored for the provided <Stmt kind, isPrevisit>.  This
+  // can reduce the number of checkers actually called.
+  CheckersOrdered *CO = &Checkers;
+  llvm::OwningPtr<CheckersOrdered> NewCO;
+  
+  const std::pair<unsigned, unsigned> &K =
+    std::make_pair((unsigned)S->getStmtClass(), isPrevisit ? 1U : 0U);
+
+  CheckersOrdered *& CO_Ref = COCache[K];
+  
+  if (!CO_Ref) {
+    // If we have no previously cached CheckersOrdered vector for this
+    // statement kind, then create one.
+    NewCO.reset(new CheckersOrdered);
+  }
+  else {
+    // Use the already cached set.
+    CO = CO_Ref;
+  }
+  
+  if (CO->empty()) {
+    // If there are no checkers, return early without doing any
+    // more work.
     Dst.insert(Src);
     return;
   }
 
   ExplodedNodeSet Tmp;
   ExplodedNodeSet *PrevSet = &Src;
+  unsigned checkersEvaluated = 0;
 
   for (CheckersOrdered::iterator I=Checkers.begin(),E=Checkers.end(); I!=E;++I){
     ExplodedNodeSet *CurrSet = 0;
@@ -190,12 +214,30 @@ void GRExprEngine::CheckerVisit(Stmt *S, ExplodedNodeSet &Dst,
     }
     void *tag = I->first;
     Checker *checker = I->second;
+    bool respondsToCallback = true;
 
     for (ExplodedNodeSet::iterator NI = PrevSet->begin(), NE = PrevSet->end();
-         NI != NE; ++NI)
-      checker->GR_Visit(*CurrSet, *Builder, *this, S, *NI, tag, isPrevisit);
+         NI != NE; ++NI) {
+
+      checker->GR_Visit(*CurrSet, *Builder, *this, S, *NI, tag, isPrevisit,
+                        respondsToCallback);
+      
+    }
+
     PrevSet = CurrSet;
+
+    if (NewCO.get()) {
+      ++checkersEvaluated;
+      if (respondsToCallback)
+        NewCO->push_back(*I);
+    }    
   }
+  
+  // If we built NewCO, check if we called all the checkers.  This is important
+  // so that we know that we accurately determined the entire set of checkers
+  // that responds to this callback.
+  if (NewCO.get() && checkersEvaluated == Checkers.size())
+    CO_Ref = NewCO.take();
 
   // Don't autotransition.  The CheckerContext objects should do this
   // automatically.
@@ -361,8 +403,14 @@ GRExprEngine::GRExprEngine(AnalysisManager &mgr, GRTransferFuncs *tf)
 GRExprEngine::~GRExprEngine() {
   BR.FlushReports();
   delete [] NSExceptionInstanceRaiseSelectors;
+  
+  // Delete the set of checkers.
   for (CheckersOrdered::iterator I=Checkers.begin(), E=Checkers.end(); I!=E;++I)
     delete I->second;
+  
+  for (CheckersOrderedCache::iterator I=COCache.begin(), E=COCache.end();
+       I!=E;++I)
+    delete I->second;
 }
 
 //===----------------------------------------------------------------------===//