diff options
Diffstat (limited to 'lib/Checker/GRCoreEngine.cpp')
| -rw-r--r-- | lib/Checker/GRCoreEngine.cpp | 599 |
1 files changed, 599 insertions, 0 deletions
diff --git a/lib/Checker/GRCoreEngine.cpp b/lib/Checker/GRCoreEngine.cpp new file mode 100644 index 000000000000..d54b0777eda7 --- /dev/null +++ b/lib/Checker/GRCoreEngine.cpp @@ -0,0 +1,599 @@ +//==- GRCoreEngine.cpp - Path-Sensitive Dataflow Engine ------------*- C++ -*-// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines a generic engine for intraprocedural, path-sensitive, +// dataflow analysis via graph reachability engine. +// +//===----------------------------------------------------------------------===// + +#include "clang/Checker/PathSensitive/GRCoreEngine.h" +#include "clang/Checker/PathSensitive/GRExprEngine.h" +#include "clang/AST/Expr.h" +#include "llvm/Support/Casting.h" +#include "llvm/ADT/DenseMap.h" +#include <vector> +#include <queue> + +using llvm::cast; +using llvm::isa; +using namespace clang; + +//===----------------------------------------------------------------------===// +// Worklist classes for exploration of reachable states. +//===----------------------------------------------------------------------===// + +namespace { +class DFS : public GRWorkList { + llvm::SmallVector<GRWorkListUnit,20> Stack; +public: + virtual bool hasWork() const { + return !Stack.empty(); + } + + virtual void Enqueue(const GRWorkListUnit& U) { + Stack.push_back(U); + } + + virtual GRWorkListUnit Dequeue() { + assert (!Stack.empty()); + const GRWorkListUnit& U = Stack.back(); + Stack.pop_back(); // This technically "invalidates" U, but we are fine. + return U; + } +}; + +class 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(); + Queue.pop(); + return U; + } +}; + +} // end anonymous namespace + +// Place the dstor for GRWorkList here because it contains virtual member +// functions, and we the code for the dstor generated in one compilation unit. +GRWorkList::~GRWorkList() {} + +GRWorkList *GRWorkList::MakeDFS() { return new DFS(); } +GRWorkList *GRWorkList::MakeBFS() { return new BFS(); } + +namespace { + class BFSBlockDFSContents : public GRWorkList { + std::queue<GRWorkListUnit> Queue; + llvm::SmallVector<GRWorkListUnit,20> Stack; + public: + 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()) { + const GRWorkListUnit& U = Stack.back(); + 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(); + Queue.pop(); + return U; + } + }; +} // end anonymous namespace + +GRWorkList* GRWorkList::MakeBFSBlockDFSContents() { + return new BFSBlockDFSContents(); +} + +//===----------------------------------------------------------------------===// +// Core analysis engine. +//===----------------------------------------------------------------------===// +void GRCoreEngine::ProcessEndPath(GREndPathNodeBuilder& Builder) { + SubEngine.ProcessEndPath(Builder); +} + +void GRCoreEngine::ProcessStmt(CFGElement E, GRStmtNodeBuilder& Builder) { + SubEngine.ProcessStmt(E, 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 GRCoreEngine::ExecuteWorkList(const LocationContext *L, unsigned Steps) { + + if (G->num_roots() == 0) { // Initialize the analysis by constructing + // the root if none exists. + + 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()); + + // Construct an edge representing the + // starting location in the function. + BlockEdge StartLoc(Entry, Succ, L); + + // Set the current block counter to being empty. + WList->setBlockCounter(BCounterFactory.GetEmptyCounter()); + + // Generate the root. + 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. + 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; + + default: + assert(isa<PostStmt>(Node->getLocation())); + HandlePostStmt(cast<PostStmt>(Node->getLocation()), WU.getBlock(), + WU.getIndex(), Node); + break; + } + } + + return WList->hasWork(); +} + + +void GRCoreEngine::HandleBlockEdge(const BlockEdge& L, ExplodedNode* Pred) { + + CFGBlock* Blk = L.getDst(); + + // Check if we are entering the EXIT block. + if (Blk == &(L.getLocationContext()->getCFG()->getExit())) { + + assert (L.getLocationContext()->getCFG()->getExit().size() == 0 + && "EXIT block cannot contain Stmts."); + + // Process the final state transition. + GREndPathNodeBuilder Builder(Blk, Pred, this); + ProcessEndPath(Builder); + + // This path is done. Don't enqueue any more nodes. + return; + } + + // FIXME: Should we allow ProcessBlockEntrance to also manipulate state? + + if (ProcessBlockEntrance(Blk, Pred->State, WList->getBlockCounter())) + GenerateNode(BlockEntrance(Blk, Pred->getLocationContext()), Pred->State, 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. + if (CFGElement E = L.getFirstElement()) { + GRStmtNodeBuilder Builder(L.getBlock(), 0, Pred, this, + SubEngine.getStateManager()); + ProcessStmt(E, Builder); + } + else + HandleBlockExit(L.getBlock(), Pred); +} + +void GRCoreEngine::HandleBlockExit(CFGBlock * B, ExplodedNode* 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: + 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); + + 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: + // + // (1) inside a basic block, which represents the binding of the + // 'element' variable to a value. + // (2) in a terminator, which represents the branch. + // + // For (1), subengines will bind a value (i.e., 0 or 1) indicating + // whether or not collection contains any more elements. We cannot + // just test to see if the element is nil because a container can + // contain nil elements. + HandleBranch(Term, Term, B, Pred); + return; + } + + case Stmt::SwitchStmtClass: { + GRSwitchNodeBuilder builder(Pred, B, cast<SwitchStmt>(Term)->getCond(), + this); + + ProcessSwitch(builder); + return; + } + + case Stmt::WhileStmtClass: + HandleBranch(cast<WhileStmt>(Term)->getCond(), Term, B, Pred); + return; + } + } + + assert (B->succ_size() == 1 && + "Blocks with no terminator should have at most 1 successor."); + + GenerateNode(BlockEdge(B, *(B->succ_begin()), Pred->getLocationContext()), + Pred->State, Pred); +} + +void GRCoreEngine::HandleBranch(Stmt* Cond, Stmt* Term, CFGBlock * B, + ExplodedNode* Pred) { + assert (B->succ_size() == 2); + + GRBranchNodeBuilder Builder(B, *(B->succ_begin()), *(B->succ_begin()+1), + Pred, this); + + ProcessBranch(Cond, Term, Builder); +} + +void GRCoreEngine::HandlePostStmt(const PostStmt& L, CFGBlock* B, + unsigned StmtIdx, ExplodedNode* Pred) { + + assert (!B->empty()); + + if (StmtIdx == B->size()) + HandleBlockExit(B, Pred); + else { + 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 GRCoreEngine::GenerateNode(const ProgramPoint& Loc, + const GRState* State, ExplodedNode* Pred) { + + bool IsNew; + 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); +} + +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(); +} + +GRStmtNodeBuilder::~GRStmtNodeBuilder() { + for (DeferredTy::iterator I=Deferred.begin(), E=Deferred.end(); I!=E; ++I) + if (!(*I)->isSink()) + GenerateAutoTransition(*I); +} + +void GRStmtNodeBuilder::GenerateAutoTransition(ExplodedNode* N) { + assert (!N->isSink()); + + 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; + ExplodedNode* Succ = Eng.G->getNode(Loc, N->State, &IsNew); + Succ->addPredecessor(N, *Eng.G); + + if (IsNew) + Eng.WList->Enqueue(Succ, B, Idx+1); +} + +static ProgramPoint GetProgramPoint(const Stmt *S, ProgramPoint::Kind K, + const LocationContext *LC, const void *tag){ + switch (K) { + default: + assert(false && "Unhandled ProgramPoint kind"); + case ProgramPoint::PreStmtKind: + return PreStmt(S, LC, tag); + case ProgramPoint::PostStmtKind: + return PostStmt(S, LC, tag); + case ProgramPoint::PreLoadKind: + return PreLoad(S, LC, tag); + case ProgramPoint::PostLoadKind: + return PostLoad(S, LC, tag); + case ProgramPoint::PreStoreKind: + return PreStore(S, LC, tag); + case ProgramPoint::PostStoreKind: + return PostStore(S, LC, tag); + case ProgramPoint::PostLValueKind: + return PostLValue(S, LC, tag); + case ProgramPoint::PostPurgeDeadSymbolsKind: + return PostPurgeDeadSymbols(S, LC, tag); + } +} + +ExplodedNode* +GRStmtNodeBuilder::generateNodeInternal(const Stmt* S, const GRState* state, + ExplodedNode* Pred, + ProgramPoint::Kind K, + const void *tag) { + + const ProgramPoint &L = GetProgramPoint(S, K, Pred->getLocationContext(),tag); + return generateNodeInternal(L, state, Pred); +} + +ExplodedNode* +GRStmtNodeBuilder::generateNodeInternal(const ProgramPoint &Loc, + const GRState* State, + ExplodedNode* Pred) { + bool IsNew; + 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; +} + +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; + + 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; +} + +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); +} + + +ExplodedNode* +GRIndirectGotoNodeBuilder::generateNode(const iterator& I, const GRState* St, + bool isSink) { + bool IsNew; + + 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; +} + + +ExplodedNode* +GRSwitchNodeBuilder::generateCaseStmtNode(const iterator& I, const GRState* St){ + + bool IsNew; + + 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; +} + + +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; + + 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; +} + +GREndPathNodeBuilder::~GREndPathNodeBuilder() { + // Auto-generate an EOP node if one has not been generated. + if (!HasGeneratedNode) generateNode(Pred->State); +} + +ExplodedNode* +GREndPathNodeBuilder::generateNode(const GRState* State, const void *tag, + ExplodedNode* P) { + HasGeneratedNode = true; + bool IsNew; + + 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; +} |