diff options
Diffstat (limited to 'lib/Analysis/GRCoreEngine.cpp')
| -rw-r--r-- | lib/Analysis/GRCoreEngine.cpp | 230 |
1 files changed, 115 insertions, 115 deletions
diff --git a/lib/Analysis/GRCoreEngine.cpp b/lib/Analysis/GRCoreEngine.cpp index 7983dd841b..909f6196d6 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 @@ -48,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 @@ -86,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()) { @@ -101,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 @@ -128,13 +128,13 @@ void GRCoreEngine::ProcessStmt(Stmt* S, GRStmtNodeBuilder& Builder) { } bool GRCoreEngine::ProcessBlockEntrance(CFGBlock* Blk, const GRState* State, - GRBlockCounter BC) { + GRBlockCounter BC) { return SubEngine.ProcessBlockEntrance(Blk, State, BC); } void GRCoreEngine::ProcessBranch(Stmt* Condition, Stmt* Terminator, GRBranchNodeBuilder& Builder) { - SubEngine.ProcessBranch(Condition, Terminator, Builder); + SubEngine.ProcessBranch(Condition, Terminator, Builder); } void GRCoreEngine::ProcessIndirectGoto(GRIndirectGotoNodeBuilder& Builder) { @@ -147,52 +147,52 @@ void GRCoreEngine::ProcessSwitch(GRSwitchNodeBuilder& 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() && + + 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, 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; @@ -201,22 +201,22 @@ bool GRCoreEngine::ExecuteWorkList(const LocationContext *L, unsigned Steps) { assert(isa<PostStmt>(Node->getLocation())); HandlePostStmt(cast<PostStmt>(Node->getLocation()), WU.getBlock(), WU.getIndex(), Node); - break; + break; } } - + return WList->hasWork(); } void GRCoreEngine::HandleBlockEdge(const BlockEdge& L, ExplodedNode* Pred) { - + CFGBlock* Blk = L.getDst(); - - // Check if we are entering the EXIT block. + + // Check if we are entering the EXIT block. if (Blk == &(Pred->getLocationContext()->getCFG()->getExit())) { - - assert (Pred->getLocationContext()->getCFG()->getExit().size() == 0 + + assert (Pred->getLocationContext()->getCFG()->getExit().size() == 0 && "EXIT block cannot contain Stmts."); // Process the final state transition. @@ -228,81 +228,81 @@ void GRCoreEngine::HandleBlockEdge(const BlockEdge& L, ExplodedNode* Pred) { } // 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. + + // Process the entrance of the block. if (Stmt* S = L.getFirstStmt()) { - GRStmtNodeBuilder Builder(L.getBlock(), 0, Pred, this, + GRStmtNodeBuilder Builder(L.getBlock(), 0, Pred, this, SubEngine.getStateManager()); ProcessStmt(S, Builder); } - else + 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: + 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: // @@ -317,15 +317,15 @@ void GRCoreEngine::HandleBlockExit(CFGBlock * B, ExplodedNode* Pred) { 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; @@ -334,8 +334,8 @@ void GRCoreEngine::HandleBlockExit(CFGBlock * B, ExplodedNode* Pred) { assert (B->succ_size() == 1 && "Blocks with no terminator should have at most 1 successor."); - - GenerateNode(BlockEdge(B, *(B->succ_begin()), Pred->getLocationContext()), + + GenerateNode(BlockEdge(B, *(B->succ_begin()), Pred->getLocationContext()), Pred->State, Pred); } @@ -345,19 +345,19 @@ void GRCoreEngine::HandleBranch(Stmt* Cond, Stmt* Term, CFGBlock * B, 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, + GRStmtNodeBuilder Builder(B, StmtIdx, Pred, this, SubEngine.getStateManager()); ProcessStmt((*B)[StmtIdx], Builder); } @@ -365,19 +365,19 @@ void GRCoreEngine::HandlePostStmt(const PostStmt& L, CFGBlock* B, /// GenerateNode - Utility method to generate nodes, hook up successors, /// and add nodes to the worklist. -void GRCoreEngine::GenerateNode(const ProgramPoint& Loc, +void GRCoreEngine::GenerateNode(const ProgramPoint& Loc, const GRState* State, ExplodedNode* Pred) { - + bool IsNew; ExplodedNode* Node = G->getNode(Loc, State, &IsNew); - - if (Pred) + + if (Pred) Node->addPredecessor(Pred); // 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); } @@ -385,7 +385,7 @@ void GRCoreEngine::GenerateNode(const ProgramPoint& Loc, 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), + : 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); @@ -400,16 +400,16 @@ GRStmtNodeBuilder::~GRStmtNodeBuilder() { 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); @@ -423,10 +423,10 @@ static inline PostStmt GetPostLoc(const Stmt* S, ProgramPoint::Kind K, switch (K) { default: assert(false && "Invalid PostXXXKind."); - + case ProgramPoint::PostStmtKind: return PostStmt(S, L, tag); - + case ProgramPoint::PostLoadKind: return PostLoad(S, L, tag); @@ -435,19 +435,19 @@ static inline PostStmt GetPostLoc(const Stmt* S, ProgramPoint::Kind K, case ProgramPoint::PostLocationChecksSucceedKind: return PostLocationChecksSucceed(S, L, tag); - + case ProgramPoint::PostOutOfBoundsCheckFailedKind: return PostOutOfBoundsCheckFailed(S, L, tag); - + case ProgramPoint::PostNullCheckFailedKind: return PostNullCheckFailed(S, L, tag); - + case ProgramPoint::PostStoreKind: return PostStore(S, L, tag); - + case ProgramPoint::PostLValueKind: return PostLValue(S, L, tag); - + case ProgramPoint::PostPurgeDeadSymbolsKind: return PostPurgeDeadSymbols(S, L, tag); } @@ -459,10 +459,10 @@ GRStmtNodeBuilder::generateNodeInternal(const Stmt* S, const GRState* State, ProgramPoint::Kind K, const void *tag) { return K == ProgramPoint::PreStmtKind - ? generateNodeInternal(PreStmt(S, Pred->getLocationContext(),tag), + ? generateNodeInternal(PreStmt(S, Pred->getLocationContext(),tag), State, Pred) : generateNodeInternal(GetPostLoc(S, K, Pred->getLocationContext(), tag), - State, Pred); + State, Pred); } ExplodedNode* @@ -473,49 +473,49 @@ GRStmtNodeBuilder::generateNodeInternal(const ProgramPoint &Loc, ExplodedNode* N = Eng.G->getNode(Loc, State, &IsNew); N->addPredecessor(Pred); Deferred.erase(Pred); - + if (IsNew) { Deferred.insert(N); LastNode = N; return N; } - + LastNode = NULL; - return 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); - + if (branch) GeneratedTrue = true; else - GeneratedFalse = true; - + 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); } @@ -525,22 +525,22 @@ ExplodedNode* GRIndirectGotoNodeBuilder::generateNode(const iterator& I, const GRState* St, bool isSink) { bool IsNew; - - ExplodedNode* Succ = Eng.G->getNode(BlockEdge(Src, I.getBlock(), + + ExplodedNode* Succ = Eng.G->getNode(BlockEdge(Src, I.getBlock(), Pred->getLocationContext()), St, &IsNew); - + Succ->addPredecessor(Pred); - + if (IsNew) { - + if (isSink) Succ->markAsSink(); else Eng.WList->Enqueue(Succ); - + return Succ; } - + return NULL; } @@ -549,42 +549,42 @@ 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); - + 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); - + if (IsNew) { if (isSink) Succ->markAsSink(); else Eng.WList->Enqueue(Succ); - + return Succ; } - + return NULL; } @@ -596,18 +596,18 @@ GREndPathNodeBuilder::~GREndPathNodeBuilder() { ExplodedNode* GREndPathNodeBuilder::generateNode(const GRState* State, const void *tag, ExplodedNode* P) { - HasGeneratedNode = true; + HasGeneratedNode = true; bool IsNew; - - ExplodedNode* Node = Eng.G->getNode(BlockEntrance(&B, + + ExplodedNode* Node = Eng.G->getNode(BlockEntrance(&B, Pred->getLocationContext(), tag), State, &IsNew); - + Node->addPredecessor(P ? P : Pred); - + if (IsNew) { Eng.G->addEndOfPath(Node); return Node; } - + return NULL; } |