[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

6 files changed, 94 insertions, 17 deletions

diff --git a/include/clang/Analysis/ProgramPoint.h b/include/clang/Analysis/ProgramPoint.h
index aa7a33c956..377f1bc256 100644
--- a/include/clang/Analysis/ProgramPoint.h
+++ b/include/clang/Analysis/ProgramPoint.h
@@ -45,14 +45,16 @@ public:
               PostLoadKind,
               PreStoreKind,
               PostStoreKind,
-              PostPurgeDeadSymbolsKind,
+              PostStmtPurgeDeadSymbolsKind,
+              PreStmtPurgeDeadSymbolsKind,
               PostConditionKind,
               PostLValueKind,
               PostInitializerKind,
               CallEnterKind,
-              CallExitKind,
+              CallExitBeginKind,
+              CallExitEndKind,
               MinPostStmtKind = PostStmtKind,
-              MaxPostStmtKind = CallExitKind,
+              MaxPostStmtKind = CallExitEndKind,
               EpsilonKind};
 
 private:
@@ -113,6 +115,14 @@ public:
     return (Kind) x;
   }
 
+  /// \brief Is this a program point corresponding to purge/removal of dead
+  /// symbols and bindings.
+  bool isPurgeKind() {
+    Kind K = getKind();
+    return (K == PostStmtPurgeDeadSymbolsKind ||
+            K == PreStmtPurgeDeadSymbolsKind);
+  }
+
   const ProgramPointTag *getTag() const { return Tag; }
 
   const LocationContext *getLocationContext() const {
@@ -340,14 +350,29 @@ public:
   }
 };
 
-class PostPurgeDeadSymbols : public PostStmt {
+/// \class Represents a point after we ran remove dead bindings BEFORE
+/// processing the given statement.
+class PreStmtPurgeDeadSymbols : public PostStmt {
 public:
-  PostPurgeDeadSymbols(const Stmt *S, const LocationContext *L,
+  PreStmtPurgeDeadSymbols(const Stmt *S, const LocationContext *L,
                        const ProgramPointTag *tag = 0)
-    : PostStmt(S, PostPurgeDeadSymbolsKind, L, tag) {}
+    : PostStmt(S, PreStmtPurgeDeadSymbolsKind, L, tag) { }
 
   static bool classof(const ProgramPoint* Location) {
-    return Location->getKind() == PostPurgeDeadSymbolsKind;
+    return Location->getKind() == PreStmtPurgeDeadSymbolsKind;
+  }
+};
+
+/// \class Represents a point after we ran remove dead bindings AFTER
+/// processing the  given statement.
+class PostStmtPurgeDeadSymbols : public PostStmt {
+public:
+  PostStmtPurgeDeadSymbols(const Stmt *S, const LocationContext *L,
+                       const ProgramPointTag *tag = 0)
+    : PostStmt(S, PostStmtPurgeDeadSymbolsKind, L, tag) { }
+
+  static bool classof(const ProgramPoint* Location) {
+    return Location->getKind() == PostStmtPurgeDeadSymbolsKind;
   }
 };
 
@@ -383,6 +408,7 @@ public:
   }
 };
 
+/// \class Represents a point when we begin processing an inlined call.
 class CallEnter : public StmtPoint {
 public:
   CallEnter(const Stmt *stmt, const StackFrameContext *calleeCtx, 
@@ -402,14 +428,38 @@ public:
   }
 };
 
