From 8ff5c41f2bde7ebbe568b4c15e59f14b8befae66 Mon Sep 17 00:00:00 2001 From: Anna Zaks Date: Mon, 24 Oct 2011 18:25:58 +0000 Subject: [PATCH] [analyzer] Use a temporary builder in CheckerContext. First step toward removing the global Stmt builder. Added several transitional methods (like takeNodes/addNodes). + Stop early if the set of exploded nodes for the next iteration is empty. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@142827 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../Core/PathSensitive/CheckerContext.h | 10 +---- .../Core/PathSensitive/CoreEngine.h | 38 +++++++++++++--- lib/StaticAnalyzer/Core/CheckerContext.cpp | 8 +--- lib/StaticAnalyzer/Core/CheckerManager.cpp | 44 +++++++++++++------ lib/StaticAnalyzer/Core/CoreEngine.cpp | 2 +- lib/StaticAnalyzer/Core/ExprEngine.cpp | 3 ++ 6 files changed, 68 insertions(+), 37 deletions(-) diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h b/include/clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h index 522749c37c..afb19276da 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h @@ -23,29 +23,24 @@ namespace clang { namespace ento { class CheckerContext { - ExplodedNodeSet &Dst; ExprEngine &Eng; ExplodedNode *Pred; const ProgramPoint Location; const ProgramState *ST; - const unsigned size; NodeBuilder &NB; public: bool *respondsToCallback; public: - CheckerContext(ExplodedNodeSet &dst, - NodeBuilder &builder, + CheckerContext(NodeBuilder &builder, ExprEngine &eng, ExplodedNode *pred, const ProgramPoint &loc, bool *respondsToCB = 0, const ProgramState *st = 0) - : Dst(dst), - Eng(eng), + : Eng(eng), Pred(pred), Location(loc), ST(st), - size(Dst.size()), NB(builder), respondsToCallback(respondsToCB) { assert(!(ST && ST != Pred->getState())); @@ -153,7 +148,6 @@ private: bool markAsSink, ExplodedNode *pred = 0, const ProgramPointTag *tag = 0) { - ExplodedNode *node = NB.generateNode(tag ? Location.withTag(tag) : Location, state, pred ? pred : Pred, markAsSink); diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h b/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h index 934d15d8cc..f31cdc986d 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h @@ -202,6 +202,14 @@ protected: return true; } + bool haveNoSinksInFrontier() { + for (iterator I = Frontier.begin(), E = Frontier.end(); I != E; ++I) { + if ((*I)->isSink()) + return false; + } + return true; + } + /// Allow subclasses to finalize results before result_begin() is executed. virtual void finalizeResults() {} @@ -214,13 +222,19 @@ public: NodeBuilder(ExplodedNode *SrcNode, ExplodedNodeSet &DstSet, const NodeBuilderContext &Ctx, bool F = true) : C(Ctx), Finalized(F), HasGeneratedNodes(false), Frontier(DstSet) { - Frontier.insert(SrcNode); + assert(DstSet.empty()); + Frontier.Add(SrcNode); } NodeBuilder(const ExplodedNodeSet &SrcSet, ExplodedNodeSet &DstSet, const NodeBuilderContext &Ctx, bool F = true) : C(Ctx), Finalized(F), HasGeneratedNodes(false), Frontier(DstSet) { + assert(DstSet.empty()); + //assert(!SrcSet.empty()); + Frontier.insert(SrcSet); + + assert(haveNoSinksInFrontier()); } virtual ~NodeBuilder() {} @@ -365,13 +379,23 @@ public: return N; } - void importNodesFromBuilder(const NodeBuilder &NB) { - ExplodedNode *NBPred = const_cast(NB.C.ContextPred); - if (NB.hasGeneratedNodes()) { - Frontier.erase(NBPred); - Frontier.insert(NB.Frontier); - } + void takeNodes(const ExplodedNodeSet &S) { + for (ExplodedNodeSet::iterator I = S.begin(), E = S.end(); I != E; ++I ) + Frontier.erase(*I); } + + void takeNodes(ExplodedNode *N) { + Frontier.erase(N); + } + + void addNodes(const ExplodedNodeSet &S) { + Frontier.insert(S); + } + + void addNodes(ExplodedNode *N) { + Frontier.Add(N); + } + }; class BranchNodeBuilder: public NodeBuilder { diff --git a/lib/StaticAnalyzer/Core/CheckerContext.cpp b/lib/StaticAnalyzer/Core/CheckerContext.cpp index 5f43b77ceb..e4638b756c 100644 --- a/lib/StaticAnalyzer/Core/CheckerContext.cpp +++ b/lib/StaticAnalyzer/Core/CheckerContext.cpp @@ -16,10 +16,4 @@ using namespace clang; using namespace ento; -CheckerContext::~CheckerContext() { - // Copy the results into the Dst set. - for (NodeBuilder::iterator I = NB.begin(), - E = NB.end(); I != E; ++I) { - Dst.Add(*I); - } -} +CheckerContext::~CheckerContext() {} diff --git a/lib/StaticAnalyzer/Core/CheckerManager.cpp b/lib/StaticAnalyzer/Core/CheckerManager.cpp index aa6a51e1aa..e77c677be0 100644 --- a/lib/StaticAnalyzer/Core/CheckerManager.cpp +++ b/lib/StaticAnalyzer/Core/CheckerManager.cpp @@ -93,6 +93,9 @@ template static void expandGraphWithCheckers(CHECK_CTX checkCtx, ExplodedNodeSet &Dst, const ExplodedNodeSet &Src) { + const NodeBuilderContext &BldrCtx = checkCtx.Eng.getBuilderContext(); + if (Src.empty()) + return; typename CHECK_CTX::CheckersTy::const_iterator I = checkCtx.checkers_begin(), E = checkCtx.checkers_end(); @@ -113,9 +116,18 @@ static void expandGraphWithCheckers(CHECK_CTX checkCtx, CurrSet->clear(); } + NodeBuilder B(*PrevSet, *CurrSet, BldrCtx); + checkCtx.Eng.getBuilder().takeNodes(*PrevSet); for (ExplodedNodeSet::iterator NI = PrevSet->begin(), NE = PrevSet->end(); - NI != NE; ++NI) - checkCtx.runChecker(*I, *CurrSet, *NI); + NI != NE; ++NI) { + checkCtx.runChecker(*I, B, *NI); + } + + // If all the produced transitions are sinks, stop. + if (CurrSet->empty()) + return; + + checkCtx.Eng.getBuilder().addNodes(*CurrSet); // Update which NodeSet is the current one. PrevSet = CurrSet; @@ -138,13 +150,13 @@ namespace { : IsPreVisit(isPreVisit), Checkers(checkers), S(s), Eng(eng) { } void runChecker(CheckerManager::CheckStmtFunc checkFn, - ExplodedNodeSet &Dst, ExplodedNode *Pred) { + NodeBuilder &Bldr, ExplodedNode *Pred) { // FIXME: Remove respondsToCallback from CheckerContext; ProgramPoint::Kind K = IsPreVisit ? ProgramPoint::PreStmtKind : ProgramPoint::PostStmtKind; const ProgramPoint &L = ProgramPoint::getProgramPoint(S, K, Pred->getLocationContext(), checkFn.Checker); - CheckerContext C(Dst, Eng.getBuilder(), Eng, Pred, L, 0); + CheckerContext C(Bldr, Eng, Pred, L, 0); checkFn(S, C); } @@ -178,12 +190,12 @@ namespace { : IsPreVisit(isPreVisit), Checkers(checkers), Msg(msg), Eng(eng) { } void runChecker(CheckerManager::CheckObjCMessageFunc checkFn, - ExplodedNodeSet &Dst, ExplodedNode *Pred) { + NodeBuilder &Bldr, ExplodedNode *Pred) { ProgramPoint::Kind K = IsPreVisit ? ProgramPoint::PreStmtKind : ProgramPoint::PostStmtKind; const ProgramPoint &L = ProgramPoint::getProgramPoint(Msg.getOriginExpr(), K, Pred->getLocationContext(), checkFn.Checker); - CheckerContext C(Dst, Eng.getBuilder(), Eng, Pred, L, 0); + CheckerContext C(Bldr, Eng, Pred, L, 0); checkFn(Msg, C); } @@ -220,12 +232,12 @@ namespace { : Checkers(checkers), Loc(loc), IsLoad(isLoad), S(s), Eng(eng) { } void runChecker(CheckerManager::CheckLocationFunc checkFn, - ExplodedNodeSet &Dst, ExplodedNode *Pred) { + NodeBuilder &Bldr, ExplodedNode *Pred) { ProgramPoint::Kind K = IsLoad ? ProgramPoint::PreLoadKind : ProgramPoint::PreStoreKind; const ProgramPoint &L = ProgramPoint::getProgramPoint(S, K, Pred->getLocationContext(), checkFn.Checker); - CheckerContext C(Dst, Eng.getBuilder(), Eng, Pred, L, 0); + CheckerContext C(Bldr, Eng, Pred, L, 0); checkFn(Loc, IsLoad, S, C); } @@ -258,11 +270,11 @@ namespace { : Checkers(checkers), Loc(loc), Val(val), S(s), Eng(eng) { } void runChecker(CheckerManager::CheckBindFunc checkFn, - ExplodedNodeSet &Dst, ExplodedNode *Pred) { + NodeBuilder &Bldr, ExplodedNode *Pred) { ProgramPoint::Kind K = ProgramPoint::PreStmtKind; const ProgramPoint &L = ProgramPoint::getProgramPoint(S, K, Pred->getLocationContext(), checkFn.Checker); - CheckerContext C(Dst, Eng.getBuilder(), Eng, Pred, L, 0); + CheckerContext C(Bldr, Eng, Pred, L, 0); checkFn(Loc, Val, S, C); } @@ -329,11 +341,11 @@ namespace { : Checkers(checkers), SR(sr), S(s), Eng(eng) { } void runChecker(CheckerManager::CheckDeadSymbolsFunc checkFn, - ExplodedNodeSet &Dst, ExplodedNode *Pred) { + NodeBuilder &Bldr, ExplodedNode *Pred) { ProgramPoint::Kind K = ProgramPoint::PostPurgeDeadSymbolsKind; const ProgramPoint &L = ProgramPoint::getProgramPoint(S, K, Pred->getLocationContext(), checkFn.Checker); - CheckerContext C(Dst, Eng.getBuilder(), Eng, Pred, L, 0); + CheckerContext C(Bldr, Eng, Pred, L, 0); checkFn(SR, C); } @@ -438,11 +450,13 @@ void CheckerManager::runCheckersForEvalCall(ExplodedNodeSet &Dst, } #endif + Eng.getBuilder().takeNodes(Pred); + ExplodedNodeSet checkDst; + NodeBuilder B(Pred, checkDst, Eng.getBuilderContext()); // Next, check if any of the EvalCall callbacks can evaluate the call. for (std::vector::iterator EI = EvalCallCheckers.begin(), EE = EvalCallCheckers.end(); EI != EE; ++EI) { - ExplodedNodeSet checkDst; ProgramPoint::Kind K = ProgramPoint::PostStmtKind; const ProgramPoint &L = ProgramPoint::getProgramPoint(CE, K, Pred->getLocationContext(), EI->Checker); @@ -450,7 +464,7 @@ void CheckerManager::runCheckersForEvalCall(ExplodedNodeSet &Dst, { // CheckerContext generates transitions(populates checkDest) on // destruction, so introduce the scope to make sure it gets properly // populated. - CheckerContext C(checkDst, Eng.getBuilder(), Eng, Pred, L, 0); + CheckerContext C(B, Eng, Pred, L, 0); evaluated = (*EI)(CE, C); } assert(!(evaluated && anyEvaluated) @@ -458,6 +472,7 @@ void CheckerManager::runCheckersForEvalCall(ExplodedNodeSet &Dst, if (evaluated) { anyEvaluated = true; Dst.insert(checkDst); + Eng.getBuilder().addNodes(checkDst); #ifdef NDEBUG break; // on release don't check that no other checker also evals. #endif @@ -466,6 +481,7 @@ void CheckerManager::runCheckersForEvalCall(ExplodedNodeSet &Dst, // If none of the checkers evaluated the call, ask ExprEngine to handle it. if (!anyEvaluated) { + Eng.getBuilder().addNodes(Pred); if (defaultEval) defaultEval->expandGraph(Dst, Pred); else diff --git a/lib/StaticAnalyzer/Core/CoreEngine.cpp b/lib/StaticAnalyzer/Core/CoreEngine.cpp index b9ab7b4c74..6616e065d3 100644 --- a/lib/StaticAnalyzer/Core/CoreEngine.cpp +++ b/lib/StaticAnalyzer/Core/CoreEngine.cpp @@ -504,7 +504,7 @@ ExplodedNode* NodeBuilder::generateNodeImpl(const ProgramPoint &Loc, if (MarkAsSink) N->markAsSink(); - if (IsNew) + if (IsNew && !MarkAsSink) Frontier.Add(N); return (IsNew ? N : 0); diff --git a/lib/StaticAnalyzer/Core/ExprEngine.cpp b/lib/StaticAnalyzer/Core/ExprEngine.cpp index 5742266de2..eaba5eedb5 100644 --- a/lib/StaticAnalyzer/Core/ExprEngine.cpp +++ b/lib/StaticAnalyzer/Core/ExprEngine.cpp @@ -964,6 +964,9 @@ void ExprEngine::processBranch(const Stmt *Condition, const Stmt *Term, NodeBuilder CheckerBldr(Pred, TmpCheckersOut, BldCtx); getCheckerManager().runCheckersForBranchCondition(Condition, CheckerBldr, Pred, *this); + // We generated only sinks. + if (TmpCheckersOut.empty()) + return; BranchNodeBuilder builder(CheckerBldr.getResults(), Dst, BldCtx, DstT, DstF); for (NodeBuilder::iterator I = CheckerBldr.begin(), -- 2.40.0