Added "GREndPathNodeBuilder", a new node builder that will be used for

evaluating transfer functions at the end-of-path.

llvm-svn: 49561

4 files changed, 102 insertions, 15 deletions

diff --git a/clang/include/clang/Analysis/PathSensitive/ExplodedGraph.h b/clang/include/clang/Analysis/PathSensitive/ExplodedGraph.h
index 8db069639b6..0d8f31fb826 100644
--- a/clang/include/clang/Analysis/PathSensitive/ExplodedGraph.h
+++ b/clang/include/clang/Analysis/PathSensitive/ExplodedGraph.h
@@ -30,12 +30,14 @@ namespace clang {
 
 class GRCoreEngineImpl;
 class ExplodedNodeImpl;
+class CFG;
+class ASTContext;
+
 class GRStmtNodeBuilderImpl;
 class GRBranchNodeBuilderImpl;
 class GRIndirectGotoNodeBuilderImpl;
 class GRSwitchNodeBuilderImpl;
-class CFG;
-class ASTContext;
+class GREndPathNodebuilderImpl;  
 
 class ExplodedNodeImpl : public llvm::FoldingSetNode {
 protected:
@@ -45,6 +47,7 @@ protected:
   friend class GRBranchNodeBuilderImpl;
   friend class GRIndirectGotoNodeBuilderImpl;
   friend class GRSwitchNodeBuilderImpl;
+  friend class GREndPathNodeBuilderImpl;  
   
   class NodeGroup {
     enum { Size1 = 0x0, SizeOther = 0x1, AuxFlag = 0x2, Mask = 0x3 };
@@ -199,6 +202,7 @@ protected:
   friend class GRBranchNodeBuilderImpl;
   friend class GRIndirectGotoNodeBuilderImpl;
   friend class GRSwitchNodeBuilderImpl;
+  friend class GREndPathNodeBuilderImpl;
   
   // Type definitions.
   typedef llvm::SmallVector<ExplodedNodeImpl*,2>    RootsTy;
diff --git a/clang/include/clang/Analysis/PathSensitive/GRCoreEngine.h b/clang/include/clang/Analysis/PathSensitive/GRCoreEngine.h
index 5b7aeb59754..ccb217ca0aa 100644
--- a/clang/include/clang/Analysis/PathSensitive/GRCoreEngine.h
+++ b/clang/include/clang/Analysis/PathSensitive/GRCoreEngine.h
@@ -28,6 +28,7 @@ class GRStmtNodeBuilderImpl;
 class GRBranchNodeBuilderImpl;
 class GRIndirectGotoNodeBuilderImpl;
 class GRSwitchNodeBuilderImpl;
+class GREndPathNodeBuilderImpl;
 class GRWorkList;
 
 //===----------------------------------------------------------------------===//
@@ -45,6 +46,7 @@ protected:
   friend class GRBranchNodeBuilderImpl;
   friend class GRIndirectGotoNodeBuilderImpl;
   friend class GRSwitchNodeBuilderImpl;
+  friend class GREndPathNodeBuilderImpl;
   
   typedef llvm::DenseMap<Stmt*,Stmt*> ParentMapTy;
     
@@ -86,7 +88,7 @@ protected:
   void HandleBranch(Expr* Cond, Stmt* Term, CFGBlock* B,
                     ExplodedNodeImpl* Pred);  
   
-  virtual void* ProcessEOP(CFGBlock* Blk, void* State) = 0;  
+  virtual void ProcessEndPath(GREndPathNodeBuilderImpl& Builder) = 0;  
   
   virtual bool ProcessBlockEntrance(CFGBlock* Blk, void* State,
                                     GRBlockCounter BC) = 0;
@@ -487,6 +489,65 @@ public:
     return static_cast<StateTy*>(NB.getState());
   }    
 };
+  
+
+class GREndPathNodeBuilderImpl {
+  GRCoreEngineImpl& Eng;
+  CFGBlock& B;
+  ExplodedNodeImpl* Pred;  
+  bool HasGeneratedNode;
+  
+public:
+  GREndPathNodeBuilderImpl(CFGBlock* b, ExplodedNodeImpl* N,
+                           GRCoreEngineImpl* e)
+    : Eng(*e), B(*b), Pred(N), HasGeneratedNode(false) {}      
+  
+  ~GREndPathNodeBuilderImpl();
+  
+  ExplodedNodeImpl* getPredecessor() const { return Pred; }
+    
+  GRBlockCounter getBlockCounter() const { return Eng.WList->getBlockCounter();}
+  
+  unsigned getCurrentBlockCount() const {
+    return getBlockCounter().getNumVisited(B.getBlockID());
+  }  
+  
+  ExplodedNodeImpl* generateNodeImpl(void* State);
+    
+  CFGBlock* getBlock() const { return &B; }
+};
+
+
+template<typename STATE>
+class GREndPathNodeBuilder  {
+  typedef STATE                   StateTy;
+  typedef ExplodedNode<StateTy>   NodeTy;
+  
+  GREndPathNodeBuilderImpl& NB;
+  
+public:
+  GREndPathNodeBuilder(GREndPathNodeBuilderImpl& nb) : NB(nb) {}
+  
+  NodeTy* getPredecessor() const {
+    return static_cast<NodeTy*>(NB.getPredecessor());
+  }
+  
+  GRBlockCounter getBlockCounter() const {
+    return NB.getBlockCounter();
+  }  
+  
+  unsigned getCurrentBlockCount() const {
+    return NB.getCurrentBlockCount();
+  }
+  
+  StateTy* getState() const {
+    return getPredecessor()->getState();
+  }
+  
+  NodeTy* MakeNode(StateTy* St) {  
+    return static_cast<NodeTy*>(NB.generateNodeImpl(St));
+  }
+};
 
   
 template<typename SUBENGINE>
@@ -504,9 +565,9 @@ protected:
     return SubEngine.getInitialState();
   }
   
