From 361fa8ecd122a5b06c2c59d44419e202f42e1c5d Mon Sep 17 00:00:00 2001 From: Ted Kremenek Date: Wed, 12 Mar 2008 21:45:47 +0000 Subject: [PATCH] Changed CallRetValSymbol to SymbolConjured to allow "conjured" symbols to be created for any expression, not just CallExprs. Added experimental support for conjuring symbols during assingments where the RHS is "unknown". This allows more value tracking for path-sensitivity. Fixed bug in "assumption" logic when processing symbolic constraints; we would improperly mark constraints we didn't support as infeasible. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@48306 91177308-0d34-0410-b5e6-96231b3b80d8 --- Analysis/CFRefCount.cpp | 6 ++--- Analysis/GRExprEngine.cpp | 23 ++++++++++++++++-- Analysis/GRSimpleVals.cpp | 2 +- Analysis/SymbolManager.cpp | 12 +++++----- .../Analysis/PathSensitive/SymbolManager.h | 24 +++++++++---------- 5 files changed, 43 insertions(+), 24 deletions(-) diff --git a/Analysis/CFRefCount.cpp b/Analysis/CFRefCount.cpp index 6c5493c206..c87ca673b9 100644 --- a/Analysis/CFRefCount.cpp +++ b/Analysis/CFRefCount.cpp @@ -588,7 +588,7 @@ void CFRefCount::EvalCall(ExplodedNodeSet& Dst, if (CE->getType() != Eng.getContext().VoidTy) { unsigned Count = Builder.getCurrentBlockCount(); - SymbolID Sym = Eng.getSymbolManager().getCallRetValSymbol(CE, Count); + SymbolID Sym = Eng.getSymbolManager().getConjuredSymbol(CE, Count); RVal X = CE->getType()->isPointerType() ? cast(lval::SymbolVal(Sym)) @@ -664,7 +664,7 @@ void CFRefCount::EvalCall(ExplodedNodeSet& Dst, case RetEffect::OwnedSymbol: { unsigned Count = Builder.getCurrentBlockCount(); - SymbolID Sym = Eng.getSymbolManager().getCallRetValSymbol(CE, Count); + SymbolID Sym = Eng.getSymbolManager().getConjuredSymbol(CE, Count); ValueState StImpl = *St; RefBindings B = GetRefBindings(StImpl); @@ -679,7 +679,7 @@ void CFRefCount::EvalCall(ExplodedNodeSet& Dst, case RetEffect::NotOwnedSymbol: { unsigned Count = Builder.getCurrentBlockCount(); - SymbolID Sym = Eng.getSymbolManager().getCallRetValSymbol(CE, Count); + SymbolID Sym = Eng.getSymbolManager().getConjuredSymbol(CE, Count); ValueState StImpl = *St; RefBindings B = GetRefBindings(StImpl); diff --git a/Analysis/GRExprEngine.cpp b/Analysis/GRExprEngine.cpp index 61643a440e..b8892e3ee5 100644 --- a/Analysis/GRExprEngine.cpp +++ b/Analysis/GRExprEngine.cpp @@ -177,7 +177,7 @@ void GRExprEngine::ProcessBranch(Expr* Condition, Stmt* Term, // Process the true branch. - bool isFeasible = true; + bool isFeasible = false; ValueState* St = Assume(PrevState, V, true, isFeasible); if (isFeasible) @@ -300,8 +300,8 @@ void GRExprEngine::ProcessSwitch(SwitchNodeBuilder& builder) { RVal Res = EvalBinOp(BinaryOperator::EQ, CondV, CaseVal); // Now "assume" that the case matches. - bool isFeasible = false; + bool isFeasible = false; ValueState* StNew = Assume(St, Res, true, isFeasible); if (isFeasible) { @@ -317,6 +317,7 @@ void GRExprEngine::ProcessSwitch(SwitchNodeBuilder& builder) { // Now "assume" that the case doesn't match. Add this state // to the default state (if it is feasible). + isFeasible = false; StNew = Assume(DefaultSt, Res, false, isFeasible); if (isFeasible) @@ -1114,10 +1115,27 @@ void GRExprEngine::VisitBinaryOperator(BinaryOperator* B, continue; } + // EXPERIMENTAL: "Conjured" symbols. + + if (RightV.isUnknown()) { + unsigned Count = Builder->getCurrentBlockCount(); + SymbolID Sym = SymMgr.getConjuredSymbol(B->getRHS(), Count); + + RightV = B->getRHS()->getType()->isPointerType() + ? cast(lval::SymbolVal(Sym)) + : cast(nonlval::SymbolVal(Sym)); + } + + // Even if the LHS evaluates to an unknown L-Value, the entire + // expression still evaluates to the RHS. + if (LeftV.isUnknown()) { St = SetRVal(St, B, RightV); break; } + + // Simulate the effects of a "store": bind the value of the RHS + // to the L-Value represented by the LHS. St = SetRVal(SetRVal(St, B, RightV), cast(LeftV), RightV); break; @@ -1531,6 +1549,7 @@ GRExprEngine::AssumeSymInt(ValueState* St, bool Assumption, switch (C.getOpcode()) { default: // No logic yet for other operators. + isFeasible = true; return St; case BinaryOperator::EQ: diff --git a/Analysis/GRSimpleVals.cpp b/Analysis/GRSimpleVals.cpp index b4abc3afdd..a03303c079 100644 --- a/Analysis/GRSimpleVals.cpp +++ b/Analysis/GRSimpleVals.cpp @@ -432,7 +432,7 @@ void GRSimpleVals::EvalCall(ExplodedNodeSet& Dst, if (CE->getType() != Eng.getContext().VoidTy) { unsigned Count = Builder.getCurrentBlockCount(); - SymbolID Sym = Eng.getSymbolManager().getCallRetValSymbol(CE, Count); + SymbolID Sym = Eng.getSymbolManager().getConjuredSymbol(CE, Count); RVal X = CE->getType()->isPointerType() ? cast(lval::SymbolVal(Sym)) diff --git a/Analysis/SymbolManager.cpp b/Analysis/SymbolManager.cpp index 5454649443..f243fa667b 100644 --- a/Analysis/SymbolManager.cpp +++ b/Analysis/SymbolManager.cpp @@ -72,10 +72,10 @@ SymbolID SymbolManager::getContentsOfSymbol(SymbolID sym) { return SymbolCounter++; } -SymbolID SymbolManager::getCallRetValSymbol(CallExpr* CE, unsigned Count) { +SymbolID SymbolManager::getConjuredSymbol(Expr* E, unsigned Count) { llvm::FoldingSetNodeID profile; - SymbolDataCallRetVal::Profile(profile, CE, Count); + SymbolConjured::Profile(profile, E, Count); void* InsertPos; SymbolData* SD = DataSet.FindNodeOrInsertPos(profile, InsertPos); @@ -83,8 +83,8 @@ SymbolID SymbolManager::getCallRetValSymbol(CallExpr* CE, unsigned Count) { if (SD) return SD->getSymbol(); - SD = (SymbolData*) BPAlloc.Allocate(); - new (SD) SymbolDataCallRetVal(SymbolCounter, CE, Count); + SD = (SymbolData*) BPAlloc.Allocate(); + new (SD) SymbolConjured(SymbolCounter, E, Count); DataSet.InsertNode(SD, InsertPos); DataMap[SymbolCounter] = SD; @@ -116,8 +116,8 @@ QualType SymbolData::getType(const SymbolManager& SymMgr) const { return T->getAsPointerType()->getPointeeType(); } - case CallRetValKind: - return cast(this)->getCallExpr()->getType(); + case ConjuredKind: + return cast(this)->getExpr()->getType(); } } diff --git a/include/clang/Analysis/PathSensitive/SymbolManager.h b/include/clang/Analysis/PathSensitive/SymbolManager.h index a740302c8d..d0473c6a8e 100644 --- a/include/clang/Analysis/PathSensitive/SymbolManager.h +++ b/include/clang/Analysis/PathSensitive/SymbolManager.h @@ -69,7 +69,7 @@ namespace clang { class SymbolData : public llvm::FoldingSetNode { public: - enum Kind { UndefKind, ParmKind, GlobalKind, ContentsOfKind, CallRetValKind }; + enum Kind { UndefKind, ParmKind, GlobalKind, ContentsOfKind, ConjuredKind }; private: Kind K; @@ -165,32 +165,32 @@ public: } }; -class SymbolDataCallRetVal : public SymbolData { - CallExpr* CE; +class SymbolConjured : public SymbolData { + Expr* E; unsigned Count; public: - SymbolDataCallRetVal(SymbolID Sym, CallExpr* ce, unsigned count) - : SymbolData(CallRetValKind, Sym), CE(ce), Count(count) {} + SymbolConjured(SymbolID Sym, Expr* exp, unsigned count) + : SymbolData(ConjuredKind, Sym), E(exp), Count(count) {} - CallExpr* getCallExpr() const { return CE; } + Expr* getExpr() const { return E; } unsigned getCount() const { return Count; } static void Profile(llvm::FoldingSetNodeID& profile, - CallExpr* CE, unsigned Count) { + Expr* E, unsigned Count) { - profile.AddInteger((unsigned) CallRetValKind); - profile.AddPointer(CE); + profile.AddInteger((unsigned) ConjuredKind); + profile.AddPointer(E); profile.AddInteger(Count); } virtual void Profile(llvm::FoldingSetNodeID& profile) { - Profile(profile, CE, Count); + Profile(profile, E, Count); } // Implement isa support. static inline bool classof(const SymbolData* D) { - return D->getKind() == CallRetValKind; + return D->getKind() == ConjuredKind; } }; @@ -243,7 +243,7 @@ public: SymbolID getSymbol(VarDecl* D); SymbolID getContentsOfSymbol(SymbolID sym); - SymbolID getCallRetValSymbol(CallExpr* CE, unsigned VisitCount); + SymbolID getConjuredSymbol(Expr* E, unsigned VisitCount); const SymbolData& getSymbolData(SymbolID ID) const; -- 2.40.0