[analyzer] Run remove dead bindings right before leaving a function.

This is needed to ensure that we always report issues in the correct
function. For example, leaks are identified when we call remove dead
bindings. In order to make sure we report a callee's leak in the callee,
we have to run the operation in the callee's context.

This change required quite a bit of infrastructure work since:
 - We used to only run remove dead bindings before a given statement;
here we need to run it after the last statement in the function. For
this, we added additional Program Point and special mode in the
SymbolReaper to remove all symbols in context lower than the current
one.
 - The call exit operation turned into a sequence of nodes, which are
now guarded by CallExitBegin and CallExitEnd nodes for clarity and
convenience.

(Sorry for the long diff.)

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

1 files changed, 75 insertions, 50 deletions

diff --git a/lib/StaticAnalyzer/Core/ExprEngine.cpp b/lib/StaticAnalyzer/Core/ExprEngine.cpp
index abc6316538..1fd4dcf712 100644
--- a/lib/StaticAnalyzer/Core/ExprEngine.cpp
+++ b/lib/StaticAnalyzer/Core/ExprEngine.cpp
@@ -42,8 +42,6 @@ using llvm::APSInt;
 
 STATISTIC(NumRemoveDeadBindings,
             "The # of times RemoveDeadBindings is called");
-STATISTIC(NumRemoveDeadBindingsSkipped,
-            "The # of times RemoveDeadBindings is skipped");
 STATISTIC(NumMaxBlockCountReached,
             "The # of aborted paths due to reaching the maximum block count in "
             "a top level function");
@@ -231,6 +229,7 @@ void ExprEngine::processCFGElement(const CFGElement E, ExplodedNode *Pred,
       ProcessImplicitDtor(*E.getAs<CFGImplicitDtor>(), Pred);
       return;
   }
