From 50d0ac299c641bee9024f3fbae2ea0640898a040 Mon Sep 17 00:00:00 2001 From: Ted Kremenek Date: Fri, 15 Feb 2008 22:09:30 +0000 Subject: [PATCH] Simplified transfer function logic for ++/-- operators. Added more boilerplate transfer function support for pointer arithmetic. Added more pretty-printing support for symbolic constraints. Added transfer function support for handling enum values. Minor pointer types cleanup in ExplodedGraphImpl. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@47183 91177308-0d34-0410-b5e6-96231b3b80d8 --- Analysis/ExplodedGraph.cpp | 3 +- Analysis/GRExprEngine.cpp | 97 ++++++------------- Analysis/RValues.cpp | 14 ++- Analysis/ValueState.cpp | 26 ++++- .../Analysis/PathSensitive/ExplodedGraph.h | 5 +- .../Analysis/PathSensitive/GRExprEngine.h | 5 + .../Analysis/PathSensitive/GRTransferFuncs.h | 15 ++- .../clang/Analysis/PathSensitive/RValues.h | 6 +- 8 files changed, 90 insertions(+), 81 deletions(-) diff --git a/Analysis/ExplodedGraph.cpp b/Analysis/ExplodedGraph.cpp index 826162f243..ca5842656f 100644 --- a/Analysis/ExplodedGraph.cpp +++ b/Analysis/ExplodedGraph.cpp @@ -75,8 +75,7 @@ ExplodedGraphImpl::~ExplodedGraphImpl() { // of the FoldingSets are nodes allocated from the BumpPtrAllocator, // so all of those will get nuked when that object is destroyed. for (EdgeNodeSetMap::iterator I=Nodes.begin(), E=Nodes.end(); I!=E; ++I) { - llvm::FoldingSet* ENodes = - reinterpret_cast*>(I->second); + llvm::FoldingSet* ENodes = I->second; for (llvm::FoldingSet::iterator I=ENodes->begin(), E=ENodes->end(); I!=E; ++I) diff --git a/Analysis/GRExprEngine.cpp b/Analysis/GRExprEngine.cpp index 5702198b38..3cd490e330 100644 --- a/Analysis/GRExprEngine.cpp +++ b/Analysis/GRExprEngine.cpp @@ -387,8 +387,7 @@ void GRExprEngine::VisitDeclRefExpr(DeclRefExpr* D, NodeTy* Pred, NodeSet& Dst){ StateTy St = Pred->getState(); - Nodify(Dst, D, Pred, - SetValue(St, D, GetValue(St, lval::DeclVal(D->getDecl())))); + Nodify(Dst, D, Pred, SetValue(St, D, GetValue(St, D))); } void GRExprEngine::VisitCast(Expr* CastE, Expr* E, NodeTy* Pred, NodeSet& Dst) { @@ -485,51 +484,29 @@ void GRExprEngine::VisitUnaryOperator(UnaryOperator* U, NodeTy* N1 = *I1; StateTy St = N1->getState(); - switch (U->getOpcode()) { - case UnaryOperator::PostInc: { - const LValue& L1 = GetLValue(St, U->getSubExpr()); - NonLValue R1 = cast(GetValue(St, L1)); - - NonLValue Result = EvalBinaryOp(ValMgr, BinaryOperator::Add, - R1, GetRValueConstant(1U, U)); - - Nodify(Dst, U, N1, SetValue(SetValue(St, U, R1), L1, Result)); - break; - } - - case UnaryOperator::PostDec: { - const LValue& L1 = GetLValue(St, U->getSubExpr()); - NonLValue R1 = cast(GetValue(St, L1)); - - NonLValue Result = EvalBinaryOp(ValMgr, BinaryOperator::Sub, - R1, GetRValueConstant(1U, U)); - + // Handle ++ and -- (both pre- and post-increment). + + if (U->isIncrementDecrementOp()) { + const LValue& L1 = GetLValue(St, U->getSubExpr()); + RValue R1 = GetValue(St, L1); + + BinaryOperator::Opcode Op = U->isIncrementOp() ? BinaryOperator::Add + : BinaryOperator::Sub; + + RValue Result = EvalBinaryOp(ValMgr, Op, R1, GetRValueConstant(1U, U)); + + if (U->isPostfix()) Nodify(Dst, U, N1, SetValue(SetValue(St, U, R1), L1, Result)); - break; - } - - case UnaryOperator::PreInc: { - const LValue& L1 = GetLValue(St, U->getSubExpr()); - NonLValue R1 = cast(GetValue(St, L1)); - - NonLValue Result = EvalBinaryOp(ValMgr, BinaryOperator::Add, - R1, GetRValueConstant(1U, U)); - + else Nodify(Dst, U, N1, SetValue(SetValue(St, U, Result), L1, Result)); - break; - } - - case UnaryOperator::PreDec: { - const LValue& L1 = GetLValue(St, U->getSubExpr()); - NonLValue R1 = cast(GetValue(St, L1)); - NonLValue Result = EvalBinaryOp(ValMgr, BinaryOperator::Sub, - R1, GetRValueConstant(1U, U)); + continue; + } + + // Handle all other unary operators. + + switch (U->getOpcode()) { - Nodify(Dst, U, N1, SetValue(SetValue(St, U, Result), L1, Result)); - break; - } - case UnaryOperator::Minus: { const NonLValue& R1 = cast(GetValue(St, U->getSubExpr())); Nodify(Dst, U, N1, SetValue(St, U, EvalMinus(ValMgr, U, R1))); @@ -703,28 +680,7 @@ void GRExprEngine::VisitBinaryOperator(BinaryOperator* B, continue; } - if (isa(V1)) { - // FIXME: Add support for RHS being a non-lvalue. - const LValue& L1 = cast(V1); - - if (isa(V2)) { - const LValue& L2 = cast(V2); - Nodify(Dst, B, N2, SetValue(St, B, - EvalBinaryOp(ValMgr, Op, L1, L2))); - } - else { - const NonLValue& R2 = cast(V2); - Nodify(Dst, B, N2, SetValue(St, B, - EvalBinaryOp(ValMgr, Op, L1, R2))); - } - } - else { - const NonLValue& R1 = cast(V1); - const NonLValue& R2 = cast(V2); - - Nodify(Dst, B, N2, SetValue(St, B, EvalBinaryOp(ValMgr, Op, R1, R2))); - } - + Nodify(Dst, B, N2, SetValue(St, B, EvalBinaryOp(ValMgr, Op, V1, V2))); continue; } @@ -746,14 +702,17 @@ void GRExprEngine::VisitBinaryOperator(BinaryOperator* B, if (Op >= BinaryOperator::AndAssign) ((int&) Op) -= (BinaryOperator::AndAssign - BinaryOperator::And); else - ((int&) Op) -= BinaryOperator::MulAssign; + ((int&) Op) -= BinaryOperator::MulAssign; - if (isa(V2)) { - // FIXME: Add support for Non-LValues on RHS. + if (B->getType()->isPointerType()) { // Perform pointer arithmetic. + const NonLValue& R2 = cast(V2); + Result = EvalBinaryOp(ValMgr, Op, L1, R2); + } + else if (isa(V2)) { // LValue comparison. const LValue& L2 = cast(V2); Result = EvalBinaryOp(ValMgr, Op, L1, L2); } - else { + else { // Any operation between two Non-LValues. const NonLValue& R1 = cast(GetValue(N1->getState(), L1)); const NonLValue& R2 = cast(V2); Result = EvalBinaryOp(ValMgr, Op, R1, R2); diff --git a/Analysis/RValues.cpp b/Analysis/RValues.cpp index 8eb607c9e5..a9b44eb3d2 100644 --- a/Analysis/RValues.cpp +++ b/Analysis/RValues.cpp @@ -428,11 +428,23 @@ void RValue::print(std::ostream& Out) const { } static void printOpcode(std::ostream& Out, BinaryOperator::Opcode Op) { - switch (Op) { + switch (Op) { + case BinaryOperator::Mul: Out << "*"; break; + case BinaryOperator::Div: Out << "/"; break; + case BinaryOperator::Rem: Out << "%" ; break; case BinaryOperator::Add: Out << "+" ; break; case BinaryOperator::Sub: Out << "-" ; break; + case BinaryOperator::Shl: Out << "<<" ; break; + case BinaryOperator::Shr: Out << ">>" ; break; + case BinaryOperator::LT: Out << "<" ; break; + case BinaryOperator::GT: Out << ">" ; break; + case BinaryOperator::LE: Out << "<=" ; break; + case BinaryOperator::GE: Out << ">=" ; break; case BinaryOperator::EQ: Out << "=="; break; case BinaryOperator::NE: Out << "!="; break; + case BinaryOperator::And: Out << "&" ; break; + case BinaryOperator::Xor: Out << "^" ; break; + case BinaryOperator::Or: Out << "|" ; break; default: assert(false && "Not yet implemented."); } } diff --git a/Analysis/ValueState.cpp b/Analysis/ValueState.cpp index 27818efa34..9b2ed9686a 100644 --- a/Analysis/ValueState.cpp +++ b/Analysis/ValueState.cpp @@ -91,7 +91,8 @@ ValueStateManager::RemoveDeadBindings(ValueState St, Stmt* Loc, Marked.insert(V); if (V->getType()->isPointerType()) { - const LValue& LV = cast(GetValue(St, lval::DeclVal(V))); + const LValue& LV = + cast(GetValue(St, lval::DeclVal(cast(V)))); for (RValue::symbol_iterator SI=LV.symbol_begin(), SE=LV.symbol_end(); SI != SE; ++SI) @@ -205,8 +206,25 @@ RValue ValueStateManager::GetValue(ValueState St, Expr* E, bool* hasVal) { // context we assume that we are retrieving the value contained // within the referenced variables. - case Stmt::DeclRefExprClass: - return GetValue(St, lval::DeclVal(cast(E)->getDecl())); + case Stmt::DeclRefExprClass: { + ValueDecl* D = cast(E)->getDecl(); + + if (VarDecl* VD = dyn_cast(D)) + return GetValue(St, lval::DeclVal(VD)); + else if (EnumConstantDecl* ED = dyn_cast(D)) { + // FIXME: Do we need to cache a copy of this enum, since it + // already has persistent storage? We do this because we + // are comparing states using pointer equality. Perhaps there is + // a better way, since APInts are fairly lightweight. + return nonlval::ConcreteInt(ValMgr.getValue(ED->getInitVal())); + } + + assert (false && + "ValueDecl support for this ValueDecl not implemented."); + + return UnknownVal(); + } + // Integer literals evaluate to an RValue. Simply retrieve the // RValue for the literal. @@ -278,7 +296,7 @@ LValue ValueStateManager::GetLValue(ValueState St, Expr* E) { E = P->getSubExpr(); if (DeclRefExpr* DR = dyn_cast(E)) - return lval::DeclVal(DR->getDecl()); + return lval::DeclVal(cast(DR->getDecl())); if (UnaryOperator* U = dyn_cast(E)) if (U->getOpcode() == UnaryOperator::Deref) diff --git a/include/clang/Analysis/PathSensitive/ExplodedGraph.h b/include/clang/Analysis/PathSensitive/ExplodedGraph.h index 871d765bd3..b6e31b9ffe 100644 --- a/include/clang/Analysis/PathSensitive/ExplodedGraph.h +++ b/include/clang/Analysis/PathSensitive/ExplodedGraph.h @@ -203,7 +203,10 @@ protected: friend class GRSwitchNodeBuilderImpl; // Type definitions. - typedef llvm::DenseMap EdgeNodeSetMap; + typedef llvm::DenseMap*> + EdgeNodeSetMap; + typedef llvm::SmallVector RootsTy; typedef llvm::SmallVector EndNodesTy; diff --git a/include/clang/Analysis/PathSensitive/GRExprEngine.h b/include/clang/Analysis/PathSensitive/GRExprEngine.h index ffb4420965..a52a776a1d 100644 --- a/include/clang/Analysis/PathSensitive/GRExprEngine.h +++ b/include/clang/Analysis/PathSensitive/GRExprEngine.h @@ -335,5 +335,10 @@ public: LValue LHS, NonLValue RHS) { return TF->EvalBinaryOp(ValMgr, Op, LHS, RHS); } + + inline RValue EvalBinaryOp(ValueManager& ValMgr, BinaryOperator::Opcode Op, + RValue LHS, RValue RHS) { + return TF->EvalBinaryOp(ValMgr, Op, LHS, RHS); + } }; } // end clang namespace \ No newline at end of file diff --git a/include/clang/Analysis/PathSensitive/GRTransferFuncs.h b/include/clang/Analysis/PathSensitive/GRTransferFuncs.h index 87ff170372..19e87dcd94 100644 --- a/include/clang/Analysis/PathSensitive/GRTransferFuncs.h +++ b/include/clang/Analysis/PathSensitive/GRTransferFuncs.h @@ -47,12 +47,25 @@ public: BinaryOperator::Opcode Op, LValue LHS, LValue RHS); - // Pointer arithmetic. virtual LValue EvalBinaryOp(ValueManager& ValMgr, BinaryOperator::Opcode Op, LValue LHS, NonLValue RHS) = 0; + inline RValue EvalBinaryOp(ValueManager& ValMgr, BinaryOperator::Opcode Op, + const RValue& L, const RValue& R) { + + if (isa(L)) { + if (isa(R)) + return EvalBinaryOp(ValMgr, Op, cast(L), cast(R)); + else + return EvalBinaryOp(ValMgr, Op, cast(L), cast(R)); + } + else + return EvalBinaryOp(ValMgr, Op, cast(L), cast(R)); + } + + // Equality operators for LValues. virtual NonLValue EvalEQ(ValueManager& ValMgr, LValue LHS, LValue RHS) = 0; virtual NonLValue EvalNE(ValueManager& ValMgr, LValue LHS, LValue RHS) = 0; diff --git a/include/clang/Analysis/PathSensitive/RValues.h b/include/clang/Analysis/PathSensitive/RValues.h index acf841170d..319270759f 100644 --- a/include/clang/Analysis/PathSensitive/RValues.h +++ b/include/clang/Analysis/PathSensitive/RValues.h @@ -474,10 +474,10 @@ namespace lval { class DeclVal : public LValue { public: - DeclVal(const ValueDecl* vd) : LValue(DeclValKind,vd) {} + DeclVal(const VarDecl* vd) : LValue(DeclValKind, vd) {} - ValueDecl* getDecl() const { - return static_cast(Data); + VarDecl* getDecl() const { + return static_cast(Data); } inline bool operator==(const DeclVal& R) const { -- 2.40.0