From 00a3a5f024ac54088ab887712b292171188064f0 Mon Sep 17 00:00:00 2001 From: Ted Kremenek Date: Wed, 12 Mar 2008 01:21:45 +0000 Subject: [PATCH] Prototype (pre-alpha) implementation of CFRef checker. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@48272 91177308-0d34-0410-b5e6-96231b3b80d8 --- Analysis/CFRefCount.cpp | 363 ++++++++++++++++-- Analysis/GRSimpleVals.cpp | 68 ++-- Analysis/GRSimpleVals.h | 21 +- Analysis/SymbolManager.cpp | 92 ++++- .../Analysis/PathSensitive/GRCoreEngine.h | 14 + .../Analysis/PathSensitive/GRExprEngine.h | 32 +- .../Analysis/PathSensitive/GRTransferFuncs.h | 30 +- .../Analysis/PathSensitive/SymbolManager.h | 173 ++++++--- .../clang/Analysis/PathSensitive/ValueState.h | 1 + 9 files changed, 618 insertions(+), 176 deletions(-) diff --git a/Analysis/CFRefCount.cpp b/Analysis/CFRefCount.cpp index ea9c8bfd37..a1f63b146a 100644 --- a/Analysis/CFRefCount.cpp +++ b/Analysis/CFRefCount.cpp @@ -86,6 +86,10 @@ public: return (*Args)[idx]; } + RetEffect getRet() const { + return Ret; + } + typedef ArgEffects::const_iterator arg_iterator; arg_iterator begin_args() const { return Args->begin(); } @@ -113,12 +117,24 @@ class CFRefSummaryManager { llvm::BumpPtrAllocator BPAlloc; ArgEffects ScratchArgs; + + + ArgEffects* getArgEffects(); + + CFRefSummary* getCannedCFSummary(FunctionTypeProto* FT, bool isRetain); + CFRefSummary* getCFSummary(FunctionDecl* FD, const char* FName); + + CFRefSummary* getCFSummaryCreateRule(FunctionTypeProto* FT); + CFRefSummary* getCFSummaryGetRule(FunctionTypeProto* FT); + + CFRefSummary* getPersistentSummary(ArgEffects* AE, RetEffect RE); + public: CFRefSummaryManager() {} ~CFRefSummaryManager(); - CFRefSummary* getSummary(FunctionDecl* FD); + CFRefSummary* getSummary(FunctionDecl* FD, ASTContext& Ctx); }; } // end anonymous namespace @@ -137,7 +153,59 @@ CFRefSummaryManager::~CFRefSummaryManager() { I->getValue().~ArgEffects(); } -CFRefSummary* CFRefSummaryManager::getSummary(FunctionDecl* FD) { +ArgEffects* CFRefSummaryManager::getArgEffects() { + + assert (!ScratchArgs.empty()); + + llvm::FoldingSetNodeID profile; + profile.Add(ScratchArgs); + void* InsertPos; + + llvm::FoldingSetNodeWrapper* E = + AESet.FindNodeOrInsertPos(profile, InsertPos); + + if (E) { + ScratchArgs.clear(); + return &E->getValue(); + } + + E = (llvm::FoldingSetNodeWrapper*) + BPAlloc.Allocate >(); + + new (E) llvm::FoldingSetNodeWrapper(ScratchArgs); + AESet.InsertNode(E, InsertPos); + + ScratchArgs.clear(); + return &E->getValue(); +} + +CFRefSummary* CFRefSummaryManager::getPersistentSummary(ArgEffects* AE, + RetEffect RE) { + + llvm::FoldingSetNodeID profile; + CFRefSummary::Profile(profile, AE, RE); + void* InsertPos; + + CFRefSummary* Summ = SummarySet.FindNodeOrInsertPos(profile, InsertPos); + + if (Summ) + return Summ; + + Summ = (CFRefSummary*) BPAlloc.Allocate(); + new (Summ) CFRefSummary(AE, RE); + SummarySet.InsertNode(Summ, InsertPos); + + return Summ; +} + + +CFRefSummary* CFRefSummaryManager::getSummary(FunctionDecl* FD, + ASTContext& Ctx) { + + SourceLocation Loc = FD->getLocation(); + + if (!Loc.isFileID()) + return NULL; { // Look into our cache of summaries to see if we have already computed // a summary for this FunctionDecl. @@ -148,12 +216,169 @@ CFRefSummary* CFRefSummaryManager::getSummary(FunctionDecl* FD) { return I->second; } - // +#if 0 + SourceManager& SrcMgr = Ctx.getSourceManager(); + unsigned fid = Loc.getFileID(); + const FileEntry* FE = SrcMgr.getFileEntryForID(fid); + if (!FE) + return NULL; + + const char* DirName = FE->getDir()->getName(); + assert (DirName); + assert (strlen(DirName) > 0); + + if (!strstr(DirName, "CoreFoundation")) { + SummaryMap[FD] = NULL; + return NULL; + } +#endif + + const char* FName = FD->getIdentifier()->getName(); + + if (FName[0] == 'C' && FName[1] == 'F') { + CFRefSummary* S = getCFSummary(FD, FName); + SummaryMap[FD] = S; + return S; + } return NULL; } +CFRefSummary* CFRefSummaryManager::getCFSummary(FunctionDecl* FD, + const char* FName) { + + // For now, only generate summaries for functions that have a prototype. + + FunctionTypeProto* FT = + dyn_cast(FD->getType().getTypePtr()); + + if (!FT) + return NULL; + + FName += 2; + + if (strcmp(FName, "Retain") == 0) + return getCannedCFSummary(FT, true); + + if (strcmp(FName, "Release") == 0) + return getCannedCFSummary(FT, false); + + assert (ScratchArgs.empty()); + bool usesCreateRule = false; + + if (strstr(FName, "Create")) + usesCreateRule = true; + + if (!usesCreateRule && strstr(FName, "Copy")) + usesCreateRule = true; + + if (usesCreateRule) + return getCFSummaryCreateRule(FT); + + if (strstr(FName, "Get")) + return getCFSummaryGetRule(FT); + + return NULL; +} + +CFRefSummary* CFRefSummaryManager::getCannedCFSummary(FunctionTypeProto* FT, + bool isRetain) { + + if (FT->getNumArgs() != 1) + return NULL; + + TypedefType* ArgT = dyn_cast(FT->getArgType(0).getTypePtr()); + + if (!ArgT) + return NULL; + + // For CFRetain/CFRelease, the first (and only) argument is of type + // "CFTypeRef". + + const char* TDName = ArgT->getDecl()->getIdentifier()->getName(); + assert (TDName); + + if (strcmp("CFTypeRef", TDName) == 0) + return NULL; + + if (!ArgT->isPointerType()) + return NULL; + + // Check the return type. It should also be "CFTypeRef". + + QualType RetTy = FT->getResultType(); + + if (RetTy.getTypePtr() != ArgT) + return NULL; + + // The function's interface checks out. Generate a canned summary. + + assert (ScratchArgs.empty()); + ScratchArgs.push_back(isRetain ? IncRef : DecRef); + + return getPersistentSummary(getArgEffects(), RetEffect::MakeAlias(0)); +} + +static bool isCFRefType(QualType T) { + + if (!T->isPointerType()) + return false; + + // Check the typedef for the name "CF" and the substring "Ref". + + TypedefType* TD = dyn_cast(T.getTypePtr()); + + if (!TD) + return false; + + const char* TDName = TD->getDecl()->getIdentifier()->getName(); + assert (TDName); + + if (TDName[0] != 'C' || TDName[1] != 'F') + return false; + + if (strstr(TDName, "Ref") == 0) + return false; + + return true; +} + + +CFRefSummary* +CFRefSummaryManager::getCFSummaryCreateRule(FunctionTypeProto* FT) { + + if (!isCFRefType(FT->getResultType())) + return NULL; + + assert (ScratchArgs.empty()); + + // FIXME: Add special-cases for functions that retain/release. For now + // just handle the default case. + + for (unsigned i = 0, n = FT->getNumArgs(); i != n; ++i) + ScratchArgs.push_back(DoNothing); + + return getPersistentSummary(getArgEffects(), RetEffect::MakeOwned()); +} + +CFRefSummary* +CFRefSummaryManager::getCFSummaryGetRule(FunctionTypeProto* FT) { + + if (!isCFRefType(FT->getResultType())) + return NULL; + + assert (ScratchArgs.empty()); + + // FIXME: Add special-cases for functions that retain/release. For now + // just handle the default case. + + for (unsigned i = 0, n = FT->getNumArgs(); i != n; ++i) + ScratchArgs.push_back(DoNothing); + + return getPersistentSummary(getArgEffects(), RetEffect::MakeNotOwned()); +} + //===----------------------------------------------------------------------===// // Transfer functions. //===----------------------------------------------------------------------===// @@ -246,8 +471,8 @@ class CFRefCount : public GRSimpleVals { // Instance variables. CFRefSummaryManager Summaries; - RefBFactoryTy RefBFactory; - + RefBFactoryTy RefBFactory; + UseAfterReleasesTy UseAfterReleases; ReleasesNotOwnedTy ReleasesNotOwned; @@ -282,9 +507,8 @@ public: // Calls. virtual void EvalCall(ExplodedNodeSet& Dst, - ValueStateManager& StateMgr, + GRExprEngine& Engine, GRStmtNodeBuilder& Builder, - BasicValueFactory& BasicVals, CallExpr* CE, LVal L, ExplodedNode* Pred); }; @@ -307,11 +531,12 @@ void CFRefCount::BindingsPrinter::PrintCheckerState(std::ostream& Out, } void CFRefCount::EvalCall(ExplodedNodeSet& Dst, - ValueStateManager& StateMgr, - GRStmtNodeBuilder& Builder, - BasicValueFactory& BasicVals, - CallExpr* CE, LVal L, - ExplodedNode* Pred) { + GRExprEngine& Engine, + GRStmtNodeBuilder& Builder, + CallExpr* CE, LVal L, + ExplodedNode* Pred) { + + ValueStateManager& StateMgr = Engine.getStateManager(); // FIXME: Support calls to things other than lval::FuncVal. At the very // least we should stop tracking ref-state for ref-counted objects passed @@ -323,7 +548,7 @@ void CFRefCount::EvalCall(ExplodedNodeSet& Dst, lval::FuncVal FV = cast(L); FunctionDecl* FD = FV.getDecl(); - CFRefSummary* Summ = Summaries.getSummary(FD); + CFRefSummary* Summ = Summaries.getSummary(FD, Engine.getContext()); // Get the state. @@ -355,35 +580,36 @@ void CFRefCount::EvalCall(ExplodedNodeSet& Dst, if (isa(V)) StateMgr.Unbind(StVals, cast(V)); - } - } - else { - - // This function has a summary. Evaluate the effect of the arguments. - - unsigned idx = 0; + } - for (CallExpr::arg_iterator I=CE->arg_begin(), E=CE->arg_end(); - I!=E; ++I, ++idx) { - - RVal V = StateMgr.GetRVal(St, *I); - - if (isa(V)) { - SymbolID Sym = cast(V).getSymbol(); - RefBindings B = GetRefBindings(StVals); - - if (RefBindings::TreeTy* T = B.SlimFind(Sym)) { - B = Update(B, Sym, T->getValue().second, Summ->getArg(idx), hasError); - SetRefBindings(StVals, B); - if (hasError) break; - } - } - } + St = StateMgr.getPersistentState(StVals); + Builder.Nodify(Dst, CE, Pred, St); + return; } - St = StateMgr.getPersistentState(StVals); + // This function has a summary. Evaluate the effect of the arguments. + unsigned idx = 0; + + for (CallExpr::arg_iterator I=CE->arg_begin(), E=CE->arg_end(); + I!=E; ++I, ++idx) { + + RVal V = StateMgr.GetRVal(St, *I); + + if (isa(V)) { + SymbolID Sym = cast(V).getSymbol(); + RefBindings B = GetRefBindings(StVals); + + if (RefBindings::TreeTy* T = B.SlimFind(Sym)) { + B = Update(B, Sym, T->getValue().second, Summ->getArg(idx), hasError); + SetRefBindings(StVals, B); + if (hasError) break; + } + } + } + if (hasError) { + St = StateMgr.getPersistentState(StVals); GRExprEngine::NodeTy* N = Builder.generateNode(CE, St, Pred); if (N) { @@ -399,10 +625,61 @@ void CFRefCount::EvalCall(ExplodedNodeSet& Dst, ReleasesNotOwned.insert(N); break; } - } + } + + return; } - else - Builder.Nodify(Dst, CE, Pred, St); + + // Finally, consult the summary for the return value. + + RetEffect RE = Summ->getRet(); + St = StateMgr.getPersistentState(StVals); + + + switch (RE.getKind()) { + default: + assert (false && "Unhandled RetEffect."); break; + + case RetEffect::Alias: { + unsigned idx = RE.getValue(); + assert (idx < CE->getNumArgs()); + RVal V = StateMgr.GetRVal(St, CE->getArg(idx)); + St = StateMgr.SetRVal(St, CE, V, Engine.getCFG().isBlkExpr(CE), false); + break; + } + + case RetEffect::OwnedSymbol: { + unsigned Count = Builder.getCurrentBlockCount(); + SymbolID Sym = Engine.getSymbolManager().getCallRetValSymbol(CE, Count); + + ValueState StImpl = *St; + RefBindings B = GetRefBindings(StImpl); + SetRefBindings(StImpl, RefBFactory.Add(B, Sym, RefVal::makeOwned(1))); + + St = StateMgr.SetRVal(StateMgr.getPersistentState(StImpl), + CE, lval::SymbolVal(Sym), + Engine.getCFG().isBlkExpr(CE), false); + + break; + } + + case RetEffect::NotOwnedSymbol: { + unsigned Count = Builder.getCurrentBlockCount(); + SymbolID Sym = Engine.getSymbolManager().getCallRetValSymbol(CE, Count); + + ValueState StImpl = *St; + RefBindings B = GetRefBindings(StImpl); + SetRefBindings(StImpl, RefBFactory.Add(B, Sym, RefVal::makeNotOwned())); + + St = StateMgr.SetRVal(StateMgr.getPersistentState(StImpl), + CE, lval::SymbolVal(Sym), + Engine.getCFG().isBlkExpr(CE), false); + + break; + } + } + + Builder.Nodify(Dst, CE, Pred, St); } @@ -418,6 +695,12 @@ CFRefCount::RefBindings CFRefCount::Update(RefBindings B, SymbolID sym, assert (false && "Unhandled CFRef transition."); case DoNothing: + if (V.getKind() == RefVal::Released) { + V = RefVal::makeUseAfterRelease(); + hasError = V.getKind(); + break; + } + return B; case IncRef: diff --git a/Analysis/GRSimpleVals.cpp b/Analysis/GRSimpleVals.cpp index ae06917e13..16cd6747a0 100644 --- a/Analysis/GRSimpleVals.cpp +++ b/Analysis/GRSimpleVals.cpp @@ -95,13 +95,13 @@ unsigned RunGRSimpleVals(CFG& cfg, FunctionDecl& FD, ASTContext& Ctx, if (Diag.hasErrorOccurred()) return 0; - GRCoreEngine Engine(cfg, FD, Ctx); - GRExprEngine* CheckerState = &Engine.getCheckerState(); + GRCoreEngine Eng(cfg, FD, Ctx); + GRExprEngine* CheckerState = &Eng.getCheckerState(); GRSimpleVals GRSV; CheckerState->setTransferFunctions(GRSV); // Execute the worklist algorithm. - Engine.ExecuteWorkList(50000); + Eng.ExecuteWorkList(50000); SourceManager& SrcMgr = Ctx.getSourceManager(); @@ -144,7 +144,7 @@ unsigned RunGRSimpleVals(CFG& cfg, FunctionDecl& FD, ASTContext& Ctx, if (Visualize) CheckerState->ViewGraph(TrimGraph); #endif - return Engine.getGraph().size(); + return Eng.getGraph().size(); } } // end clang namespace @@ -153,14 +153,16 @@ unsigned RunGRSimpleVals(CFG& cfg, FunctionDecl& FD, ASTContext& Ctx, // Transfer function for Casts. //===----------------------------------------------------------------------===// -RVal GRSimpleVals::EvalCast(BasicValueFactory& BasicVals, NonLVal X, QualType T) { +RVal GRSimpleVals::EvalCast(GRExprEngine& Eng, NonLVal X, QualType T) { if (!isa(X)) return UnknownVal(); + + BasicValueFactory& BasicVals = Eng.getBasicVals(); llvm::APSInt V = cast(X).getValue(); V.setIsUnsigned(T->isUnsignedIntegerType() || T->isPointerType()); - V.extOrTrunc(BasicVals.getContext().getTypeSize(T)); + V.extOrTrunc(Eng.getContext().getTypeSize(T)); if (T->isPointerType()) return lval::ConcreteInt(BasicVals.getValue(V)); @@ -170,7 +172,7 @@ RVal GRSimpleVals::EvalCast(BasicValueFactory& BasicVals, NonLVal X, QualType T) // Casts. -RVal GRSimpleVals::EvalCast(BasicValueFactory& BasicVals, LVal X, QualType T) { +RVal GRSimpleVals::EvalCast(GRExprEngine& Eng, LVal X, QualType T) { if (T->isPointerType() || T->isReferenceType()) return X; @@ -180,33 +182,35 @@ RVal GRSimpleVals::EvalCast(BasicValueFactory& BasicVals, LVal X, QualType T) { if (!isa(X)) return UnknownVal(); + BasicValueFactory& BasicVals = Eng.getBasicVals(); + llvm::APSInt V = cast(X).getValue(); V.setIsUnsigned(T->isUnsignedIntegerType() || T->isPointerType()); - V.extOrTrunc(BasicVals.getContext().getTypeSize(T)); + V.extOrTrunc(Eng.getContext().getTypeSize(T)); return nonlval::ConcreteInt(BasicVals.getValue(V)); } // Unary operators. -RVal GRSimpleVals::EvalMinus(BasicValueFactory& BasicVals, UnaryOperator* U, NonLVal X){ +RVal GRSimpleVals::EvalMinus(GRExprEngine& Eng, UnaryOperator* U, NonLVal X){ switch (X.getSubKind()) { case nonlval::ConcreteIntKind: - return cast(X).EvalMinus(BasicVals, U); + return cast(X).EvalMinus(Eng.getBasicVals(), U); default: return UnknownVal(); } } -RVal GRSimpleVals::EvalComplement(BasicValueFactory& BasicVals, NonLVal X) { +RVal GRSimpleVals::EvalComplement(GRExprEngine& Eng, NonLVal X) { switch (X.getSubKind()) { case nonlval::ConcreteIntKind: - return cast(X).EvalComplement(BasicVals); + return cast(X).EvalComplement(Eng.getBasicVals()); default: return UnknownVal(); @@ -215,8 +219,11 @@ RVal GRSimpleVals::EvalComplement(BasicValueFactory& BasicVals, NonLVal X) { // Binary operators. -RVal GRSimpleVals::EvalBinOp(BasicValueFactory& BasicVals, BinaryOperator::Opcode Op, - NonLVal L, NonLVal R) { +RVal GRSimpleVals::EvalBinOp(GRExprEngine& Eng, BinaryOperator::Opcode Op, + NonLVal L, NonLVal R) { + + BasicValueFactory& BasicVals = Eng.getBasicVals(); + while (1) { switch (L.getSubKind()) { @@ -242,7 +249,7 @@ RVal GRSimpleVals::EvalBinOp(BasicValueFactory& BasicVals, BinaryOperator::Opcod if (isa(R)) { const SymIntConstraint& C = BasicVals.getConstraint(cast(L).getSymbol(), Op, - cast(R).getValue()); + cast(R).getValue()); return nonlval::SymIntConstraintVal(C); } @@ -256,7 +263,7 @@ RVal GRSimpleVals::EvalBinOp(BasicValueFactory& BasicVals, BinaryOperator::Opcod // Binary Operators (except assignments and comma). -RVal GRSimpleVals::EvalBinOp(BasicValueFactory& BasicVals, BinaryOperator::Opcode Op, +RVal GRSimpleVals::EvalBinOp(GRExprEngine& Eng, BinaryOperator::Opcode Op, LVal L, LVal R) { switch (Op) { @@ -265,23 +272,25 @@ RVal GRSimpleVals::EvalBinOp(BasicValueFactory& BasicVals, BinaryOperator::Opcod return UnknownVal(); case BinaryOperator::EQ: - return EvalEQ(BasicVals, L, R); + return EvalEQ(Eng, L, R); case BinaryOperator::NE: - return EvalNE(BasicVals, L, R); + return EvalNE(Eng, L, R); } } // Pointer arithmetic. -RVal GRSimpleVals::EvalBinOp(BasicValueFactory& BasicVals, BinaryOperator::Opcode Op, +RVal GRSimpleVals::EvalBinOp(GRExprEngine& Eng, BinaryOperator::Opcode Op, LVal L, NonLVal R) { return UnknownVal(); } // Equality operators for LVals. -RVal GRSimpleVals::EvalEQ(BasicValueFactory& BasicVals, LVal L, LVal R) { +RVal GRSimpleVals::EvalEQ(GRExprEngine& Eng, LVal L, LVal R) { + + BasicValueFactory& BasicVals = Eng.getBasicVals(); switch (L.getSubKind()) { @@ -337,8 +346,10 @@ RVal GRSimpleVals::EvalEQ(BasicValueFactory& BasicVals, LVal L, LVal R) { return NonLVal::MakeIntTruthVal(BasicVals, false); } -RVal GRSimpleVals::EvalNE(BasicValueFactory& BasicVals, LVal L, LVal R) { +RVal GRSimpleVals::EvalNE(GRExprEngine& Eng, LVal L, LVal R) { + BasicValueFactory& BasicVals = Eng.getBasicVals(); + switch (L.getSubKind()) { default: @@ -356,8 +367,8 @@ RVal GRSimpleVals::EvalNE(BasicValueFactory& BasicVals, LVal L, LVal R) { else if (isa(R)) { const SymIntConstraint& C = BasicVals.getConstraint(cast(R).getSymbol(), - BinaryOperator::NE, - cast(L).getValue()); + BinaryOperator::NE, + cast(L).getValue()); return nonlval::SymIntConstraintVal(C); } @@ -368,8 +379,8 @@ RVal GRSimpleVals::EvalNE(BasicValueFactory& BasicVals, LVal L, LVal R) { if (isa(R)) { const SymIntConstraint& C = BasicVals.getConstraint(cast(L).getSymbol(), - BinaryOperator::NE, - cast(R).getValue()); + BinaryOperator::NE, + cast(R).getValue()); return nonlval::SymIntConstraintVal(C); } @@ -398,9 +409,8 @@ RVal GRSimpleVals::EvalNE(BasicValueFactory& BasicVals, LVal L, LVal R) { //===----------------------------------------------------------------------===// void GRSimpleVals::EvalCall(ExplodedNodeSet& Dst, - ValueStateManager& StateMgr, + GRExprEngine& Eng, GRStmtNodeBuilder& Builder, - BasicValueFactory& BasicVals, CallExpr* CE, LVal L, ExplodedNode* Pred) { @@ -411,10 +421,10 @@ void GRSimpleVals::EvalCall(ExplodedNodeSet& Dst, for (CallExpr::arg_iterator I = CE->arg_begin(), E = CE->arg_end(); I != E; ++I) { - RVal V = StateMgr.GetRVal(St, *I); + RVal V = Eng.getStateManager().GetRVal(St, *I); if (isa(V)) - St = StateMgr.SetRVal(St, cast(V), UnknownVal()); + St = Eng.getStateManager().SetRVal(St, cast(V), UnknownVal()); } Builder.Nodify(Dst, CE, Pred, St); diff --git a/Analysis/GRSimpleVals.h b/Analysis/GRSimpleVals.h index 33ccd26be3..2b3d0fd00a 100644 --- a/Analysis/GRSimpleVals.h +++ b/Analysis/GRSimpleVals.h @@ -28,34 +28,33 @@ public: // Casts. - virtual RVal EvalCast(BasicValueFactory& BasicVals, NonLVal V, QualType CastT); - virtual RVal EvalCast(BasicValueFactory& BasicVals, LVal V, QualType CastT); + virtual RVal EvalCast(GRExprEngine& Engine, NonLVal V, QualType CastT); + virtual RVal EvalCast(GRExprEngine& Engine, LVal V, QualType CastT); // Unary Operators. - virtual RVal EvalMinus(BasicValueFactory& BasicVals, UnaryOperator* U, NonLVal X); + virtual RVal EvalMinus(GRExprEngine& Engine, UnaryOperator* U, NonLVal X); - virtual RVal EvalComplement(BasicValueFactory& BasicVals, NonLVal X); + virtual RVal EvalComplement(GRExprEngine& Engine, NonLVal X); // Binary Operators. - virtual RVal EvalBinOp(BasicValueFactory& BasicVals, BinaryOperator::Opcode Op, + virtual RVal EvalBinOp(GRExprEngine& Engine, BinaryOperator::Opcode Op, NonLVal L, NonLVal R); - virtual RVal EvalBinOp(BasicValueFactory& BasicVals, BinaryOperator::Opcode Op, + virtual RVal EvalBinOp(GRExprEngine& Engine, BinaryOperator::Opcode Op, LVal L, LVal R); // Pointer arithmetic. - virtual RVal EvalBinOp(BasicValueFactory& BasicVals, BinaryOperator::Opcode Op, + virtual RVal EvalBinOp(GRExprEngine& Engine, BinaryOperator::Opcode Op, LVal L, NonLVal R); // Calls. virtual void EvalCall(ExplodedNodeSet& Dst, - ValueStateManager& StateMgr, + GRExprEngine& Engine, GRStmtNodeBuilder& Builder, - BasicValueFactory& BasicVals, CallExpr* CE, LVal L, ExplodedNode* Pred); @@ -63,8 +62,8 @@ protected: // Equality operators for LVals. - RVal EvalEQ(BasicValueFactory& BasicVals, LVal L, LVal R); - RVal EvalNE(BasicValueFactory& BasicVals, LVal L, LVal R); + RVal EvalEQ(GRExprEngine& Engine, LVal L, LVal R); + RVal EvalNE(GRExprEngine& Engine, LVal L, LVal R); }; } // end clang namespace diff --git a/Analysis/SymbolManager.cpp b/Analysis/SymbolManager.cpp index 95fbbb937a..5454649443 100644 --- a/Analysis/SymbolManager.cpp +++ b/Analysis/SymbolManager.cpp @@ -20,30 +20,84 @@ SymbolID SymbolManager::getSymbol(VarDecl* D) { assert (isa(D) || D->hasGlobalStorage()); - SymbolID& X = DataToSymbol[getKey(D)]; - - if (!X.isInitialized()) { - X = SymbolToData.size(); - - if (ParmVarDecl* VD = dyn_cast(D)) - SymbolToData.push_back(SymbolDataParmVar(VD)); - else - SymbolToData.push_back(SymbolDataGlobalVar(D)); + llvm::FoldingSetNodeID profile; + + ParmVarDecl* PD = dyn_cast(D); + + if (PD) + SymbolDataParmVar::Profile(profile, PD); + else + SymbolDataGlobalVar::Profile(profile, D); + + void* InsertPos; + + SymbolData* SD = DataSet.FindNodeOrInsertPos(profile, InsertPos); + + if (SD) + return SD->getSymbol(); + + if (PD) { + SD = (SymbolData*) BPAlloc.Allocate(); + new (SD) SymbolDataParmVar(SymbolCounter, PD); + } + else { + SD = (SymbolData*) BPAlloc.Allocate(); + new (SD) SymbolDataGlobalVar(SymbolCounter, D); } - return X; + DataSet.InsertNode(SD, InsertPos); + + DataMap[SymbolCounter] = SD; + return SymbolCounter++; } SymbolID SymbolManager::getContentsOfSymbol(SymbolID sym) { - SymbolID& X = DataToSymbol[getKey(sym)]; - if (!X.isInitialized()) { - X = SymbolToData.size(); - SymbolToData.push_back(SymbolDataContentsOf(sym)); - } + llvm::FoldingSetNodeID profile; + SymbolDataContentsOf::Profile(profile, sym); + void* InsertPos; + + SymbolData* SD = DataSet.FindNodeOrInsertPos(profile, InsertPos); + + if (SD) + return SD->getSymbol(); + + SD = (SymbolData*) BPAlloc.Allocate(); + new (SD) SymbolDataContentsOf(SymbolCounter, sym); + + + DataSet.InsertNode(SD, InsertPos); + DataMap[SymbolCounter] = SD; - return X; + return SymbolCounter++; } + +SymbolID SymbolManager::getCallRetValSymbol(CallExpr* CE, unsigned Count) { + + llvm::FoldingSetNodeID profile; + SymbolDataCallRetVal::Profile(profile, CE, Count); + void* InsertPos; + + SymbolData* SD = DataSet.FindNodeOrInsertPos(profile, InsertPos); + + if (SD) + return SD->getSymbol(); + + SD = (SymbolData*) BPAlloc.Allocate(); + new (SD) SymbolDataCallRetVal(SymbolCounter, CE, Count); + + DataSet.InsertNode(SD, InsertPos); + DataMap[SymbolCounter] = SD; + + return SymbolCounter++; +} + +const SymbolData& SymbolManager::getSymbolData(SymbolID Sym) const { + DataMapTy::const_iterator I = DataMap.find(Sym); + assert (I != DataMap.end()); + return *I->second; +} + QualType SymbolData::getType(const SymbolManager& SymMgr) const { switch (getKind()) { @@ -57,12 +111,14 @@ QualType SymbolData::getType(const SymbolManager& SymMgr) const { return cast(this)->getDecl()->getType(); case ContentsOfKind: { - SymbolID x = cast(this)->getSymbol(); + SymbolID x = cast(this)->getContainerSymbol(); QualType T = SymMgr.getSymbolData(x).getType(SymMgr); return T->getAsPointerType()->getPointeeType(); } + + case CallRetValKind: + return cast(this)->getCallExpr()->getType(); } } -SymbolManager::SymbolManager() {} SymbolManager::~SymbolManager() {} diff --git a/include/clang/Analysis/PathSensitive/GRCoreEngine.h b/include/clang/Analysis/PathSensitive/GRCoreEngine.h index 9a8be4e0fd..bb0e209552 100644 --- a/include/clang/Analysis/PathSensitive/GRCoreEngine.h +++ b/include/clang/Analysis/PathSensitive/GRCoreEngine.h @@ -143,6 +143,12 @@ public: return LastNode ? (LastNode->isSink() ? NULL : LastNode) : NULL; } + GRBlockCounter getBlockCounter() const { return Eng.WList->getBlockCounter();} + + unsigned getCurrentBlockCount() const { + return getBlockCounter().getNumVisited(B.getBlockID()); + } + ExplodedNodeImpl* generateNodeImpl(Stmt* S, void* State, ExplodedNodeImpl* Pred); @@ -182,6 +188,14 @@ public: return static_cast(NB.generateNodeImpl(S, St)); } + GRBlockCounter getBlockCounter() const { + return NB.getBlockCounter(); + } + + unsigned getCurrentBlockCount() const { + return NB.getCurrentBlockCount(); + } + StateTy* GetState(NodeTy* Pred) const { if ((ExplodedNodeImpl*) Pred == NB.getBasePredecessor()) return CleanedState; diff --git a/include/clang/Analysis/PathSensitive/GRExprEngine.h b/include/clang/Analysis/PathSensitive/GRExprEngine.h index 1a4c814a5f..405dada995 100644 --- a/include/clang/Analysis/PathSensitive/GRExprEngine.h +++ b/include/clang/Analysis/PathSensitive/GRExprEngine.h @@ -263,6 +263,16 @@ public: /// nodes by processing the 'effects' of a switch statement. void ProcessSwitch(SwitchNodeBuilder& builder); + + ValueStateManager& getStateManager() { return StateMgr; } + const ValueStateManager& getStateManger() const { return StateMgr; } + + BasicValueFactory& getBasicVals() { return BasicVals; } + const BasicValueFactory& getBasicVals() const { return BasicVals; } + + SymbolManager& getSymbolManager() { return SymMgr; } + const SymbolManager& getSymbolManager() const { return SymMgr; } + protected: ValueState* GetState(NodeTy* N) { @@ -394,25 +404,25 @@ protected: return X; if (isa(X)) - return TF->EvalCast(BasicVals, cast(X), CastT); + return TF->EvalCast(*this, cast(X), CastT); else - return TF->EvalCast(BasicVals, cast(X), CastT); + return TF->EvalCast(*this, cast(X), CastT); } RVal EvalMinus(UnaryOperator* U, RVal X) { - return X.isValid() ? TF->EvalMinus(BasicVals, U, cast(X)) : X; + return X.isValid() ? TF->EvalMinus(*this, U, cast(X)) : X; } RVal EvalComplement(RVal X) { - return X.isValid() ? TF->EvalComplement(BasicVals, cast(X)) : X; + return X.isValid() ? TF->EvalComplement(*this, cast(X)) : X; } RVal EvalBinOp(BinaryOperator::Opcode Op, NonLVal L, RVal R) { - return R.isValid() ? TF->EvalBinOp(BasicVals, Op, L, cast(R)) : R; + return R.isValid() ? TF->EvalBinOp(*this, Op, L, cast(R)) : R; } RVal EvalBinOp(BinaryOperator::Opcode Op, NonLVal L, NonLVal R) { - return R.isValid() ? TF->EvalBinOp(BasicVals, Op, L, R) : R; + return R.isValid() ? TF->EvalBinOp(*this, Op, L, R) : R; } RVal EvalBinOp(BinaryOperator::Opcode Op, RVal L, RVal R) { @@ -425,9 +435,9 @@ protected: if (isa(L)) { if (isa(R)) - return TF->EvalBinOp(BasicVals, Op, cast(L), cast(R)); + return TF->EvalBinOp(*this, Op, cast(L), cast(R)); else - return TF->EvalBinOp(BasicVals, Op, cast(L), cast(R)); + return TF->EvalBinOp(*this, Op, cast(L), cast(R)); } if (isa(R)) { @@ -437,15 +447,15 @@ protected: assert (Op == BinaryOperator::Add || Op == BinaryOperator::Sub); // Commute the operands. - return TF->EvalBinOp(BasicVals, Op, cast(R), cast(L)); + return TF->EvalBinOp(*this, Op, cast(R), cast(L)); } else - return TF->EvalBinOp(BasicVals, Op, cast(L), cast(R)); + return TF->EvalBinOp(*this, Op, cast(L), cast(R)); } void EvalCall(NodeSet& Dst, CallExpr* CE, LVal L, NodeTy* Pred) { assert (Builder && "GRStmtNodeBuilder must be defined."); - return TF->EvalCall(Dst, StateMgr, *Builder, BasicVals, CE, L, Pred); + return TF->EvalCall(Dst, *this, *Builder, CE, L, Pred); } ValueState* MarkBranch(ValueState* St, Stmt* Terminator, bool branchTaken); diff --git a/include/clang/Analysis/PathSensitive/GRTransferFuncs.h b/include/clang/Analysis/PathSensitive/GRTransferFuncs.h index 7432c7fb61..55a0fae273 100644 --- a/include/clang/Analysis/PathSensitive/GRTransferFuncs.h +++ b/include/clang/Analysis/PathSensitive/GRTransferFuncs.h @@ -21,6 +21,8 @@ namespace clang { + class GRExprEngine; + class GRTransferFuncs { public: GRTransferFuncs() {} @@ -32,38 +34,34 @@ public: // Casts. - virtual RVal EvalCast(BasicValueFactory& BasicVals, NonLVal V, - QualType CastT) =0; - - virtual RVal EvalCast(BasicValueFactory& BasicVals, LVal V, - QualType CastT) = 0; + virtual RVal EvalCast(GRExprEngine& Engine, NonLVal V, QualType CastT) =0; + virtual RVal EvalCast(GRExprEngine& Engine, LVal V, QualType CastT) = 0; // Unary Operators. - virtual RVal EvalMinus(BasicValueFactory& BasicVals, UnaryOperator* U, - NonLVal X) = 0; + virtual RVal EvalMinus(GRExprEngine& Engine, UnaryOperator* U, NonLVal X) = 0; - virtual RVal EvalComplement(BasicValueFactory& BasicVals, NonLVal X) = 0; + virtual RVal EvalComplement(GRExprEngine& Engine, NonLVal X) = 0; // Binary Operators. - virtual RVal EvalBinOp(BasicValueFactory& BasicVals, - BinaryOperator::Opcode Op, NonLVal L, NonLVal R) = 0; + virtual RVal EvalBinOp(GRExprEngine& Engine, BinaryOperator::Opcode Op, + NonLVal L, NonLVal R) = 0; - virtual RVal EvalBinOp(BasicValueFactory& BasicVals, - BinaryOperator::Opcode Op, LVal L, LVal R) = 0; + virtual RVal EvalBinOp(GRExprEngine& Engine, BinaryOperator::Opcode Op, + LVal L, LVal R) = 0; // Pointer arithmetic. - virtual RVal EvalBinOp(BasicValueFactory& BasicVals, - BinaryOperator::Opcode Op, LVal L, NonLVal R) = 0; + virtual RVal EvalBinOp(GRExprEngine& Engine, BinaryOperator::Opcode Op, + LVal L, NonLVal R) = 0; // Calls. virtual void EvalCall(ExplodedNodeSet& Dst, - ValueStateManager& StateMgr, + GRExprEngine& Engine, GRStmtNodeBuilder& Builder, - BasicValueFactory& BasicVals, CallExpr* CE, LVal L, + CallExpr* CE, LVal L, ExplodedNode* Pred) = 0; }; diff --git a/include/clang/Analysis/PathSensitive/SymbolManager.h b/include/clang/Analysis/PathSensitive/SymbolManager.h index 125100aebb..e3eedd736b 100644 --- a/include/clang/Analysis/PathSensitive/SymbolManager.h +++ b/include/clang/Analysis/PathSensitive/SymbolManager.h @@ -20,7 +20,7 @@ #include "llvm/ADT/FoldingSet.h" #include "llvm/ADT/DenseMap.h" #include "llvm/Support/DataTypes.h" -#include +#include "llvm/Support/Allocator.h" namespace clang { @@ -28,15 +28,14 @@ class SymbolManager; class SymbolID { unsigned Data; + public: - SymbolID() : Data(~0) {} SymbolID(unsigned x) : Data(x) {} - bool isInitialized() const { return Data != (unsigned) ~0; } - operator unsigned() const { assert (isInitialized()); return Data; } + operator unsigned() const { return Data; } + unsigned getNumber() const { return Data; } void Profile(llvm::FoldingSetNodeID& ID) const { - assert (isInitialized()); ID.AddInteger(Data); } @@ -44,51 +43,74 @@ public: X.Profile(ID); } }; + +} // end clang namespace + +namespace llvm { + template <> struct DenseMapInfo { + static inline clang::SymbolID getEmptyKey() { + return clang::SymbolID(~0U); + } + static inline clang::SymbolID getTombstoneKey() { + return clang::SymbolID(~0U - 1); + } + static unsigned getHashValue(clang::SymbolID X) { + return X.getNumber(); + } + static bool isEqual(clang::SymbolID X, clang::SymbolID Y) { + return X.getNumber() == Y.getNumber(); + } + static bool isPod() { return true; } + }; +} // SymbolData: Used to record meta data about symbols. -class SymbolData { +namespace clang { + +class SymbolData : public llvm::FoldingSetNode { public: - enum Kind { UndefKind, ParmKind, GlobalKind, ContentsOfKind }; + enum Kind { UndefKind, ParmKind, GlobalKind, ContentsOfKind, CallRetValKind }; private: - uintptr_t Data; Kind K; + SymbolID Sym; protected: - SymbolData(uintptr_t D, Kind k) : Data(D), K(k) {} - SymbolData(void* D, Kind k) : Data(reinterpret_cast(D)), K(k) {} - - void* getPtr() const { - assert (K != UndefKind); - return reinterpret_cast(Data); - } - - uintptr_t getInt() const { - assert (K != UndefKind); - return Data; - } - + SymbolData(Kind k, SymbolID sym) : K(k), Sym(sym) {} + public: - SymbolData() : Data(0), K(UndefKind) {} + virtual ~SymbolData() {} - Kind getKind() const { return K; } - - inline bool operator==(const SymbolData& R) const { - return K == R.K && Data == R.Data; - } + Kind getKind() const { return K; } + SymbolID getSymbol() const { return Sym; } + QualType getType(const SymbolManager& SymMgr) const; + virtual void Profile(llvm::FoldingSetNodeID& profile) = 0; + // Implement isa support. static inline bool classof(const SymbolData*) { return true; } }; class SymbolDataParmVar : public SymbolData { -public: - SymbolDataParmVar(ParmVarDecl* VD) : SymbolData(VD, ParmKind) {} + ParmVarDecl *VD; + +public: + SymbolDataParmVar(SymbolID MySym, ParmVarDecl* vd) + : SymbolData(ParmKind, MySym), VD(vd) {} + + ParmVarDecl* getDecl() const { return VD; } - ParmVarDecl* getDecl() const { return (ParmVarDecl*) getPtr(); } + static void Profile(llvm::FoldingSetNodeID& profile, ParmVarDecl* VD) { + profile.AddInteger((unsigned) ParmKind); + profile.AddPointer(VD); + } + + virtual void Profile(llvm::FoldingSetNodeID& profile) { + Profile(profile, VD); + } // Implement isa support. static inline bool classof(const SymbolData* D) { @@ -97,10 +119,22 @@ public: }; class SymbolDataGlobalVar : public SymbolData { + VarDecl *VD; + public: - SymbolDataGlobalVar(VarDecl* VD) : SymbolData(VD, GlobalKind) {} + SymbolDataGlobalVar(SymbolID MySym, VarDecl* vd) : + SymbolData(GlobalKind, MySym), VD(vd) {} + + VarDecl* getDecl() const { return VD; } - VarDecl* getDecl() const { return (VarDecl*) getPtr(); } + static void Profile(llvm::FoldingSetNodeID& profile, VarDecl* VD) { + profile.AddInteger((unsigned) GlobalKind); + profile.AddPointer(VD); + } + + virtual void Profile(llvm::FoldingSetNodeID& profile) { + Profile(profile, VD); + } // Implement isa support. static inline bool classof(const SymbolData* D) { @@ -109,16 +143,57 @@ public: }; class SymbolDataContentsOf : public SymbolData { + SymbolID Sym; + public: - SymbolDataContentsOf(SymbolID ID) : SymbolData(ID, ContentsOfKind) {} + SymbolDataContentsOf(SymbolID MySym, SymbolID sym) : + SymbolData(ContentsOfKind, MySym), Sym(sym) {} + + SymbolID getContainerSymbol() const { return Sym; } - SymbolID getSymbol() const { return (SymbolID) getInt(); } + static void Profile(llvm::FoldingSetNodeID& profile, SymbolID Sym) { + profile.AddInteger((unsigned) ContentsOfKind); + profile.AddInteger(Sym); + } + + virtual void Profile(llvm::FoldingSetNodeID& profile) { + Profile(profile, Sym); + } // Implement isa support. static inline bool classof(const SymbolData* D) { return D->getKind() == ContentsOfKind; } }; + +class SymbolDataCallRetVal : public SymbolData { + CallExpr* CE; + unsigned Count; + +public: + SymbolDataCallRetVal(SymbolID Sym, CallExpr* ce, unsigned count) + : SymbolData(CallRetValKind, Sym), CE(ce), Count(count) {} + + CallExpr* getCallExpr() const { return CE; } + unsigned getCount() const { return Count; } + + static void Profile(llvm::FoldingSetNodeID& profile, + CallExpr* CE, unsigned Count) { + + profile.AddInteger((unsigned) CallRetValKind); + profile.AddPointer(CE); + profile.AddInteger(Count); + } + + virtual void Profile(llvm::FoldingSetNodeID& profile) { + Profile(profile, CE, Count); + } + + // Implement isa support. + static inline bool classof(const SymbolData* D) { + return D->getKind() == CallRetValKind; + } +}; // Constraints on symbols. Usually wrapped by RValues. @@ -133,7 +208,7 @@ public: Op(op), Val(V) {} BinaryOperator::Opcode getOpcode() const { return Op; } - const SymbolID& getSymbol() const { return Symbol; } + SymbolID getSymbol() const { return Symbol; } const llvm::APSInt& getInt() const { return Val; } static inline void Profile(llvm::FoldingSetNodeID& ID, @@ -152,32 +227,28 @@ public: class SymbolManager { - std::vector SymbolToData; - - typedef llvm::DenseMap MapTy; - MapTy DataToSymbol; + typedef llvm::FoldingSet DataSetTy; + typedef llvm::DenseMap DataMapTy; - void* getKey(void* P) const { - return reinterpret_cast(reinterpret_cast(P) | 0x1); - } + DataSetTy DataSet; + DataMapTy DataMap; - void* getKey(SymbolID sym) const { - return reinterpret_cast((uintptr_t) (sym << 1)); - } + unsigned SymbolCounter; + llvm::BumpPtrAllocator& BPAlloc; public: - SymbolManager(); + SymbolManager(llvm::BumpPtrAllocator& bpalloc) + : SymbolCounter(0), BPAlloc(bpalloc) {} + ~SymbolManager(); SymbolID getSymbol(VarDecl* D); SymbolID getContentsOfSymbol(SymbolID sym); + SymbolID getCallRetValSymbol(CallExpr* CE, unsigned VisitCount); - inline const SymbolData& getSymbolData(SymbolID ID) const { - assert (ID < SymbolToData.size()); - return SymbolToData[ID]; - } + const SymbolData& getSymbolData(SymbolID ID) const; - inline QualType getType(SymbolID ID) const { + QualType getType(SymbolID ID) const { return getSymbolData(ID).getType(*this); } }; diff --git a/include/clang/Analysis/PathSensitive/ValueState.h b/include/clang/Analysis/PathSensitive/ValueState.h index 1a6ad38a9e..71e6abddba 100644 --- a/include/clang/Analysis/PathSensitive/ValueState.h +++ b/include/clang/Analysis/PathSensitive/ValueState.h @@ -214,6 +214,7 @@ public: CNEFactory(alloc), CEFactory(alloc), BasicVals(Ctx, alloc), + SymMgr(alloc), Alloc(alloc) {} ValueState* getInitialState(); -- 2.40.0