From d763eb91aab5bdecd11825fadb35d6d8cc905f63 Mon Sep 17 00:00:00 2001 From: Ted Kremenek Date: Tue, 26 Feb 2008 02:15:56 +0000 Subject: [PATCH] Added lazy "symbolication" of parameter variables and global variables. Added recording of divide-by-zero and divide-by-uninitialized nodes. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@47586 91177308-0d34-0410-b5e6-96231b3b80d8 --- Analysis/GRExprEngine.cpp | 71 ++++++++++++++++--- Analysis/RValues.cpp | 2 +- Analysis/SymbolManager.cpp | 18 +++-- Analysis/ValueState.cpp | 10 ++- .../Analysis/PathSensitive/GRExprEngine.h | 34 ++++----- .../clang/Analysis/PathSensitive/RValues.h | 2 +- .../Analysis/PathSensitive/SymbolManager.h | 16 ++++- 7 files changed, 118 insertions(+), 35 deletions(-) diff --git a/Analysis/GRExprEngine.cpp b/Analysis/GRExprEngine.cpp index 6c363b00b3..fcbe4ccaef 100644 --- a/Analysis/GRExprEngine.cpp +++ b/Analysis/GRExprEngine.cpp @@ -396,6 +396,22 @@ void GRExprEngine::Nodify(NodeSet& Dst, Stmt* S, NodeTy* Pred, void GRExprEngine::VisitDeclRefExpr(DeclRefExpr* D, NodeTy* Pred, NodeSet& Dst){ + if (VarDecl* VD = dyn_cast(D->getDecl())) + if (VD->hasGlobalStorage() || isa(VD)) { + + StateTy StOld = Pred->getState(); + StateTy St = Symbolicate(StOld, VD); + + if (!(St == StOld)) { + if (D != CurrentStmt) + Nodify(Dst, D, Pred, St); + else + Nodify(Dst, D, Pred, SetRVal(St, D, GetRVal(St, D))); + + return; + } + } + if (D != CurrentStmt) { Dst.Add(Pred); // No-op. Simply propagate the current state unchanged. return; @@ -796,7 +812,20 @@ void GRExprEngine::VisitLVal(Expr* Ex, NodeTy* Pred, NodeSet& Dst) { Ex = Ex->IgnoreParens(); - if (isa(Ex)) { + if (DeclRefExpr* DR = dyn_cast(Ex)) { + + if (VarDecl* VD = dyn_cast(DR->getDecl())) + if (VD->hasGlobalStorage() || isa(VD)) { + + StateTy StOld = Pred->getState(); + StateTy St = Symbolicate(StOld, VD); + + if (!(St == StOld)) { + Nodify(Dst, Ex, Pred, St); + return; + } + } + Dst.Add(Pred); return; } @@ -857,20 +886,33 @@ void GRExprEngine::VisitBinaryOperator(BinaryOperator* B, if ((Op == BinaryOperator::Div || Op == BinaryOperator::Rem) && RHS->getType()->isIntegerType()) { + + // Check if the denominator is uninitialized. - // Check for divide/remaindner-by-zero. - - // First, "assume" that the denominator is 0. + if (RightV.isUninit()) { + NodeTy* DivUninit = Builder->generateNode(B, St, N2); + + if (DivUninit) { + DivUninit->markAsSink(); + BadDivides.insert(DivUninit); + } + + continue; + } + + // Check for divide/remainder-by-zero. + // + // First, "assume" that the denominator is 0 or uninitialized. bool isFeasible = false; - StateTy ZeroSt = Assume(St, RightV, false, isFeasible); + StateTy ZeroSt = Assume(St, RightV, false,isFeasible); if (isFeasible) { NodeTy* DivZeroNode = Builder->generateNode(B, ZeroSt, N2); if (DivZeroNode) { DivZeroNode->markAsSink(); - DivZeroes.insert(DivZeroNode); + BadDivides.insert(DivZeroNode); } } @@ -1003,8 +1045,19 @@ void GRExprEngine::VisitBinaryOperator(BinaryOperator* B, if ((Op == BinaryOperator::Div || Op == BinaryOperator::Rem) && RHS->getType()->isIntegerType()) { - // Check for divide/remainder-by-zero. - + // Check if the denominator is uninitialized. + + if (RightV.isUninit()) { + NodeTy* DivUninit = Builder->generateNode(B, St, N2); + + if (DivUninit) { + DivUninit->markAsSink(); + BadDivides.insert(DivUninit); + } + + continue; + } + // First, "assume" that the denominator is 0. bool isFeasible = false; @@ -1015,7 +1068,7 @@ void GRExprEngine::VisitBinaryOperator(BinaryOperator* B, if (DivZeroNode) { DivZeroNode->markAsSink(); - DivZeroes.insert(DivZeroNode); + BadDivides.insert(DivZeroNode); } } diff --git a/Analysis/RValues.cpp b/Analysis/RValues.cpp index 178d794065..bc6a75c7f7 100644 --- a/Analysis/RValues.cpp +++ b/Analysis/RValues.cpp @@ -214,7 +214,7 @@ NonLVal NonLVal::MakeIntTruthVal(ValueManager& ValMgr, bool b) { return nonlval::ConcreteInt(ValMgr.getTruthValue(b)); } -RVal RVal::GetSymbolValue(SymbolManager& SymMgr, ParmVarDecl* D) { +RVal RVal::GetSymbolValue(SymbolManager& SymMgr, VarDecl* D) { QualType T = D->getType(); diff --git a/Analysis/SymbolManager.cpp b/Analysis/SymbolManager.cpp index ced5741f44..dd71dc9d04 100644 --- a/Analysis/SymbolManager.cpp +++ b/Analysis/SymbolManager.cpp @@ -16,17 +16,24 @@ using namespace clang; -SymbolID SymbolManager::getSymbol(ParmVarDecl* D) { +SymbolID SymbolManager::getSymbol(VarDecl* D) { + + assert (isa(D) || D->hasGlobalStorage()); + SymbolID& X = DataToSymbol[getKey(D)]; if (!X.isInitialized()) { X = SymbolToData.size(); - SymbolToData.push_back(SymbolDataParmVar(D)); + + if (ParmVarDecl* VD = dyn_cast(D)) + SymbolToData.push_back(SymbolDataParmVar(VD)); + else + SymbolToData.push_back(SymbolDataGlobalVar(D)); } return X; -} - +} + SymbolID SymbolManager::getContentsOfSymbol(SymbolID sym) { SymbolID& X = DataToSymbol[getKey(sym)]; @@ -45,6 +52,9 @@ QualType SymbolData::getType(const SymbolManager& SymMgr) const { case ParmKind: return cast(this)->getDecl()->getType(); + + case GlobalKind: + return cast(this)->getDecl()->getType(); case ContentsOfKind: { SymbolID x = cast(this)->getSymbol(); diff --git a/Analysis/ValueState.cpp b/Analysis/ValueState.cpp index 75f719ae6a..03b2996b65 100644 --- a/Analysis/ValueState.cpp +++ b/Analysis/ValueState.cpp @@ -78,8 +78,16 @@ ValueStateManager::RemoveDeadBindings(ValueState St, Stmt* Loc, // Iterate over the variable bindings. for (ValueState::vb_iterator I = St.vb_begin(), E = St.vb_end(); I!=E ; ++I) - if (Liveness.isLive(Loc, I.getKey())) + if (Liveness.isLive(Loc, I.getKey())) { WList.push_back(I.getKey()); + + RVal X = I.getData(); + + for (RVal::symbol_iterator SI = X.symbol_begin(), SE = X.symbol_end(); + SI != SE; ++SI) { + MarkedSymbols.insert(*SI); + } + } // Perform the mark-and-sweep. diff --git a/include/clang/Analysis/PathSensitive/GRExprEngine.h b/include/clang/Analysis/PathSensitive/GRExprEngine.h index bc8bec78e1..a2d92f1ea6 100644 --- a/include/clang/Analysis/PathSensitive/GRExprEngine.h +++ b/include/clang/Analysis/PathSensitive/GRExprEngine.h @@ -135,9 +135,9 @@ protected: /// taking a dereference on an uninitialized value. BadDerefTy UninitDeref; - /// DivZeroes - Nodes in the ExplodedGraph that result from evaluating - /// a divide-by-zero. - DivZerosTy DivZeroes; + /// BadDivides - Nodes in the ExplodedGraph that result from evaluating + /// a divide-by-zero or divide-by-uninitialized. + DivZerosTy BadDivides; bool StateCleaned; @@ -172,20 +172,7 @@ public: /// getInitialState - Return the initial state used for the root vertex /// in the ExplodedGraph. - StateTy getInitialState() { - StateTy St = StateMgr.getInitialState(); - - // Iterate the parameters. - FunctionDecl& F = G.getFunctionDecl(); - - for (FunctionDecl::param_iterator I = F.param_begin(), E = F.param_end(); - I != E; ++I) { - St = SetRVal(St, lval::DeclVal(*I), - RVal::GetSymbolValue(SymMgr, *I)); - } - - return St; - } + StateTy getInitialState() { return StateMgr.getInitialState(); } bool isUninitControlFlow(const NodeTy* N) const { return N->isSink() && UninitBranches.count(const_cast(N)) != 0; @@ -207,6 +194,10 @@ public: return N->isSink() && UninitDeref.count(const_cast(N)) != 0; } + bool isBadDivide(const NodeTy* N) const { + return N->isSink() && BadDivides.count(const_cast(N)) != 0; + } + typedef BadDerefTy::iterator null_iterator; null_iterator null_begin() { return ExplicitNullDeref.begin(); } null_iterator null_end() { return ExplicitNullDeref.end(); } @@ -271,6 +262,15 @@ public: return StateMgr.GetLVal(St, Ex); } + StateTy Symbolicate(StateTy St, VarDecl* VD) { + lval::DeclVal X(VD); + + if (GetRVal(St, X).isUnknown()) { + return SetRVal(St, lval::DeclVal(VD), RVal::GetSymbolValue(SymMgr, VD)); + } + else return St; + } + inline NonLVal MakeConstantVal(uint64_t X, Expr* Ex) { return NonLVal::MakeVal(ValMgr, X, Ex->getType(), Ex->getLocStart()); } diff --git a/include/clang/Analysis/PathSensitive/RValues.h b/include/clang/Analysis/PathSensitive/RValues.h index f6403949c0..e43edb9253 100644 --- a/include/clang/Analysis/PathSensitive/RValues.h +++ b/include/clang/Analysis/PathSensitive/RValues.h @@ -65,7 +65,7 @@ public: return !(*this == R); } - static RVal GetSymbolValue(SymbolManager& SymMgr, ParmVarDecl *D); + static RVal GetSymbolValue(SymbolManager& SymMgr, VarDecl *D); inline bool isUnknown() const { return getRawKind() == UnknownKind; diff --git a/include/clang/Analysis/PathSensitive/SymbolManager.h b/include/clang/Analysis/PathSensitive/SymbolManager.h index d29e0e08b9..3747f54d7d 100644 --- a/include/clang/Analysis/PathSensitive/SymbolManager.h +++ b/include/clang/Analysis/PathSensitive/SymbolManager.h @@ -49,7 +49,7 @@ public: class SymbolData { public: - enum Kind { UninitKind, ParmKind, ContentsOfKind }; + enum Kind { UninitKind, ParmKind, GlobalKind, ContentsOfKind }; private: uintptr_t Data; @@ -95,6 +95,18 @@ public: return D->getKind() == ParmKind; } }; + +class SymbolDataGlobalVar : public SymbolData { +public: + SymbolDataGlobalVar(VarDecl* VD) : SymbolData(VD, GlobalKind) {} + + VarDecl* getDecl() const { return (VarDecl*) getPtr(); } + + // Implement isa support. + static inline bool classof(const SymbolData* D) { + return D->getKind() == GlobalKind; + } +}; class SymbolDataContentsOf : public SymbolData { public: @@ -157,7 +169,7 @@ public: SymbolManager(); ~SymbolManager(); - SymbolID getSymbol(ParmVarDecl* D); + SymbolID getSymbol(VarDecl* D); SymbolID getContentsOfSymbol(SymbolID sym); inline const SymbolData& getSymbolData(SymbolID ID) const { -- 2.40.0