From 86946745225096243f6969dc745267b78fc211a6 Mon Sep 17 00:00:00 2001 From: Ted Kremenek Date: Thu, 17 Jan 2008 20:48:37 +0000 Subject: [PATCH] Modified the notion of "Block-level expressions" in CFGs to include Stmt*. This is because GNU-style Statement-expressions cause the last statement in the statement-expression to act like an expression. We now have two notions: block-level statements and block-level expressions. The former are all Stmt* that appear in the list of statements in CFGBlocks. The latter is the subset of the former; these block-level statements are used as subexpressions somewhere in the AST. CFG::isBlockExpr() returns true for the latter, not the former (previously isBlockExpr() always returned true for non-Expr Stmt*). Modified the LiveVariables analysis to also track liveness state for block-level expressions (using the updated definition of block-level expressions). Modified the dataflow solver so that when it records values for block-level statements, it records the dataflow value *before* the transfer function for a Stmt* is evaluated (not after). This is more in sync in what clients will want. Modified CFGStmtVisitor to record the current block-level statement. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@46143 91177308-0d34-0410-b5e6-96231b3b80d8 --- AST/CFG.cpp | 26 +++++++++++-------- Analysis/LiveVariables.cpp | 15 ++++++++++- include/clang/AST/CFG.h | 5 ++-- .../clang/Analysis/Analyses/LiveVariables.h | 15 ++++++----- .../Analysis/FlowSensitive/DataflowSolver.h | 2 +- .../Analysis/FlowSensitive/DataflowValues.h | 4 +-- .../Analysis/Support/ExprDeclBitVector.h | 14 +++++----- .../clang/Analysis/Visitors/CFGStmtVisitor.h | 14 +++++----- 8 files changed, 58 insertions(+), 37 deletions(-) diff --git a/AST/CFG.cpp b/AST/CFG.cpp index befd84020d..7a13ac187a 100644 --- a/AST/CFG.cpp +++ b/AST/CFG.cpp @@ -988,7 +988,7 @@ void CFGBlock::reverseStmts() { std::reverse(Stmts.begin(),Stmts.end()); } //===----------------------------------------------------------------------===// namespace { - typedef llvm::DenseMap BlkExprMapTy; + typedef llvm::DenseMap BlkExprMapTy; } static BlkExprMapTy* PopulateBlkExprMap(CFG& cfg) { @@ -999,23 +999,27 @@ static BlkExprMapTy* PopulateBlkExprMap(CFG& cfg) { if (const Expr* E = dyn_cast(*BI)) { unsigned x = M->size(); (*M)[E] = x; + + // Special handling for statement expressions. The last statement + // in the statement expression is also a block-level expr. + if (const StmtExpr* S = dyn_cast(E)) { + const CompoundStmt* C = S->getSubStmt(); + if (!C->body_empty()) { + x = M->size(); + (*M)[C->body_back()] = x; + } + } } - - return M; -} -bool CFG::isBlkExpr(const Stmt* S) { - assert (S != NULL); - if (const Expr* E = dyn_cast(S)) return getBlkExprNum(E); - else return true; // Statements are by default "block-level expressions." + return M; } -CFG::BlkExprNumTy CFG::getBlkExprNum(const Expr* E) { - assert(E != NULL); +CFG::BlkExprNumTy CFG::getBlkExprNum(const Stmt* S) { + assert(S != NULL); if (!BlkExprMap) { BlkExprMap = (void*) PopulateBlkExprMap(*this); } BlkExprMapTy* M = reinterpret_cast(BlkExprMap); - BlkExprMapTy::iterator I = M->find(E); + BlkExprMapTy::iterator I = M->find(S); if (I == M->end()) return CFG::BlkExprNumTy(); else return CFG::BlkExprNumTy(I->second); diff --git a/Analysis/LiveVariables.cpp b/Analysis/LiveVariables.cpp index ff4224a06f..5bd72b42af 100644 --- a/Analysis/LiveVariables.cpp +++ b/Analysis/LiveVariables.cpp @@ -77,7 +77,16 @@ void TransferFuncs::Visit(Stmt *S) { if (AD.Observer) AD.Observer->ObserveStmt(S,AD,LiveState); - static_cast*>(this)->Visit(S); + + if (S == getCurrentBlkStmt()) { + StmtVisitor::Visit(S); + if (getCFG().isBlkExpr(S)) LiveState(S,AD) = Dead; + } + else if (!getCFG().isBlkExpr(S)) + StmtVisitor::Visit(S); + else + // For block-level expressions, mark that they are live. + LiveState(S,AD) = Alive; } void TransferFuncs::VisitDeclRefExpr(DeclRefExpr* DR) { @@ -186,6 +195,10 @@ bool LiveVariables::isLive(const ValTy& Live, const VarDecl* D) const { return Live(D,getAnalysisData()); } +bool LiveVariables::isLive(const Stmt* Loc, const Stmt* StmtVal) const { + return getStmtData(Loc)(StmtVal,getAnalysisData()); +} + //===----------------------------------------------------------------------===// // printing liveness state for debugging // diff --git a/include/clang/AST/CFG.h b/include/clang/AST/CFG.h index 90e1338643..95f9cfdb8c 100644 --- a/include/clang/AST/CFG.h +++ b/include/clang/AST/CFG.h @@ -255,9 +255,8 @@ public: operator unsigned() const { assert(Idx >=0); return (unsigned) Idx; } }; - bool isBlkExpr(const Stmt* S); - bool isBlkExpr(const Expr* E) { return getBlkExprNum(E); } - BlkExprNumTy getBlkExprNum(const Expr* E); + bool isBlkExpr(const Stmt* S) { return getBlkExprNum(S); } + BlkExprNumTy getBlkExprNum(const Stmt* S); unsigned getNumBlkExprs(); unsigned getNumBlockIDs() const { return NumBlockIDs; } diff --git a/include/clang/Analysis/Analyses/LiveVariables.h b/include/clang/Analysis/Analyses/LiveVariables.h index 9f536988a9..19e8d80029 100644 --- a/include/clang/Analysis/Analyses/LiveVariables.h +++ b/include/clang/Analysis/Analyses/LiveVariables.h @@ -30,11 +30,10 @@ struct LiveVariables_ValueTypes { // We need to keep track of both declarations and CFGBlock-level expressions, - // (so that we don't explore such expressions twice), but we only need - // liveness information for declarations (hence - // ValTy = DeclBitVector_Types::ValTy instead of - // ValTy = ExprDeclBitVector_Types::ValTy). - + // (so that we don't explore such expressions twice). We also want + // to compute liveness information for block-level expressions, since these + // act as "temporary" values. + struct AnalysisDataTy : public ExprDeclBitVector_Types::AnalysisDataTy { ObserverTy* Observer; @@ -42,7 +41,7 @@ struct LiveVariables_ValueTypes { }; // We only keep actual dataflow state for declarations. - typedef DeclBitVector_Types::ValTy ValTy; + typedef ExprDeclBitVector_Types::ValTy ValTy; //===-----------------------------------------------------===// // ObserverTy - Observer for uninitialized values queries. @@ -76,6 +75,10 @@ public: /// 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 - Returns true the block-level expression "value" is live + /// before the given block-level expression (see runOnAllBlocks). + bool isLive(const Stmt* Loc, const Stmt* StmtVal) const; /// IsLive - Return true if a variable is live according to the /// provided livness bitvector. diff --git a/include/clang/Analysis/FlowSensitive/DataflowSolver.h b/include/clang/Analysis/FlowSensitive/DataflowSolver.h index 02619f5496..24ef6bb0ba 100644 --- a/include/clang/Analysis/FlowSensitive/DataflowSolver.h +++ b/include/clang/Analysis/FlowSensitive/DataflowSolver.h @@ -236,8 +236,8 @@ private: /// ProcessBlock - Process the transfer functions for a given block. 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(); + TF.BlockStmt_Visit(const_cast(*I)); } } diff --git a/include/clang/Analysis/FlowSensitive/DataflowValues.h b/include/clang/Analysis/FlowSensitive/DataflowValues.h index be0a960149..d6427a5cab 100644 --- a/include/clang/Analysis/FlowSensitive/DataflowValues.h +++ b/include/clang/Analysis/FlowSensitive/DataflowValues.h @@ -110,9 +110,9 @@ public: /// 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. + /// this data corresponds to the point immediately before 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 + /// the point after 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."); diff --git a/include/clang/Analysis/Support/ExprDeclBitVector.h b/include/clang/Analysis/Support/ExprDeclBitVector.h index 12b93f98e6..dc634df5ed 100644 --- a/include/clang/Analysis/Support/ExprDeclBitVector.h +++ b/include/clang/Analysis/Support/ExprDeclBitVector.h @@ -139,11 +139,11 @@ struct ExprDeclBitVector_Types { void setCFG(CFG* c) { cfg = c; } CFG& getCFG() { assert(cfg && "CFG should not be NULL."); return *cfg; } - bool isTracked(const Expr* E) { return cfg->isBlkExpr(E); } + bool isTracked(const Stmt* S) { return cfg->isBlkExpr(S); } using DeclBitVector_Types::AnalysisDataTy::isTracked; - unsigned getIdx(const Expr* E) const { - CFG::BlkExprNumTy I = cfg->getBlkExprNum(E); + unsigned getIdx(const Stmt* S) const { + CFG::BlkExprNumTy I = cfg->getBlkExprNum(S); assert(I && "expression not tracked for bitvector."); return I; } @@ -187,12 +187,12 @@ struct ExprDeclBitVector_Types { } llvm::BitVector::reference - operator()(const Expr* E, const AnalysisDataTy& AD) { - return ExprBV[AD.getIdx(E)]; + operator()(const Stmt* S, const AnalysisDataTy& AD) { + return ExprBV[AD.getIdx(S)]; } const llvm::BitVector::reference - operator()(const Expr* E, const AnalysisDataTy& AD) const { - return const_cast(*this)(E,AD); + operator()(const Stmt* S, const AnalysisDataTy& AD) const { + return const_cast(*this)(S,AD); } using DeclBitVector_Types::ValTy::operator(); diff --git a/include/clang/Analysis/Visitors/CFGStmtVisitor.h b/include/clang/Analysis/Visitors/CFGStmtVisitor.h index cca2f40db4..3d55b9d416 100644 --- a/include/clang/Analysis/Visitors/CFGStmtVisitor.h +++ b/include/clang/Analysis/Visitors/CFGStmtVisitor.h @@ -33,7 +33,7 @@ static_cast(this)->BlockStmt_Visit ## CLASS(static_cast(S)); template class CFGStmtVisitor : public StmtVisitor { - Stmt* CurrentBlkExpr; + Stmt* CurrentBlkStmt; struct NullifyStmt { Stmt*& S; @@ -42,11 +42,13 @@ class CFGStmtVisitor : public StmtVisitor { ~NullifyStmt() { S = NULL; } }; -public: - CFGStmtVisitor() : CurrentBlkExpr(NULL) {} +public: + CFGStmtVisitor() : CurrentBlkStmt(NULL) {} + + Stmt* getCurrentBlkStmt() const { return CurrentBlkStmt; } RetTy Visit(Stmt* S) { - if (S == CurrentBlkExpr || + if (S == CurrentBlkStmt || !static_cast(this)->getCFG().isBlkExpr(S)) return StmtVisitor::Visit(S); else @@ -59,8 +61,8 @@ public: /// is no implementation provided for a BlockStmt_XXX method, we default /// to using StmtVisitor's Visit method. RetTy BlockStmt_Visit(Stmt* S) { - CurrentBlkExpr = S; - NullifyStmt cleanup(CurrentBlkExpr); + CurrentBlkStmt = S; + NullifyStmt cleanup(CurrentBlkStmt); switch (S->getStmtClass()) { DISPATCH_CASE(CallExpr) -- 2.40.0