diff options
Diffstat (limited to 'lib/Analysis/GRCoreEngine.cpp')
| -rw-r--r-- | lib/Analysis/GRCoreEngine.cpp | 439 |
1 files changed, 238 insertions, 201 deletions
diff --git a/lib/Analysis/GRCoreEngine.cpp b/lib/Analysis/GRCoreEngine.cpp index ff7b548bc054..87472472fdee 100644 --- a/lib/Analysis/GRCoreEngine.cpp +++ b/lib/Analysis/GRCoreEngine.cpp @@ -1,5 +1,5 @@ //==- GRCoreEngine.cpp - Path-Sensitive Dataflow Engine ------------*- C++ -*-// -// +// // The LLVM Compiler Infrastructure // // This file is distributed under the University of Illinois Open Source @@ -13,6 +13,7 @@ //===----------------------------------------------------------------------===// #include "clang/Analysis/PathSensitive/GRCoreEngine.h" +#include "clang/Analysis/PathSensitive/GRExprEngine.h" #include "clang/AST/Expr.h" #include "llvm/Support/Compiler.h" #include "llvm/Support/Casting.h" @@ -29,7 +30,7 @@ using namespace clang; //===----------------------------------------------------------------------===// namespace { - class VISIBILITY_HIDDEN DFS : public GRWorkList { +class VISIBILITY_HIDDEN DFS : public GRWorkList { llvm::SmallVector<GRWorkListUnit,20> Stack; public: virtual bool hasWork() const { @@ -47,27 +48,27 @@ public: return U; } }; - + class VISIBILITY_HIDDEN BFS : public GRWorkList { std::queue<GRWorkListUnit> Queue; public: virtual bool hasWork() const { return !Queue.empty(); } - + virtual void Enqueue(const GRWorkListUnit& U) { Queue.push(U); } - + virtual GRWorkListUnit Dequeue() { // Don't use const reference. The subsequent pop_back() might make it // unsafe. - GRWorkListUnit U = Queue.front(); + GRWorkListUnit U = Queue.front(); Queue.pop(); return U; } }; - + } // end anonymous namespace // Place the dstor for GRWorkList here because it contains virtual member @@ -85,14 +86,14 @@ namespace { virtual bool hasWork() const { return !Queue.empty() || !Stack.empty(); } - + virtual void Enqueue(const GRWorkListUnit& U) { if (isa<BlockEntrance>(U.getNode()->getLocation())) Queue.push(U); else Stack.push_back(U); } - + virtual GRWorkListUnit Dequeue() { // Process all basic blocks to completion. if (!Stack.empty()) { @@ -100,13 +101,13 @@ namespace { Stack.pop_back(); // This technically "invalidates" U, but we are fine. return U; } - + assert(!Queue.empty()); // Don't use const reference. The subsequent pop_back() might make it // unsafe. - GRWorkListUnit U = Queue.front(); + GRWorkListUnit U = Queue.front(); Queue.pop(); - return U; + return U; } }; } // end anonymous namespace @@ -118,55 +119,80 @@ GRWorkList* GRWorkList::MakeBFSBlockDFSContents() { //===----------------------------------------------------------------------===// // Core analysis engine. //===----------------------------------------------------------------------===// +void GRCoreEngine::ProcessEndPath(GREndPathNodeBuilder& Builder) { + SubEngine.ProcessEndPath(Builder); +} + +void GRCoreEngine::ProcessStmt(Stmt* S, GRStmtNodeBuilder& Builder) { + SubEngine.ProcessStmt(S, Builder); +} + +bool GRCoreEngine::ProcessBlockEntrance(CFGBlock* Blk, const GRState* State, + GRBlockCounter BC) { + return SubEngine.ProcessBlockEntrance(Blk, State, BC); +} + +void GRCoreEngine::ProcessBranch(Stmt* Condition, Stmt* Terminator, + GRBranchNodeBuilder& Builder) { + SubEngine.ProcessBranch(Condition, Terminator, Builder); +} + +void GRCoreEngine::ProcessIndirectGoto(GRIndirectGotoNodeBuilder& Builder) { + SubEngine.ProcessIndirectGoto(Builder); +} + +void GRCoreEngine::ProcessSwitch(GRSwitchNodeBuilder& Builder) { + SubEngine.ProcessSwitch(Builder); +} /// ExecuteWorkList - Run the worklist algorithm for a maximum number of steps. -bool GRCoreEngineImpl::ExecuteWorkList(unsigned Steps) { - +bool GRCoreEngine::ExecuteWorkList(const LocationContext *L, unsigned Steps) { + if (G->num_roots() == 0) { // Initialize the analysis by constructing // the root if none exists. - - CFGBlock* Entry = &getCFG().getEntry(); - - assert (Entry->empty() && + + CFGBlock* Entry = &(L->getCFG()->getEntry()); + + assert (Entry->empty() && "Entry block must be empty."); - + assert (Entry->succ_size() == 1 && "Entry block must have 1 successor."); - + // Get the solitary successor. - CFGBlock* Succ = *(Entry->succ_begin()); - + CFGBlock* Succ = *(Entry->succ_begin()); + // Construct an edge representing the // starting location in the function. - BlockEdge StartLoc(Entry, Succ); - + BlockEdge StartLoc(Entry, Succ, L); + // Set the current block counter to being empty. WList->setBlockCounter(BCounterFactory.GetEmptyCounter()); - + // Generate the root. - GenerateNode(StartLoc, getInitialState(), 0); + GenerateNode(StartLoc, getInitialState(L), 0); } - + while (Steps && WList->hasWork()) { --Steps; const GRWorkListUnit& WU = WList->Dequeue(); - + // Set the current block counter. WList->setBlockCounter(WU.getBlockCounter()); // Retrieve the node. - ExplodedNodeImpl* Node = WU.getNode(); - + ExplodedNode* Node = WU.getNode(); + // Dispatch on the location type. switch (Node->getLocation().getKind()) { case ProgramPoint::BlockEdgeKind: HandleBlockEdge(cast<BlockEdge>(Node->getLocation()), Node); break; - + case ProgramPoint::BlockEntranceKind: HandleBlockEntrance(cast<BlockEntrance>(Node->getLocation()), Node); break; - + case ProgramPoint::BlockExitKind: assert (false && "BlockExit location never occur in forward analysis."); break; @@ -175,26 +201,26 @@ bool GRCoreEngineImpl::ExecuteWorkList(unsigned Steps) { assert(isa<PostStmt>(Node->getLocation())); HandlePostStmt(cast<PostStmt>(Node->getLocation()), WU.getBlock(), WU.getIndex(), Node); - break; + break; } } - + return WList->hasWork(); } -void GRCoreEngineImpl::HandleBlockEdge(const BlockEdge& L, - ExplodedNodeImpl* Pred) { - + +void GRCoreEngine::HandleBlockEdge(const BlockEdge& L, ExplodedNode* Pred) { + CFGBlock* Blk = L.getDst(); - - // Check if we are entering the EXIT block. - if (Blk == &getCFG().getExit()) { - - assert (getCFG().getExit().size() == 0 + + // Check if we are entering the EXIT block. + if (Blk == &(Pred->getLocationContext()->getCFG()->getExit())) { + + assert (Pred->getLocationContext()->getCFG()->getExit().size() == 0 && "EXIT block cannot contain Stmts."); // Process the final state transition. - GREndPathNodeBuilderImpl Builder(Blk, Pred, this); + GREndPathNodeBuilder Builder(Blk, Pred, this); ProcessEndPath(Builder); // This path is done. Don't enqueue any more nodes. @@ -202,84 +228,81 @@ void GRCoreEngineImpl::HandleBlockEdge(const BlockEdge& L, } // FIXME: Should we allow ProcessBlockEntrance to also manipulate state? - + if (ProcessBlockEntrance(Blk, Pred->State, WList->getBlockCounter())) - GenerateNode(BlockEntrance(Blk), Pred->State, Pred); + GenerateNode(BlockEntrance(Blk, Pred->getLocationContext()), Pred->State, Pred); } -void GRCoreEngineImpl::HandleBlockEntrance(const BlockEntrance& L, - ExplodedNodeImpl* Pred) { - +void GRCoreEngine::HandleBlockEntrance(const BlockEntrance& L, + ExplodedNode* Pred) { + // Increment the block counter. GRBlockCounter Counter = WList->getBlockCounter(); Counter = BCounterFactory.IncrementCount(Counter, L.getBlock()->getBlockID()); WList->setBlockCounter(Counter); - - // Process the entrance of the block. + + // Process the entrance of the block. if (Stmt* S = L.getFirstStmt()) { - GRStmtNodeBuilderImpl Builder(L.getBlock(), 0, Pred, this); + GRStmtNodeBuilder Builder(L.getBlock(), 0, Pred, this, + SubEngine.getStateManager()); ProcessStmt(S, Builder); } - else + else HandleBlockExit(L.getBlock(), Pred); } -GRCoreEngineImpl::~GRCoreEngineImpl() { - delete WList; -} +void GRCoreEngine::HandleBlockExit(CFGBlock * B, ExplodedNode* Pred) { -void GRCoreEngineImpl::HandleBlockExit(CFGBlock * B, ExplodedNodeImpl* Pred) { - if (Stmt* Term = B->getTerminator()) { switch (Term->getStmtClass()) { default: assert(false && "Analysis for this terminator not implemented."); break; - + case Stmt::BinaryOperatorClass: // '&&' and '||' HandleBranch(cast<BinaryOperator>(Term)->getLHS(), Term, B, Pred); return; - + case Stmt::ConditionalOperatorClass: HandleBranch(cast<ConditionalOperator>(Term)->getCond(), Term, B, Pred); return; - + // FIXME: Use constant-folding in CFG construction to simplify this // case. - + case Stmt::ChooseExprClass: HandleBranch(cast<ChooseExpr>(Term)->getCond(), Term, B, Pred); return; - + case Stmt::DoStmtClass: HandleBranch(cast<DoStmt>(Term)->getCond(), Term, B, Pred); return; - + case Stmt::ForStmtClass: HandleBranch(cast<ForStmt>(Term)->getCond(), Term, B, Pred); return; - + case Stmt::ContinueStmtClass: case Stmt::BreakStmtClass: - case Stmt::GotoStmtClass: + case Stmt::GotoStmtClass: break; - + case Stmt::IfStmtClass: HandleBranch(cast<IfStmt>(Term)->getCond(), Term, B, Pred); return; - + case Stmt::IndirectGotoStmtClass: { // Only 1 successor: the indirect goto dispatch block. assert (B->succ_size() == 1); - - GRIndirectGotoNodeBuilderImpl + + GRIndirectGotoNodeBuilder builder(Pred, B, cast<IndirectGotoStmt>(Term)->getTarget(), *(B->succ_begin()), this); - + ProcessIndirectGoto(builder); return; } - + case Stmt::ObjCForCollectionStmtClass: { // In the case of ObjCForCollectionStmt, it appears twice in a CFG: // @@ -294,16 +317,15 @@ void GRCoreEngineImpl::HandleBlockExit(CFGBlock * B, ExplodedNodeImpl* Pred) { HandleBranch(Term, Term, B, Pred); return; } - + case Stmt::SwitchStmtClass: { - GRSwitchNodeBuilderImpl builder(Pred, B, - cast<SwitchStmt>(Term)->getCond(), - this); - + GRSwitchNodeBuilder builder(Pred, B, cast<SwitchStmt>(Term)->getCond(), + this); + ProcessSwitch(builder); return; } - + case Stmt::WhileStmtClass: HandleBranch(cast<WhileStmt>(Term)->getCond(), Term, B, Pred); return; @@ -312,265 +334,280 @@ void GRCoreEngineImpl::HandleBlockExit(CFGBlock * B, ExplodedNodeImpl* Pred) { assert (B->succ_size() == 1 && "Blocks with no terminator should have at most 1 successor."); - - GenerateNode(BlockEdge(B, *(B->succ_begin())), Pred->State, Pred); + + GenerateNode(BlockEdge(B, *(B->succ_begin()), Pred->getLocationContext()), + Pred->State, Pred); } -void GRCoreEngineImpl::HandleBranch(Stmt* Cond, Stmt* Term, CFGBlock * B, - ExplodedNodeImpl* Pred) { +void GRCoreEngine::HandleBranch(Stmt* Cond, Stmt* Term, CFGBlock * B, + ExplodedNode* Pred) { assert (B->succ_size() == 2); - GRBranchNodeBuilderImpl Builder(B, *(B->succ_begin()), *(B->succ_begin()+1), - Pred, this); - + GRBranchNodeBuilder Builder(B, *(B->succ_begin()), *(B->succ_begin()+1), + Pred, this); + ProcessBranch(Cond, Term, Builder); } -void GRCoreEngineImpl::HandlePostStmt(const PostStmt& L, CFGBlock* B, - unsigned StmtIdx, ExplodedNodeImpl* Pred) { - +void GRCoreEngine::HandlePostStmt(const PostStmt& L, CFGBlock* B, + unsigned StmtIdx, ExplodedNode* Pred) { + assert (!B->empty()); if (StmtIdx == B->size()) HandleBlockExit(B, Pred); else { - GRStmtNodeBuilderImpl Builder(B, StmtIdx, Pred, this); + GRStmtNodeBuilder Builder(B, StmtIdx, Pred, this, + SubEngine.getStateManager()); ProcessStmt((*B)[StmtIdx], Builder); } } /// GenerateNode - Utility method to generate nodes, hook up successors, /// and add nodes to the worklist. -void GRCoreEngineImpl::GenerateNode(const ProgramPoint& Loc, const void* State, - ExplodedNodeImpl* Pred) { - +void GRCoreEngine::GenerateNode(const ProgramPoint& Loc, + const GRState* State, ExplodedNode* Pred) { + bool IsNew; - ExplodedNodeImpl* Node = G->getNodeImpl(Loc, State, &IsNew); - - if (Pred) - Node->addPredecessor(Pred); // Link 'Node' with its predecessor. + ExplodedNode* Node = G->getNode(Loc, State, &IsNew); + + if (Pred) + Node->addPredecessor(Pred, *G); // Link 'Node' with its predecessor. else { assert (IsNew); G->addRoot(Node); // 'Node' has no predecessor. Make it a root. } - + // Only add 'Node' to the worklist if it was freshly generated. if (IsNew) WList->Enqueue(Node); } -GRStmtNodeBuilderImpl::GRStmtNodeBuilderImpl(CFGBlock* b, unsigned idx, - ExplodedNodeImpl* N, GRCoreEngineImpl* e) - : Eng(*e), B(*b), Idx(idx), Pred(N), LastNode(N) { +GRStmtNodeBuilder::GRStmtNodeBuilder(CFGBlock* b, unsigned idx, + ExplodedNode* N, GRCoreEngine* e, + GRStateManager &mgr) + : Eng(*e), B(*b), Idx(idx), Pred(N), LastNode(N), Mgr(mgr), Auditor(0), + PurgingDeadSymbols(false), BuildSinks(false), HasGeneratedNode(false), + PointKind(ProgramPoint::PostStmtKind), Tag(0) { Deferred.insert(N); + CleanedState = getLastNode()->getState(); } -GRStmtNodeBuilderImpl::~GRStmtNodeBuilderImpl() { +GRStmtNodeBuilder::~GRStmtNodeBuilder() { for (DeferredTy::iterator I=Deferred.begin(), E=Deferred.end(); I!=E; ++I) if (!(*I)->isSink()) GenerateAutoTransition(*I); } -void GRStmtNodeBuilderImpl::GenerateAutoTransition(ExplodedNodeImpl* N) { +void GRStmtNodeBuilder::GenerateAutoTransition(ExplodedNode* N) { assert (!N->isSink()); - - PostStmt Loc(getStmt()); - + + PostStmt Loc(getStmt(), N->getLocationContext()); + if (Loc == N->getLocation()) { // Note: 'N' should be a fresh node because otherwise it shouldn't be // a member of Deferred. Eng.WList->Enqueue(N, B, Idx+1); return; } - + bool IsNew; - ExplodedNodeImpl* Succ = Eng.G->getNodeImpl(Loc, N->State, &IsNew); - Succ->addPredecessor(N); + ExplodedNode* Succ = Eng.G->getNode(Loc, N->State, &IsNew); + Succ->addPredecessor(N, *Eng.G); if (IsNew) Eng.WList->Enqueue(Succ, B, Idx+1); } -static inline PostStmt GetPostLoc(Stmt* S, ProgramPoint::Kind K, - const void *tag) { +static inline PostStmt GetPostLoc(const Stmt* S, ProgramPoint::Kind K, + const LocationContext *L, const void *tag) { switch (K) { default: assert(false && "Invalid PostXXXKind."); - + case ProgramPoint::PostStmtKind: - return PostStmt(S, tag); - + return PostStmt(S, L, tag); + case ProgramPoint::PostLoadKind: - return PostLoad(S, tag); + return PostLoad(S, L, tag); case ProgramPoint::PostUndefLocationCheckFailedKind: - return PostUndefLocationCheckFailed(S, tag); + return PostUndefLocationCheckFailed(S, L, tag); case ProgramPoint::PostLocationChecksSucceedKind: - return PostLocationChecksSucceed(S, tag); - + return PostLocationChecksSucceed(S, L, tag); + case ProgramPoint::PostOutOfBoundsCheckFailedKind: - return PostOutOfBoundsCheckFailed(S, tag); - + return PostOutOfBoundsCheckFailed(S, L, tag); + case ProgramPoint::PostNullCheckFailedKind: - return PostNullCheckFailed(S, tag); - + return PostNullCheckFailed(S, L, tag); + case ProgramPoint::PostStoreKind: - return PostStore(S, tag); - + return PostStore(S, L, tag); + case ProgramPoint::PostLValueKind: - return PostLValue(S, tag); - + return PostLValue(S, L, tag); + case ProgramPoint::PostPurgeDeadSymbolsKind: - return PostPurgeDeadSymbols(S, tag); + return PostPurgeDeadSymbols(S, L, tag); } } -ExplodedNodeImpl* -GRStmtNodeBuilderImpl::generateNodeImpl(Stmt* S, const void* State, - ExplodedNodeImpl* Pred, +ExplodedNode* +GRStmtNodeBuilder::generateNodeInternal(const Stmt* S, const GRState* State, + ExplodedNode* Pred, ProgramPoint::Kind K, const void *tag) { - return generateNodeImpl(GetPostLoc(S, K, tag), State, Pred); + return K == ProgramPoint::PreStmtKind + ? generateNodeInternal(PreStmt(S, Pred->getLocationContext(),tag), + State, Pred) + : generateNodeInternal(GetPostLoc(S, K, Pred->getLocationContext(), tag), + State, Pred); } -ExplodedNodeImpl* -GRStmtNodeBuilderImpl::generateNodeImpl(PostStmt Loc, const void* State, - ExplodedNodeImpl* Pred) { +ExplodedNode* +GRStmtNodeBuilder::generateNodeInternal(const ProgramPoint &Loc, + const GRState* State, + ExplodedNode* Pred) { bool IsNew; - ExplodedNodeImpl* N = Eng.G->getNodeImpl(Loc, State, &IsNew); - N->addPredecessor(Pred); + ExplodedNode* N = Eng.G->getNode(Loc, State, &IsNew); + N->addPredecessor(Pred, *Eng.G); Deferred.erase(Pred); - + if (IsNew) { Deferred.insert(N); LastNode = N; return N; } - + LastNode = NULL; - return NULL; + return NULL; } -ExplodedNodeImpl* GRBranchNodeBuilderImpl::generateNodeImpl(const void* State, - bool branch) { +ExplodedNode* GRBranchNodeBuilder::generateNode(const GRState* State, + bool branch) { + + // If the branch has been marked infeasible we should not generate a node. + if (!isFeasible(branch)) + return NULL; + bool IsNew; - - ExplodedNodeImpl* Succ = - Eng.G->getNodeImpl(BlockEdge(Src, branch ? DstT : DstF), State, &IsNew); - - Succ->addPredecessor(Pred); - - if (branch) GeneratedTrue = true; - else GeneratedFalse = true; - + + ExplodedNode* Succ = + Eng.G->getNode(BlockEdge(Src,branch ? DstT:DstF,Pred->getLocationContext()), + State, &IsNew); + + Succ->addPredecessor(Pred, *Eng.G); + + if (branch) + GeneratedTrue = true; + else + GeneratedFalse = true; + if (IsNew) { Deferred.push_back(Succ); return Succ; } - + return NULL; } -GRBranchNodeBuilderImpl::~GRBranchNodeBuilderImpl() { - if (!GeneratedTrue) generateNodeImpl(Pred->State, true); - if (!GeneratedFalse) generateNodeImpl(Pred->State, false); - +GRBranchNodeBuilder::~GRBranchNodeBuilder() { + if (!GeneratedTrue) generateNode(Pred->State, true); + if (!GeneratedFalse) generateNode(Pred->State, false); + for (DeferredTy::iterator I=Deferred.begin(), E=Deferred.end(); I!=E; ++I) if (!(*I)->isSink()) Eng.WList->Enqueue(*I); } -ExplodedNodeImpl* -GRIndirectGotoNodeBuilderImpl::generateNodeImpl(const Iterator& I, - const void* St, - bool isSink) { +ExplodedNode* +GRIndirectGotoNodeBuilder::generateNode(const iterator& I, const GRState* St, + bool isSink) { bool IsNew; - - ExplodedNodeImpl* Succ = - Eng.G->getNodeImpl(BlockEdge(Src, I.getBlock()), St, &IsNew); - - Succ->addPredecessor(Pred); - + + ExplodedNode* Succ = Eng.G->getNode(BlockEdge(Src, I.getBlock(), + Pred->getLocationContext()), St, &IsNew); + + Succ->addPredecessor(Pred, *Eng.G); + if (IsNew) { - + if (isSink) Succ->markAsSink(); else Eng.WList->Enqueue(Succ); - + return Succ; } - + return NULL; } -ExplodedNodeImpl* -GRSwitchNodeBuilderImpl::generateCaseStmtNodeImpl(const Iterator& I, - const void* St) { +ExplodedNode* +GRSwitchNodeBuilder::generateCaseStmtNode(const iterator& I, const GRState* St){ bool IsNew; - - ExplodedNodeImpl* Succ = Eng.G->getNodeImpl(BlockEdge(Src, I.getBlock()), - St, &IsNew); - Succ->addPredecessor(Pred); - + + ExplodedNode* Succ = Eng.G->getNode(BlockEdge(Src, I.getBlock(), + Pred->getLocationContext()), St, &IsNew); + Succ->addPredecessor(Pred, *Eng.G); + if (IsNew) { Eng.WList->Enqueue(Succ); return Succ; } - + return NULL; } -ExplodedNodeImpl* -GRSwitchNodeBuilderImpl::generateDefaultCaseNodeImpl(const void* St, - bool isSink) { - +ExplodedNode* +GRSwitchNodeBuilder::generateDefaultCaseNode(const GRState* St, bool isSink) { + // Get the block for the default case. assert (Src->succ_rbegin() != Src->succ_rend()); CFGBlock* DefaultBlock = *Src->succ_rbegin(); - + bool IsNew; - - ExplodedNodeImpl* Succ = Eng.G->getNodeImpl(BlockEdge(Src, DefaultBlock), - St, &IsNew); - Succ->addPredecessor(Pred); - + + ExplodedNode* Succ = Eng.G->getNode(BlockEdge(Src, DefaultBlock, + Pred->getLocationContext()), St, &IsNew); + Succ->addPredecessor(Pred, *Eng.G); + if (IsNew) { if (isSink) Succ->markAsSink(); else Eng.WList->Enqueue(Succ); - + return Succ; } - + return NULL; } -GREndPathNodeBuilderImpl::~GREndPathNodeBuilderImpl() { +GREndPathNodeBuilder::~GREndPathNodeBuilder() { // Auto-generate an EOP node if one has not been generated. - if (!HasGeneratedNode) generateNodeImpl(Pred->State); + if (!HasGeneratedNode) generateNode(Pred->State); } -ExplodedNodeImpl* -GREndPathNodeBuilderImpl::generateNodeImpl(const void* State, - const void *tag, - ExplodedNodeImpl* P) { - HasGeneratedNode = true; +ExplodedNode* +GREndPathNodeBuilder::generateNode(const GRState* State, const void *tag, + ExplodedNode* P) { + HasGeneratedNode = true; bool IsNew; - - ExplodedNodeImpl* Node = - Eng.G->getNodeImpl(BlockEntrance(&B, tag), State, &IsNew); - - Node->addPredecessor(P ? P : Pred); - + + ExplodedNode* Node = Eng.G->getNode(BlockEntrance(&B, + Pred->getLocationContext(), tag), State, &IsNew); + + Node->addPredecessor(P ? P : Pred, *Eng.G); + if (IsNew) { Eng.G->addEndOfPath(Node); return Node; } - + return NULL; } |