From 4e82d3cf6fd4c907265e3fa3aac0a835c35dc759 Mon Sep 17 00:00:00 2001 From: Anna Zaks Date: Tue, 18 Oct 2011 23:06:44 +0000 Subject: [PATCH] [analyzer] Make NodeBuilder and Pred node loosely coupled NodeBuilder should not assume it's dealing with a single predecessor. Remove predecessor getters. Modify the BranchNodeBuilder to not be responsible for doing auto-transitions (which depend on a predecessor). git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@142453 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/clang/StaticAnalyzer/Core/Checker.h | 5 +- .../StaticAnalyzer/Core/CheckerManager.h | 6 ++- .../Core/PathSensitive/CoreEngine.h | 46 ++++++------------- .../Core/PathSensitive/ExprEngine.h | 14 ++++-- .../Core/PathSensitive/SubEngine.h | 3 +- .../Checkers/UndefBranchChecker.cpp | 10 ++-- lib/StaticAnalyzer/Core/CheckerManager.cpp | 3 +- lib/StaticAnalyzer/Core/CoreEngine.cpp | 15 ++---- lib/StaticAnalyzer/Core/ExprEngine.cpp | 43 +++++++++-------- 9 files changed, 66 insertions(+), 79 deletions(-) diff --git a/include/clang/StaticAnalyzer/Core/Checker.h b/include/clang/StaticAnalyzer/Core/Checker.h index 51533489e5..2e270000c7 100644 --- a/include/clang/StaticAnalyzer/Core/Checker.h +++ b/include/clang/StaticAnalyzer/Core/Checker.h @@ -215,8 +215,9 @@ public: class BranchCondition { template static void _checkBranchCondition(void *checker, const Stmt *condition, - NodeBuilder &B, ExprEngine &Eng) { - ((const CHECKER *)checker)->checkBranchCondition(condition, B, Eng); + NodeBuilder &B, ExplodedNode *Pred, + ExprEngine &Eng) { + ((const CHECKER *)checker)->checkBranchCondition(condition, B, Pred, Eng); } public: diff --git a/include/clang/StaticAnalyzer/Core/CheckerManager.h b/include/clang/StaticAnalyzer/Core/CheckerManager.h index 6026aec643..7450df63c4 100644 --- a/include/clang/StaticAnalyzer/Core/CheckerManager.h +++ b/include/clang/StaticAnalyzer/Core/CheckerManager.h @@ -232,7 +232,8 @@ public: /// \brief Run checkers for branch condition. void runCheckersForBranchCondition(const Stmt *condition, - NodeBuilder &B, ExprEngine &Eng); + NodeBuilder &B, ExplodedNode *Pred, + ExprEngine &Eng); /// \brief Run checkers for live symbols. /// @@ -334,7 +335,8 @@ public: typedef CheckerFn CheckEndPathFunc; - typedef CheckerFn + typedef CheckerFn CheckBranchConditionFunc; typedef CheckerFn diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h b/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h index 7d7aa1417b..4892293a42 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h @@ -191,6 +191,8 @@ protected: /// is set to false, autotransitions are yet to be generated. bool Finalized; + bool HasGeneratedNodes; + /// \brief The frontier set - a set of nodes which need to be propagated after /// the builder dies. typedef llvm::SmallPtrSet DeferredTy; @@ -218,14 +220,14 @@ protected: public: NodeBuilder(ExplodedNode *N, NodeBuilderContext &Ctx, bool F = true) - : BuilderPred(N), C(Ctx), Finalized(F) { + : BuilderPred(N), C(Ctx), Finalized(F), HasGeneratedNodes(false) { assert(!N->isSink()); Deferred.insert(N); } /// Create a new builder using the parent builder's context. NodeBuilder(ExplodedNode *N, const NodeBuilder &ParentBldr, bool F = true) - : BuilderPred(N), C(ParentBldr.C), Finalized(F) { + : BuilderPred(N), C(ParentBldr.C), Finalized(F), HasGeneratedNodes(false) { assert(!N->isSink()); Deferred.insert(N); } @@ -243,8 +245,9 @@ public: return generateNodeImpl(PP, State, Pred, MarkAsSink); } + // TODO: will get removed. bool hasGeneratedNodes() const { - return (!Deferred.count(BuilderPred)); + return HasGeneratedNodes; } typedef DeferredTy::iterator iterator; @@ -269,12 +272,6 @@ public: BuilderPred->getLocationContext()->getCurrentStackFrame(), C.Block->getBlockID()); } - - // \brief Get the builder's predecessor - the parent to all the other nodes. - ExplodedNode *getPredecessor() const { return BuilderPred; } - - // \brief Returns state of the predecessor. - const ProgramState *getState() const { return BuilderPred->getState(); } }; class CommonNodeBuilder { @@ -366,7 +363,7 @@ public: } void importNodesFromBuilder(const NodeBuilder &NB) { - ExplodedNode *NBPred = const_cast(NB.getPredecessor()); + ExplodedNode *NBPred = const_cast(NB.BuilderPred); if (NB.hasGeneratedNodes()) { Deferred.erase(NBPred); Deferred.insert(NB.Deferred.begin(), NB.Deferred.end()); @@ -378,35 +375,20 @@ class BranchNodeBuilder: public NodeBuilder { const CFGBlock *DstT; const CFGBlock *DstF; - bool GeneratedTrue; - bool GeneratedFalse; bool InFeasibleTrue; bool InFeasibleFalse; - /// Generate default branching transitions of none were generated or - /// suppressed. - void finalizeResults() { - if (Finalized) - return; - if (!GeneratedTrue) generateNode(BuilderPred->State, true); - if (!GeneratedFalse) generateNode(BuilderPred->State, false); - Finalized = true; - } - public: BranchNodeBuilder(ExplodedNode *Pred, NodeBuilderContext &C, const CFGBlock *dstT, const CFGBlock *dstF) - : NodeBuilder(Pred, C, false), DstT(dstT), DstF(dstF), - GeneratedTrue(false), GeneratedFalse(false), - InFeasibleTrue(!DstT), InFeasibleFalse(!DstF) { - } + : NodeBuilder(Pred, C), DstT(dstT), DstF(dstF), + InFeasibleTrue(!DstT), InFeasibleFalse(!DstF) {} /// Create a new builder using the parent builder's context. BranchNodeBuilder(ExplodedNode *Pred, BranchNodeBuilder &ParentBldr) - : NodeBuilder(Pred, ParentBldr, false), DstT(ParentBldr.DstT), - DstF(ParentBldr.DstF), GeneratedTrue(false), GeneratedFalse(false), - InFeasibleTrue(!DstT), InFeasibleFalse(!DstF) { - } + : NodeBuilder(Pred, ParentBldr), DstT(ParentBldr.DstT), + DstF(ParentBldr.DstF), + InFeasibleTrue(!DstT), InFeasibleFalse(!DstF) {} ExplodedNode *generateNode(const ProgramState *State, bool branch, ExplodedNode *Pred = 0); @@ -417,9 +399,9 @@ public: void markInfeasible(bool branch) { if (branch) - InFeasibleTrue = GeneratedTrue = true; + InFeasibleTrue = true; else - InFeasibleFalse = GeneratedFalse = true; + InFeasibleFalse = true; } bool isFeasible(bool branch) { diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h b/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h index bc84e2f7d5..df4580aa90 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h @@ -132,16 +132,20 @@ public: /// processCFGElement - Called by CoreEngine. Used to generate new successor /// nodes by processing the 'effects' of a CFG element. - void processCFGElement(const CFGElement E, StmtNodeBuilder& builder); + void processCFGElement(const CFGElement E, StmtNodeBuilder& Bldr, + ExplodedNode *Pred); - void ProcessStmt(const CFGStmt S, StmtNodeBuilder &builder); + void ProcessStmt(const CFGStmt S, StmtNodeBuilder &builder, + ExplodedNode *Pred); - void ProcessInitializer(const CFGInitializer I, StmtNodeBuilder &builder); + void ProcessInitializer(const CFGInitializer I, StmtNodeBuilder &Bldr, + ExplodedNode *Pred); - void ProcessImplicitDtor(const CFGImplicitDtor D, StmtNodeBuilder &builder); + void ProcessImplicitDtor(const CFGImplicitDtor D, StmtNodeBuilder &builder, + ExplodedNode *Pred); void ProcessAutomaticObjDtor(const CFGAutomaticObjDtor D, - StmtNodeBuilder &builder); + StmtNodeBuilder &builder, ExplodedNode *Pred); void ProcessBaseDtor(const CFGBaseDtor D, StmtNodeBuilder &builder); void ProcessMemberDtor(const CFGMemberDtor D, StmtNodeBuilder &builder); void ProcessTemporaryDtor(const CFGTemporaryDtor D, diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/SubEngine.h b/include/clang/StaticAnalyzer/Core/PathSensitive/SubEngine.h index 38b7538b6b..8dfc1865bd 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/SubEngine.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/SubEngine.h @@ -55,7 +55,8 @@ public: /// Called by CoreEngine. Used to generate new successor /// nodes by processing the 'effects' of a block-level statement. - virtual void processCFGElement(const CFGElement E, StmtNodeBuilder& builder)=0; + virtual void processCFGElement(const CFGElement E, StmtNodeBuilder& builder, + ExplodedNode* Pred)=0; /// Called by CoreEngine when it starts processing a CFGBlock. The /// SubEngine is expected to populate dstNodes with new nodes representing diff --git a/lib/StaticAnalyzer/Checkers/UndefBranchChecker.cpp b/lib/StaticAnalyzer/Checkers/UndefBranchChecker.cpp index 451fa91b3a..d030469459 100644 --- a/lib/StaticAnalyzer/Checkers/UndefBranchChecker.cpp +++ b/lib/StaticAnalyzer/Checkers/UndefBranchChecker.cpp @@ -50,26 +50,26 @@ class UndefBranchChecker : public Checker { public: void checkBranchCondition(const Stmt *Condition, NodeBuilder &Builder, - ExprEngine &Eng) const; + ExplodedNode *Pred, ExprEngine &Eng) const; }; } void UndefBranchChecker::checkBranchCondition(const Stmt *Condition, NodeBuilder &Builder, + ExplodedNode *Pred, ExprEngine &Eng) const { - const ProgramState *state = Builder.getState(); + const ProgramState *state = Pred->getState(); SVal X = state->getSVal(Condition); if (X.isUndef()) { // TODO: The PP will be generated with the correct tag by the CheckerManager // after we migrate the callback to CheckerContext. const ProgramPointTag *Tag = 0; - ProgramPoint PP = PostCondition(Condition, - Builder.getPredecessor()->getLocationContext(), Tag); + ProgramPoint PP = PostCondition(Condition, Pred->getLocationContext(), Tag); // Generate a sink node, which implicitly marks both outgoing branches as // infeasible. ExplodedNode *N = Builder.generateNode(PP, state, - Builder.getPredecessor(), true); + Pred, true); if (N) { if (!BT) BT.reset( diff --git a/lib/StaticAnalyzer/Core/CheckerManager.cpp b/lib/StaticAnalyzer/Core/CheckerManager.cpp index d47033a70e..aa6a51e1aa 100644 --- a/lib/StaticAnalyzer/Core/CheckerManager.cpp +++ b/lib/StaticAnalyzer/Core/CheckerManager.cpp @@ -298,10 +298,11 @@ void CheckerManager::runCheckersForEndPath(EndOfFunctionNodeBuilder &B, /// \brief Run checkers for branch condition. void CheckerManager::runCheckersForBranchCondition(const Stmt *condition, NodeBuilder &B, + ExplodedNode *Pred, ExprEngine &Eng) { for (unsigned i = 0, e = BranchConditionCheckers.size(); i != e; ++i) { CheckBranchConditionFunc fn = BranchConditionCheckers[i]; - fn(condition, B, Eng); + fn(condition, B, Pred, Eng); } } diff --git a/lib/StaticAnalyzer/Core/CoreEngine.cpp b/lib/StaticAnalyzer/Core/CoreEngine.cpp index 0a308670c0..a40a0dc683 100644 --- a/lib/StaticAnalyzer/Core/CoreEngine.cpp +++ b/lib/StaticAnalyzer/Core/CoreEngine.cpp @@ -316,7 +316,7 @@ void CoreEngine::HandleBlockEntrance(const BlockEntrance &L, if (CFGElement E = L.getFirstElement()) { NodeBuilderContext Ctx(*this, L.getBlock()); StmtNodeBuilder Builder(Pred, 0, Ctx); - SubEng.processCFGElement(E, Builder); + SubEng.processCFGElement(E, Builder, Pred); } else HandleBlockExit(L.getBlock(), Pred); @@ -433,7 +433,7 @@ void CoreEngine::HandlePostStmt(const CFGBlock *B, unsigned StmtIdx, else { NodeBuilderContext Ctx(*this, B); StmtNodeBuilder Builder(Pred, StmtIdx, Ctx); - SubEng.processCFGElement((*B)[StmtIdx], Builder); + SubEng.processCFGElement((*B)[StmtIdx], Builder, Pred); } } @@ -489,6 +489,8 @@ ExplodedNode* NodeBuilder::generateNodeImpl(const ProgramPoint &Loc, const ProgramState *State, ExplodedNode *FromN, bool MarkAsSink) { + HasGeneratedNodes = true; + bool IsNew; ExplodedNode *N = C.Eng.G->getNode(Loc, State, &IsNew); N->addPredecessor(FromN, *C.Eng.G); @@ -567,9 +569,6 @@ ExplodedNode *StmtNodeBuilder::MakeNode(ExplodedNodeSet &Dst, ExplodedNode *BranchNodeBuilder::generateNode(const ProgramState *State, bool branch, ExplodedNode *NodePred) { - assert(Finalized == false && - "We cannot create new nodes after the results have been finalized."); - // If the branch has been marked infeasible we should not generate a node. if (!isFeasible(branch)) return NULL; @@ -579,12 +578,6 @@ ExplodedNode *BranchNodeBuilder::generateNode(const ProgramState *State, ProgramPoint Loc = BlockEdge(C.Block, branch ? DstT:DstF, NodePred->getLocationContext()); ExplodedNode *Succ = generateNodeImpl(Loc, State, NodePred); - - if (branch) - GeneratedTrue = true; - else - GeneratedFalse = true; - return Succ; } diff --git a/lib/StaticAnalyzer/Core/ExprEngine.cpp b/lib/StaticAnalyzer/Core/ExprEngine.cpp index 2cce0414c9..19b1a2fa73 100644 --- a/lib/StaticAnalyzer/Core/ExprEngine.cpp +++ b/lib/StaticAnalyzer/Core/ExprEngine.cpp @@ -196,26 +196,29 @@ void ExprEngine::processEndWorklist(bool hasWorkRemaining) { } void ExprEngine::processCFGElement(const CFGElement E, - StmtNodeBuilder& builder) { + StmtNodeBuilder& Bldr, + ExplodedNode *Pred) { switch (E.getKind()) { case CFGElement::Invalid: llvm_unreachable("Unexpected CFGElement kind."); case CFGElement::Statement: - ProcessStmt(const_cast(E.getAs()->getStmt()), builder); + ProcessStmt(const_cast(E.getAs()->getStmt()), Bldr, Pred); return; case CFGElement::Initializer: - ProcessInitializer(E.getAs()->getInitializer(), builder); + ProcessInitializer(E.getAs()->getInitializer(), + Bldr, Pred); return; case CFGElement::AutomaticObjectDtor: case CFGElement::BaseDtor: case CFGElement::MemberDtor: case CFGElement::TemporaryDtor: - ProcessImplicitDtor(*E.getAs(), builder); + ProcessImplicitDtor(*E.getAs(), Bldr, Pred); return; } } -void ExprEngine::ProcessStmt(const CFGStmt S, StmtNodeBuilder& builder) { +void ExprEngine::ProcessStmt(const CFGStmt S, StmtNodeBuilder& builder, + ExplodedNode *Pred) { // TODO: Use RAII to remove the unnecessary, tagged nodes. //RegisterCreatedNodes registerCreatedNodes(getGraph()); @@ -232,7 +235,7 @@ void ExprEngine::ProcessStmt(const CFGStmt S, StmtNodeBuilder& builder) { // A tag to track convenience transitions, which can be removed at cleanup. static SimpleProgramPointTag cleanupTag("ExprEngine : Clean Node"); Builder = &builder; - EntryNode = builder.getPredecessor(); + EntryNode = Pred; const ProgramState *EntryState = EntryNode->getState(); CleanedState = EntryState; @@ -320,12 +323,10 @@ void ExprEngine::ProcessStmt(const CFGStmt S, StmtNodeBuilder& builder) { } void ExprEngine::ProcessInitializer(const CFGInitializer Init, - StmtNodeBuilder &builder) { + StmtNodeBuilder &builder, + ExplodedNode *pred) { // We don't set EntryNode and currentStmt. And we don't clean up state. const CXXCtorInitializer *BMI = Init.getInitializer(); - - ExplodedNode *pred = builder.getPredecessor(); - const StackFrameContext *stackFrame = cast(pred->getLocationContext()); const CXXConstructorDecl *decl = cast(stackFrame->getDecl()); const CXXThisRegion *thisReg = getCXXThisRegion(decl, stackFrame); @@ -373,12 +374,13 @@ void ExprEngine::ProcessInitializer(const CFGInitializer Init, } void ExprEngine::ProcessImplicitDtor(const CFGImplicitDtor D, - StmtNodeBuilder &builder) { + StmtNodeBuilder &builder, + ExplodedNode *Pred) { Builder = &builder; switch (D.getKind()) { case CFGElement::AutomaticObjectDtor: - ProcessAutomaticObjDtor(cast(D), builder); + ProcessAutomaticObjDtor(cast(D), builder, Pred); break; case CFGElement::BaseDtor: ProcessBaseDtor(cast(D), builder); @@ -395,8 +397,8 @@ void ExprEngine::ProcessImplicitDtor(const CFGImplicitDtor D, } void ExprEngine::ProcessAutomaticObjDtor(const CFGAutomaticObjDtor dtor, - StmtNodeBuilder &builder) { - ExplodedNode *pred = builder.getPredecessor(); + StmtNodeBuilder &builder, + ExplodedNode *pred) { const ProgramState *state = pred->getState(); const VarDecl *varDecl = dtor.getVarDecl(); @@ -949,6 +951,7 @@ void ExprEngine::processBranch(const Stmt *Condition, const Stmt *Term, if (!Condition) { BranchNodeBuilder NullCondBldr(Pred, BldCtx, DstT, DstF); NullCondBldr.markInfeasible(false); + NullCondBldr.generateNode(Pred->getState(), true, Pred); Engine.enqueue(NullCondBldr); return; } @@ -959,7 +962,7 @@ void ExprEngine::processBranch(const Stmt *Condition, const Stmt *Term, NodeBuilder CheckerBldr(Pred, BldCtx); getCheckerManager().runCheckersForBranchCondition(Condition, CheckerBldr, - *this); + Pred, *this); for (NodeBuilder::iterator I = CheckerBldr.results_begin(), E = CheckerBldr.results_end(); E != I; ++I) { @@ -969,7 +972,7 @@ void ExprEngine::processBranch(const Stmt *Condition, const Stmt *Term, continue; BranchNodeBuilder builder(PredI, BldCtx, DstT, DstF); - const ProgramState *PrevState = builder.getState(); + const ProgramState *PrevState = Pred->getState(); SVal X = PrevState->getSVal(Condition); if (X.isUnknownOrUndef()) { @@ -992,8 +995,8 @@ void ExprEngine::processBranch(const Stmt *Condition, const Stmt *Term, } // If the condition is still unknown, give up. if (X.isUnknownOrUndef()) { - builder.generateNode(MarkBranch(PrevState, Term, true), true); - builder.generateNode(MarkBranch(PrevState, Term, false), false); + builder.generateNode(MarkBranch(PrevState, Term, true), true, PredI); + builder.generateNode(MarkBranch(PrevState, Term, false), false, PredI); // Enqueue the results into the work list. Engine.enqueue(builder); continue; @@ -1004,7 +1007,7 @@ void ExprEngine::processBranch(const Stmt *Condition, const Stmt *Term, // Process the true branch. if (builder.isFeasible(true)) { if (const ProgramState *state = PrevState->assume(V, true)) - builder.generateNode(MarkBranch(state, Term, true), true); + builder.generateNode(MarkBranch(state, Term, true), true, PredI); else builder.markInfeasible(true); } @@ -1012,7 +1015,7 @@ void ExprEngine::processBranch(const Stmt *Condition, const Stmt *Term, // Process the false branch. if (builder.isFeasible(false)) { if (const ProgramState *state = PrevState->assume(V, false)) - builder.generateNode(MarkBranch(state, Term, false), false); + builder.generateNode(MarkBranch(state, Term, false), false, PredI); else builder.markInfeasible(false); } -- 2.40.0