diff options
Diffstat (limited to 'include/clang/Analysis/PathSensitive/GRCoreEngine.h')
| -rw-r--r-- | include/clang/Analysis/PathSensitive/GRCoreEngine.h | 190 |
1 files changed, 95 insertions, 95 deletions
diff --git a/include/clang/Analysis/PathSensitive/GRCoreEngine.h b/include/clang/Analysis/PathSensitive/GRCoreEngine.h index 72aaf6ebb5..48b86b9eaf 100644 --- a/include/clang/Analysis/PathSensitive/GRCoreEngine.h +++ b/include/clang/Analysis/PathSensitive/GRCoreEngine.h @@ -1,5 +1,5 @@ //==- GRCoreEngine.h - Path-Sensitive Dataflow Engine --------------*- C++ -*-// -// +// // The LLVM Compiler Infrastructure // // This file is distributed under the University of Illinois Open Source @@ -26,7 +26,7 @@ namespace clang { //===----------------------------------------------------------------------===// -/// GRCoreEngine - Implements the core logic of the graph-reachability +/// GRCoreEngine - Implements the core logic of the graph-reachability /// analysis. It traverses the CFG and generates the ExplodedGraph. /// Program "states" are treated as opaque void pointers. /// The template class GRCoreEngine (which subclasses GRCoreEngine) @@ -45,61 +45,61 @@ class GRCoreEngine { /// G - The simulation graph. Each node is a (location,state) pair. llvm::OwningPtr<ExplodedGraph> G; - + /// WList - A set of queued nodes that need to be processed by the /// worklist algorithm. It is up to the implementation of WList to decide /// the order that nodes are processed. GRWorkList* WList; - + /// BCounterFactory - A factory object for created GRBlockCounter objects. /// These are used to record for key nodes in the ExplodedGraph the /// number of times different CFGBlocks have been visited along a path. GRBlockCounter::Factory BCounterFactory; - + void GenerateNode(const ProgramPoint& Loc, const GRState* State, ExplodedNode* Pred); - + void HandleBlockEdge(const BlockEdge& E, ExplodedNode* Pred); void HandleBlockEntrance(const BlockEntrance& E, ExplodedNode* Pred); void HandleBlockExit(CFGBlock* B, ExplodedNode* Pred); void HandlePostStmt(const PostStmt& S, CFGBlock* B, unsigned StmtIdx, ExplodedNode *Pred); - + void HandleBranch(Stmt* Cond, Stmt* Term, CFGBlock* B, - ExplodedNode* Pred); + ExplodedNode* Pred); /// Get the initial state from the subengine. - const GRState* getInitialState(const LocationContext *InitLoc) { + const GRState* getInitialState(const LocationContext *InitLoc) { return SubEngine.getInitialState(InitLoc); } void ProcessEndPath(GREndPathNodeBuilder& Builder); - + void ProcessStmt(Stmt* S, GRStmtNodeBuilder& Builder); - + bool ProcessBlockEntrance(CFGBlock* Blk, const GRState* State, GRBlockCounter BC); - + void ProcessBranch(Stmt* Condition, Stmt* Terminator, GRBranchNodeBuilder& Builder); void ProcessIndirectGoto(GRIndirectGotoNodeBuilder& Builder); - + void ProcessSwitch(GRSwitchNodeBuilder& Builder); private: GRCoreEngine(const GRCoreEngine&); // Do not implement. GRCoreEngine& operator=(const GRCoreEngine&); - + public: /// Construct a GRCoreEngine object to analyze the provided CFG using /// a DFS exploration of the exploded graph. GRCoreEngine(ASTContext& ctx, GRSubEngine& subengine) - : SubEngine(subengine), G(new ExplodedGraph(ctx)), + : SubEngine(subengine), G(new ExplodedGraph(ctx)), WList(GRWorkList::MakeBFS()), BCounterFactory(G->getAllocator()) {} @@ -116,7 +116,7 @@ public: /// getGraph - Returns the exploded graph. ExplodedGraph& getGraph() { return *G.get(); } - + /// takeGraph - Returns the exploded graph. Ownership of the graph is /// transfered to the caller. ExplodedGraph* takeGraph() { return G.take(); } @@ -125,13 +125,13 @@ public: /// steps. Returns true if there is still simulation state on the worklist. bool ExecuteWorkList(const LocationContext *L, unsigned Steps); }; - + class GRStmtNodeBuilder { GRCoreEngine& Eng; CFGBlock& B; const unsigned Idx; ExplodedNode* Pred; - ExplodedNode* LastNode; + ExplodedNode* LastNode; GRStateManager& Mgr; GRAuditor* Auditor; @@ -141,23 +141,23 @@ public: bool HasGeneratedNode; ProgramPoint::Kind PointKind; const void *Tag; - - const GRState* CleanedState; - + + const GRState* CleanedState; + typedef llvm::SmallPtrSet<ExplodedNode*,5> DeferredTy; DeferredTy Deferred; - + void GenerateAutoTransition(ExplodedNode* N); - + public: - GRStmtNodeBuilder(CFGBlock* b, unsigned idx, ExplodedNode* N, - GRCoreEngine* e, GRStateManager &mgr); - + GRStmtNodeBuilder(CFGBlock* b, unsigned idx, ExplodedNode* N, + GRCoreEngine* e, GRStateManager &mgr); + ~GRStmtNodeBuilder(); - + ExplodedNode* getBasePredecessor() const { return Pred; } - + ExplodedNode* getLastNode() const { return LastNode ? (LastNode->isSink() ? NULL : LastNode) : NULL; } @@ -167,26 +167,26 @@ public: } GRBlockCounter getBlockCounter() const { return Eng.WList->getBlockCounter();} - + unsigned getCurrentBlockCount() const { return getBlockCounter().getNumVisited(B.getBlockID()); - } + } ExplodedNode* generateNode(PostStmt PP,const GRState* St,ExplodedNode* Pred) { HasGeneratedNode = true; return generateNodeInternal(PP, St, Pred); } - + ExplodedNode* generateNode(const Stmt *S, const GRState *St, ExplodedNode *Pred, ProgramPoint::Kind K) { HasGeneratedNode = true; - if (PurgingDeadSymbols) - K = ProgramPoint::PostPurgeDeadSymbolsKind; + if (PurgingDeadSymbols) + K = ProgramPoint::PostPurgeDeadSymbolsKind; return generateNodeInternal(S, St, Pred, K, Tag); } - + ExplodedNode* generateNode(const Stmt *S, const GRState *St, ExplodedNode *Pred) { return generateNode(S, St, Pred, PointKind); @@ -195,16 +195,16 @@ public: ExplodedNode* generateNodeInternal(const ProgramPoint &PP, const GRState* State, ExplodedNode* Pred); - + ExplodedNode* generateNodeInternal(const Stmt* S, const GRState* State, ExplodedNode* Pred, ProgramPoint::Kind K = ProgramPoint::PostStmtKind, const void *tag = 0); - + /// getStmt - Return the current block-level expression associated with /// this builder. Stmt* getStmt() const { return B[Idx]; } - + /// getBlock - Return the CFGBlock associated with the block-level expression /// of this builder. CFGBlock* getBlock() const { return &B; } @@ -218,40 +218,40 @@ public: return Pred->getState(); } - ExplodedNode* MakeNode(ExplodedNodeSet& Dst, Stmt* S, ExplodedNode* Pred, + ExplodedNode* MakeNode(ExplodedNodeSet& Dst, Stmt* S, ExplodedNode* Pred, const GRState* St) { return MakeNode(Dst, S, Pred, St, PointKind); } - + ExplodedNode* MakeNode(ExplodedNodeSet& Dst, Stmt* S, ExplodedNode* Pred, - const GRState* St, ProgramPoint::Kind K) { - + const GRState* St, ProgramPoint::Kind K) { + const GRState* PredState = GetState(Pred); - + // If the state hasn't changed, don't generate a new node. if (!BuildSinks && St == PredState && Auditor == 0) { Dst.Add(Pred); return NULL; } - + ExplodedNode* N = generateNode(S, St, Pred, K); - - if (N) { + + if (N) { if (BuildSinks) N->markAsSink(); else { if (Auditor && Auditor->Audit(N, Mgr)) N->markAsSink(); - + Dst.Add(N); } } - + return N; } - + ExplodedNode* MakeSinkNode(ExplodedNodeSet& Dst, Stmt* S, - ExplodedNode* Pred, const GRState* St) { + ExplodedNode* Pred, const GRState* St) { bool Tmp = BuildSinks; BuildSinks = true; ExplodedNode* N = MakeNode(Dst, S, Pred, St); @@ -260,7 +260,7 @@ public: } }; - + class GRBranchNodeBuilder { GRCoreEngine& Eng; CFGBlock* Src; @@ -270,44 +270,44 @@ class GRBranchNodeBuilder { typedef llvm::SmallVector<ExplodedNode*,3> DeferredTy; DeferredTy Deferred; - + bool GeneratedTrue; bool GeneratedFalse; bool InFeasibleTrue; bool InFeasibleFalse; - + public: GRBranchNodeBuilder(CFGBlock* src, CFGBlock* dstT, CFGBlock* dstF, - ExplodedNode* pred, GRCoreEngine* e) + ExplodedNode* pred, GRCoreEngine* e) : Eng(*e), Src(src), DstT(dstT), DstF(dstF), Pred(pred), GeneratedTrue(false), GeneratedFalse(false), InFeasibleTrue(!DstT), InFeasibleFalse(!DstF) {} - + ~GRBranchNodeBuilder(); - + ExplodedNode* getPredecessor() const { return Pred; } const ExplodedGraph& getGraph() const { return *Eng.G; } GRBlockCounter getBlockCounter() const { return Eng.WList->getBlockCounter();} - + ExplodedNode* generateNode(const GRState* State, bool branch); - + CFGBlock* getTargetBlock(bool branch) const { return branch ? DstT : DstF; - } - + } + void markInfeasible(bool branch) { if (branch) InFeasibleTrue = GeneratedTrue = true; else InFeasibleFalse = GeneratedFalse = true; } - + bool isFeasible(bool branch) { return branch ? !InFeasibleTrue : !InFeasibleFalse; } - + const GRState* getState() const { return getPredecessor()->getState(); } @@ -318,81 +318,81 @@ class GRIndirectGotoNodeBuilder { CFGBlock* Src; CFGBlock& DispatchBlock; Expr* E; - ExplodedNode* Pred; + ExplodedNode* Pred; public: - GRIndirectGotoNodeBuilder(ExplodedNode* pred, CFGBlock* src, Expr* e, + GRIndirectGotoNodeBuilder(ExplodedNode* pred, CFGBlock* src, Expr* e, CFGBlock* dispatch, GRCoreEngine* eng) : Eng(*eng), Src(src), DispatchBlock(*dispatch), E(e), Pred(pred) {} class iterator { CFGBlock::succ_iterator I; - - friend class GRIndirectGotoNodeBuilder; - iterator(CFGBlock::succ_iterator i) : I(i) {} + + friend class GRIndirectGotoNodeBuilder; + iterator(CFGBlock::succ_iterator i) : I(i) {} public: - + iterator& operator++() { ++I; return *this; } bool operator!=(const iterator& X) const { return I != X.I; } - + LabelStmt* getLabel() const { return llvm::cast<LabelStmt>((*I)->getLabel()); } - + CFGBlock* getBlock() const { return *I; } }; - + iterator begin() { return iterator(DispatchBlock.succ_begin()); } iterator end() { return iterator(DispatchBlock.succ_end()); } - + ExplodedNode* generateNode(const iterator& I, const GRState* State, bool isSink = false); - + Expr* getTarget() const { return E; } const GRState* getState() const { return Pred->State; } }; - + class GRSwitchNodeBuilder { GRCoreEngine& Eng; CFGBlock* Src; Expr* Condition; - ExplodedNode* Pred; + ExplodedNode* Pred; public: GRSwitchNodeBuilder(ExplodedNode* pred, CFGBlock* src, Expr* condition, GRCoreEngine* eng) : Eng(*eng), Src(src), Condition(condition), Pred(pred) {} - + class iterator { CFGBlock::succ_reverse_iterator I; - - friend class GRSwitchNodeBuilder; - iterator(CFGBlock::succ_reverse_iterator i) : I(i) {} + + friend class GRSwitchNodeBuilder; + iterator(CFGBlock::succ_reverse_iterator i) : I(i) {} public: iterator& operator++() { ++I; return *this; } bool operator!=(const iterator& X) const { return I != X.I; } - + CaseStmt* getCase() const { return llvm::cast<CaseStmt>((*I)->getLabel()); } - + CFGBlock* getBlock() const { return *I; } }; - + iterator begin() { return iterator(Src->succ_rbegin()+1); } iterator end() { return iterator(Src->succ_rend()); } - + ExplodedNode* generateCaseStmtNode(const iterator& I, const GRState* State); - + ExplodedNode* generateDefaultCaseNode(const GRState* State, bool isSink = false); - + Expr* getCondition() const { return Condition; } const GRState* getState() const { return Pred->State; } @@ -401,28 +401,28 @@ public: class GREndPathNodeBuilder { GRCoreEngine& Eng; CFGBlock& B; - ExplodedNode* Pred; + ExplodedNode* Pred; bool HasGeneratedNode; - + public: GREndPathNodeBuilder(CFGBlock* b, ExplodedNode* N, GRCoreEngine* e) - : Eng(*e), B(*b), Pred(N), HasGeneratedNode(false) {} - + : Eng(*e), B(*b), Pred(N), HasGeneratedNode(false) {} + ~GREndPathNodeBuilder(); - + ExplodedNode* getPredecessor() const { return Pred; } - - GRBlockCounter getBlockCounter() const { + + GRBlockCounter getBlockCounter() const { return Eng.WList->getBlockCounter(); } - + unsigned getCurrentBlockCount() const { return getBlockCounter().getNumVisited(B.getBlockID()); - } - + } + ExplodedNode* generateNode(const GRState* State, const void *tag = 0, ExplodedNode *P = 0); - + CFGBlock* getBlock() const { return &B; } const GRState* getState() const { |