diff options
Diffstat (limited to 'include/clang/Analysis/PathSensitive/GRCoreEngine.h')
| -rw-r--r-- | include/clang/Analysis/PathSensitive/GRCoreEngine.h | 443 |
1 files changed, 0 insertions, 443 deletions
diff --git a/include/clang/Analysis/PathSensitive/GRCoreEngine.h b/include/clang/Analysis/PathSensitive/GRCoreEngine.h deleted file mode 100644 index 74f7a147b841..000000000000 --- a/include/clang/Analysis/PathSensitive/GRCoreEngine.h +++ /dev/null @@ -1,443 +0,0 @@ -//==- GRCoreEngine.h - 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. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_CLANG_ANALYSIS_GRENGINE -#define LLVM_CLANG_ANALYSIS_GRENGINE - -#include "clang/AST/Expr.h" -#include "clang/Analysis/PathSensitive/ExplodedGraph.h" -#include "clang/Analysis/PathSensitive/GRWorkList.h" -#include "clang/Analysis/PathSensitive/GRBlockCounter.h" -#include "clang/Analysis/PathSensitive/GRAuditor.h" -#include "clang/Analysis/PathSensitive/GRSubEngine.h" -#include "llvm/ADT/OwningPtr.h" - -namespace clang { - -//===----------------------------------------------------------------------===// -/// 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) -/// provides the matching component to the engine that knows the actual types -/// for states. Note that this engine only dispatches to transfer functions -/// at the statement and block-level. The analyses themselves must implement -/// any transfer function logic and the sub-expression level (if any). -class GRCoreEngine { - friend class GRStmtNodeBuilder; - friend class GRBranchNodeBuilder; - friend class GRIndirectGotoNodeBuilder; - friend class GRSwitchNodeBuilder; - friend class GREndPathNodeBuilder; - - GRSubEngine& SubEngine; - - /// 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); - - /// Get the initial state from the subengine. - const GRState* getInitialState(const LocationContext *InitLoc) { - return SubEngine.getInitialState(InitLoc); - } - - void ProcessEndPath(GREndPathNodeBuilder& Builder); - - void ProcessStmt(CFGElement E, 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)), - WList(GRWorkList::MakeBFS()), - BCounterFactory(G->getAllocator()) {} - - /// Construct a GRCoreEngine object to analyze the provided CFG and to - /// use the provided worklist object to execute the worklist algorithm. - /// The GRCoreEngine object assumes ownership of 'wlist'. - GRCoreEngine(ASTContext& ctx, GRWorkList* wlist, GRSubEngine& subengine) - : SubEngine(subengine), G(new ExplodedGraph(ctx)), WList(wlist), - BCounterFactory(G->getAllocator()) {} - - ~GRCoreEngine() { - delete WList; - } - - /// 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(); } - - /// ExecuteWorkList - Run the worklist algorithm for a maximum number of - /// 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; - GRStateManager& Mgr; - GRAuditor* Auditor; - -public: - bool PurgingDeadSymbols; - bool BuildSinks; - bool HasGeneratedNode; - ProgramPoint::Kind PointKind; - const void *Tag; - - 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(); - - ExplodedNode* getBasePredecessor() const { return Pred; } - - ExplodedNode* getLastNode() const { - return LastNode ? (LastNode->isSink() ? NULL : LastNode) : NULL; - } - - // FIXME: This should not be exposed. - GRWorkList *getWorkList() { return Eng.WList; } - - void SetCleanedState(const GRState* St) { - CleanedState = St; - } - - 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; - - return generateNodeInternal(S, St, Pred, K, Tag); - } - - ExplodedNode* generateNode(const Stmt *S, const GRState *St, - ExplodedNode *Pred) { - return generateNode(S, St, Pred, PointKind); - } - - 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; } - - unsigned getIndex() const { return Idx; } - - void setAuditor(GRAuditor* A) { Auditor = A; } - - const GRState* GetState(ExplodedNode* Pred) const { - if (Pred == getBasePredecessor()) - return CleanedState; - else - return Pred->getState(); - } - - 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* 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 (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) { - bool Tmp = BuildSinks; - BuildSinks = true; - ExplodedNode* N = MakeNode(Dst, S, Pred, St); - BuildSinks = Tmp; - return N; - } - -}; - -class GRBranchNodeBuilder { - GRCoreEngine& Eng; - CFGBlock* Src; - CFGBlock* DstT; - CFGBlock* DstF; - ExplodedNode* Pred; - - 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) - : 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(); - } -}; - -class GRIndirectGotoNodeBuilder { - GRCoreEngine& Eng; - CFGBlock* Src; - CFGBlock& DispatchBlock; - Expr* E; - ExplodedNode* Pred; - -public: - 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) {} - 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; - -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) {} - - 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; } -}; - -class GREndPathNodeBuilder { - GRCoreEngine &Eng; - CFGBlock& B; - ExplodedNode* Pred; - -public: - bool HasGeneratedNode; - -public: - GREndPathNodeBuilder(CFGBlock* b, ExplodedNode* N, GRCoreEngine* e) - : Eng(*e), B(*b), Pred(N), HasGeneratedNode(false) {} - - ~GREndPathNodeBuilder(); - - GRWorkList &getWorkList() { return *Eng.WList; } - - ExplodedNode* getPredecessor() const { return Pred; } - - 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 { - return getPredecessor()->getState(); - } -}; - -} // end clang namespace - -#endif |