From 79649dfed2fc4b8cf0f7b6890df69458dbceeb04 Mon Sep 17 00:00:00 2001 From: Ted Kremenek Date: Thu, 17 Jan 2008 18:25:22 +0000 Subject: [PATCH] Added support to dataflow solver to (when requested) also record dataflow values for the block-level expressions. Modified 'LiveVariables' to provide the option to clients to record liveness information for block-level expressions (using the above feature). Modified 'DeadStores' to conform to the new interface of 'LiveVariables'. Modified 'GRConstants' to compute liveness information for block-level expressions. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@46137 91177308-0d34-0410-b5e6-96231b3b80d8 --- Analysis/DeadStores.cpp | 2 +- Analysis/GRConstants.cpp | 16 ++++----- Analysis/LiveVariables.cpp | 7 ++-- .../clang/Analysis/Analyses/LiveVariables.h | 14 +++++++- .../Analysis/FlowSensitive/DataflowSolver.h | 34 +++++++++++------- .../Analysis/FlowSensitive/DataflowValues.h | 35 ++++++++++++++++++- 6 files changed, 79 insertions(+), 29 deletions(-) diff --git a/Analysis/DeadStores.cpp b/Analysis/DeadStores.cpp index 564478d626..926109e1b2 100644 --- a/Analysis/DeadStores.cpp +++ b/Analysis/DeadStores.cpp @@ -80,7 +80,7 @@ void CheckDeadStores(CFG& cfg, ASTContext &Ctx, Diagnostic &Diags) { LiveVariables L(cfg); L.runOnCFG(cfg); DeadStoreObs A(Ctx, Diags); - L.runOnAllBlocks(cfg,A); + L.runOnAllBlocks(cfg,&A); } } // end namespace clang diff --git a/Analysis/GRConstants.cpp b/Analysis/GRConstants.cpp index 64cc199b57..75f7fa0d3e 100644 --- a/Analysis/GRConstants.cpp +++ b/Analysis/GRConstants.cpp @@ -189,6 +189,7 @@ public: cfg = &c; Liveness = new LiveVariables(c); Liveness->runOnCFG(c); + Liveness->runOnAllBlocks(c, NULL, true); } StateTy getInitialState() { @@ -274,9 +275,6 @@ void GRConstants::SwitchNodeSets() { GRConstants::StateTy GRConstants::RemoveSubExprMappings(StateTy M) { -#if 0 - return M; -#else for (StateTy::iterator I = M.begin(), E = M.end(); I!=E && I.getKey().getKind() == DSPtr::IsSubExp; ++I) { // Note: we can assign a new map to M since the iterators are @@ -286,16 +284,12 @@ GRConstants::RemoveSubExprMappings(StateTy M) { } return M; -#endif } GRConstants::StateTy GRConstants::RemoveDescendantMappings(Stmt* S, GRConstants::StateTy State, unsigned Levels) { -#if 1 - return State; -#else typedef Stmt::child_iterator iterator; for (iterator I=S->child_begin(), E=S->child_end(); I!=E; ++I) @@ -317,7 +311,6 @@ GRConstants::RemoveDescendantMappings(Stmt* S, GRConstants::StateTy State, } return State; -#endif } void GRConstants::DoStmt(Stmt* S) { @@ -357,8 +350,11 @@ void GRConstants::VisitBinSub(BinaryOperator* B) { void GRConstants::VisitBinAssign(BinaryOperator* B) { - if (DeclRefExpr* D = dyn_cast(B->getLHS()->IgnoreParens())) - AddBinding(D->getDecl(), GetBinding(B->getRHS())); + if (DeclRefExpr* D = dyn_cast(B->getLHS()->IgnoreParens())) { + ExprVariantTy V = GetBinding(B->getRHS()); + AddBinding(D->getDecl(), V); + AddBinding(B, V); + } } //===----------------------------------------------------------------------===// diff --git a/Analysis/LiveVariables.cpp b/Analysis/LiveVariables.cpp index 256b00d70d..ff4224a06f 100644 --- a/Analysis/LiveVariables.cpp +++ b/Analysis/LiveVariables.cpp @@ -165,11 +165,12 @@ void LiveVariables::runOnCFG(CFG& cfg) { } void LiveVariables::runOnAllBlocks(const CFG& cfg, - LiveVariables::ObserverTy& Obs) { + LiveVariables::ObserverTy* Obs, + bool recordStmtValues) { Solver S(*this); ObserverTy* OldObserver = getAnalysisData().Observer; - getAnalysisData().Observer = &Obs; - S.runOnAllBlocks(cfg); + getAnalysisData().Observer = Obs; + S.runOnAllBlocks(cfg, recordStmtValues); getAnalysisData().Observer = OldObserver; } diff --git a/include/clang/Analysis/Analyses/LiveVariables.h b/include/clang/Analysis/Analyses/LiveVariables.h index 33516e78aa..9f536988a9 100644 --- a/include/clang/Analysis/Analyses/LiveVariables.h +++ b/include/clang/Analysis/Analyses/LiveVariables.h @@ -70,6 +70,12 @@ public: /// IsLive - Return true if a variable is live at beginning of a /// specified block. bool isLive(const CFGBlock* B, const VarDecl* D) const; + + /// IsLive - Returns true if a variable is live at the beginning of the + /// the statement. This query only works if liveness information + /// has been recorded at the statement level (see runOnAllBlocks), and + /// only returns liveness information for block-level expressions. + bool isLive(const Stmt* S, const VarDecl* D) const; /// IsLive - Return true if a variable is live according to the /// provided livness bitvector. @@ -93,7 +99,13 @@ public: void InitializeValues(const CFG& cfg); void runOnCFG(CFG& cfg); - void runOnAllBlocks(const CFG& cfg, ObserverTy& Obs); + + /// runOnAllBlocks - Propagate the dataflow values once for each block, + /// starting from the current dataflow values. 'recordStmtValues' indicates + /// whether the method should store dataflow values per each individual + /// block-level expression. + void runOnAllBlocks(const CFG& cfg, ObserverTy* Obs, + bool recordStmtValues=false); }; } // end namespace clang diff --git a/include/clang/Analysis/FlowSensitive/DataflowSolver.h b/include/clang/Analysis/FlowSensitive/DataflowSolver.h index 12ca5b9271..02619f5496 100644 --- a/include/clang/Analysis/FlowSensitive/DataflowSolver.h +++ b/include/clang/Analysis/FlowSensitive/DataflowSolver.h @@ -140,12 +140,12 @@ public: ~DataflowSolver() {} /// runOnCFG - Computes dataflow values for all blocks in a CFG. - void runOnCFG(CFG& cfg) { + void runOnCFG(CFG& cfg, bool recordStmtValues = false) { // Set initial dataflow values and boundary conditions. D.InitializeValues(cfg); // Solve the dataflow equations. This will populate D.EdgeDataMap // with dataflow values. - SolveDataflowEquations(cfg); + SolveDataflowEquations(cfg, recordStmtValues); } /// runOnBlock - Computes dataflow values for a given block. This @@ -153,23 +153,29 @@ public: /// dataflow values using runOnCFG, as runOnBlock is intended to /// only be used for querying the dataflow values within a block /// with and Observer object. - void runOnBlock(const CFGBlock* B) { + void runOnBlock(const CFGBlock* B, bool recordStmtValues) { BlockDataMapTy& M = D.getBlockDataMap(); typename BlockDataMapTy::iterator I = M.find(B); if (I != M.end()) { TF.getVal().copyValues(I->second); - ProcessBlock(B); + ProcessBlock(B, recordStmtValues); } } - void runOnBlock(const CFGBlock& B) { runOnBlock(&B); } - void runOnBlock(CFG::iterator& I) { runOnBlock(*I); } - void runOnBlock(CFG::const_iterator& I) { runOnBlock(*I); } + void runOnBlock(const CFGBlock& B, bool recordStmtValues) { + runOnBlock(&B, recordStmtValues); + } + void runOnBlock(CFG::iterator& I, bool recordStmtValues) { + runOnBlock(*I, recordStmtValues); + } + void runOnBlock(CFG::const_iterator& I, bool recordStmtValues) { + runOnBlock(*I, recordStmtValues); + } - void runOnAllBlocks(const CFG& cfg) { + void runOnAllBlocks(const CFG& cfg, bool recordStmtValues = false) { for (CFG::const_iterator I=cfg.begin(), E=cfg.end(); I!=E; ++I) - runOnBlock(I); + runOnBlock(I, recordStmtValues); } //===----------------------------------------------------===// @@ -180,13 +186,13 @@ private: /// SolveDataflowEquations - Perform the actual worklist algorithm /// to compute dataflow values. - void SolveDataflowEquations(CFG& cfg) { + void SolveDataflowEquations(CFG& cfg, bool recordStmtValues) { EnqueueFirstBlock(cfg,AnalysisDirTag()); while (!WorkList.isEmpty()) { const CFGBlock* B = WorkList.dequeue(); ProcessMerge(cfg,B); - ProcessBlock(B); + ProcessBlock(B, recordStmtValues); UpdateEdges(cfg,B,TF.getVal()); } } @@ -228,9 +234,11 @@ private: /// ProcessBlock - Process the transfer functions for a given block. - void ProcessBlock(const CFGBlock* B) { - for (StmtItr I=ItrTraits::StmtBegin(B), E=ItrTraits::StmtEnd(B); I!=E; ++I) + void ProcessBlock(const CFGBlock* B, bool recordStmtValues) { + for (StmtItr I=ItrTraits::StmtBegin(B), E=ItrTraits::StmtEnd(B); I!=E;++I) { TF.BlockStmt_Visit(const_cast(*I)); + if (recordStmtValues) D.getStmtDataMap()[*I] = TF.getVal(); + } } /// UpdateEdges - After processing the transfer functions for a diff --git a/include/clang/Analysis/FlowSensitive/DataflowValues.h b/include/clang/Analysis/FlowSensitive/DataflowValues.h index 1604b88e30..be0a960149 100644 --- a/include/clang/Analysis/FlowSensitive/DataflowValues.h +++ b/include/clang/Analysis/FlowSensitive/DataflowValues.h @@ -50,6 +50,7 @@ public: typedef _AnalysisDirTag AnalysisDirTag; typedef llvm::DenseMap EdgeDataMapTy; typedef llvm::DenseMap BlockDataMapTy; + typedef llvm::DenseMap StmtDataMapTy; //===--------------------------------------------------------------------===// // Predicates. @@ -73,6 +74,9 @@ private: //===--------------------------------------------------------------------===// public: + DataflowValues() : StmtDataMap(NULL) {} + ~DataflowValues() { delete StmtDataMap; } + /// InitializeValues - Invoked by the solver to initialize state needed for /// dataflow analysis. This method is usually specialized by subclasses. void InitializeValues(const CFG& cfg) {}; @@ -102,7 +106,24 @@ public: const ValTy& getBlockData(const CFGBlock* B) const { return const_cast(this)->getBlockData(B); - } + } + + /// getStmtData - Retrieves the dataflow values associated with a + /// specified Stmt. If the dataflow analysis is a forward analysis, + /// this data corresponds to the point immediately after a Stmt. + /// If the analysis is a backwards analysis, it is associated with + /// the point before a Stmt. This data is only computed for block-level + /// expressions, and only when requested when the analysis is executed. + ValTy& getStmtData(const Stmt* S) { + assert (StmtDataMap && "Dataflow values were not computed for statements."); + typename StmtDataMapTy::iterator I = StmtDataMap->find(S); + assert (I != StmtDataMap->end() && "No data associated with statement."); + return I->second; + } + + const ValTy& getStmtData(const Stmt* S) const { + return const_cast(this)->getStmtData(S); + } /// getEdgeDataMap - Retrieves the internal map between CFG edges and /// dataflow values. Usually used by a dataflow solver to compute @@ -117,6 +138,17 @@ public: /// to the dataflow values at the end of the block. BlockDataMapTy& getBlockDataMap() { return BlockDataMap; } const BlockDataMapTy& getBlockDataMap() const { return BlockDataMap; } + + /// getStmtDataMap - Retrieves the internal map between Stmts and + /// dataflow values. + StmtDataMapTy& getStmtDataMap() { + if (!StmtDataMap) StmtDataMap = new StmtDataMapTy(); + return *StmtDataMap; + } + + const StmtDataMapTy& getStmtDataMap() const { + return const_cast(this)->getStmtDataMap(); + } /// getAnalysisData - Retrieves the meta data associated with a /// dataflow analysis for analyzing a particular CFG. @@ -132,6 +164,7 @@ public: protected: EdgeDataMapTy EdgeDataMap; BlockDataMapTy BlockDataMap; + StmtDataMapTy* StmtDataMap; AnalysisDataTy AnalysisData; }; -- 2.40.0