+  currentBuilderContext = 0;
 }
 
 static bool shouldRemoveDeadBindings(AnalysisManager &AMgr,
@@ -260,62 +259,47 @@ static bool shouldRemoveDeadBindings(AnalysisManager &AMgr,
   return !PM.isConsumedExpr(cast<Expr>(S.getStmt()));
 }
 
-void ExprEngine::ProcessStmt(const CFGStmt S,
-                             ExplodedNode *Pred) {
-  // Reclaim any unnecessary nodes in the ExplodedGraph.
-  G.reclaimRecentlyAllocatedNodes();
-  
-  currentStmt = S.getStmt();
-  PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
-                                currentStmt->getLocStart(),
-                                "Error evaluating statement");
-
-  EntryNode = Pred;
-
-  ProgramStateRef EntryState = EntryNode->getState();
-  CleanedState = EntryState;
-
-  // Create the cleaned state.
-  const LocationContext *LC = EntryNode->getLocationContext();
-  SymbolReaper SymReaper(LC, currentStmt, SymMgr, getStoreManager());
-
-  if (shouldRemoveDeadBindings(AMgr, S, Pred, LC)) {
-    NumRemoveDeadBindings++;
-    getCheckerManager().runCheckersForLiveSymbols(CleanedState, SymReaper);
-
-    const StackFrameContext *SFC = LC->getCurrentStackFrame();
-
-    // Create a state in which dead bindings are removed from the environment
-    // and the store. TODO: The function should just return new env and store,
-    // not a new state.
-    CleanedState = StateMgr.removeDeadBindings(CleanedState, SFC, SymReaper);
-  } else {
-    NumRemoveDeadBindingsSkipped++;
-  }
+void ExprEngine::removeDead(ExplodedNode *Pred, ExplodedNodeSet &Out,
+                            const Stmt *ReferenceStmt,
+                            const LocationContext *LC,
+                            const Stmt *DiagnosticStmt,
+                            ProgramPoint::Kind K) {
+  assert((K == ProgramPoint::PreStmtPurgeDeadSymbolsKind ||
+          ReferenceStmt == 0) && "PreStmt is not generally supported by "
+                                 "the SymbolReaper yet");
+  NumRemoveDeadBindings++;
+  CleanedState = Pred->getState();
+  SymbolReaper SymReaper(LC, ReferenceStmt, SymMgr, getStoreManager());
+
+  getCheckerManager().runCheckersForLiveSymbols(CleanedState, SymReaper);
+
+  // Create a state in which dead bindings are removed from the environment
+  // and the store. TODO: The function should just return new env and store,
+  // not a new state.
+  const StackFrameContext *SFC = LC->getCurrentStackFrame();
+  CleanedState = StateMgr.removeDeadBindings(CleanedState, SFC, SymReaper);
 
   // Process any special transfer function for dead symbols.
-  ExplodedNodeSet Tmp;
   // A tag to track convenience transitions, which can be removed at cleanup.
   static SimpleProgramPointTag cleanupTag("ExprEngine : Clean Node");
-
   if (!SymReaper.hasDeadSymbols()) {
     // Generate a CleanedNode that has the environment and store cleaned
     // up. Since no symbols are dead, we can optimize and not clean out
     // the constraint manager.
-    StmtNodeBuilder Bldr(Pred, Tmp, *currentBuilderContext);
-    Bldr.generateNode(currentStmt, EntryNode, CleanedState, false, &cleanupTag);
+    StmtNodeBuilder Bldr(Pred, Out, *currentBuilderContext);
+    Bldr.generateNode(DiagnosticStmt, Pred, CleanedState, false, &cleanupTag,K);
 
   } else {
     // Call checkers with the non-cleaned state so that they could query the
     // values of the soon to be dead symbols.
     ExplodedNodeSet CheckedSet;
-    getCheckerManager().runCheckersForDeadSymbols(CheckedSet, EntryNode,
-                                                 SymReaper, currentStmt, *this);
+    getCheckerManager().runCheckersForDeadSymbols(CheckedSet, Pred, SymReaper,
+                                                  DiagnosticStmt, *this, K);
 
     // For each node in CheckedSet, generate CleanedNodes that have the
     // environment, the store, and the constraints cleaned up but have the
     // user-supplied states as the predecessors.
-    StmtNodeBuilder Bldr(CheckedSet, Tmp, *currentBuilderContext);
+    StmtNodeBuilder Bldr(CheckedSet, Out, *currentBuilderContext);
     for (ExplodedNodeSet::const_iterator
           I = CheckedSet.begin(), E = CheckedSet.end(); I != E; ++I) {
       ProgramStateRef CheckerState = (*I)->getState();
@@ -324,10 +308,10 @@ void ExprEngine::ProcessStmt(const CFGStmt S,
       CheckerState = getConstraintManager().removeDeadBindings(CheckerState,
                                                                SymReaper);
 
-      assert(StateMgr.haveEqualEnvironments(CheckerState, EntryState) &&
+      assert(StateMgr.haveEqualEnvironments(CheckerState, Pred->getState()) &&
         "Checkers are not allowed to modify the Environment as a part of "
         "checkDeadSymbols processing.");
-      assert(StateMgr.haveEqualStores(CheckerState, EntryState) &&
+      assert(StateMgr.haveEqualStores(CheckerState, Pred->getState()) &&
         "Checkers are not allowed to modify the Store as a part of "
         "checkDeadSymbols processing.");
 
@@ -335,13 +319,35 @@ void ExprEngine::ProcessStmt(const CFGStmt S,
       // generate a transition to that state.
       ProgramStateRef CleanedCheckerSt =
         StateMgr.getPersistentStateWithGDM(CleanedState, CheckerState);
-      Bldr.generateNode(currentStmt, *I, CleanedCheckerSt, false, &cleanupTag,
-                        ProgramPoint::PostPurgeDeadSymbolsKind);
+      Bldr.generateNode(DiagnosticStmt, *I, CleanedCheckerSt, false,
+                        &cleanupTag, K);
     }
   }
+}
+
+void ExprEngine::ProcessStmt(const CFGStmt S,
+                             ExplodedNode *Pred) {
+  // Reclaim any unnecessary nodes in the ExplodedGraph.
+  G.reclaimRecentlyAllocatedNodes();
+
+  currentStmt = S.getStmt();
+  PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
+                                currentStmt->getLocStart(),
+                                "Error evaluating statement");
 
+  // Remove dead bindings and symbols.
+  EntryNode = Pred;
+  ExplodedNodeSet CleanedStates;
+  if (shouldRemoveDeadBindings(AMgr, S, Pred, EntryNode->getLocationContext())){
+    removeDead(EntryNode, CleanedStates, currentStmt,
+               Pred->getLocationContext(), currentStmt);
+  } else
+    CleanedStates.Add(EntryNode);
+
+  // Visit the statement.
   ExplodedNodeSet Dst;
-  for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) {
+  for (ExplodedNodeSet::iterator I = CleanedStates.begin(),
+                                 E = CleanedStates.end(); I != E; ++I) {
     ExplodedNodeSet DstI;
     // Visit the statement.
     Visit(currentStmt, *I, DstI);
@@ -994,7 +1000,7 @@ bool ExprEngine::replayWithoutInlining(ExplodedNode *N,
       continue;
     // We reached the caller. Find the node right before we started
     // processing the CallExpr.
-    if (isa<PostPurgeDeadSymbols>(L))
+    if (L.isPurgeKind())
       continue;
     if (const StmtPoint *SP = dyn_cast<StmtPoint>(&L))
       if (SP->getStmt() == CalleeSF->getCallSite())
@@ -1861,10 +1867,17 @@ struct DOTGraphTraits<ExplodedNode*> :
     ProgramPoint Loc = N->getLocation();
 
     switch (Loc.getKind()) {
-      case ProgramPoint::BlockEntranceKind:
+      case ProgramPoint::BlockEntranceKind: {
         Out << "Block Entrance: B"
             << cast<BlockEntrance>(Loc).getBlock()->getBlockID();
+        if (const NamedDecl *ND =
+                    dyn_cast<NamedDecl>(Loc.getLocationContext()->getDecl())) {
+          Out << " (";
+          ND->printName(Out);
+          Out << ")";
+        }
         break;
+      }
 
       case ProgramPoint::BlockExitKind:
         assert (false);
@@ -1874,8 +1887,20 @@ struct DOTGraphTraits<ExplodedNode*> :
         Out << "CallEnter";
         break;
 
-      case ProgramPoint::CallExitKind:
-        Out << "CallExit";
+      case ProgramPoint::CallExitBeginKind:
+        Out << "CallExitBegin";
+        break;
+
+      case ProgramPoint::CallExitEndKind:
+        Out << "CallExitEnd";
+        break;
+
+      case ProgramPoint::PostStmtPurgeDeadSymbolsKind:
+        Out << "PostStmtPurgeDeadSymbols";
+        break;
+
+      case ProgramPoint::PreStmtPurgeDeadSymbolsKind:
+        Out << "PreStmtPurgeDeadSymbols";
         break;
 
       case ProgramPoint::EpsilonKind: