From cb48b9c9c3c95f2650b74530264c288d1f58c73c Mon Sep 17 00:00:00 2001 From: Ted Kremenek Date: Tue, 29 Jan 2008 00:33:40 +0000 Subject: [PATCH] Driver now passes the top-level FunctionDecl* to GRConstants. Refactoring: for GREngine and GRConstants, pushed references to CFG, ASTContext, and the top-level FunctionDecl into ExplodedGraphImpl. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@46475 91177308-0d34-0410-b5e6-96231b3b80d8 --- Analysis/GRConstants.cpp | 60 +++++++++---------- Analysis/GREngine.cpp | 11 ++-- Driver/ASTConsumers.cpp | 22 +++++-- include/clang/Analysis/Analyses/GRConstants.h | 2 +- .../Analysis/PathSensitive/ExplodedGraph.h | 26 +++++++- .../clang/Analysis/PathSensitive/GREngine.h | 31 ++++------ 6 files changed, 87 insertions(+), 65 deletions(-) diff --git a/Analysis/GRConstants.cpp b/Analysis/GRConstants.cpp index 196c28b5cb..f003007f65 100644 --- a/Analysis/GRConstants.cpp +++ b/Analysis/GRConstants.cpp @@ -149,7 +149,7 @@ typedef llvm::ImmutableSet APSIntSetTy; class VISIBILITY_HIDDEN ValueManager { - ASTContext* Ctx; + ASTContext& Ctx; typedef llvm::FoldingSet > APSIntSetTy; APSIntSetTy APSIntSet; @@ -157,12 +157,10 @@ class VISIBILITY_HIDDEN ValueManager { llvm::BumpPtrAllocator BPAlloc; public: - ValueManager() {} + ValueManager(ASTContext& ctx) : Ctx(ctx) {} ~ValueManager(); - void setContext(ASTContext* ctx) { Ctx = ctx; } - ASTContext* getContext() const { return Ctx; } - + ASTContext& getContext() const { return Ctx; } APSInt& getValue(const APSInt& X); }; @@ -385,8 +383,8 @@ public: assert (CastExpr->getType()->isIntegerType()); APSInt X(getValue()); - X.extOrTrunc(ValMgr.getContext()->getTypeSize(CastExpr->getType(), - CastExpr->getLocStart())); + X.extOrTrunc(ValMgr.getContext().getTypeSize(CastExpr->getType(), + CastExpr->getLocStart())); return ValMgr.getValue(X); } @@ -547,7 +545,8 @@ class VISIBILITY_HIDDEN GRConstants { public: typedef ValueMapTy StateTy; typedef GRNodeBuilder NodeBuilder; - typedef ExplodedNode NodeTy; + typedef ExplodedGraph GraphTy; + typedef GraphTy::NodeTy NodeTy; class NodeSet { typedef llvm::SmallVector ImplTy; @@ -573,6 +572,9 @@ public: }; protected: + /// G - the simulation graph. + GraphTy& G; + /// Liveness - live-variables information the ValueDecl* and block-level /// Expr* in the CFG. Used to prune out dead state. LiveVariables* Liveness; @@ -587,9 +589,6 @@ protected: /// ValueMgr - Object that manages the data for all created RValues. ValueManager ValMgr; - /// cfg - the current CFG. - CFG* cfg; - /// StmtEntryNode - The immediate predecessor node. NodeTy* StmtEntryNode; @@ -598,32 +597,29 @@ protected: bool StateCleaned; - ASTContext* getContext() const { return ValMgr.getContext(); } + ASTContext& getContext() const { return G.getContext(); } public: - GRConstants() : Liveness(NULL), Builder(NULL), cfg(NULL), - StmtEntryNode(NULL), CurrentStmt(NULL) {} + GRConstants(GraphTy& g) : G(g), Liveness(NULL), Builder(NULL), + ValMgr(G.getContext()), StmtEntryNode(NULL), CurrentStmt(NULL) { - ~GRConstants() { delete Liveness; } - - /// getCFG - Returns the CFG associated with this analysis. - CFG& getCFG() { assert (cfg); return *cfg; } - - /// Initialize - Initialize the checker's state based on the specified - /// CFG. This results in liveness information being computed for - /// each block-level statement in the CFG. - void Initialize(CFG& c, ASTContext& ctx) { - cfg = &c; - ValMgr.setContext(&ctx); + // Compute liveness information. + CFG& c = G.getCFG(); Liveness = new LiveVariables(c); Liveness->runOnCFG(c); Liveness->runOnAllBlocks(c, NULL, true); } + + ~GRConstants() { delete Liveness; } + + /// getCFG - Returns the CFG associated with this analysis. + CFG& getCFG() { return G.getCFG(); } /// getInitialState - Return the initial state used for the root vertex /// in the ExplodedGraph. StateTy getInitialState() { - return StateMgr.GetEmptyMap(); + StateTy St = StateMgr.GetEmptyMap(); + return St; } /// ProcessStmt - Called by GREngine. Used to generate new successor @@ -910,7 +906,7 @@ void GRConstants::VisitUnaryOperator(UnaryOperator* U, NonLValue R1 = cast(GetValue(St, L1)); QualType T = U->getType(); - unsigned bits = getContext()->getTypeSize(T, U->getLocStart()); + unsigned bits = getContext().getTypeSize(T, U->getLocStart()); APSInt One(llvm::APInt(bits, 1), T->isUnsignedIntegerType()); NonLValue R2 = NonLValue::GetValue(ValMgr, One); @@ -924,7 +920,7 @@ void GRConstants::VisitUnaryOperator(UnaryOperator* U, NonLValue R1 = cast(GetValue(St, L1)); QualType T = U->getType(); - unsigned bits = getContext()->getTypeSize(T, U->getLocStart()); + unsigned bits = getContext().getTypeSize(T, U->getLocStart()); APSInt One(llvm::APInt(bits, 1), T->isUnsignedIntegerType()); NonLValue R2 = NonLValue::GetValue(ValMgr, One); @@ -938,7 +934,7 @@ void GRConstants::VisitUnaryOperator(UnaryOperator* U, NonLValue R1 = cast(GetValue(St, L1)); QualType T = U->getType(); - unsigned bits = getContext()->getTypeSize(T, U->getLocStart()); + unsigned bits = getContext().getTypeSize(T, U->getLocStart()); APSInt One(llvm::APInt(bits, 1), T->isUnsignedIntegerType()); NonLValue R2 = NonLValue::GetValue(ValMgr, One); @@ -952,7 +948,7 @@ void GRConstants::VisitUnaryOperator(UnaryOperator* U, NonLValue R1 = cast(GetValue(St, L1)); QualType T = U->getType(); - unsigned bits = getContext()->getTypeSize(T, U->getLocStart()); + unsigned bits = getContext().getTypeSize(T, U->getLocStart()); APSInt One(llvm::APInt(bits, 1), T->isUnsignedIntegerType()); NonLValue R2 = NonLValue::GetValue(ValMgr, One); @@ -1235,8 +1231,8 @@ struct VISIBILITY_HIDDEN DOTGraphTraits : #endif namespace clang { -void RunGRConstants(CFG& cfg, ASTContext& Ctx) { - GREngine Engine(cfg, Ctx); +void RunGRConstants(CFG& cfg, FunctionDecl& FD, ASTContext& Ctx) { + GREngine Engine(cfg, FD, Ctx); Engine.ExecuteWorkList(); #ifndef NDEBUG llvm::ViewGraph(*Engine.getGraph().roots_begin(),"GRConstants"); diff --git a/Analysis/GREngine.cpp b/Analysis/GREngine.cpp index f0c59cf93a..65cfb24fe3 100644 --- a/Analysis/GREngine.cpp +++ b/Analysis/GREngine.cpp @@ -56,7 +56,7 @@ bool GREngineImpl::ExecuteWorkList(unsigned Steps) { if (G->num_roots() == 0) { // Initialize the analysis by constructing // the root if none exists. - CFGBlock* Entry = &cfg.getEntry(); + CFGBlock* Entry = &getCFG().getEntry(); assert (Entry->empty() && "Entry block must be empty."); @@ -69,7 +69,7 @@ bool GREngineImpl::ExecuteWorkList(unsigned Steps) { // Construct an edge representing the // starting location in the function. - BlockEdge StartLoc(cfg, Entry, Succ); + BlockEdge StartLoc(getCFG(), Entry, Succ); // Generate the root. GenerateNode(StartLoc, getInitialState()); @@ -110,9 +110,10 @@ void GREngineImpl::HandleBlockEdge(const BlockEdge& L, ExplodedNodeImpl* Pred) { CFGBlock* Blk = L.getDst(); // Check if we are entering the EXIT block. - if (Blk == &cfg.getExit()) { + if (Blk == &getCFG().getExit()) { - assert (cfg.getExit().size() == 0 && "EXIT block cannot contain Stmts."); + assert (getCFG().getExit().size() == 0 + && "EXIT block cannot contain Stmts."); // Process the final state transition. void* State = ProcessEOP(Blk, Pred->State); @@ -154,7 +155,7 @@ void GREngineImpl::HandleBlockExit(CFGBlock * B, ExplodedNodeImpl* Pred) { assert (B->succ_size() == 1 && "Blocks with no terminator should have at most 1 successor."); - GenerateNode(BlockEdge(cfg,B,*(B->succ_begin())), Pred->State, Pred); + GenerateNode(BlockEdge(getCFG(),B,*(B->succ_begin())), Pred->State, Pred); } } diff --git a/Driver/ASTConsumers.cpp b/Driver/ASTConsumers.cpp index 30c717fa50..69f344cac4 100644 --- a/Driver/ASTConsumers.cpp +++ b/Driver/ASTConsumers.cpp @@ -566,14 +566,12 @@ ASTConsumer *clang::CreateUnitValsChecker(Diagnostic &Diags) { // GRConstants - Perform intra-procedural, path-sensitive constant propagation. namespace { - class GRConstantsVisitor : public CFGVisitor { + class GRConstantsVisitor : public ASTConsumer { ASTContext* Ctx; public: - virtual void Initialize(ASTContext &Context) { Ctx = &Context; } - virtual void VisitCFG(CFG& C) { - RunGRConstants(C, *Ctx); - } + virtual void Initialize(ASTContext &Context) { Ctx = &Context; } + virtual void HandleTopLevelDecl(Decl *D); }; } // end anonymous namespace @@ -581,6 +579,20 @@ ASTConsumer* clang::CreateGRConstants() { return new GRConstantsVisitor(); } +void GRConstantsVisitor::HandleTopLevelDecl(Decl *D) { + FunctionDecl *FD = dyn_cast(D); + + if (!FD || !FD->getBody()) + return; + + DeclPrinter().PrintFunctionDeclStart(FD); + llvm::cerr << '\n'; + + CFG *C = CFG::buildCFG(FD->getBody()); + RunGRConstants(*C, *FD, *Ctx); + delete C; +} + //===----------------------------------------------------------------------===// // LLVM Emitter diff --git a/include/clang/Analysis/Analyses/GRConstants.h b/include/clang/Analysis/Analyses/GRConstants.h index 8da44b743d..3a0385e5f7 100644 --- a/include/clang/Analysis/Analyses/GRConstants.h +++ b/include/clang/Analysis/Analyses/GRConstants.h @@ -23,7 +23,7 @@ namespace clang { /// on a provided CFG. This interface will eventually be replaced with /// something more elaborate as the requirements on the interface become /// clearer. - void RunGRConstants(CFG& cfg, ASTContext& Ctx); + void RunGRConstants(CFG& cfg, FunctionDecl& FD, ASTContext& Ctx); } // end clang namespace diff --git a/include/clang/Analysis/PathSensitive/ExplodedGraph.h b/include/clang/Analysis/PathSensitive/ExplodedGraph.h index 9818095350..9545e7c0d8 100644 --- a/include/clang/Analysis/PathSensitive/ExplodedGraph.h +++ b/include/clang/Analysis/PathSensitive/ExplodedGraph.h @@ -29,7 +29,11 @@ namespace clang { class GREngineImpl; class ExplodedNodeImpl; class GRNodeBuilderImpl; +class CFG; +class ASTContext; +class FunctionDecl; + class ExplodedNodeImpl : public llvm::FoldingSetNode { protected: friend class ExplodedGraphImpl; @@ -210,6 +214,15 @@ protected: /// Allocator - BumpPtrAllocator to create nodes. llvm::BumpPtrAllocator Allocator; + + /// cfg - The CFG associated with this analysis graph. + CFG& cfg; + + /// FD - The function declaration of the function being analyzed. + FunctionDecl& FD; + + /// Ctx - The ASTContext used to "interpret" FD. + ASTContext& Ctx; /// getNodeImpl - Retrieve the node associated with a (Location,State) /// pair, where 'State' is represented as an opaque void*. This method @@ -228,12 +241,20 @@ protected: EndNodes.push_back(V); return V; } + + // ctor. + ExplodedGraphImpl(CFG& c, FunctionDecl& f, ASTContext& ctx) + : cfg(c), FD(f), Ctx(ctx) {} public: virtual ~ExplodedGraphImpl(); unsigned num_roots() const { return Roots.size(); } unsigned num_eops() const { return EndNodes.size(); } + + CFG& getCFG() { return cfg; } + ASTContext& getContext() { return Ctx; } + FunctionDecl& getFunctionDecl() { return FD; } }; template @@ -243,7 +264,7 @@ public: typedef typename CHECKER::StateTy StateTy; typedef ExplodedNode NodeTy; -protected: +protected: llvm::OwningPtr CheckerState; protected: @@ -253,7 +274,8 @@ protected: } public: - ExplodedGraph() : CheckerState(new CheckerTy()) {} + ExplodedGraph(CFG& c, FunctionDecl& fd, ASTContext& ctx) + : ExplodedGraphImpl(c, fd, ctx), CheckerState(new CheckerTy(*this)) {} /// getCheckerState - Returns the internal checker state associated /// with the exploded graph. Ownership remains with the ExplodedGraph diff --git a/include/clang/Analysis/PathSensitive/GREngine.h b/include/clang/Analysis/PathSensitive/GREngine.h index 5dcf6d7d0e..52a323dfb6 100644 --- a/include/clang/Analysis/PathSensitive/GREngine.h +++ b/include/clang/Analysis/PathSensitive/GREngine.h @@ -21,8 +21,6 @@ namespace clang { -class CFG; -class ASTContext; class GRNodeBuilderImpl; class GRWorkList; @@ -31,9 +29,6 @@ protected: friend class GRNodeBuilderImpl; typedef llvm::DenseMap ParentMapTy; - - /// cfg - The control-flow graph of the function being analyzed. - CFG& cfg; /// G - The simulation graph. Each node is a (location,state) pair. llvm::OwningPtr G; @@ -77,8 +72,7 @@ private: GREngineImpl& operator=(const GREngineImpl&); protected: - GREngineImpl(CFG& c, ExplodedGraphImpl* g, GRWorkList* wl) - : cfg(c), G(g), WList(wl) {} + GREngineImpl(ExplodedGraphImpl* g, GRWorkList* wl) : G(g), WList(wl) {} public: /// ExecuteWorkList - Run the worklist algorithm for a maximum number of @@ -86,6 +80,8 @@ public: bool ExecuteWorkList(unsigned Steps = 1000000); virtual ~GREngineImpl() {} + + CFG& getCFG() { return G->getCFG(); } }; class GRNodeBuilderImpl { @@ -108,7 +104,7 @@ public: ~GRNodeBuilderImpl(); const ExplodedGraphImpl& getGraph() const { return *Eng.G; } - + inline ExplodedNodeImpl* getLastNode() { return LastNode ? (LastNode->isInfeasible() ? NULL : LastNode) : NULL; } @@ -170,8 +166,7 @@ public: protected: // A local reference to the checker that avoids an indirect access // via the Graph. - CheckerTy* Checker; - + CheckerTy* Checker; virtual void* getInitialState() { return GRTrait::toPtr(getCheckerState().getInitialState()); @@ -196,20 +191,16 @@ protected: public: /// Construct a GREngine object to analyze the provided CFG using /// a DFS exploration of the exploded graph. - GREngine(CFG& cfg, ASTContext& Ctx) - : GREngineImpl(cfg, new GraphTy(), GRWorkList::MakeDFS()), - Checker(static_cast(G.get())->getCheckerState()) { - Checker->Initialize(cfg, Ctx); - } + GREngine(CFG& cfg, FunctionDecl& fd, ASTContext& ctx) + : GREngineImpl(new GraphTy(cfg, fd, ctx), GRWorkList::MakeDFS()), + Checker(static_cast(G.get())->getCheckerState()) {} /// Construct a GREngine object to analyze the provided CFG and to /// use the provided worklist object to execute the worklist algorithm. /// The GREngine object assumes ownership of 'wlist'. - GREngine(CFG& cfg, GRWorkList* wlist) - : GREngineImpl(cfg, new GraphTy(), wlist), - Checker(static_cast(G.get())->getCheckerState()) { - Checker->Initialize(cfg); - } + GREngine(CFG& cfg, FunctionDecl& fd, ASTContext& ctx, GRWorkList* wlist) + : GREngineImpl(new GraphTy(cfg, fd, ctx), wlist), + Checker(static_cast(G.get())->getCheckerState()) {} virtual ~GREngine() {} -- 2.40.0