From 1b8bd4d71c2098126041b4de4267175a82f0103c Mon Sep 17 00:00:00 2001 From: Ted Kremenek Date: Tue, 29 Apr 2008 21:04:26 +0000 Subject: [PATCH] Major rewrite/refactoring of static analysis engine. We now use EvalStore/EvalLoad to handle all loads/stores from symbolic memory, allowing us to do checks for null dereferences, etc., at any arbitrary load/store (these were missed checks before). This also resulted in some major cleanups, some conceptual, and others just in the structure of the code. This temporarily introduces a regression in the test suite (null-deref-ps.c) before I add a new LVal type for structure fields. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@50443 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../Analysis/PathSensitive/GRCoreEngine.h | 16 +- .../Analysis/PathSensitive/GRExprEngine.h | 65 +- .../clang/Analysis/PathSensitive/ValueState.h | 1 - include/clang/Analysis/ProgramPoint.h | 21 +- lib/Analysis/GRCoreEngine.cpp | 11 +- lib/Analysis/GRExprEngine.cpp | 1101 ++++++++--------- lib/Analysis/ValueState.cpp | 56 - 7 files changed, 601 insertions(+), 670 deletions(-) diff --git a/include/clang/Analysis/PathSensitive/GRCoreEngine.h b/include/clang/Analysis/PathSensitive/GRCoreEngine.h index d4074af5a9..bef2e2c0b6 100644 --- a/include/clang/Analysis/PathSensitive/GRCoreEngine.h +++ b/include/clang/Analysis/PathSensitive/GRCoreEngine.h @@ -151,12 +151,14 @@ public: } ExplodedNodeImpl* generateNodeImpl(Stmt* S, void* State, - ExplodedNodeImpl* Pred); + ExplodedNodeImpl* Pred, + bool isLoad = false); - inline ExplodedNodeImpl* generateNodeImpl(Stmt* S, void* State) { + inline ExplodedNodeImpl* generateNodeImpl(Stmt* S, void* State, + bool isLoad = false) { ExplodedNodeImpl* N = getLastNode(); assert (N && "Predecessor of new node is infeasible."); - return generateNodeImpl(S, State, N); + return generateNodeImpl(S, State, N, isLoad); } Stmt* getStmt() const { return B[Idx]; } @@ -201,14 +203,14 @@ public: return static_cast(NB.getLastNode()); } - NodeTy* generateNode(Stmt* S, StateTy* St, NodeTy* Pred) { + NodeTy* generateNode(Stmt* S, StateTy* St, NodeTy* Pred, bool isLoad = false){ HasGeneratedNode = true; - return static_cast(NB.generateNodeImpl(S, St, Pred)); + return static_cast(NB.generateNodeImpl(S, St, Pred, isLoad)); } - NodeTy* generateNode(Stmt* S, StateTy* St) { + NodeTy* generateNode(Stmt* S, StateTy* St, bool isLoad = false) { HasGeneratedNode = true; - return static_cast(NB.generateNodeImpl(S, St)); + return static_cast(NB.generateNodeImpl(S, St, isLoad)); } GRBlockCounter getBlockCounter() const { diff --git a/include/clang/Analysis/PathSensitive/GRExprEngine.h b/include/clang/Analysis/PathSensitive/GRExprEngine.h index de8807a201..7005263033 100644 --- a/include/clang/Analysis/PathSensitive/GRExprEngine.h +++ b/include/clang/Analysis/PathSensitive/GRExprEngine.h @@ -425,10 +425,6 @@ protected: return StateMgr.GetRVal(St, LV, T); } - RVal GetLVal(ValueState* St, Expr* Ex) { - return StateMgr.GetLVal(St, Ex); - } - inline NonLVal MakeConstantVal(uint64_t X, Expr* Ex) { return NonLVal::MakeVal(BasicVals, X, Ex->getType()); } @@ -474,11 +470,7 @@ protected: assert (Builder && "GRStmtNodeBuilder not present."); return Builder->MakeNode(Dst, S, Pred, St); } - - /// HandleUndefinedStore - Create the necessary sink node to represent - /// a store to an "undefined" LVal. - void HandleUndefinedStore(Stmt* S, NodeTy* Pred); - + /// Visit - Transfer function logic for all statements. Dispatches to /// other functions that handle specific kinds of statements. void Visit(Stmt* S, NodeTy* Pred, NodeSet& Dst); @@ -520,7 +512,8 @@ protected: void VisitCast(Expr* CastE, Expr* Ex, NodeTy* Pred, NodeSet& Dst); /// VisitDeclRefExpr - Transfer function logic for DeclRefExprs. - void VisitDeclRefExpr(DeclRefExpr* DR, NodeTy* Pred, NodeSet& Dst); + void VisitDeclRefExpr(DeclRefExpr* DR, NodeTy* Pred, NodeSet& Dst, + bool asLval); /// VisitDeclStmt - Transfer function logic for DeclStmts. void VisitDeclStmt(DeclStmt* DS, NodeTy* Pred, NodeSet& Dst); @@ -528,12 +521,6 @@ protected: void VisitDeclStmtAux(DeclStmt* DS, ScopedDecl* D, NodeTy* Pred, NodeSet& Dst); - void VisitDeref(UnaryOperator* U, NodeTy* Pred, NodeSet& Dst, - bool GetLVal = false); - - void VisitDeref(Expr* Ex, RVal V, ValueState* St, NodeTy* Pred, NodeSet& Dst, - bool GetLVal); - /// VisitGuardedExpr - Transfer function logic for ?, __builtin_choose void VisitGuardedExpr(Expr* Ex, Expr* L, Expr* R, NodeTy* Pred, NodeSet& Dst); @@ -543,10 +530,6 @@ protected: /// VisitMemberExpr - Transfer function for member expressions. void VisitMemberExpr(MemberExpr* M, NodeTy* Pred, NodeSet& Dst, bool asLVal); - void VisitMemberExprField(MemberExpr* M, Expr* Base, NodeTy* Pred, - NodeSet& Dst, bool asLVal); - - /// VisitObjCMessageExpr - Transfer function for ObjC message expressions. void VisitObjCMessageExpr(ObjCMessageExpr* ME, NodeTy* Pred, NodeSet& Dst); @@ -564,15 +547,12 @@ protected: /// VisitSizeOfAlignOfTypeExpr - Transfer function for sizeof(type). void VisitSizeOfAlignOfTypeExpr(SizeOfAlignOfTypeExpr* Ex, NodeTy* Pred, NodeSet& Dst); - - // VisitSizeOfExpr - Transfer function for sizeof(expr). - void VisitSizeOfExpr(UnaryOperator* U, NodeTy* Pred, NodeSet& Dst); - + /// VisitUnaryOperator - Transfer function logic for unary operators. - void VisitUnaryOperator(UnaryOperator* B, NodeTy* Pred, NodeSet& Dst); - - - + void VisitUnaryOperator(UnaryOperator* B, NodeTy* Pred, NodeSet& Dst, + bool asLVal); + + bool CheckDivideZero(Expr* Ex, ValueState* St, NodeTy* Pred, RVal Denom); RVal EvalCast(RVal X, QualType CastT) { if (X.isUnknownOrUndef()) @@ -584,8 +564,6 @@ protected: return TF->EvalCast(*this, cast(X), CastT); } - - RVal EvalMinus(UnaryOperator* U, RVal X) { return X.isValid() ? TF->EvalMinus(*this, U, cast(X)) : X; } @@ -603,27 +581,27 @@ protected: } RVal EvalBinOp(BinaryOperator::Opcode Op, RVal L, RVal R) { - + if (L.isUndef() || R.isUndef()) return UndefinedVal(); - + if (L.isUnknown() || R.isUnknown()) return UnknownVal(); - + if (isa(L)) { if (isa(R)) return TF->EvalBinOp(*this, Op, cast(L), cast(R)); else return TF->EvalBinOp(*this, Op, cast(L), cast(R)); } - + if (isa(R)) { // Support pointer arithmetic where the increment/decrement operand // is on the left and the pointer on the right. - + assert (Op == BinaryOperator::Add || Op == BinaryOperator::Sub); - // Commute the operands. + // Commute the operands. return TF->EvalBinOp(*this, Op, cast(R), cast(L)); } else @@ -631,11 +609,11 @@ protected: } void EvalCall(NodeSet& Dst, CallExpr* CE, RVal L, NodeTy* Pred) { - assert (Builder && "GRStmtNodeBuilder must be defined."); + assert (Builder && "GRStmtNodeBuilder must be defined."); TF->EvalCall(Dst, *this, *Builder, CE, L, Pred); } - void EvalObjCMessageExpr(NodeSet& Dst, ObjCMessageExpr* ME, NodeTy* Pred) { + void EvalObjCMessageExpr(NodeSet& Dst, ObjCMessageExpr* ME, NodeTy* Pred) { assert (Builder && "GRStmtNodeBuilder must be defined."); TF->EvalObjCMessageExpr(Dst, *this, *Builder, ME, Pred); } @@ -643,7 +621,16 @@ protected: void EvalStore(NodeSet& Dst, Expr* E, NodeTy* Pred, ValueState* St, RVal TargetLV, RVal Val); - void EvalReturn(NodeSet& Dst, ReturnStmt* s, NodeTy* Pred); + // FIXME: The "CheckOnly" option exists only because Array and Field + // loads aren't fully implemented. Eventually this option will go away. + + void EvalLoad(NodeSet& Dst, Expr* Ex, NodeTy* Pred, + ValueState* St, RVal location, bool CheckOnly = false); + + ValueState* EvalLocation(Expr* Ex, NodeTy* Pred, + ValueState* St, RVal location, bool isLoad = false); + + void EvalReturn(NodeSet& Dst, ReturnStmt* s, NodeTy* Pred); ValueState* MarkBranch(ValueState* St, Stmt* Terminator, bool branchTaken); }; diff --git a/include/clang/Analysis/PathSensitive/ValueState.h b/include/clang/Analysis/PathSensitive/ValueState.h index 5e287b23b0..a4133085a8 100644 --- a/include/clang/Analysis/PathSensitive/ValueState.h +++ b/include/clang/Analysis/PathSensitive/ValueState.h @@ -242,7 +242,6 @@ public: RVal GetRVal(ValueState* St, Expr* E); RVal GetRVal(ValueState* St, LVal LV, QualType T = QualType()); - RVal GetLVal(ValueState* St, Expr* E); RVal GetBlkExprRVal(ValueState* St, Expr* Ex); diff --git a/include/clang/Analysis/ProgramPoint.h b/include/clang/Analysis/ProgramPoint.h index 5fc1fb651b..efd16b416d 100644 --- a/include/clang/Analysis/ProgramPoint.h +++ b/include/clang/Analysis/ProgramPoint.h @@ -25,8 +25,9 @@ namespace clang { class ProgramPoint { public: - enum Kind { BlockEntranceKind=0, PostStmtKind=1, BlockExitKind=2, - BlockEdgeSrcKind=3, BlockEdgeDstKind=4, BlockEdgeAuxKind=5 }; + enum Kind { BlockEntranceKind=0, PostStmtKind=1, PostLoadKind=2, + BlockExitKind=3, BlockEdgeSrcKind=4, BlockEdgeDstKind=5, + BlockEdgeAuxKind=6 }; protected: uintptr_t Data; @@ -100,13 +101,25 @@ public: class PostStmt : public ProgramPoint { +protected: + PostStmt(const Stmt* S, Kind k) : ProgramPoint(S, k) {} public: PostStmt(const Stmt* S) : ProgramPoint(S, PostStmtKind) {} - + Stmt* getStmt() const { return (Stmt*) getRawPtr(); } static bool classof(const ProgramPoint* Location) { - return Location->getKind() == PostStmtKind; + unsigned k = Location->getKind(); + return k == PostStmtKind || k == PostLoadKind; + } +}; + +class PostLoad : public PostStmt { +public: + PostLoad(const Stmt* S) : PostStmt(S, PostLoadKind) {} + + static bool classof(const ProgramPoint* Location) { + return Location->getKind() == PostLoadKind; } }; diff --git a/lib/Analysis/GRCoreEngine.cpp b/lib/Analysis/GRCoreEngine.cpp index c2b8c115fd..05f9303856 100644 --- a/lib/Analysis/GRCoreEngine.cpp +++ b/lib/Analysis/GRCoreEngine.cpp @@ -102,7 +102,8 @@ bool GRCoreEngineImpl::ExecuteWorkList(unsigned Steps) { case ProgramPoint::BlockExitKind: assert (false && "BlockExit location never occur in forward analysis."); break; - + + case ProgramPoint::PostLoadKind: case ProgramPoint::PostStmtKind: HandlePostStmt(cast(Node->getLocation()), WU.getBlock(), WU.getIndex(), Node); @@ -316,11 +317,13 @@ void GRStmtNodeBuilderImpl::GenerateAutoTransition(ExplodedNodeImpl* N) { Eng.WList->Enqueue(Succ, B, Idx+1); } -ExplodedNodeImpl* GRStmtNodeBuilderImpl::generateNodeImpl(Stmt* S, void* State, - ExplodedNodeImpl* Pred) { +ExplodedNodeImpl* +GRStmtNodeBuilderImpl::generateNodeImpl(Stmt* S, void* State, + ExplodedNodeImpl* Pred, bool isLoad) { bool IsNew; - ExplodedNodeImpl* N = Eng.G->getNodeImpl(PostStmt(S), State, &IsNew); + ProgramPoint Loc = isLoad ? PostLoad(S) : PostStmt(S); + ExplodedNodeImpl* N = Eng.G->getNodeImpl(Loc, State, &IsNew); N->addPredecessor(Pred); Deferred.erase(Pred); diff --git a/lib/Analysis/GRExprEngine.cpp b/lib/Analysis/GRExprEngine.cpp index 287c6e982a..2353058e76 100644 --- a/lib/Analysis/GRExprEngine.cpp +++ b/lib/Analysis/GRExprEngine.cpp @@ -312,7 +312,7 @@ void GRExprEngine::Visit(Stmt* S, NodeTy* Pred, NodeSet& Dst) { } case Stmt::DeclRefExprClass: - VisitDeclRefExpr(cast(S), Pred, Dst); + VisitDeclRefExpr(cast(S), Pred, Dst, false); break; case Stmt::DeclStmtClass: @@ -339,6 +339,10 @@ void GRExprEngine::Visit(Stmt* S, NodeTy* Pred, NodeSet& Dst) { Visit(cast(S)->getSubExpr()->IgnoreParens(), Pred, Dst); break; + case Stmt::ReturnStmtClass: + VisitReturnStmt(cast(S), Pred, Dst); + break; + case Stmt::SizeOfAlignOfTypeExprClass: VisitSizeOfAlignOfTypeExpr(cast(S), Pred, Dst); break; @@ -360,25 +364,41 @@ void GRExprEngine::Visit(Stmt* S, NodeTy* Pred, NodeSet& Dst) { break; } - // FIXME: We may wish to always bind state to ReturnStmts so - // that users can quickly query what was the state at the - // exit points of a function. + case Stmt::UnaryOperatorClass: + VisitUnaryOperator(cast(S), Pred, Dst, false); + break; + } +} + +void GRExprEngine::VisitLVal(Expr* Ex, NodeTy* Pred, NodeSet& Dst) { + + Ex = Ex->IgnoreParens(); + + if (Ex != CurrentStmt && getCFG().isBlkExpr(Ex)) { + Dst.Add(Pred); + return; + } + + switch (Ex->getStmtClass()) { + default: + Visit(Ex, Pred, Dst); + return; - case Stmt::ReturnStmtClass: - VisitReturnStmt(cast(S), Pred, Dst); break; + case Stmt::ArraySubscriptExprClass: + VisitArraySubscriptExpr(cast(Ex), Pred, Dst, true); + return; - case Stmt::UnaryOperatorClass: { - UnaryOperator* U = cast(S); + case Stmt::DeclRefExprClass: + VisitDeclRefExpr(cast(Ex), Pred, Dst, true); + return; - switch (U->getOpcode()) { - case UnaryOperator::Deref: VisitDeref(U, Pred, Dst); break; - case UnaryOperator::Plus: Visit(U->getSubExpr(), Pred, Dst); break; - case UnaryOperator::SizeOf: VisitSizeOfExpr(U, Pred, Dst); break; - default: VisitUnaryOperator(U, Pred, Dst); break; - } + case Stmt::UnaryOperatorClass: + VisitUnaryOperator(cast(Ex), Pred, Dst, true); + return; - break; - } + case Stmt::MemberExprClass: + VisitMemberExpr(cast(Ex), Pred, Dst, true); + return; } } @@ -741,20 +761,18 @@ void GRExprEngine::VisitLogicalExpr(BinaryOperator* B, NodeTy* Pred, // Transfer functions: Loads and stores. //===----------------------------------------------------------------------===// -void GRExprEngine::VisitDeclRefExpr(DeclRefExpr* D, NodeTy* Pred, NodeSet& Dst){ - - if (D != CurrentStmt) { - Dst.Add(Pred); // No-op. Simply propagate the current state unchanged. - return; - } - - // If we are here, we are loading the value of the decl and binding - // it to the block-level expression. +void GRExprEngine::VisitDeclRefExpr(DeclRefExpr* D, NodeTy* Pred, NodeSet& Dst, + bool asLVal) { - ValueState* St = GetState(Pred); + ValueState* St = GetState(Pred); RVal X = RVal::MakeVal(BasicVals, D); - RVal Y = isa(X) ? GetRVal(St, cast(X)) : X; - MakeNode(Dst, D, Pred, SetBlkExprRVal(St, D, Y)); + + if (asLVal) + MakeNode(Dst, D, Pred, SetRVal(St, D, cast(X))); + else { + RVal V = isa(X) ? GetRVal(St, cast(X)) : X; + MakeNode(Dst, D, Pred, SetRVal(St, D, V)); + } } /// VisitArraySubscriptExpr - Transfer function for array accesses @@ -763,24 +781,57 @@ void GRExprEngine::VisitArraySubscriptExpr(ArraySubscriptExpr* A, NodeTy* Pred, Expr* Base = A->getBase()->IgnoreParens(); - // Evaluate the base. - NodeSet Tmp1; - Visit(Base, Pred, Tmp1); + // Always visit the base as an LVal expression. This computes the + // abstract address of the base object. + NodeSet Tmp; - // Dereference the base. - NodeSet Tmp2; - - for (NodeSet::iterator I=Tmp1.begin(), E=Tmp1.end(); I!=E; ++I) { - ValueState* St = GetState(*I); - VisitDeref(Base, GetRVal(St, Base), St, *I, Tmp2, true); + if (Base->getType()->isPointerType()) // Base always is an LVal. + Visit(Base, Pred, Tmp); + else + VisitLVal(Base, Pred, Tmp); + + // TODO: Compute the LVal for the entry. This will enable array sensitivity + // for the analysis. + + // Return the LVal of the array entry. + if (asLVal) { + + // This is a redunant copy; we do this as a placeholder for future logic. + for (NodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) { + + ValueState* St = GetState(*I); + RVal V = GetRVal(St, Base); + + // TODO: Compute the LVal for the entry. This will enable array sensitivity + // for the analysis. + + if (!(V.isUndef() || V.isUnknown() || isa(V))) + V = UnknownVal(); + + MakeNode(Dst, A, *I, SetRVal(St, A, V)); + } + + return; } - // Get the index. - Tmp1.clear(); - Expr* Index = A->getIdx()->IgnoreParens(); + // We are doing a load. Check for a bad dereference. In the future we + // will check the actual entry lval; for now, check the Base LVal. For now + // the load will just return "UnknownVal" (since we don't have array + // sensitivity), but it will perform a null check. - for (NodeSet::iterator I=Tmp2.begin(), E=Tmp2.end(); I!=E; ++I) - Visit(Index, *I, Dst); + for (NodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) { + + ValueState* St = GetState(*I); + RVal V = GetRVal(St, Base); + + // TODO: Compute the LVal for the entry. This will enable array sensitivity + // for the analysis. + + if (!(V.isUndef() || V.isUnknown() || isa(V))) + V = UnknownVal(); + + EvalLoad(Dst, A, *I, St, GetRVal(St, Base), true); + } } /// VisitMemberExpr - Transfer function for member expressions. @@ -789,50 +840,165 @@ void GRExprEngine::VisitMemberExpr(MemberExpr* M, NodeTy* Pred, Expr* Base = M->getBase()->IgnoreParens(); + // Always visit the base as an LVal expression. This computes the + // abstract address of the base object. NodeSet Tmp; - VisitLVal(Base, Pred, Tmp); - if (Base->getType()->isPointerType()) { - NodeSet Tmp2; + if (Base->getType()->isPointerType()) // Base always is an LVal. + Visit(Base, Pred, Tmp); + else + VisitLVal(Base, Pred, Tmp); + + + // Return the LVal of the field access. + if (asLVal) { + // This is a redunant copy; we do this as a placeholder for future logic. for (NodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) { - ValueState* St = GetState(*I); - VisitDeref(Base, GetRVal(St, Base), St, *I, Tmp2, true); + ValueState* St = GetState(*I); + RVal V = GetRVal(St, Base); + + // TODO: Compute the LVal for the field. This will enable field + // sensitivity for the analysis. + + if (!(V.isUndef() || V.isUnknown() || isa(V))) + V = UnknownVal(); + + MakeNode(Dst, M, *I, SetRVal(St, M, V)); + } + + return; + } + + // We are doing a load. Check for a bad dereference. In the future we + // will check the actual field lval; for now, check the Base LVal. For now + // the load will just return "UnknownVal" (since we don't have field + // sensitivity), but it will perform a null check. + + for (NodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) { + ValueState* St = GetState(*I); - for (NodeSet::iterator I=Tmp2.begin(), E=Tmp2.end(); I!=E; ++I) - VisitMemberExprField(M, Base, *I, Dst, asLVal); + RVal V = GetRVal(St, Base); + + // TODO: Compute the LVal for the field. This will enable field + // sensitivity for the analysis. + + if (!(V.isUndef() || V.isUnknown() || isa(V))) + V = UnknownVal(); + + EvalLoad(Dst, M, *I, St, V, true); } - else - for (NodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) - VisitMemberExprField(M, Base, *I, Dst, asLVal); } -void GRExprEngine::VisitMemberExprField(MemberExpr* M, Expr* Base, NodeTy* Pred, - NodeSet& Dst, bool asLVal) { - Dst.Add(Pred); -} - -void GRExprEngine::EvalStore(NodeSet& Dst, Expr* E, NodeTy* Pred, - ValueState* St, RVal TargetLV, RVal Val) { +void GRExprEngine::EvalStore(NodeSet& Dst, Expr* Ex, NodeTy* Pred, + ValueState* St, RVal location, RVal Val) { assert (Builder && "GRStmtNodeBuilder must be defined."); + // Evaluate the location (checks for bad dereferences). + St = EvalLocation(Ex, Pred, St, location); + + if (!St) + return; + + // Proceed with the store. + unsigned size = Dst.size(); SaveAndRestore OldSink(Builder->BuildSinks); SaveOr OldHasGen(Builder->HasGeneratedNode); - assert (!TargetLV.isUndef()); + assert (!location.isUndef()); - TF->EvalStore(Dst, *this, *Builder, E, Pred, St, TargetLV, Val); + TF->EvalStore(Dst, *this, *Builder, Ex, Pred, St, location, Val); // Handle the case where no nodes where generated. Auto-generate that // contains the updated state if we aren't generating sinks. if (!Builder->BuildSinks && Dst.size() == size && !Builder->HasGeneratedNode) - TF->GRTransferFuncs::EvalStore(Dst, *this, *Builder, E, Pred, St, - TargetLV, Val); + TF->GRTransferFuncs::EvalStore(Dst, *this, *Builder, Ex, Pred, St, + location, Val); +} + +void GRExprEngine::EvalLoad(NodeSet& Dst, Expr* Ex, NodeTy* Pred, + ValueState* St, RVal location, bool CheckOnly) { + + // Evaluate the location (checks for bad dereferences). + + St = EvalLocation(Ex, Pred, St, location, true); + + if (!St) + return; + + // Proceed with the load. + + // FIXME: Currently symbolic analysis "generates" new symbols + // for the contents of values. We need a better approach. + + // FIXME: The "CheckOnly" option exists only because Array and Field + // loads aren't fully implemented. Eventually this option will go away. + + if (location.isUnknown() || CheckOnly) + MakeNode(Dst, Ex, Pred, St); + else + MakeNode(Dst, Ex, Pred, SetRVal(St, Ex, GetRVal(St, cast(location), + Ex->getType()))); +} + +ValueState* GRExprEngine::EvalLocation(Expr* Ex, NodeTy* Pred, + ValueState* St, RVal location, + bool isLoad) { + + // Check for loads/stores from/to undefined values. + if (location.isUndef()) { + if (NodeTy* Succ = Builder->generateNode(Ex, St, Pred, isLoad)) { + Succ->markAsSink(); + UndefDeref.insert(Succ); + } + + return NULL; + } + + // Check for loads/stores from/to unknown locations. Treat as No-Ops. + if (location.isUnknown()) + return St; + + // During a load, one of two possible situations arise: + // (1) A crash, because the location (pointer) was NULL. + // (2) The location (pointer) is not NULL, and the dereference works. + // + // We add these assumptions. + + LVal LV = cast(location); + + // "Assume" that the pointer is not NULL. + + bool isFeasibleNotNull = false; + ValueState* StNotNull = Assume(St, LV, true, isFeasibleNotNull); + + // "Assume" that the pointer is NULL. + + bool isFeasibleNull = false; + ValueState* StNull = Assume(St, LV, false, isFeasibleNull); + + if (isFeasibleNull) { + + // We don't use "MakeNode" here because the node will be a sink + // and we have no intention of processing it later. + + NodeTy* NullNode = Builder->generateNode(Ex, StNull, Pred, isLoad); + + if (NullNode) { + + NullNode->markAsSink(); + + if (isFeasibleNotNull) ImplicitNullDeref.insert(NullNode); + else ExplicitNullDeref.insert(NullNode); + } + } + + return isFeasibleNotNull ? StNotNull : NULL; } //===----------------------------------------------------------------------===// @@ -870,7 +1036,7 @@ void GRExprEngine::VisitCall(CallExpr* CE, NodeTy* Pred, for (NodeSet::iterator DI = DstTmp.begin(), DE = DstTmp.end(); DI!=DE; ++DI) { ValueState* St = GetState(*DI); - RVal L = GetLVal(St, Callee); + RVal L = GetRVal(St, Callee); // FIXME: Add support for symbolic function calls (calls involving // function pointer values that are symbolic). @@ -1127,7 +1293,7 @@ void GRExprEngine::VisitCast(Expr* CastE, Expr* Ex, NodeTy* Pred, NodeSet& Dst){ for (NodeSet::iterator I1 = S1.begin(), E1 = S1.end(); I1 != E1; ++I1) { NodeTy* N = *I1; ValueState* St = GetState(N); - RVal V = T->isReferenceType() ? GetLVal(St, Ex) : GetRVal(St, Ex); + RVal V = GetRVal(St, Ex); // Unknown? @@ -1275,7 +1441,6 @@ void GRExprEngine::VisitDeclStmtAux(DeclStmt* DS, ScopedDecl* D, void GRExprEngine::VisitSizeOfAlignOfTypeExpr(SizeOfAlignOfTypeExpr* Ex, NodeTy* Pred, NodeSet& Dst) { - QualType T = Ex->getArgumentType(); uint64_t amt; @@ -1295,284 +1460,191 @@ void GRExprEngine::VisitSizeOfAlignOfTypeExpr(SizeOfAlignOfTypeExpr* Ex, amt = getContext().getTypeAlign(T) / 8; MakeNode(Dst, Ex, Pred, - SetRVal(GetState(Pred), Ex, - NonLVal::MakeVal(BasicVals, amt, Ex->getType()))); -} - -void GRExprEngine::VisitDeref(UnaryOperator* U, NodeTy* Pred, - NodeSet& Dst, bool GetLVal) { - - Expr* Ex = U->getSubExpr()->IgnoreParens(); - - NodeSet DstTmp; - - if (isa(Ex)) - DstTmp.Add(Pred); - else - Visit(Ex, Pred, DstTmp); - - for (NodeSet::iterator I = DstTmp.begin(), DE = DstTmp.end(); I != DE; ++I) { - ValueState* St = GetState(*I); - RVal V = GetRVal(St, Ex); - VisitDeref(U, V, St, *I, Dst, GetLVal); - } + SetRVal(GetState(Pred), Ex, + NonLVal::MakeVal(BasicVals, amt, Ex->getType()))); } -void GRExprEngine::VisitDeref(Expr* Ex, RVal V, ValueState* St, NodeTy* Pred, - NodeSet& Dst, bool GetLVal) { - - // Check for dereferences of undefined values. - - if (V.isUndef()) { - if (NodeTy* Succ = Builder->generateNode(Ex, St, Pred)) { - Succ->markAsSink(); - UndefDeref.insert(Succ); - } - - return; - } - - // Check for dereferences of unknown values. Treat as No-Ops. - - if (V.isUnknown()) { - Dst.Add(Pred); - return; - } - - // After a dereference, one of two possible situations arise: - // (1) A crash, because the pointer was NULL. - // (2) The pointer is not NULL, and the dereference works. - // - // We add these assumptions. - - LVal LV = cast(V); - bool isFeasibleNotNull; - - // "Assume" that the pointer is Not-NULL. - - ValueState* StNotNull = Assume(St, LV, true, isFeasibleNotNull); - - if (isFeasibleNotNull) { - - if (GetLVal) - MakeNode(Dst, Ex, Pred, SetRVal(StNotNull, Ex, LV)); - else { - - // FIXME: Currently symbolic analysis "generates" new symbols - // for the contents of values. We need a better approach. - - MakeNode(Dst, Ex, Pred, - SetRVal(StNotNull, Ex, GetRVal(StNotNull, LV, Ex->getType()))); - } - } - - bool isFeasibleNull; - - // Now "assume" that the pointer is NULL. - - ValueState* StNull = Assume(St, LV, false, isFeasibleNull); - - if (isFeasibleNull) { - - // We don't use "MakeNode" here because the node will be a sink - // and we have no intention of processing it later. - - NodeTy* NullNode = Builder->generateNode(Ex, StNull, Pred); - - if (NullNode) { - - NullNode->markAsSink(); - - if (isFeasibleNotNull) ImplicitNullDeref.insert(NullNode); - else ExplicitNullDeref.insert(NullNode); - } - } -} void GRExprEngine::VisitUnaryOperator(UnaryOperator* U, NodeTy* Pred, - NodeSet& Dst) { - - NodeSet S1; - - assert (U->getOpcode() != UnaryOperator::Deref); - assert (U->getOpcode() != UnaryOperator::SizeOf); - assert (U->getOpcode() != UnaryOperator::AlignOf); - - bool use_GetLVal = false; - + NodeSet& Dst, bool asLVal) { + switch (U->getOpcode()) { - case UnaryOperator::PostInc: - case UnaryOperator::PostDec: - case UnaryOperator::PreInc: - case UnaryOperator::PreDec: - case UnaryOperator::AddrOf: - // Evalue subexpression as an LVal. - use_GetLVal = true; - VisitLVal(U->getSubExpr(), Pred, S1); - break; default: - Visit(U->getSubExpr(), Pred, S1); break; - } - - for (NodeSet::iterator I1 = S1.begin(), E1 = S1.end(); I1 != E1; ++I1) { - - NodeTy* N1 = *I1; - ValueState* St = GetState(N1); + + case UnaryOperator::Deref: { + + Expr* Ex = U->getSubExpr()->IgnoreParens(); + NodeSet Tmp; + Visit(Ex, Pred, Tmp); + + for (NodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) { - RVal SubV = use_GetLVal ? GetLVal(St, U->getSubExpr()) : - GetRVal(St, U->getSubExpr()); - - if (SubV.isUnknown()) { - Dst.Add(N1); - continue; - } + ValueState* St = GetState(*I); + RVal location = GetRVal(St, Ex); + + if (asLVal) + MakeNode(Dst, U, *I, SetRVal(St, U, location)); + else + EvalLoad(Dst, Ex, *I, St, location); + } - if (SubV.isUndef()) { - MakeNode(Dst, U, N1, SetRVal(St, U, SubV)); - continue; + return; } - - if (U->isIncrementDecrementOp()) { + + case UnaryOperator::Plus: assert (!asLVal); // FALL-THROUGH. + case UnaryOperator::Extension: { - // Handle ++ and -- (both pre- and post-increment). + // Unary "+" is a no-op, similar to a parentheses. We still have places + // where it may be a block-level expression, so we need to + // generate an extra node that just propagates the value of the + // subexpression. + + Expr* Ex = U->getSubExpr()->IgnoreParens(); + NodeSet Tmp; + Visit(Ex, Pred, Tmp); - LVal SubLV = cast(SubV); - RVal V = GetRVal(St, SubLV, U->getType()); + for (NodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) { + ValueState* St = GetState(*I); + MakeNode(Dst, U, *I, SetRVal(St, U, GetRVal(St, Ex))); + } - if (V.isUnknown()) { - Dst.Add(N1); - continue; + return; + } + + case UnaryOperator::AddrOf: { + + assert (!asLVal); + Expr* Ex = U->getSubExpr()->IgnoreParens(); + NodeSet Tmp; + VisitLVal(Ex, Pred, Tmp); + + for (NodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) { + ValueState* St = GetState(*I); + RVal V = GetRVal(St, Ex); + St = SetRVal(St, U, V); + MakeNode(Dst, U, *I, St); } - // Propagate undefined values. - if (V.isUndef()) { - MakeNode(Dst, U, N1, SetRVal(St, U, V)); - continue; - } - - // Handle all other values. + return; + } - BinaryOperator::Opcode Op = U->isIncrementOp() ? BinaryOperator::Add - : BinaryOperator::Sub; + case UnaryOperator::LNot: + case UnaryOperator::Minus: + case UnaryOperator::Not: { - RVal Result = EvalBinOp(Op, V, MakeConstantVal(1U, U)); + assert (!asLVal); + Expr* Ex = U->getSubExpr()->IgnoreParens(); + NodeSet Tmp; + Visit(Ex, Pred, Tmp); - if (U->isPostfix()) - St = SetRVal(SetRVal(St, U, V), SubLV, Result); - else - St = SetRVal(SetRVal(St, U, Result), SubLV, Result); + for (NodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) { + ValueState* St = GetState(*I); + RVal V = GetRVal(St, Ex); - MakeNode(Dst, U, N1, St); - continue; - } - - // Handle all other unary operators. - - switch (U->getOpcode()) { - - case UnaryOperator::Extension: - St = SetRVal(St, U, SubV); - break; - - case UnaryOperator::Minus: - St = SetRVal(St, U, EvalMinus(U, cast(SubV))); - break; + if (V.isUnknownOrUndef()) { + MakeNode(Dst, U, *I, SetRVal(St, U, V)); + continue; + } - case UnaryOperator::Not: - St = SetRVal(St, U, EvalComplement(cast(SubV))); - break; + switch (U->getOpcode()) { + default: + assert(false && "Invalid Opcode."); + break; + + case UnaryOperator::Not: + St = SetRVal(St, U, EvalComplement(cast(V))); + break; + + case UnaryOperator::Minus: + St = SetRVal(St, U, EvalMinus(U, cast(V))); + break; + + case UnaryOperator::LNot: + + // C99 6.5.3.3: "The expression !E is equivalent to (0==E)." + // + // Note: technically we do "E == 0", but this is the same in the + // transfer functions as "0 == E". + + if (isa(V)) { + lval::ConcreteInt X(BasicVals.getZeroWithPtrWidth()); + RVal Result = EvalBinOp(BinaryOperator::EQ, cast(V), X); + St = SetRVal(St, U, Result); + } + else { + nonlval::ConcreteInt X(BasicVals.getValue(0, Ex->getType())); + RVal Result = EvalBinOp(BinaryOperator::EQ, cast(V), X); + St = SetRVal(St, U, Result); + } + + break; + } - case UnaryOperator::LNot: + MakeNode(Dst, U, *I, St); + } + + return; + } + + case UnaryOperator::SizeOf: { + + QualType T = U->getSubExpr()->getType(); - // C99 6.5.3.3: "The expression !E is equivalent to (0==E)." - // - // Note: technically we do "E == 0", but this is the same in the - // transfer functions as "0 == E". - - if (isa(SubV)) { - lval::ConcreteInt V(BasicVals.getZeroWithPtrWidth()); - RVal Result = EvalBinOp(BinaryOperator::EQ, cast(SubV), V); - St = SetRVal(St, U, Result); - } - else { - Expr* Ex = U->getSubExpr(); - nonlval::ConcreteInt V(BasicVals.getValue(0, Ex->getType())); - RVal Result = EvalBinOp(BinaryOperator::EQ, cast(SubV), V); - St = SetRVal(St, U, Result); - } + // FIXME: Add support for VLAs. + + if (!T.getTypePtr()->isConstantSizeType()) + return; - break; + uint64_t size = getContext().getTypeSize(T) / 8; + ValueState* St = GetState(Pred); + St = SetRVal(St, U, NonLVal::MakeVal(BasicVals, size, U->getType())); - case UnaryOperator::AddrOf: { - assert (isa(SubV)); - St = SetRVal(St, U, SubV); - break; - } - - default: ; - assert (false && "Not implemented."); - } - - MakeNode(Dst, U, N1, St); + MakeNode(Dst, U, Pred, St); + return; + } } -} - -void GRExprEngine::VisitSizeOfExpr(UnaryOperator* U, NodeTy* Pred, - NodeSet& Dst) { - - QualType T = U->getSubExpr()->getType(); - - // FIXME: Add support for VLAs. - if (!T.getTypePtr()->isConstantSizeType()) - return; - - uint64_t size = getContext().getTypeSize(T) / 8; - ValueState* St = GetState(Pred); - St = SetRVal(St, U, NonLVal::MakeVal(BasicVals, size, U->getType())); - - MakeNode(Dst, U, Pred, St); -} - -void GRExprEngine::VisitLVal(Expr* Ex, NodeTy* Pred, NodeSet& Dst) { - Ex = Ex->IgnoreParens(); + // Handle ++ and -- (both pre- and post-increment). - if (Ex != CurrentStmt && getCFG().isBlkExpr(Ex)) { - Dst.Add(Pred); - return; - } + assert (U->isIncrementDecrementOp()); + NodeSet Tmp; + Expr* Ex = U->getSubExpr()->IgnoreParens(); + VisitLVal(Ex, Pred, Tmp); - switch (Ex->getStmtClass()) { - default: - break; - - case Stmt::ArraySubscriptExprClass: - VisitArraySubscriptExpr(cast(Ex), Pred, Dst, true); - return; + for (NodeSet::iterator I = Tmp.begin(), E = Tmp.end(); I!=E; ++I) { + + ValueState* St = GetState(*I); + RVal V1 = GetRVal(St, Ex); + + // Perform a load. + NodeSet Tmp2; + EvalLoad(Tmp2, Ex, *I, St, V1); - case Stmt::DeclRefExprClass: - Dst.Add(Pred); - return; + for (NodeSet::iterator I2 = Tmp2.begin(), E2 = Tmp2.end(); I2!=E2; ++I2) { + + St = GetState(*I2); + RVal V2 = GetRVal(St, Ex); + + // Propagate unknown and undefined values. + if (V2.isUnknownOrUndef()) { + MakeNode(Dst, U, *I2, SetRVal(St, U, V2)); + continue; + } - case Stmt::UnaryOperatorClass: { - UnaryOperator* U = cast(Ex); + // Handle all other values. - if (U->getOpcode() == UnaryOperator::Deref) { - VisitDeref(U, Pred, Dst, true); - return; - } + BinaryOperator::Opcode Op = U->isIncrementOp() ? BinaryOperator::Add + : BinaryOperator::Sub; - break; + RVal Result = EvalBinOp(Op, V2, MakeConstantVal(1U, U)); + St = SetRVal(St, U, U->isPostfix() ? V2 : Result); + + // Perform the store. + EvalStore(Dst, U, *I, St, V1, Result); } - - case Stmt::MemberExprClass: - VisitMemberExpr(cast(Ex), Pred, Dst, true); - return; } - - Visit(Ex, Pred, Dst); } void GRExprEngine::VisitAsmStmt(AsmStmt* A, NodeTy* Pred, NodeSet& Dst) { @@ -1615,9 +1687,8 @@ void GRExprEngine::VisitAsmStmtHelperInputs(AsmStmt* A, for (AsmStmt::outputs_iterator OI = A->begin_outputs(), OE = A->end_outputs(); OI != OE; ++OI) { - RVal X = GetLVal(St, *OI); - - assert (!isa(X)); + RVal X = GetRVal(St, *OI); + assert (!isa(X)); // Should be an Lval, or unknown, undef. if (isa(X)) St = SetRVal(St, cast(X), UnknownVal()); @@ -1705,136 +1776,83 @@ void GRExprEngine::VisitReturnStmt(ReturnStmt* S, NodeTy* Pred, NodeSet& Dst) { // Transfer functions: Binary operators. //===----------------------------------------------------------------------===// +bool GRExprEngine::CheckDivideZero(Expr* Ex, ValueState* St, + NodeTy* Pred, RVal Denom) { + + // Divide by undefined? (potentially zero) + + if (Denom.isUndef()) { + NodeTy* DivUndef = Builder->generateNode(Ex, St, Pred); + + if (DivUndef) { + DivUndef->markAsSink(); + ExplicitBadDivides.insert(DivUndef); + } + + return true; + } + + // Check for divide/remainder-by-zero. + // First, "assume" that the denominator is 0 or undefined. + + bool isFeasibleZero = false; + ValueState* ZeroSt = Assume(St, Denom, false, isFeasibleZero); + + // Second, "assume" that the denominator cannot be 0. + + bool isFeasibleNotZero = false; + St = Assume(St, Denom, true, isFeasibleNotZero); + + // Create the node for the divide-by-zero (if it occurred). + + if (isFeasibleZero) + if (NodeTy* DivZeroNode = Builder->generateNode(Ex, ZeroSt, Pred)) { + DivZeroNode->markAsSink(); + + if (isFeasibleNotZero) + ImplicitBadDivides.insert(DivZeroNode); + else + ExplicitBadDivides.insert(DivZeroNode); + + } + + return !isFeasibleNotZero; +} + void GRExprEngine::VisitBinaryOperator(BinaryOperator* B, GRExprEngine::NodeTy* Pred, GRExprEngine::NodeSet& Dst) { - NodeSet S1; + + NodeSet Tmp1; + Expr* LHS = B->getLHS()->IgnoreParens(); + Expr* RHS = B->getRHS()->IgnoreParens(); if (B->isAssignmentOp()) - VisitLVal(B->getLHS(), Pred, S1); + VisitLVal(LHS, Pred, Tmp1); else - Visit(B->getLHS(), Pred, S1); + Visit(LHS, Pred, Tmp1); - for (NodeSet::iterator I1=S1.begin(), E1=S1.end(); I1 != E1; ++I1) { + for (NodeSet::iterator I1=Tmp1.begin(), E1=Tmp1.end(); I1 != E1; ++I1) { - NodeTy* N1 = *I1; + RVal LeftV = GetRVal((*I1)->getState(), LHS); - // When getting the value for the LHS, check if we are in an assignment. - // In such cases, we want to (initially) treat the LHS as an LVal, - // so we use GetLVal instead of GetRVal so that DeclRefExpr's are - // evaluated to LValDecl's instead of to an NonLVal. - - RVal LeftV = B->isAssignmentOp() ? GetLVal(GetState(N1), B->getLHS()) - : GetRVal(GetState(N1), B->getLHS()); + // Process the RHS. - // Visit the RHS... + NodeSet Tmp2; + Visit(RHS, *I1, Tmp2); - NodeSet S2; - Visit(B->getRHS(), N1, S2); + // With both the LHS and RHS evaluated, process the operation itself. - // Process the binary operator. - - for (NodeSet::iterator I2 = S2.begin(), E2 = S2.end(); I2 != E2; ++I2) { + for (NodeSet::iterator I2=Tmp2.begin(), E2=Tmp2.end(); I2 != E2; ++I2) { - NodeTy* N2 = *I2; - ValueState* St = GetState(N2); - Expr* RHS = B->getRHS(); + ValueState* St = GetState(*I2); RVal RightV = GetRVal(St, RHS); - BinaryOperator::Opcode Op = B->getOpcode(); - if ((Op == BinaryOperator::Div || Op == BinaryOperator::Rem) - && RHS->getType()->isIntegerType()) { - - // Check if the denominator is undefined. - - if (!RightV.isUnknown()) { - - if (RightV.isUndef()) { - NodeTy* DivUndef = Builder->generateNode(B, St, N2); - - if (DivUndef) { - DivUndef->markAsSink(); - ExplicitBadDivides.insert(DivUndef); - } - - continue; - } - - // Check for divide/remainder-by-zero. - // - // First, "assume" that the denominator is 0 or undefined. - - bool isFeasibleZero = false; - ValueState* ZeroSt = Assume(St, RightV, false, isFeasibleZero); - - // Second, "assume" that the denominator cannot be 0. - - bool isFeasibleNotZero = false; - St = Assume(St, RightV, true, isFeasibleNotZero); - - // Create the node for the divide-by-zero (if it occurred). - - if (isFeasibleZero) - if (NodeTy* DivZeroNode = Builder->generateNode(B, ZeroSt, N2)) { - DivZeroNode->markAsSink(); - - if (isFeasibleNotZero) - ImplicitBadDivides.insert(DivZeroNode); - else - ExplicitBadDivides.insert(DivZeroNode); - - } - - if (!isFeasibleNotZero) - continue; - } - - // Fall-through. The logic below processes the divide. - } - - - if (Op <= BinaryOperator::Or) { - - // Process non-assignements except commas or short-circuited - // logical expressions (LAnd and LOr). - - RVal Result = EvalBinOp(Op, LeftV, RightV); - - if (Result.isUnknown()) { - Dst.Add(N2); - continue; - } - - if (Result.isUndef() && !LeftV.isUndef() && !RightV.isUndef()) { - - // The operands were not undefined, but the result is undefined. - - if (NodeTy* UndefNode = Builder->generateNode(B, St, N2)) { - UndefNode->markAsSink(); - UndefResults.insert(UndefNode); - } - - continue; - } - - MakeNode(Dst, B, N2, SetRVal(St, B, Result)); - continue; - } - - // Process assignments. - - switch (Op) { + switch (Op) { case BinaryOperator::Assign: { - // Simple assignments. - - if (LeftV.isUndef()) { - HandleUndefinedStore(B, N2); - continue; - } - // EXPERIMENTAL: "Conjured" symbols. if (RightV.isUnknown()) { @@ -1842,180 +1860,144 @@ void GRExprEngine::VisitBinaryOperator(BinaryOperator* B, SymbolID Sym = SymMgr.getConjuredSymbol(B->getRHS(), Count); RightV = B->getRHS()->getType()->isPointerType() - ? cast(lval::SymbolVal(Sym)) - : cast(nonlval::SymbolVal(Sym)); + ? cast(lval::SymbolVal(Sym)) + : cast(nonlval::SymbolVal(Sym)); } // Simulate the effects of a "store": bind the value of the RHS // to the L-Value represented by the LHS. - - EvalStore(Dst, B, N2, SetRVal(St, B, RightV), - LeftV, RightV); + EvalStore(Dst, B, *I2, SetRVal(St, B, RightV), LeftV, RightV); continue; } - - // Compound assignment operators. - default: { + case BinaryOperator::Div: + case BinaryOperator::Rem: - assert (B->isCompoundAssignmentOp()); + // Special checking for integer denominators. - if (Op >= BinaryOperator::AndAssign) - ((int&) Op) -= (BinaryOperator::AndAssign - BinaryOperator::And); - else - ((int&) Op) -= BinaryOperator::MulAssign; + if (RHS->getType()->isIntegerType() + && CheckDivideZero(B, St, *I2, RightV)) + continue; - // Check if the LHS is undefined. + // FALL-THROUGH. + + default: { + + if (B->isAssignmentOp()) + break; - if (LeftV.isUndef()) { - HandleUndefinedStore(B, N2); + // Process non-assignements except commas or short-circuited + // logical expressions (LAnd and LOr). + + RVal Result = EvalBinOp(Op, LeftV, RightV); + + if (Result.isUnknown()) { + Dst.Add(*I2); continue; } - if (LeftV.isUnknown()) { - assert (isa(GetRVal(St, B))); - Dst.Add(N2); + if (Result.isUndef() && !LeftV.isUndef() && !RightV.isUndef()) { + + // The operands were *not* undefined, but the result is undefined. + // This is a special node that should be flagged as an error. + + if (NodeTy* UndefNode = Builder->generateNode(B, St, *I2)) { + UndefNode->markAsSink(); + UndefResults.insert(UndefNode); + } + continue; } - // At this pointer we know that the LHS evaluates to an LVal - // that is neither "Unknown" or "Undefined." - - LVal LeftLV = cast(LeftV); + // Otherwise, create a new node. - // Fetch the value of the LHS (the value of the variable, etc.). - - RVal V = GetRVal(GetState(N1), LeftLV, B->getLHS()->getType()); + MakeNode(Dst, B, *I2, SetRVal(St, B, Result)); + continue; + } + } + + assert (B->isCompoundAssignmentOp()); + + if (Op >= BinaryOperator::AndAssign) + ((int&) Op) -= (BinaryOperator::AndAssign - BinaryOperator::And); + else + ((int&) Op) -= BinaryOperator::MulAssign; - // Propagate undefined value (left-side). We - // propogate undefined values for the RHS below when - // we also check for divide-by-zero. + // Perform a load (the LHS). This performs the checks for + // null dereferences, and so on. + NodeSet Tmp3; + RVal location = GetRVal(St, LHS); + EvalLoad(Tmp3, LHS, *I2, St, location); + + for (NodeSet::iterator I3=Tmp3.begin(), E3=Tmp3.end(); I3!=E3; ++I3) { + + St = GetState(*I3); + RVal V = GetRVal(St, LHS); + + // Propagate undefined values (left-side). + if (V.isUndef()) { + EvalStore(Dst, B, *I3, SetRVal(St, B, V), location, V); + continue; + } + + // Propagate unknown values (left and right-side). + if (RightV.isUnknown() || V.isUnknown()) { + EvalStore(Dst, B, *I3, SetRVal(St, B, UnknownVal()), location, + UnknownVal()); + continue; + } + + // At this point: + // + // The LHS is not Undef/Unknown. + // The RHS is not Unknown. + + // Get the computation type. + QualType CTy = cast(B)->getComputationType(); - if (V.isUndef()) { - St = SetRVal(St, B, V); - break; - } + // Perform promotions. + V = EvalCast(V, CTy); + RightV = EvalCast(RightV, CTy); - // Propagate unknown values. + // Evaluate operands and promote to result type. + + if ((Op == BinaryOperator::Div || Op == BinaryOperator::Rem) + && RHS->getType()->isIntegerType()) { - if (V.isUnknown()) { - // The value bound to LeftV is unknown. Thus we just - // propagate the current node (as "B" is already bound to nothing). - assert (isa(GetRVal(St, B))); - Dst.Add(N2); + if (CheckDivideZero(B, St, *I3, RightV)) continue; - } - - if (RightV.isUnknown()) { - assert (isa(GetRVal(St, B))); - St = SetRVal(St, LeftLV, UnknownVal()); - break; - } + } + else if (RightV.isUndef()) { - // At this point: - // - // The LHS is not Undef/Unknown. - // The RHS is not Unknown. + // Propagate undefined values (right-side). - // Get the computation type. - QualType CTy = cast(B)->getComputationType(); - - // Perform promotions. - V = EvalCast(V, CTy); - RightV = EvalCast(RightV, CTy); + EvalStore(Dst, B, *I3, SetRVal(St, B, RightV), location, RightV); + continue; + } + + // Compute the result of the operation. + + RVal Result = EvalCast(EvalBinOp(Op, V, RightV), B->getType()); - // Evaluate operands and promote to result type. - - if ((Op == BinaryOperator::Div || Op == BinaryOperator::Rem) - && RHS->getType()->isIntegerType()) { - - // Check if the denominator is undefined. - - if (RightV.isUndef()) { - NodeTy* DivUndef = Builder->generateNode(B, St, N2); - - if (DivUndef) { - DivUndef->markAsSink(); - ExplicitBadDivides.insert(DivUndef); - } - - continue; - } - - // First, "assume" that the denominator is 0. - - bool isFeasibleZero = false; - ValueState* ZeroSt = Assume(St, RightV, false, isFeasibleZero); - - // Second, "assume" that the denominator cannot be 0. + if (Result.isUndef()) { - bool isFeasibleNotZero = false; - St = Assume(St, RightV, true, isFeasibleNotZero); - - // Create the node for the divide-by-zero error (if it occurred). - - if (isFeasibleZero) { - NodeTy* DivZeroNode = Builder->generateNode(B, ZeroSt, N2); - - if (DivZeroNode) { - DivZeroNode->markAsSink(); - - if (isFeasibleNotZero) - ImplicitBadDivides.insert(DivZeroNode); - else - ExplicitBadDivides.insert(DivZeroNode); - } - } - - if (!isFeasibleNotZero) - continue; - - // Fall-through. The logic below processes the divide. - } - else { - - // Propagate undefined values (right-side). - - if (RightV.isUndef()) { - St = SetRVal(SetRVal(St, B, RightV), LeftLV, RightV); - break; - } - - } - - RVal Result = EvalCast(EvalBinOp(Op, V, RightV), B->getType()); + // The operands were not undefined, but the result is undefined. - if (Result.isUndef()) { - - // The operands were not undefined, but the result is undefined. - - if (NodeTy* UndefNode = Builder->generateNode(B, St, N2)) { - UndefNode->markAsSink(); - UndefResults.insert(UndefNode); - } - - continue; + if (NodeTy* UndefNode = Builder->generateNode(B, St, *I3)) { + UndefNode->markAsSink(); + UndefResults.insert(UndefNode); } - // St = SetRVal(SetRVal(St, B, Result), LeftLV, Result); - EvalStore(Dst, B, N2, SetRVal(St, B, Result), LeftLV, Result); continue; } + + EvalStore(Dst, B, *I3, SetRVal(St, B, Result), location, Result); } - - MakeNode(Dst, B, N2, St); } } } -void GRExprEngine::HandleUndefinedStore(Stmt* S, NodeTy* Pred) { - NodeTy* N = Builder->generateNode(S, GetState(Pred), Pred); - N->markAsSink(); - UndefStores.insert(N); -} - - //===----------------------------------------------------------------------===// // "Assume" logic. //===----------------------------------------------------------------------===// @@ -2325,6 +2307,7 @@ struct VISIBILITY_HIDDEN DOTGraphTraits : assert (false); break; + case ProgramPoint::PostLoadKind: case ProgramPoint::PostStmtKind: { const PostStmt& L = cast(Loc); Stmt* S = L.getStmt(); diff --git a/lib/Analysis/ValueState.cpp b/lib/Analysis/ValueState.cpp index e36bbfa9d3..cba0253ea1 100644 --- a/lib/Analysis/ValueState.cpp +++ b/lib/Analysis/ValueState.cpp @@ -271,22 +271,6 @@ RVal ValueStateManager::GetRVal(ValueState* St, Expr* E) { E = cast(E)->getSubExpr(); continue; - // DeclRefExprs can either evaluate to an LVal or a Non-LVal - // (assuming an implicit "load") depending on the context. In this - // context we assume that we are retrieving the value contained - // within the referenced variables. - - case Stmt::DeclRefExprClass: { - - // Check if this expression is a block-level expression. If so, - // return its value. - ValueState::ExprBindingsTy::TreeTy* T=St->BlockExprBindings.SlimFind(E); - if (T) return T->getValue().second; - - RVal X = RVal::MakeVal(BasicVals, cast(E)); - return isa(X) ? GetRVal(St, cast(X)) : X; - } - case Stmt::CharacterLiteralClass: { CharacterLiteral* C = cast(E); return NonLVal::MakeVal(BasicVals, C->getValue(), C->getType()); @@ -326,18 +310,6 @@ RVal ValueStateManager::GetRVal(ValueState* St, Expr* E) { break; } - case Stmt::UnaryOperatorClass: { - - UnaryOperator* U = cast(E); - - if (U->getOpcode() == UnaryOperator::Plus) { - E = U->getSubExpr(); - continue; - } - - break; - } - // Handle all other Expr* using a lookup. default: @@ -377,34 +349,6 @@ RVal ValueStateManager::GetBlkExprRVal(ValueState* St, Expr* E) { } } -RVal ValueStateManager::GetLVal(ValueState* St, Expr* E) { - - E = E->IgnoreParens(); - - if (DeclRefExpr* DR = dyn_cast(E)) { - ValueDecl* VD = DR->getDecl(); - - if (FunctionDecl* FD = dyn_cast(VD)) - return lval::FuncVal(FD); - else - return lval::DeclVal(cast(DR->getDecl())); - } - - if (UnaryOperator* U = dyn_cast(E)) - if (U->getOpcode() == UnaryOperator::Deref) { - E = U->getSubExpr()->IgnoreParens(); - - if (DeclRefExpr* DR = dyn_cast(E)) { - lval::DeclVal X(cast(DR->getDecl())); - return GetRVal(St, X); - } - else - return GetRVal(St, E); - } - - return GetRVal(St, E); -} - ValueState* ValueStateManager::SetRVal(ValueState* St, Expr* E, RVal V, bool isBlkExpr, bool Invalidate) { -- 2.40.0