From ede5a4ba111f0590879670b6cb07f4d6d0bd9075 Mon Sep 17 00:00:00 2001 From: Ted Kremenek Date: Mon, 7 Jan 2008 21:56:52 +0000 Subject: [PATCH] Added ownership of "checker state" within the ExplodedGraph. Moved code that creates the initial root node from the constructor of ReachabilityEngine to ReachabilityEngine::ExecuteWorklist. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@45722 91177308-0d34-0410-b5e6-96231b3b80d8 --- Analysis/ReachabilityEngine.cpp | 44 ++++++++++--------- .../Analysis/PathSensitive/ExplodedGraph.h | 32 ++++++++++---- .../PathSensitive/ReachabilityEngine.h | 38 +++++++++++----- 3 files changed, 76 insertions(+), 38 deletions(-) diff --git a/Analysis/ReachabilityEngine.cpp b/Analysis/ReachabilityEngine.cpp index 9893736bdc..02804b10dd 100644 --- a/Analysis/ReachabilityEngine.cpp +++ b/Analysis/ReachabilityEngine.cpp @@ -27,29 +27,14 @@ clang::reng::DFS::~DFS() {} ReachabilityEngineImpl::ReachabilityEngineImpl(CFG& c, clang::reng::WorkList* wlist) - : cfg(c), WList(wlist) { - - // Get the entry block. Make sure that it has 1 (and only 1) successor. - CFGBlock* Entry = &c.getEntry(); - assert (Entry->empty() && "Entry block must be empty."); - assert (Entry->succ_size() == 1 && "Entry block must have 1 successor."); - - // Get the first (and only) successor of Entry. - CFGBlock* Succ = *(Entry->succ_begin()); - - // Construct an edge representing the starting location in the function. - BlkBlkEdge StartLoc(Entry,Succ); - - // Create the root node. - assert (false && "FIXME soon."); -// WList->Enqueue(G->addRoot(getNode(StartLoc)); -} + : cfg(c), WList(wlist) {} -void ReachabilityEngineImpl::getNode(const ProgramEdge& Loc, void* State, - ExplodedNodeImpl* Pred) { +ExplodedNodeImpl* ReachabilityEngineImpl::getNode(const ProgramEdge& Loc, + void* State, + ExplodedNodeImpl* Pred) { bool IsNew; - ExplodedNodeImpl* V = G->getNodeImpl(Loc,State,IsNew); + ExplodedNodeImpl* V = G->getNodeImpl(Loc,State,&IsNew); // Link the node with its predecessor. V->addUntypedPredecessor(Pred); @@ -72,6 +57,8 @@ void ReachabilityEngineImpl::getNode(const ProgramEdge& Loc, void* State, } } } + + return V; } void ReachabilityEngineImpl::PopulateParentMap(Stmt* Parent) { @@ -85,6 +72,23 @@ void ReachabilityEngineImpl::PopulateParentMap(Stmt* Parent) { } bool ReachabilityEngineImpl::ExecuteWorkList(unsigned Steps) { + + // Initialize the analysis by constructing the root if none exists. + if (G->num_roots() == 0) { + // Get the entry block. Make sure that it has 1 (and only 1) successor. + CFGBlock* Entry = &cfg.getEntry(); + assert (Entry->empty() && "Entry block must be empty."); + assert (Entry->succ_size() == 1 && "Entry block must have 1 successor."); + + // Get the first (and only) successor of Entry. + CFGBlock* Succ = *(Entry->succ_begin()); + + // Construct an edge representing the starting location in the function. + BlkBlkEdge StartLoc(Entry,Succ); + + // Create the root node. + WList->Enqueue(G->addRoot(G->getNodeImpl(StartLoc,getInitialState(),NULL))); + } while (Steps && WList->hasWork()) { --Steps; diff --git a/include/clang/Analysis/PathSensitive/ExplodedGraph.h b/include/clang/Analysis/PathSensitive/ExplodedGraph.h index 6c1c83a2f5..5420a6d87a 100644 --- a/include/clang/Analysis/PathSensitive/ExplodedGraph.h +++ b/include/clang/Analysis/PathSensitive/ExplodedGraph.h @@ -20,6 +20,7 @@ #include "llvm/ADT/FoldingSet.h" #include "llvm/ADT/DenseMap.h" #include "llvm/Support/Allocator.h" +#include "llvm/ADT/OwningPtr.h" namespace clang { @@ -60,13 +61,19 @@ protected: /// pair, where 'State' is represented as an opaque void*. This method /// is intended to be used only by ReachabilityEngineImpl. virtual ExplodedNodeImpl* getNodeImpl(const ProgramEdge& L, void* State, - bool& IsNew) = 0; + bool* IsNew) = 0; /// addRoot - Add an untyped node to the set of roots. - void addRoot(ExplodedNodeImpl* V) { Roots.push_back(V); } + ExplodedNodeImpl* addRoot(ExplodedNodeImpl* V) { + Roots.push_back(V); + return V; + } /// addEndOfPath - Add an untyped node to the set of EOP nodes. - void addEndOfPath(ExplodedNodeImpl* V) { EndNodes.push_back(V); } + ExplodedNodeImpl* addEndOfPath(ExplodedNodeImpl* V) { + EndNodes.push_back(V); + return V; + } public: virtual ~ExplodedGraphImpl() {}; @@ -76,16 +83,20 @@ public: unsigned getCounter() const { return NodeCounter; } }; -template +template class ExplodedGraph : public ExplodedGraphImpl { public: - typedef STATE StateTy; - typedef ExplodedNode NodeTy; + typedef CHECKER CheckerTy; + typedef typename CHECKER::StateTy StateTy; + typedef ExplodedNode NodeTy; + +protected: + llvm::OwningPtr CheckerState; protected: virtual ExplodedNodeImpl* - getNodeImpl(const ProgramEdge& L, void* State, bool& IsNew) { - return getNode(L,ReachabilityTrait::toState(State),&IsNew); + getNodeImpl(const ProgramEdge& L, void* State, bool* IsNew) { + return getNode(L,ReachabilityTrait::toState(State),IsNew); } public: @@ -97,6 +108,11 @@ public: delete reinterpret_cast*>(I->second); } + /// getCheckerState - Returns the internal checker state associated + /// with the exploded graph. Ownership remains with the ExplodedGraph + /// objecct. + CheckerTy* getCheckerState() const { return CheckerState.get(); } + /// getNode - Retrieve the node associated with a (Location,State) pair, /// where the 'Location' is a ProgramEdge in the CFG. If no node for /// this pair exists, it is created. IsNew is set to true if diff --git a/include/clang/Analysis/PathSensitive/ReachabilityEngine.h b/include/clang/Analysis/PathSensitive/ReachabilityEngine.h index 1fced630f2..d53c7f102f 100644 --- a/include/clang/Analysis/PathSensitive/ReachabilityEngine.h +++ b/include/clang/Analysis/PathSensitive/ReachabilityEngine.h @@ -78,14 +78,22 @@ protected: // Internal methods. /// getNode - Implemented by ReachabilityEngine<> subclass. - /// Creates/fetches a node and inserts it into the graph. - virtual void getNode(const ProgramEdge& Loc, void* State, - ExplodedNodeImpl* Pred); + /// Creates/fetches a node and inserts it into the + ExplodedNodeImpl* getNode(const ProgramEdge& Loc, void* State, + ExplodedNodeImpl* Pred); - inline void getNode(const ProgramEdge& Loc, ExplodedNodeImpl* Pred) { - getNode(Loc,Pred->State,Pred); + inline ExplodedNodeImpl* getNode(const ProgramEdge& Loc, + ExplodedNodeImpl* Pred) { + + return getNode(Loc,Pred->State,Pred); } + /// getInitialState - Gets the void* representing the initial 'state' + /// of the analysis. This is simply a wrapper (implemented + /// in ReachabilityEngine) that performs type erasure on the initial + /// state returned by the checker object. + virtual void* getInitialState() = 0; + /// PopulateParentMap - Populates ParentMap starting from the specified /// expression. void PopulateParentMap(Stmt* Parent); @@ -117,13 +125,17 @@ public: template class ReachabilityEngine : public ReachabilityEngineImpl { public: - typedef CHECKER CheckerTy; + typedef CHECKER CheckerTy; typedef typename CheckerTy::StateTy StateTy; - typedef typename CheckerTy::StateManagerTy StateManagerTy; - typedef ExplodedGraph GraphTy; + typedef ExplodedGraph GraphTy; typedef typename GraphTy::NodeTy NodeTy; protected: + + virtual void* getInitialState() { + return (void*) getCheckerState()->getInitialState(); + } + virtual void ProcessEOP(CFGBlock* Blk, ExplodedNodeImpl* Pred) { assert (false && "Not implemented yet."); // FIXME: Perform dispatch to adjust state. @@ -162,9 +174,15 @@ public: /// with the ReachabilityEngine object. GraphTy* getGraph() const { return static_cast(G.get()); } - /// takeGraph - Returns the exploded graph. Ownership of the graph is + /// getCheckerState - Returns the internal checker state. Ownership is not /// transferred to the caller. - GraphTy* takeGraph() { return static_cast(G.take()); } + CheckerTy* getCheckerState() const { + return static_cast(G.get())->getCheckerState(); + } + + /// takeGraph - Returns the exploded graph. Ownership of the graph is + /// transfered to the caller. + GraphTy* takeGraph() { return static_cast(G.take()); } }; } // end clang namespace -- 2.40.0