-  virtual void* ProcessEOP(CFGBlock* Blk, void* State) {
-    // FIXME: Perform dispatch to adjust state.
-    return State;
+  virtual void ProcessEndPath(GREndPathNodeBuilderImpl& BuilderImpl) {
+    GREndPathNodeBuilder<StateTy> Builder(BuilderImpl);
+    SubEngine.ProcessEndPath(Builder);
   }
   
   virtual void ProcessStmt(Stmt* S, GRStmtNodeBuilderImpl& BuilderImpl) {
diff --git a/clang/include/clang/Analysis/PathSensitive/GRExprEngine.h b/clang/include/clang/Analysis/PathSensitive/GRExprEngine.h
index 473b658b679..1c813dfd899 100644
--- a/clang/include/clang/Analysis/PathSensitive/GRExprEngine.h
+++ b/clang/include/clang/Analysis/PathSensitive/GRExprEngine.h
@@ -39,6 +39,7 @@ public:
   typedef GRBranchNodeBuilder<StateTy>        BranchNodeBuilder;
   typedef GRIndirectGotoNodeBuilder<StateTy>  IndirectGotoNodeBuilder;
   typedef GRSwitchNodeBuilder<StateTy>        SwitchNodeBuilder;
+  typedef GREndPathNodeBuilder<StateTy>       EndPathNodeBuilder;
   typedef ExplodedNodeSet<StateTy>            NodeSet;
   
     
@@ -364,6 +365,9 @@ public:
   ///  nodes by processing the 'effects' of a switch statement.
   void ProcessSwitch(SwitchNodeBuilder& builder);
   
+  /// ProcessEndPath - Called by GRCoreEngine.  Used to generate end-of-path
+  ///  nodes when the control reaches the end of a function.
+  void ProcessEndPath(EndPathNodeBuilder& builder) {}
   
   ValueStateManager& getStateManager() { return StateMgr; }
   const ValueStateManager& getStateManger() const { return StateMgr; }
diff --git a/clang/lib/Analysis/GRCoreEngine.cpp b/clang/lib/Analysis/GRCoreEngine.cpp
index 53831ed06d5..42c89270f90 100644
--- a/clang/lib/Analysis/GRCoreEngine.cpp
+++ b/clang/lib/Analysis/GRCoreEngine.cpp
@@ -124,16 +124,10 @@ void GRCoreEngineImpl::HandleBlockEdge(const BlockEdge& L,
     assert (getCFG().getExit().size() == 0 
             && "EXIT block cannot contain Stmts.");
 
-    // Process the final state transition.    
-    void* State = ProcessEOP(Blk, Pred->State);
+    // Process the final state transition.
+    GREndPathNodeBuilderImpl Builder(Blk, Pred, this);
+    ProcessEndPath(Builder);
 
-    bool IsNew;
-    ExplodedNodeImpl* Node = G->getNodeImpl(BlockEntrance(Blk), State, &IsNew);
-    Node->addPredecessor(Pred);
-    
-    // If the node was freshly created, mark it as an "End-Of-Path" node.
-    if (IsNew) G->addEndOfPath(Node); 
-    
     // This path is done. Don't enqueue any more nodes.
     return;
   }
@@ -442,3 +436,27 @@ GRSwitchNodeBuilderImpl::generateDefaultCaseNodeImpl(void* St, bool isSink) {
   
   return NULL;
 }
+
+GREndPathNodeBuilderImpl::~GREndPathNodeBuilderImpl() {
+  // Auto-generate an EOP node if one has not been generated.
+  if (!HasGeneratedNode) generateNodeImpl(Pred->State);
+}
+
+ExplodedNodeImpl* GREndPathNodeBuilderImpl::generateNodeImpl(void* State) {
+  HasGeneratedNode = true;
+    
+  bool IsNew;
+  
+  ExplodedNodeImpl* Node =
+    Eng.G->getNodeImpl(BlockEntrance(&B), Pred->State, &IsNew);
+  
+
+  Node->addPredecessor(Pred);
+  
+  if (IsNew) {
+    Node->markAsSink();
+    Eng.G->addEndOfPath(Node);
+  }
+  
+  return Node;
+}