-class CallExit : public StmtPoint {
+/// \class Represents a point when we start the call exit sequence (for
+/// inlined call).
+///
+/// The call exit is simulated with a sequence of nodes, which occur between
+/// CallExitBegin and CallExitEnd. The following operations occur between the
+/// two program points:
+/// - CallExitBegin
+/// - Bind the return value
+/// - Run Remove dead bindings (to clean up the dead symbols from the callee).
+/// - CallExitEnd
+class CallExitBegin : public StmtPoint {
+public:
+  // CallExitBegin uses the callee's location context.
+  CallExitBegin(const Stmt *S, const LocationContext *L)
+    : StmtPoint(S, 0, CallExitBeginKind, L, 0) {}
+
+  static bool classof(const ProgramPoint *Location) {
+    return Location->getKind() == CallExitBeginKind;
+  }
+};
+
+/// \class Represents a point when we finish the call exit sequence (for
+/// inlined call).
+/// \sa CallExitBegin
+class CallExitEnd : public StmtPoint {
 public:
-  // CallExit uses the callee's location context.
-  CallExit(const Stmt *S, const LocationContext *L)
-    : StmtPoint(S, 0, CallExitKind, L, 0) {}
+  // CallExitEnd uses the caller's location context.
+  CallExitEnd(const Stmt *S, const LocationContext *L)
+    : StmtPoint(S, 0, CallExitEndKind, L, 0) {}
 
   static bool classof(const ProgramPoint *Location) {
-    return Location->getKind() == CallExitKind;
+    return Location->getKind() == CallExitEndKind;
   }
 };
 
diff --git a/include/clang/StaticAnalyzer/Core/BugReporter/PathDiagnostic.h b/include/clang/StaticAnalyzer/Core/BugReporter/PathDiagnostic.h
index 5a8a1c78ca..730a558b74 100644
--- a/include/clang/StaticAnalyzer/Core/BugReporter/PathDiagnostic.h
+++ b/include/clang/StaticAnalyzer/Core/BugReporter/PathDiagnostic.h
@@ -362,7 +362,7 @@ public:
 /// \brief Interface for classes constructing Stack hints.
 ///
 /// If a PathDiagnosticEvent occurs in a different frame than the final 
-/// diagnostic the hints can be used to summarise the effect of the call.
+/// diagnostic the hints can be used to summarize the effect of the call.
 class StackHintGenerator {
 public:
   virtual ~StackHintGenerator() = 0;
@@ -510,7 +510,7 @@ public:
   }
   
   static PathDiagnosticCallPiece *construct(const ExplodedNode *N,
-                                            const CallExit &CE,
+                                            const CallExitEnd &CE,
                                             const SourceManager &SM);
   
   static PathDiagnosticCallPiece *construct(PathPieces &pieces,
diff --git a/include/clang/StaticAnalyzer/Core/CheckerManager.h b/include/clang/StaticAnalyzer/Core/CheckerManager.h
index d215f992e6..252d36d69b 100644
--- a/include/clang/StaticAnalyzer/Core/CheckerManager.h
+++ b/include/clang/StaticAnalyzer/Core/CheckerManager.h
@@ -272,7 +272,8 @@ public:
   void runCheckersForDeadSymbols(ExplodedNodeSet &Dst,
                                  const ExplodedNodeSet &Src,
                                  SymbolReaper &SymReaper, const Stmt *S,
-                                 ExprEngine &Eng);
+                                 ExprEngine &Eng,
+                                 ProgramPoint::Kind K);
 
   /// \brief True if at least one checker wants to check region changes.
   bool wantsRegionChangeUpdate(ProgramStateRef state);
diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h b/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h
index f5984021d8..5bd566ff63 100644
--- a/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h
+++ b/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h
@@ -104,7 +104,7 @@ private:
   CoreEngine(const CoreEngine&); // Do not implement.
   CoreEngine& operator=(const CoreEngine&);
 
-  ExplodedNode *generateCallExitNode(ExplodedNode *N);
+  ExplodedNode *generateCallExitBeginNode(ExplodedNode *N);
 
 public:
   /// Construct a CoreEngine object to analyze the provided CFG using
diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h b/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h
index 2a21a03e9a..73f39b1bce 100644
--- a/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h
+++ b/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h
@@ -151,6 +151,25 @@ public:
   ExplodedGraph& getGraph() { return G; }
   const ExplodedGraph& getGraph() const { return G; }
 
+  /// \brief Run the analyzer's garbage collection - remove dead symbols and
+  /// bindings.
+  ///
+  /// \param Node - The predecessor node, from which the processing should 
+  /// start.
+  /// \param Out - The returned set of output nodes.
+  /// \param ReferenceStmt - Run garbage collection using the symbols, 
+  /// which are live before the given statement.
+  /// \param LC - The location context of the ReferenceStmt.
+  /// \param DiagnosticStmt - the statement used to associate the diagnostic 
+  /// message, if any warnings should occur while removing the dead (leaks 
+  /// are usually reported here).
+  /// \param K - In some cases it is possible to use PreStmt kind. (Do 
+  /// not use it unless you know what you are doing.) 
+  void removeDead(ExplodedNode *Node, ExplodedNodeSet &Out,
+            const Stmt *ReferenceStmt, const LocationContext *LC,
+            const Stmt *DiagnosticStmt,
+            ProgramPoint::Kind K = ProgramPoint::PreStmtPurgeDeadSymbolsKind);
+
   /// processCFGElement - Called by CoreEngine. Used to generate new successor
   ///  nodes by processing the 'effects' of a CFG element.
   void processCFGElement(const CFGElement E, ExplodedNode *Pred,
@@ -199,7 +218,8 @@ public:
   /// Generate the entry node of the callee.
   void processCallEnter(CallEnter CE, ExplodedNode *Pred);
 
-  /// Generate the first post callsite node.
+  /// Generate the sequence of nodes that simulate the call exit and the post
+  /// visit for CallExpr.
   void processCallExit(ExplodedNode *Pred);
 
   /// Called by CoreEngine when the analysis worklist has terminated.
diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h b/include/clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h
index 69f5e7ca6b..4d329d2f10 100644
--- a/include/clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h
+++ b/include/clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h
@@ -553,6 +553,7 @@ public:
   BasicValueFactory &getBasicVals() { return BV; }
 };
 
+/// \class A class responsible for cleaning up unused symbols.
 class SymbolReaper {
   enum SymbolStatus {
     NotProcessed,
@@ -576,6 +577,11 @@ class SymbolReaper {
   llvm::DenseMap<const MemRegion *, unsigned> includedRegionCache;
 
 public:
+  /// \brief Construct a reaper object, which removes everything which is not
+  /// live before we execute statement s in the given location context.
+  ///
+  /// If the statement is NULL, everything is this and parent contexts is
+  /// considered live.
   SymbolReaper(const LocationContext *ctx, const Stmt *s, SymbolManager& symmgr,
                StoreManager &storeMgr)
    : LCtx(ctx), Loc(s), SymMgr(symmgr), reapedStore(0, storeMgr) {}