CoreEngine.h revision ad8dcf4a9df0e24051dc31bf9e6f3cd138a34298
1d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis//==- CoreEngine.h - Path-Sensitive Dataflow Engine ----------------*- C++ -*-// 21eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump// 3f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek// The LLVM Compiler Infrastructure 4f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek// 5f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek// This file is distributed under the University of Illinois Open Source 6f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek// License. See LICENSE.TXT for details. 7f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek// 8f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek//===----------------------------------------------------------------------===// 9f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek// 10f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek// This file defines a generic engine for intraprocedural, path-sensitive, 118e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek// dataflow analysis via graph reachability. 12f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek// 13f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek//===----------------------------------------------------------------------===// 14f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek 15d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis#ifndef LLVM_CLANG_GR_COREENGINE 16d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis#define LLVM_CLANG_GR_COREENGINE 17f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek 1899c6ad3f22b865d0f4cce52bc36904403c9ed4c4Ted Kremenek#include "clang/AST/Expr.h" 199b663716449b618ba0390b1dbebc54fa8e971124Ted Kremenek#include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h" 209b663716449b618ba0390b1dbebc54fa8e971124Ted Kremenek#include "clang/StaticAnalyzer/Core/PathSensitive/WorkList.h" 219b663716449b618ba0390b1dbebc54fa8e971124Ted Kremenek#include "clang/StaticAnalyzer/Core/PathSensitive/BlockCounter.h" 229b663716449b618ba0390b1dbebc54fa8e971124Ted Kremenek#include "clang/StaticAnalyzer/Core/PathSensitive/SubEngine.h" 23f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek#include "llvm/ADT/OwningPtr.h" 24f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek 25f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremeneknamespace clang { 260111f575b968e423dccae439e501225b8314b257Zhongxing Xu 279ef6537a894c33003359b1f9b9676e9178e028b7Ted Kremeneknamespace ento { 285a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis 2924f1a967741ff9f8025ee23be12ba6feacc31f77Ted Kremenek//===----------------------------------------------------------------------===// 30d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis/// CoreEngine - Implements the core logic of the graph-reachability 31922059dec59c7bed235da01aff75ae522a369811Ted Kremenek/// analysis. It traverses the CFG and generates the ExplodedGraph. 32922059dec59c7bed235da01aff75ae522a369811Ted Kremenek/// Program "states" are treated as opaque void pointers. 33d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis/// The template class CoreEngine (which subclasses CoreEngine) 34922059dec59c7bed235da01aff75ae522a369811Ted Kremenek/// provides the matching component to the engine that knows the actual types 35922059dec59c7bed235da01aff75ae522a369811Ted Kremenek/// for states. Note that this engine only dispatches to transfer functions 36922059dec59c7bed235da01aff75ae522a369811Ted Kremenek/// at the statement and block-level. The analyses themselves must implement 37922059dec59c7bed235da01aff75ae522a369811Ted Kremenek/// any transfer function logic and the sub-expression level (if any). 38d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidisclass CoreEngine { 39d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis friend class StmtNodeBuilder; 4027c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek friend class GenericNodeBuilderImpl; 41d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis friend class BranchNodeBuilder; 42d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis friend class IndirectGotoNodeBuilder; 43d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis friend class SwitchNodeBuilder; 44e36de1fe51c39d9161915dd3dbef880954af6476Ted Kremenek friend class EndOfFunctionNodeBuilder; 45d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis friend class CallEnterNodeBuilder; 46d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis friend class CallExitNodeBuilder; 470111f575b968e423dccae439e501225b8314b257Zhongxing Xu 48a7a8a450d908b34fa5f569f2e694ebd4b61aae2fTom Carepublic: 49a7a8a450d908b34fa5f569f2e694ebd4b61aae2fTom Care typedef std::vector<std::pair<BlockEdge, const ExplodedNode*> > 50a7a8a450d908b34fa5f569f2e694ebd4b61aae2fTom Care BlocksAborted; 51a7a8a450d908b34fa5f569f2e694ebd4b61aae2fTom Careprivate: 52a7a8a450d908b34fa5f569f2e694ebd4b61aae2fTom Care 53d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis SubEngine& SubEng; 540111f575b968e423dccae439e501225b8314b257Zhongxing Xu 55f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek /// G - The simulation graph. Each node is a (location,state) pair. 5638b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu llvm::OwningPtr<ExplodedGraph> G; 571eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 58f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek /// WList - A set of queued nodes that need to be processed by the 59f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek /// worklist algorithm. It is up to the implementation of WList to decide 60f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek /// the order that nodes are processed. 61d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis WorkList* WList; 621eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 63d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis /// BCounterFactory - A factory object for created BlockCounter objects. 648e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek /// These are used to record for key nodes in the ExplodedGraph the 658e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek /// number of times different CFGBlocks have been visited along a path. 66d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis BlockCounter::Factory BCounterFactory; 67f598087b4adfea164acdd5b53ea2951bde740a2dTed Kremenek 68f598087b4adfea164acdd5b53ea2951bde740a2dTed Kremenek /// The locations where we stopped doing work because we visited a location 69f598087b4adfea164acdd5b53ea2951bde740a2dTed Kremenek /// too many times. 70f598087b4adfea164acdd5b53ea2951bde740a2dTed Kremenek BlocksAborted blocksAborted; 711eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 72d048c6ef5b6cfaa0cecb8cc1d4bdace32ed21d07Ted Kremenek void generateNode(const ProgramPoint& Loc, const GRState* State, 73c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu ExplodedNode* Pred); 741eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 75c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu void HandleBlockEdge(const BlockEdge& E, ExplodedNode* Pred); 76c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu void HandleBlockEntrance(const BlockEntrance& E, ExplodedNode* Pred); 7703509aea098772644bf4662dc1c88634818ceeccZhongxing Xu void HandleBlockExit(const CFGBlock* B, ExplodedNode* Pred); 789dc84c9455df2a77195147d0210c915dc1775a88Zhongxing Xu void HandlePostStmt(const CFGBlock* B, unsigned StmtIdx, ExplodedNode *Pred); 791eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 8003509aea098772644bf4662dc1c88634818ceeccZhongxing Xu void HandleBranch(const Stmt* Cond, const Stmt* Term, const CFGBlock* B, 811eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump ExplodedNode* Pred); 82102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor void HandleCallEnter(const CallEnter &L, const CFGBlock *Block, 83102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor unsigned Index, ExplodedNode *Pred); 84102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor void HandleCallExit(const CallExit &L, ExplodedNode *Pred); 850111f575b968e423dccae439e501225b8314b257Zhongxing Xu 86f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenekprivate: 87d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis CoreEngine(const CoreEngine&); // Do not implement. 88d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis CoreEngine& operator=(const CoreEngine&); 891eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 90f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenekpublic: 91d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis /// Construct a CoreEngine object to analyze the provided CFG using 920111f575b968e423dccae439e501225b8314b257Zhongxing Xu /// a DFS exploration of the exploded graph. 93d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis CoreEngine(SubEngine& subengine) 94d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis : SubEng(subengine), G(new ExplodedGraph()), 9555825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek WList(WorkList::makeBFS()), 96f598087b4adfea164acdd5b53ea2951bde740a2dTed Kremenek BCounterFactory(G->getAllocator()) {} 970111f575b968e423dccae439e501225b8314b257Zhongxing Xu 98d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis /// Construct a CoreEngine object to analyze the provided CFG and to 990111f575b968e423dccae439e501225b8314b257Zhongxing Xu /// use the provided worklist object to execute the worklist algorithm. 100d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis /// The CoreEngine object assumes ownership of 'wlist'. 101d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis CoreEngine(WorkList* wlist, SubEngine& subengine) 102d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis : SubEng(subengine), G(new ExplodedGraph()), WList(wlist), 103f598087b4adfea164acdd5b53ea2951bde740a2dTed Kremenek BCounterFactory(G->getAllocator()) {} 1040111f575b968e423dccae439e501225b8314b257Zhongxing Xu 105d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis ~CoreEngine() { 1060111f575b968e423dccae439e501225b8314b257Zhongxing Xu delete WList; 1070111f575b968e423dccae439e501225b8314b257Zhongxing Xu } 1080111f575b968e423dccae439e501225b8314b257Zhongxing Xu 1090111f575b968e423dccae439e501225b8314b257Zhongxing Xu /// getGraph - Returns the exploded graph. 110031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu ExplodedGraph& getGraph() { return *G.get(); } 1111eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1120111f575b968e423dccae439e501225b8314b257Zhongxing Xu /// takeGraph - Returns the exploded graph. Ownership of the graph is 1130111f575b968e423dccae439e501225b8314b257Zhongxing Xu /// transfered to the caller. 114031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu ExplodedGraph* takeGraph() { return G.take(); } 1150111f575b968e423dccae439e501225b8314b257Zhongxing Xu 116f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek /// ExecuteWorkList - Run the worklist algorithm for a maximum number of 117f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek /// steps. Returns true if there is still simulation state on the worklist. 1182ce43c8f43254a9edea53a20dc0e69195bc82ae0Zhongxing Xu bool ExecuteWorkList(const LocationContext *L, unsigned Steps, 1192ce43c8f43254a9edea53a20dc0e69195bc82ae0Zhongxing Xu const GRState *InitState); 1202ce43c8f43254a9edea53a20dc0e69195bc82ae0Zhongxing Xu void ExecuteWorkListWithInitialState(const LocationContext *L, unsigned Steps, 1212ce43c8f43254a9edea53a20dc0e69195bc82ae0Zhongxing Xu const GRState *InitState, 1222ce43c8f43254a9edea53a20dc0e69195bc82ae0Zhongxing Xu ExplodedNodeSet &Dst); 123bc42c533e7d3d946704a49e242939dd232f33072Tom Care 124bc42c533e7d3d946704a49e242939dd232f33072Tom Care // Functions for external checking of whether we have unfinished work 125f598087b4adfea164acdd5b53ea2951bde740a2dTed Kremenek bool wasBlockAborted() const { return !blocksAborted.empty(); } 126f598087b4adfea164acdd5b53ea2951bde740a2dTed Kremenek bool hasWorkRemaining() const { return wasBlockAborted() || WList->hasWork(); } 127bc42c533e7d3d946704a49e242939dd232f33072Tom Care 128d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis WorkList *getWorkList() const { return WList; } 129f598087b4adfea164acdd5b53ea2951bde740a2dTed Kremenek 130f598087b4adfea164acdd5b53ea2951bde740a2dTed Kremenek BlocksAborted::const_iterator blocks_aborted_begin() const { 131f598087b4adfea164acdd5b53ea2951bde740a2dTed Kremenek return blocksAborted.begin(); 132f598087b4adfea164acdd5b53ea2951bde740a2dTed Kremenek } 133f598087b4adfea164acdd5b53ea2951bde740a2dTed Kremenek BlocksAborted::const_iterator blocks_aborted_end() const { 134f598087b4adfea164acdd5b53ea2951bde740a2dTed Kremenek return blocksAborted.end(); 135f598087b4adfea164acdd5b53ea2951bde740a2dTed Kremenek } 136f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek}; 1371eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 138d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidisclass StmtNodeBuilder { 139d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis CoreEngine& Eng; 14003509aea098772644bf4662dc1c88634818ceeccZhongxing Xu const CFGBlock& B; 141f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek const unsigned Idx; 142c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu ExplodedNode* Pred; 143031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu GRStateManager& Mgr; 144031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu 145031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xupublic: 146031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu bool PurgingDeadSymbols; 147031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu bool BuildSinks; 148b4857264b8d3d861f688cdaa174aab30e0729a73Ted Kremenek bool hasGeneratedNode; 149031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu ProgramPoint::Kind PointKind; 150031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu const void *Tag; 1511eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1521eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump const GRState* CleanedState; 1531eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 154031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu 155c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu typedef llvm::SmallPtrSet<ExplodedNode*,5> DeferredTy; 156f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek DeferredTy Deferred; 1571eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 158c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu void GenerateAutoTransition(ExplodedNode* N); 1591eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 160f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenekpublic: 161d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis StmtNodeBuilder(const CFGBlock* b, unsigned idx, ExplodedNode* N, 162d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis CoreEngine* e, GRStateManager &mgr); 1631eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 164d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis ~StmtNodeBuilder(); 1651eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 166b4857264b8d3d861f688cdaa174aab30e0729a73Ted Kremenek ExplodedNode* getPredecessor() const { return Pred; } 1671eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 168798d2ca60d1cd6de70d28a5ce60337a2b03a663fZhongxing Xu // FIXME: This should not be exposed. 169d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis WorkList *getWorkList() { return Eng.WList; } 170798d2ca60d1cd6de70d28a5ce60337a2b03a663fZhongxing Xu 171031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu void SetCleanedState(const GRState* St) { 172031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu CleanedState = St; 173031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu } 174031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu 175d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis BlockCounter getBlockCounter() const { return Eng.WList->getBlockCounter();} 1761eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 17700a3a5f024ac54088ab887712b292171188064f0Ted Kremenek unsigned getCurrentBlockCount() const { 178d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu return getBlockCounter().getNumVisited( 179d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu Pred->getLocationContext()->getCurrentStackFrame(), 180d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu B.getBlockID()); 1811eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump } 182031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu 183031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu ExplodedNode* generateNode(PostStmt PP,const GRState* St,ExplodedNode* Pred) { 184b4857264b8d3d861f688cdaa174aab30e0729a73Ted Kremenek hasGeneratedNode = true; 185031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu return generateNodeInternal(PP, St, Pred); 186031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu } 1871eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 188e1ccccff777f6bad6b25e9c6a762f98fd8003181Ted Kremenek ExplodedNode* generateNode(const Stmt *S, const GRState *St, 1894bac726dadb09ee38bab8147f1e706380368b362Ted Kremenek ExplodedNode *Pred, ProgramPoint::Kind K, 1904bac726dadb09ee38bab8147f1e706380368b362Ted Kremenek const void *tag = 0) { 191b4857264b8d3d861f688cdaa174aab30e0729a73Ted Kremenek hasGeneratedNode = true; 192031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu 1931eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump if (PurgingDeadSymbols) 1941eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump K = ProgramPoint::PostPurgeDeadSymbolsKind; 195031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu 1964bac726dadb09ee38bab8147f1e706380368b362Ted Kremenek return generateNodeInternal(S, St, Pred, K, tag ? tag : Tag); 197031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu } 1981eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 199e1ccccff777f6bad6b25e9c6a762f98fd8003181Ted Kremenek ExplodedNode* generateNode(const Stmt *S, const GRState *St, 2004bac726dadb09ee38bab8147f1e706380368b362Ted Kremenek ExplodedNode *Pred, const void *tag = 0) { 2014bac726dadb09ee38bab8147f1e706380368b362Ted Kremenek return generateNode(S, St, Pred, PointKind, tag); 202031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu } 203031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu 204102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor ExplodedNode *generateNode(const ProgramPoint &PP, const GRState* State, 205102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor ExplodedNode* Pred) { 206b4857264b8d3d861f688cdaa174aab30e0729a73Ted Kremenek hasGeneratedNode = true; 207102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor return generateNodeInternal(PP, State, Pred); 208102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor } 209102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 210c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu ExplodedNode* 211031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu generateNodeInternal(const ProgramPoint &PP, const GRState* State, 212031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu ExplodedNode* Pred); 2131eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 214c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu ExplodedNode* 215031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu generateNodeInternal(const Stmt* S, const GRState* State, ExplodedNode* Pred, 2161670e403c48f3af4fceff3f6773a0e1cfc6c4eb3Ted Kremenek ProgramPoint::Kind K = ProgramPoint::PostStmtKind, 2171670e403c48f3af4fceff3f6773a0e1cfc6c4eb3Ted Kremenek const void *tag = 0); 2181eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 219331b0ac44b9eb0ffcba66b4f3f3f9adb27c2434fTed Kremenek /// getStmt - Return the current block-level expression associated with 220331b0ac44b9eb0ffcba66b4f3f3f9adb27c2434fTed Kremenek /// this builder. 221b36cd3e1757fb4fcd9509f35558c847b04bef35fZhongxing Xu const Stmt* getStmt() const { 222b36cd3e1757fb4fcd9509f35558c847b04bef35fZhongxing Xu CFGStmt CS = B[Idx].getAs<CFGStmt>(); 223b36cd3e1757fb4fcd9509f35558c847b04bef35fZhongxing Xu if (CS) 224b36cd3e1757fb4fcd9509f35558c847b04bef35fZhongxing Xu return CS.getStmt(); 225b36cd3e1757fb4fcd9509f35558c847b04bef35fZhongxing Xu else 226b36cd3e1757fb4fcd9509f35558c847b04bef35fZhongxing Xu return 0; 227b36cd3e1757fb4fcd9509f35558c847b04bef35fZhongxing Xu } 2281eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 229331b0ac44b9eb0ffcba66b4f3f3f9adb27c2434fTed Kremenek /// getBlock - Return the CFGBlock associated with the block-level expression 230331b0ac44b9eb0ffcba66b4f3f3f9adb27c2434fTed Kremenek /// of this builder. 23103509aea098772644bf4662dc1c88634818ceeccZhongxing Xu const CFGBlock* getBlock() const { return &B; } 232bdb435ddaafd5069becd543d638112f68825b89dTed Kremenek 233598278bee8e5797bc73d24d6ac8a1d6ff6413caeZhongxing Xu unsigned getIndex() const { return Idx; } 234598278bee8e5797bc73d24d6ac8a1d6ff6413caeZhongxing Xu 235031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu const GRState* GetState(ExplodedNode* Pred) const { 236b4857264b8d3d861f688cdaa174aab30e0729a73Ted Kremenek if (Pred == getPredecessor()) 2373bbad550be7edc628be31b51d2a51b6d7d46eafbTed Kremenek return CleanedState; 2383bbad550be7edc628be31b51d2a51b6d7d46eafbTed Kremenek else 2393bbad550be7edc628be31b51d2a51b6d7d46eafbTed Kremenek return Pred->getState(); 2403bbad550be7edc628be31b51d2a51b6d7d46eafbTed Kremenek } 241031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu 2423992a50eea030a2913f1d267554f55ecd00d694cZhongxing Xu ExplodedNode* MakeNode(ExplodedNodeSet& Dst, const Stmt* S, 2433992a50eea030a2913f1d267554f55ecd00d694cZhongxing Xu ExplodedNode* Pred, const GRState* St) { 244bf4e419d996bf42e4933cada610d973a0fcc40ebTed Kremenek return MakeNode(Dst, S, Pred, St, PointKind); 245bf4e419d996bf42e4933cada610d973a0fcc40ebTed Kremenek } 2461eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 2473992a50eea030a2913f1d267554f55ecd00d694cZhongxing Xu ExplodedNode* MakeNode(ExplodedNodeSet& Dst, const Stmt* S,ExplodedNode* Pred, 248868e78d59d2dfaf9cda511925e5a58f3a712db96Zhongxing Xu const GRState* St, ProgramPoint::Kind K); 2491eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 2503992a50eea030a2913f1d267554f55ecd00d694cZhongxing Xu ExplodedNode* MakeSinkNode(ExplodedNodeSet& Dst, const Stmt* S, 2511eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump ExplodedNode* Pred, const GRState* St) { 25270a733e64e2379a654631a14fa29e46761d5f80dTed Kremenek bool Tmp = BuildSinks; 25370a733e64e2379a654631a14fa29e46761d5f80dTed Kremenek BuildSinks = true; 254031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu ExplodedNode* N = MakeNode(Dst, S, Pred, St); 25570a733e64e2379a654631a14fa29e46761d5f80dTed Kremenek BuildSinks = Tmp; 25670a733e64e2379a654631a14fa29e46761d5f80dTed Kremenek return N; 25770a733e64e2379a654631a14fa29e46761d5f80dTed Kremenek } 258f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek}; 2591eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 260d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidisclass BranchNodeBuilder { 261d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis CoreEngine& Eng; 26203509aea098772644bf4662dc1c88634818ceeccZhongxing Xu const CFGBlock* Src; 26303509aea098772644bf4662dc1c88634818ceeccZhongxing Xu const CFGBlock* DstT; 26403509aea098772644bf4662dc1c88634818ceeccZhongxing Xu const CFGBlock* DstF; 265c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu ExplodedNode* Pred; 26652a16499df87730c0252b431abdf2b2e32d756a6Ted Kremenek 267c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu typedef llvm::SmallVector<ExplodedNode*,3> DeferredTy; 2683b4f6702860208692f6ef28401e68de4e3ff9af9Ted Kremenek DeferredTy Deferred; 2691eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 27071c29bdc931bc49644c581ec7d698f0dbf01a0aaTed Kremenek bool GeneratedTrue; 27171c29bdc931bc49644c581ec7d698f0dbf01a0aaTed Kremenek bool GeneratedFalse; 272520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek bool InFeasibleTrue; 273520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek bool InFeasibleFalse; 2741eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 2757d7fe6d539b3bdb1701835223cca306c325614a7Ted Kremenekpublic: 276d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis BranchNodeBuilder(const CFGBlock* src, const CFGBlock* dstT, 277d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis const CFGBlock* dstF, ExplodedNode* pred, CoreEngine* e) 27871c29bdc931bc49644c581ec7d698f0dbf01a0aaTed Kremenek : Eng(*e), Src(src), DstT(dstT), DstF(dstF), Pred(pred), 279520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek GeneratedTrue(false), GeneratedFalse(false), 280520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek InFeasibleTrue(!DstT), InFeasibleFalse(!DstF) {} 2811eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 282d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis ~BranchNodeBuilder(); 2831eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 284c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu ExplodedNode* getPredecessor() const { return Pred; } 285031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu 28638b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu const ExplodedGraph& getGraph() const { return *Eng.G; } 287031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu 288d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis BlockCounter getBlockCounter() const { return Eng.WList->getBlockCounter();} 2891eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 290031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu ExplodedNode* generateNode(const GRState* State, bool branch); 2911eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 29203509aea098772644bf4662dc1c88634818ceeccZhongxing Xu const CFGBlock* getTargetBlock(bool branch) const { 2938e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek return branch ? DstT : DstF; 2941eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump } 2951eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 29652a16499df87730c0252b431abdf2b2e32d756a6Ted Kremenek void markInfeasible(bool branch) { 297520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek if (branch) 298520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek InFeasibleTrue = GeneratedTrue = true; 299520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek else 300520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek InFeasibleFalse = GeneratedFalse = true; 301520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek } 3021eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 303520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek bool isFeasible(bool branch) { 304520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek return branch ? !InFeasibleTrue : !InFeasibleFalse; 30552a16499df87730c0252b431abdf2b2e32d756a6Ted Kremenek } 3061eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 307031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu const GRState* getState() const { 308b38911f16b4943548db6a3695fc6ae23070b25d2Ted Kremenek return getPredecessor()->getState(); 309b38911f16b4943548db6a3695fc6ae23070b25d2Ted Kremenek } 3107d7fe6d539b3bdb1701835223cca306c325614a7Ted Kremenek}; 311031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu 312d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidisclass IndirectGotoNodeBuilder { 313d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis CoreEngine& Eng; 31403509aea098772644bf4662dc1c88634818ceeccZhongxing Xu const CFGBlock* Src; 31503509aea098772644bf4662dc1c88634818ceeccZhongxing Xu const CFGBlock& DispatchBlock; 31603509aea098772644bf4662dc1c88634818ceeccZhongxing Xu const Expr* E; 3171eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump ExplodedNode* Pred; 318031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu 319754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenekpublic: 320d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis IndirectGotoNodeBuilder(ExplodedNode* pred, const CFGBlock* src, 321d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis const Expr* e, const CFGBlock* dispatch, CoreEngine* eng) 32203509aea098772644bf4662dc1c88634818ceeccZhongxing Xu : Eng(*eng), Src(src), DispatchBlock(*dispatch), E(e), Pred(pred) {} 323754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek 324031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu class iterator { 32503509aea098772644bf4662dc1c88634818ceeccZhongxing Xu CFGBlock::const_succ_iterator I; 3261eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 327d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis friend class IndirectGotoNodeBuilder; 32803509aea098772644bf4662dc1c88634818ceeccZhongxing Xu iterator(CFGBlock::const_succ_iterator i) : I(i) {} 329754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek public: 3301eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 331031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu iterator& operator++() { ++I; return *this; } 332031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu bool operator!=(const iterator& X) const { return I != X.I; } 3331eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 334ad8dcf4a9df0e24051dc31bf9e6f3cd138a34298Chris Lattner const LabelDecl *getLabel() const { 335ad8dcf4a9df0e24051dc31bf9e6f3cd138a34298Chris Lattner return llvm::cast<LabelStmt>((*I)->getLabel())->getDecl(); 33624f1a967741ff9f8025ee23be12ba6feacc31f77Ted Kremenek } 3371eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 338ad8dcf4a9df0e24051dc31bf9e6f3cd138a34298Chris Lattner const CFGBlock *getBlock() const { 33924f1a967741ff9f8025ee23be12ba6feacc31f77Ted Kremenek return *I; 34024f1a967741ff9f8025ee23be12ba6feacc31f77Ted Kremenek } 341754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek }; 3421eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 343031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu iterator begin() { return iterator(DispatchBlock.succ_begin()); } 344031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu iterator end() { return iterator(DispatchBlock.succ_end()); } 3451eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 346031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu ExplodedNode* generateNode(const iterator& I, const GRState* State, 347031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu bool isSink = false); 3481eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 34903509aea098772644bf4662dc1c88634818ceeccZhongxing Xu const Expr* getTarget() const { return E; } 350754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek 351031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu const GRState* getState() const { return Pred->State; } 352754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek}; 3531eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 354d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidisclass SwitchNodeBuilder { 355d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis CoreEngine& Eng; 35603509aea098772644bf4662dc1c88634818ceeccZhongxing Xu const CFGBlock* Src; 35703509aea098772644bf4662dc1c88634818ceeccZhongxing Xu const Expr* Condition; 3581eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump ExplodedNode* Pred; 359031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu 360daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenekpublic: 361d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis SwitchNodeBuilder(ExplodedNode* pred, const CFGBlock* src, 362d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis const Expr* condition, CoreEngine* eng) 363daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek : Eng(*eng), Src(src), Condition(condition), Pred(pred) {} 3641eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 365031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu class iterator { 36603509aea098772644bf4662dc1c88634818ceeccZhongxing Xu CFGBlock::const_succ_reverse_iterator I; 3671eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 368d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis friend class SwitchNodeBuilder; 36903509aea098772644bf4662dc1c88634818ceeccZhongxing Xu iterator(CFGBlock::const_succ_reverse_iterator i) : I(i) {} 370031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu 371daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek public: 372031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu iterator& operator++() { ++I; return *this; } 37334feff654c6304e0a59ceb1376989d28dbc956ffTed Kremenek bool operator!=(const iterator &X) const { return I != X.I; } 37434feff654c6304e0a59ceb1376989d28dbc956ffTed Kremenek bool operator==(const iterator &X) const { return I == X.I; } 3751eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 37603509aea098772644bf4662dc1c88634818ceeccZhongxing Xu const CaseStmt* getCase() const { 377daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek return llvm::cast<CaseStmt>((*I)->getLabel()); 378daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek } 3791eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 38003509aea098772644bf4662dc1c88634818ceeccZhongxing Xu const CFGBlock* getBlock() const { 381daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek return *I; 382daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek } 383daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek }; 3841eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 385031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu iterator begin() { return iterator(Src->succ_rbegin()+1); } 386031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu iterator end() { return iterator(Src->succ_rend()); } 3871eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3884d3175c1e5a44251ea97b0c81e80f060629d9c08Ted Kremenek const SwitchStmt *getSwitch() const { 3894d3175c1e5a44251ea97b0c81e80f060629d9c08Ted Kremenek return llvm::cast<SwitchStmt>(Src->getTerminator()); 3904d3175c1e5a44251ea97b0c81e80f060629d9c08Ted Kremenek } 3914d3175c1e5a44251ea97b0c81e80f060629d9c08Ted Kremenek 392031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu ExplodedNode* generateCaseStmtNode(const iterator& I, const GRState* State); 3931eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 394031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu ExplodedNode* generateDefaultCaseNode(const GRState* State, 395031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu bool isSink = false); 3961eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 39703509aea098772644bf4662dc1c88634818ceeccZhongxing Xu const Expr* getCondition() const { return Condition; } 398daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek 399031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu const GRState* getState() const { return Pred->State; } 400daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek}; 40111062b118476368fa5b294954713e5df97d8599fTed Kremenek 40227c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenekclass GenericNodeBuilderImpl { 40327c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenekprotected: 40427c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek CoreEngine &engine; 40527c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek ExplodedNode *pred; 40627c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek ProgramPoint pp; 40727c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek llvm::SmallVector<ExplodedNode*, 2> sinksGenerated; 40827c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek 40927c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek ExplodedNode *generateNodeImpl(const GRState *state, ExplodedNode *pred, 41027c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek ProgramPoint programPoint, bool asSink); 41127c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek 41227c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek GenericNodeBuilderImpl(CoreEngine &eng, ExplodedNode *pr, ProgramPoint p) 413b4857264b8d3d861f688cdaa174aab30e0729a73Ted Kremenek : engine(eng), pred(pr), pp(p), hasGeneratedNode(false) {} 41427c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek 41527c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenekpublic: 416b4857264b8d3d861f688cdaa174aab30e0729a73Ted Kremenek bool hasGeneratedNode; 41727c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek 41827c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek WorkList &getWorkList() { return *engine.WList; } 41927c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek 42027c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek ExplodedNode* getPredecessor() const { return pred; } 42127c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek 42227c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek BlockCounter getBlockCounter() const { 42327c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek return engine.WList->getBlockCounter(); 42427c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek } 42527c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek 42627c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek const llvm::SmallVectorImpl<ExplodedNode*> &sinks() const { 42727c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek return sinksGenerated; 42827c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek } 42927c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek}; 43027c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek 431b6a2b08a6b3fbce1a6a4b69d4185165de970696cTed Kremenektemplate <typename PP_T> 43227c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenekclass GenericNodeBuilder : public GenericNodeBuilderImpl { 43327c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenekpublic: 434b6a2b08a6b3fbce1a6a4b69d4185165de970696cTed Kremenek GenericNodeBuilder(CoreEngine &eng, ExplodedNode *pr, const PP_T &p) 43527c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek : GenericNodeBuilderImpl(eng, pr, p) {} 43627c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek 43727c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek ExplodedNode *generateNode(const GRState *state, ExplodedNode *pred, 438b6a2b08a6b3fbce1a6a4b69d4185165de970696cTed Kremenek const void *tag, bool asSink) { 439b6a2b08a6b3fbce1a6a4b69d4185165de970696cTed Kremenek return generateNodeImpl(state, pred, cast<PP_T>(pp).withTag(tag), 440b6a2b08a6b3fbce1a6a4b69d4185165de970696cTed Kremenek asSink); 44127c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek } 44227c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek 443b6a2b08a6b3fbce1a6a4b69d4185165de970696cTed Kremenek const PP_T &getProgramPoint() const { return cast<PP_T>(pp); } 44427c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek}; 44527c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek 446e36de1fe51c39d9161915dd3dbef880954af6476Ted Kremenekclass EndOfFunctionNodeBuilder { 447d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis CoreEngine &Eng; 44803509aea098772644bf4662dc1c88634818ceeccZhongxing Xu const CFGBlock& B; 4491eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump ExplodedNode* Pred; 450f605aae3227ffa3a5dae8eb34fdd79ba0a0d19d1Zhongxing Xu 451f605aae3227ffa3a5dae8eb34fdd79ba0a0d19d1Zhongxing Xupublic: 452b4857264b8d3d861f688cdaa174aab30e0729a73Ted Kremenek bool hasGeneratedNode; 4531eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 45411062b118476368fa5b294954713e5df97d8599fTed Kremenekpublic: 455e36de1fe51c39d9161915dd3dbef880954af6476Ted Kremenek EndOfFunctionNodeBuilder(const CFGBlock* b, ExplodedNode* N, CoreEngine* e) 456b4857264b8d3d861f688cdaa174aab30e0729a73Ted Kremenek : Eng(*e), B(*b), Pred(N), hasGeneratedNode(false) {} 4571eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 458e36de1fe51c39d9161915dd3dbef880954af6476Ted Kremenek ~EndOfFunctionNodeBuilder(); 4591eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 460d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis WorkList &getWorkList() { return *Eng.WList; } 461598278bee8e5797bc73d24d6ac8a1d6ff6413caeZhongxing Xu 462c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu ExplodedNode* getPredecessor() const { return Pred; } 4631eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 464d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis BlockCounter getBlockCounter() const { 465031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu return Eng.WList->getBlockCounter(); 466031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu } 4671eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 46811062b118476368fa5b294954713e5df97d8599fTed Kremenek unsigned getCurrentBlockCount() const { 469d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu return getBlockCounter().getNumVisited( 470d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu Pred->getLocationContext()->getCurrentStackFrame(), 471d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu B.getBlockID()); 4721eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump } 4731eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 474031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu ExplodedNode* generateNode(const GRState* State, const void *tag = 0, 475031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu ExplodedNode *P = 0); 4761eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 477102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor void GenerateCallExitNode(const GRState *state); 478102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 47903509aea098772644bf4662dc1c88634818ceeccZhongxing Xu const CFGBlock* getBlock() const { return &B; } 48011062b118476368fa5b294954713e5df97d8599fTed Kremenek 481031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu const GRState* getState() const { 48211062b118476368fa5b294954713e5df97d8599fTed Kremenek return getPredecessor()->getState(); 48311062b118476368fa5b294954713e5df97d8599fTed Kremenek } 48411062b118476368fa5b294954713e5df97d8599fTed Kremenek}; 485754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek 486d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidisclass CallEnterNodeBuilder { 487d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis CoreEngine &Eng; 488102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 489102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor const ExplodedNode *Pred; 490102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 49119b78d9e3dbbc27bbcbdd8c3017a00fe88849ecdZhongxing Xu // The call site. For implicit automatic object dtor, this is the trigger 49219b78d9e3dbbc27bbcbdd8c3017a00fe88849ecdZhongxing Xu // statement. 493102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor const Stmt *CE; 494102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 49519b78d9e3dbbc27bbcbdd8c3017a00fe88849ecdZhongxing Xu // The context of the callee. 49619b78d9e3dbbc27bbcbdd8c3017a00fe88849ecdZhongxing Xu const StackFrameContext *CalleeCtx; 497102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 498102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor // The parent block of the CallExpr. 499102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor const CFGBlock *Block; 500102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 501102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor // The CFGBlock index of the CallExpr. 502102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor unsigned Index; 503102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 504102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregorpublic: 505d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis CallEnterNodeBuilder(CoreEngine &eng, const ExplodedNode *pred, 50619b78d9e3dbbc27bbcbdd8c3017a00fe88849ecdZhongxing Xu const Stmt *s, const StackFrameContext *callee, 507102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor const CFGBlock *blk, unsigned idx) 508c6238d2786cfd961b94580b3d3675a1b3ff0721cZhongxing Xu : Eng(eng), Pred(pred), CE(s), CalleeCtx(callee), Block(blk), Index(idx) {} 509102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 510102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor const GRState *getState() const { return Pred->getState(); } 511102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 512102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor const LocationContext *getLocationContext() const { 513102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor return Pred->getLocationContext(); 514102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor } 515102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 516102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor const Stmt *getCallExpr() const { return CE; } 517102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 51819b78d9e3dbbc27bbcbdd8c3017a00fe88849ecdZhongxing Xu const StackFrameContext *getCalleeContext() const { return CalleeCtx; } 519102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 520102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor const CFGBlock *getBlock() const { return Block; } 521102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 522102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor unsigned getIndex() const { return Index; } 523102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 524d048c6ef5b6cfaa0cecb8cc1d4bdace32ed21d07Ted Kremenek void generateNode(const GRState *state); 525102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor}; 526102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 527d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidisclass CallExitNodeBuilder { 528d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis CoreEngine &Eng; 529102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor const ExplodedNode *Pred; 530102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 531102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregorpublic: 532d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis CallExitNodeBuilder(CoreEngine &eng, const ExplodedNode *pred) 533102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor : Eng(eng), Pred(pred) {} 534102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 535102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor const ExplodedNode *getPredecessor() const { return Pred; } 536102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 537102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor const GRState *getState() const { return Pred->getState(); } 538102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 539d048c6ef5b6cfaa0cecb8cc1d4bdace32ed21d07Ted Kremenek void generateNode(const GRState *state); 540102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor}; 5415a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis 5425a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis} // end GR namespace 5435a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis 544f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek} // end clang namespace 545f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek 546f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek#endif 547