CoreEngine.h revision fc8f0e14ad142ed811e90fbd9a30e419e301c717
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*> > 5066750fa464ace9f8c41666c8585ec71a248c1ccaTed Kremenek BlocksExhausted; 51422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek 52422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek typedef std::vector<std::pair<const CFGBlock*, const ExplodedNode*> > 53422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek BlocksAborted; 54422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek 55a7a8a450d908b34fa5f569f2e694ebd4b61aae2fTom Careprivate: 56a7a8a450d908b34fa5f569f2e694ebd4b61aae2fTom Care 57d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis SubEngine& SubEng; 580111f575b968e423dccae439e501225b8314b257Zhongxing Xu 59f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek /// G - The simulation graph. Each node is a (location,state) pair. 6038b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu llvm::OwningPtr<ExplodedGraph> G; 611eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 62f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek /// WList - A set of queued nodes that need to be processed by the 63f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek /// worklist algorithm. It is up to the implementation of WList to decide 64f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek /// the order that nodes are processed. 65d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis WorkList* WList; 661eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 67d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis /// BCounterFactory - A factory object for created BlockCounter objects. 688e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek /// These are used to record for key nodes in the ExplodedGraph the 698e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek /// number of times different CFGBlocks have been visited along a path. 70d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis BlockCounter::Factory BCounterFactory; 71f598087b4adfea164acdd5b53ea2951bde740a2dTed Kremenek 72f598087b4adfea164acdd5b53ea2951bde740a2dTed Kremenek /// The locations where we stopped doing work because we visited a location 73f598087b4adfea164acdd5b53ea2951bde740a2dTed Kremenek /// too many times. 7466750fa464ace9f8c41666c8585ec71a248c1ccaTed Kremenek BlocksExhausted blocksExhausted; 75422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek 76422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek /// The locations where we stopped because the engine aborted analysis, 77422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek /// usually because it could not reason about something. 78422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek BlocksAborted blocksAborted; 791eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 80d048c6ef5b6cfaa0cecb8cc1d4bdace32ed21d07Ted Kremenek void generateNode(const ProgramPoint& Loc, const GRState* State, 81c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu ExplodedNode* Pred); 821eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 83c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu void HandleBlockEdge(const BlockEdge& E, ExplodedNode* Pred); 84c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu void HandleBlockEntrance(const BlockEntrance& E, ExplodedNode* Pred); 8503509aea098772644bf4662dc1c88634818ceeccZhongxing Xu void HandleBlockExit(const CFGBlock* B, ExplodedNode* Pred); 869dc84c9455df2a77195147d0210c915dc1775a88Zhongxing Xu void HandlePostStmt(const CFGBlock* B, unsigned StmtIdx, ExplodedNode *Pred); 871eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 8803509aea098772644bf4662dc1c88634818ceeccZhongxing Xu void HandleBranch(const Stmt* Cond, const Stmt* Term, const CFGBlock* B, 891eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump ExplodedNode* Pred); 90102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor void HandleCallEnter(const CallEnter &L, const CFGBlock *Block, 91102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor unsigned Index, ExplodedNode *Pred); 92102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor void HandleCallExit(const CallExit &L, ExplodedNode *Pred); 930111f575b968e423dccae439e501225b8314b257Zhongxing Xu 94f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenekprivate: 95d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis CoreEngine(const CoreEngine&); // Do not implement. 96d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis CoreEngine& operator=(const CoreEngine&); 971eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 98f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenekpublic: 99d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis /// Construct a CoreEngine object to analyze the provided CFG using 1000111f575b968e423dccae439e501225b8314b257Zhongxing Xu /// a DFS exploration of the exploded graph. 101d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis CoreEngine(SubEngine& subengine) 102d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis : SubEng(subengine), G(new ExplodedGraph()), 10355825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek WList(WorkList::makeBFS()), 104f598087b4adfea164acdd5b53ea2951bde740a2dTed Kremenek BCounterFactory(G->getAllocator()) {} 1050111f575b968e423dccae439e501225b8314b257Zhongxing Xu 106d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis /// Construct a CoreEngine object to analyze the provided CFG and to 1070111f575b968e423dccae439e501225b8314b257Zhongxing Xu /// use the provided worklist object to execute the worklist algorithm. 108d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis /// The CoreEngine object assumes ownership of 'wlist'. 109d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis CoreEngine(WorkList* wlist, SubEngine& subengine) 110d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis : SubEng(subengine), G(new ExplodedGraph()), WList(wlist), 111f598087b4adfea164acdd5b53ea2951bde740a2dTed Kremenek BCounterFactory(G->getAllocator()) {} 1120111f575b968e423dccae439e501225b8314b257Zhongxing Xu 113d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis ~CoreEngine() { 1140111f575b968e423dccae439e501225b8314b257Zhongxing Xu delete WList; 1150111f575b968e423dccae439e501225b8314b257Zhongxing Xu } 1160111f575b968e423dccae439e501225b8314b257Zhongxing Xu 1170111f575b968e423dccae439e501225b8314b257Zhongxing Xu /// getGraph - Returns the exploded graph. 118031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu ExplodedGraph& getGraph() { return *G.get(); } 1191eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1200111f575b968e423dccae439e501225b8314b257Zhongxing Xu /// takeGraph - Returns the exploded graph. Ownership of the graph is 121fc8f0e14ad142ed811e90fbd9a30e419e301c717Chris Lattner /// transferred to the caller. 122031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu ExplodedGraph* takeGraph() { return G.take(); } 1230111f575b968e423dccae439e501225b8314b257Zhongxing Xu 124f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek /// ExecuteWorkList - Run the worklist algorithm for a maximum number of 125f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek /// steps. Returns true if there is still simulation state on the worklist. 1262ce43c8f43254a9edea53a20dc0e69195bc82ae0Zhongxing Xu bool ExecuteWorkList(const LocationContext *L, unsigned Steps, 1272ce43c8f43254a9edea53a20dc0e69195bc82ae0Zhongxing Xu const GRState *InitState); 1282ce43c8f43254a9edea53a20dc0e69195bc82ae0Zhongxing Xu void ExecuteWorkListWithInitialState(const LocationContext *L, unsigned Steps, 1292ce43c8f43254a9edea53a20dc0e69195bc82ae0Zhongxing Xu const GRState *InitState, 1302ce43c8f43254a9edea53a20dc0e69195bc82ae0Zhongxing Xu ExplodedNodeSet &Dst); 131bc42c533e7d3d946704a49e242939dd232f33072Tom Care 132bc42c533e7d3d946704a49e242939dd232f33072Tom Care // Functions for external checking of whether we have unfinished work 133422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek bool wasBlockAborted() const { return !blocksAborted.empty(); } 134422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek bool wasBlocksExhausted() const { return !blocksExhausted.empty(); } 135422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek bool hasWorkRemaining() const { return wasBlocksExhausted() || 136422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek WList->hasWork() || 137422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek wasBlockAborted(); } 138422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek 139422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek /// Inform the CoreEngine that a basic block was aborted because 140422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek /// it could not be completely analyzed. 141422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek void addAbortedBlock(const ExplodedNode *node, const CFGBlock *block) { 142422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek blocksAborted.push_back(std::make_pair(block, node)); 143422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek } 144422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek 145d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis WorkList *getWorkList() const { return WList; } 146f598087b4adfea164acdd5b53ea2951bde740a2dTed Kremenek 147422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek BlocksExhausted::const_iterator blocks_exhausted_begin() const { 14866750fa464ace9f8c41666c8585ec71a248c1ccaTed Kremenek return blocksExhausted.begin(); 149f598087b4adfea164acdd5b53ea2951bde740a2dTed Kremenek } 150422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek BlocksExhausted::const_iterator blocks_exhausted_end() const { 15166750fa464ace9f8c41666c8585ec71a248c1ccaTed Kremenek return blocksExhausted.end(); 152f598087b4adfea164acdd5b53ea2951bde740a2dTed Kremenek } 153422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek BlocksAborted::const_iterator blocks_aborted_begin() const { 154422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek return blocksAborted.begin(); 155422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek } 156422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek BlocksAborted::const_iterator blocks_aborted_end() const { 157422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek return blocksAborted.end(); 158422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek } 159f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek}; 1601eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 161d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidisclass StmtNodeBuilder { 162d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis CoreEngine& Eng; 16303509aea098772644bf4662dc1c88634818ceeccZhongxing Xu const CFGBlock& B; 164f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek const unsigned Idx; 165c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu ExplodedNode* Pred; 166031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu GRStateManager& Mgr; 167031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu 168031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xupublic: 169031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu bool PurgingDeadSymbols; 170031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu bool BuildSinks; 171b4857264b8d3d861f688cdaa174aab30e0729a73Ted Kremenek bool hasGeneratedNode; 172031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu ProgramPoint::Kind PointKind; 173031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu const void *Tag; 1741eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1751eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump const GRState* CleanedState; 1761eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 177031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu 178c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu typedef llvm::SmallPtrSet<ExplodedNode*,5> DeferredTy; 179f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek DeferredTy Deferred; 1801eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 181c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu void GenerateAutoTransition(ExplodedNode* N); 1821eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 183f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenekpublic: 184d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis StmtNodeBuilder(const CFGBlock* b, unsigned idx, ExplodedNode* N, 185d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis CoreEngine* e, GRStateManager &mgr); 1861eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 187d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis ~StmtNodeBuilder(); 1881eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 189b4857264b8d3d861f688cdaa174aab30e0729a73Ted Kremenek ExplodedNode* getPredecessor() const { return Pred; } 1901eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 191798d2ca60d1cd6de70d28a5ce60337a2b03a663fZhongxing Xu // FIXME: This should not be exposed. 192d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis WorkList *getWorkList() { return Eng.WList; } 193798d2ca60d1cd6de70d28a5ce60337a2b03a663fZhongxing Xu 194031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu void SetCleanedState(const GRState* St) { 195031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu CleanedState = St; 196031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu } 197031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu 198d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis BlockCounter getBlockCounter() const { return Eng.WList->getBlockCounter();} 1991eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 20000a3a5f024ac54088ab887712b292171188064f0Ted Kremenek unsigned getCurrentBlockCount() const { 201d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu return getBlockCounter().getNumVisited( 202d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu Pred->getLocationContext()->getCurrentStackFrame(), 203d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu B.getBlockID()); 2041eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump } 205031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu 206031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu ExplodedNode* generateNode(PostStmt PP,const GRState* St,ExplodedNode* Pred) { 207b4857264b8d3d861f688cdaa174aab30e0729a73Ted Kremenek hasGeneratedNode = true; 208031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu return generateNodeInternal(PP, St, Pred); 209031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu } 2101eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 211e1ccccff777f6bad6b25e9c6a762f98fd8003181Ted Kremenek ExplodedNode* generateNode(const Stmt *S, const GRState *St, 2124bac726dadb09ee38bab8147f1e706380368b362Ted Kremenek ExplodedNode *Pred, ProgramPoint::Kind K, 2134bac726dadb09ee38bab8147f1e706380368b362Ted Kremenek const void *tag = 0) { 214b4857264b8d3d861f688cdaa174aab30e0729a73Ted Kremenek hasGeneratedNode = true; 215031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu 2161eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump if (PurgingDeadSymbols) 2171eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump K = ProgramPoint::PostPurgeDeadSymbolsKind; 218031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu 2194bac726dadb09ee38bab8147f1e706380368b362Ted Kremenek return generateNodeInternal(S, St, Pred, K, tag ? tag : Tag); 220031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu } 2211eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 222e1ccccff777f6bad6b25e9c6a762f98fd8003181Ted Kremenek ExplodedNode* generateNode(const Stmt *S, const GRState *St, 2234bac726dadb09ee38bab8147f1e706380368b362Ted Kremenek ExplodedNode *Pred, const void *tag = 0) { 2244bac726dadb09ee38bab8147f1e706380368b362Ted Kremenek return generateNode(S, St, Pred, PointKind, tag); 225031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu } 226031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu 227102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor ExplodedNode *generateNode(const ProgramPoint &PP, const GRState* State, 228102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor ExplodedNode* Pred) { 229b4857264b8d3d861f688cdaa174aab30e0729a73Ted Kremenek hasGeneratedNode = true; 230102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor return generateNodeInternal(PP, State, Pred); 231102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor } 232102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 233c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu ExplodedNode* 234031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu generateNodeInternal(const ProgramPoint &PP, const GRState* State, 235031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu ExplodedNode* Pred); 2361eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 237c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu ExplodedNode* 238031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu generateNodeInternal(const Stmt* S, const GRState* State, ExplodedNode* Pred, 2391670e403c48f3af4fceff3f6773a0e1cfc6c4eb3Ted Kremenek ProgramPoint::Kind K = ProgramPoint::PostStmtKind, 2401670e403c48f3af4fceff3f6773a0e1cfc6c4eb3Ted Kremenek const void *tag = 0); 2411eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 242331b0ac44b9eb0ffcba66b4f3f3f9adb27c2434fTed Kremenek /// getStmt - Return the current block-level expression associated with 243331b0ac44b9eb0ffcba66b4f3f3f9adb27c2434fTed Kremenek /// this builder. 244b36cd3e1757fb4fcd9509f35558c847b04bef35fZhongxing Xu const Stmt* getStmt() const { 2453c0349e87cdbd7316d06d2411d86ee1086e717a5Ted Kremenek const CFGStmt *CS = B[Idx].getAs<CFGStmt>(); 2463c0349e87cdbd7316d06d2411d86ee1086e717a5Ted Kremenek return CS ? CS->getStmt() : 0; 247b36cd3e1757fb4fcd9509f35558c847b04bef35fZhongxing Xu } 2481eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 249331b0ac44b9eb0ffcba66b4f3f3f9adb27c2434fTed Kremenek /// getBlock - Return the CFGBlock associated with the block-level expression 250331b0ac44b9eb0ffcba66b4f3f3f9adb27c2434fTed Kremenek /// of this builder. 25103509aea098772644bf4662dc1c88634818ceeccZhongxing Xu const CFGBlock* getBlock() const { return &B; } 252bdb435ddaafd5069becd543d638112f68825b89dTed Kremenek 253598278bee8e5797bc73d24d6ac8a1d6ff6413caeZhongxing Xu unsigned getIndex() const { return Idx; } 254598278bee8e5797bc73d24d6ac8a1d6ff6413caeZhongxing Xu 255031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu const GRState* GetState(ExplodedNode* Pred) const { 256b4857264b8d3d861f688cdaa174aab30e0729a73Ted Kremenek if (Pred == getPredecessor()) 2573bbad550be7edc628be31b51d2a51b6d7d46eafbTed Kremenek return CleanedState; 2583bbad550be7edc628be31b51d2a51b6d7d46eafbTed Kremenek else 2593bbad550be7edc628be31b51d2a51b6d7d46eafbTed Kremenek return Pred->getState(); 2603bbad550be7edc628be31b51d2a51b6d7d46eafbTed Kremenek } 261031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu 2623992a50eea030a2913f1d267554f55ecd00d694cZhongxing Xu ExplodedNode* MakeNode(ExplodedNodeSet& Dst, const Stmt* S, 2633992a50eea030a2913f1d267554f55ecd00d694cZhongxing Xu ExplodedNode* Pred, const GRState* St) { 264bf4e419d996bf42e4933cada610d973a0fcc40ebTed Kremenek return MakeNode(Dst, S, Pred, St, PointKind); 265bf4e419d996bf42e4933cada610d973a0fcc40ebTed Kremenek } 2661eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 2673992a50eea030a2913f1d267554f55ecd00d694cZhongxing Xu ExplodedNode* MakeNode(ExplodedNodeSet& Dst, const Stmt* S,ExplodedNode* Pred, 268868e78d59d2dfaf9cda511925e5a58f3a712db96Zhongxing Xu const GRState* St, ProgramPoint::Kind K); 2691eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 2703992a50eea030a2913f1d267554f55ecd00d694cZhongxing Xu ExplodedNode* MakeSinkNode(ExplodedNodeSet& Dst, const Stmt* S, 2711eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump ExplodedNode* Pred, const GRState* St) { 27270a733e64e2379a654631a14fa29e46761d5f80dTed Kremenek bool Tmp = BuildSinks; 27370a733e64e2379a654631a14fa29e46761d5f80dTed Kremenek BuildSinks = true; 274031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu ExplodedNode* N = MakeNode(Dst, S, Pred, St); 27570a733e64e2379a654631a14fa29e46761d5f80dTed Kremenek BuildSinks = Tmp; 27670a733e64e2379a654631a14fa29e46761d5f80dTed Kremenek return N; 27770a733e64e2379a654631a14fa29e46761d5f80dTed Kremenek } 278f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek}; 2791eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 280d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidisclass BranchNodeBuilder { 281d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis CoreEngine& Eng; 28203509aea098772644bf4662dc1c88634818ceeccZhongxing Xu const CFGBlock* Src; 28303509aea098772644bf4662dc1c88634818ceeccZhongxing Xu const CFGBlock* DstT; 28403509aea098772644bf4662dc1c88634818ceeccZhongxing Xu const CFGBlock* DstF; 285c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu ExplodedNode* Pred; 28652a16499df87730c0252b431abdf2b2e32d756a6Ted Kremenek 287c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu typedef llvm::SmallVector<ExplodedNode*,3> DeferredTy; 2883b4f6702860208692f6ef28401e68de4e3ff9af9Ted Kremenek DeferredTy Deferred; 2891eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 29071c29bdc931bc49644c581ec7d698f0dbf01a0aaTed Kremenek bool GeneratedTrue; 29171c29bdc931bc49644c581ec7d698f0dbf01a0aaTed Kremenek bool GeneratedFalse; 292520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek bool InFeasibleTrue; 293520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek bool InFeasibleFalse; 2941eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 2957d7fe6d539b3bdb1701835223cca306c325614a7Ted Kremenekpublic: 296d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis BranchNodeBuilder(const CFGBlock* src, const CFGBlock* dstT, 297d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis const CFGBlock* dstF, ExplodedNode* pred, CoreEngine* e) 29871c29bdc931bc49644c581ec7d698f0dbf01a0aaTed Kremenek : Eng(*e), Src(src), DstT(dstT), DstF(dstF), Pred(pred), 299520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek GeneratedTrue(false), GeneratedFalse(false), 300520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek InFeasibleTrue(!DstT), InFeasibleFalse(!DstF) {} 3011eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 302d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis ~BranchNodeBuilder(); 3031eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 304c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu ExplodedNode* getPredecessor() const { return Pred; } 305031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu 30638b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu const ExplodedGraph& getGraph() const { return *Eng.G; } 307031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu 308d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis BlockCounter getBlockCounter() const { return Eng.WList->getBlockCounter();} 3091eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3108083414ee7cc8f5c807ed6a4e120fb4e0ab50ff8Ted Kremenek ExplodedNode* generateNode(const Stmt *Condition, const GRState* State); 3118083414ee7cc8f5c807ed6a4e120fb4e0ab50ff8Ted Kremenek 312031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu ExplodedNode* generateNode(const GRState* State, bool branch); 3131eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 31403509aea098772644bf4662dc1c88634818ceeccZhongxing Xu const CFGBlock* getTargetBlock(bool branch) const { 3158e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek return branch ? DstT : DstF; 3161eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump } 3171eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 31852a16499df87730c0252b431abdf2b2e32d756a6Ted Kremenek void markInfeasible(bool branch) { 319520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek if (branch) 320520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek InFeasibleTrue = GeneratedTrue = true; 321520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek else 322520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek InFeasibleFalse = GeneratedFalse = true; 323520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek } 3241eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 325520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek bool isFeasible(bool branch) { 326520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek return branch ? !InFeasibleTrue : !InFeasibleFalse; 32752a16499df87730c0252b431abdf2b2e32d756a6Ted Kremenek } 3281eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 329031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu const GRState* getState() const { 330b38911f16b4943548db6a3695fc6ae23070b25d2Ted Kremenek return getPredecessor()->getState(); 331b38911f16b4943548db6a3695fc6ae23070b25d2Ted Kremenek } 3327d7fe6d539b3bdb1701835223cca306c325614a7Ted Kremenek}; 333031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu 334d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidisclass IndirectGotoNodeBuilder { 335d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis CoreEngine& Eng; 33603509aea098772644bf4662dc1c88634818ceeccZhongxing Xu const CFGBlock* Src; 33703509aea098772644bf4662dc1c88634818ceeccZhongxing Xu const CFGBlock& DispatchBlock; 33803509aea098772644bf4662dc1c88634818ceeccZhongxing Xu const Expr* E; 3391eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump ExplodedNode* Pred; 340031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu 341754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenekpublic: 342d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis IndirectGotoNodeBuilder(ExplodedNode* pred, const CFGBlock* src, 343d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis const Expr* e, const CFGBlock* dispatch, CoreEngine* eng) 34403509aea098772644bf4662dc1c88634818ceeccZhongxing Xu : Eng(*eng), Src(src), DispatchBlock(*dispatch), E(e), Pred(pred) {} 345754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek 346031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu class iterator { 34703509aea098772644bf4662dc1c88634818ceeccZhongxing Xu CFGBlock::const_succ_iterator I; 3481eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 349d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis friend class IndirectGotoNodeBuilder; 35003509aea098772644bf4662dc1c88634818ceeccZhongxing Xu iterator(CFGBlock::const_succ_iterator i) : I(i) {} 351754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek public: 3521eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 353031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu iterator& operator++() { ++I; return *this; } 354031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu bool operator!=(const iterator& X) const { return I != X.I; } 3551eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 356ad8dcf4a9df0e24051dc31bf9e6f3cd138a34298Chris Lattner const LabelDecl *getLabel() const { 357ad8dcf4a9df0e24051dc31bf9e6f3cd138a34298Chris Lattner return llvm::cast<LabelStmt>((*I)->getLabel())->getDecl(); 35824f1a967741ff9f8025ee23be12ba6feacc31f77Ted Kremenek } 3591eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 360ad8dcf4a9df0e24051dc31bf9e6f3cd138a34298Chris Lattner const CFGBlock *getBlock() const { 36124f1a967741ff9f8025ee23be12ba6feacc31f77Ted Kremenek return *I; 36224f1a967741ff9f8025ee23be12ba6feacc31f77Ted Kremenek } 363754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek }; 3641eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 365031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu iterator begin() { return iterator(DispatchBlock.succ_begin()); } 366031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu iterator end() { return iterator(DispatchBlock.succ_end()); } 3671eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 368031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu ExplodedNode* generateNode(const iterator& I, const GRState* State, 369031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu bool isSink = false); 3701eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 37103509aea098772644bf4662dc1c88634818ceeccZhongxing Xu const Expr* getTarget() const { return E; } 372754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek 373031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu const GRState* getState() const { return Pred->State; } 374754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek}; 3751eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 376d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidisclass SwitchNodeBuilder { 377d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis CoreEngine& Eng; 37803509aea098772644bf4662dc1c88634818ceeccZhongxing Xu const CFGBlock* Src; 37903509aea098772644bf4662dc1c88634818ceeccZhongxing Xu const Expr* Condition; 3801eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump ExplodedNode* Pred; 381031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu 382daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenekpublic: 383d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis SwitchNodeBuilder(ExplodedNode* pred, const CFGBlock* src, 384d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis const Expr* condition, CoreEngine* eng) 385daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek : Eng(*eng), Src(src), Condition(condition), Pred(pred) {} 3861eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 387031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu class iterator { 38803509aea098772644bf4662dc1c88634818ceeccZhongxing Xu CFGBlock::const_succ_reverse_iterator I; 3891eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 390d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis friend class SwitchNodeBuilder; 39103509aea098772644bf4662dc1c88634818ceeccZhongxing Xu iterator(CFGBlock::const_succ_reverse_iterator i) : I(i) {} 392031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu 393daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek public: 394031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu iterator& operator++() { ++I; return *this; } 39534feff654c6304e0a59ceb1376989d28dbc956ffTed Kremenek bool operator!=(const iterator &X) const { return I != X.I; } 39634feff654c6304e0a59ceb1376989d28dbc956ffTed Kremenek bool operator==(const iterator &X) const { return I == X.I; } 3971eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 39803509aea098772644bf4662dc1c88634818ceeccZhongxing Xu const CaseStmt* getCase() const { 399daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek return llvm::cast<CaseStmt>((*I)->getLabel()); 400daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek } 4011eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 40203509aea098772644bf4662dc1c88634818ceeccZhongxing Xu const CFGBlock* getBlock() const { 403daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek return *I; 404daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek } 405daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek }; 4061eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 407031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu iterator begin() { return iterator(Src->succ_rbegin()+1); } 408031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu iterator end() { return iterator(Src->succ_rend()); } 4091eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4104d3175c1e5a44251ea97b0c81e80f060629d9c08Ted Kremenek const SwitchStmt *getSwitch() const { 4114d3175c1e5a44251ea97b0c81e80f060629d9c08Ted Kremenek return llvm::cast<SwitchStmt>(Src->getTerminator()); 4124d3175c1e5a44251ea97b0c81e80f060629d9c08Ted Kremenek } 4134d3175c1e5a44251ea97b0c81e80f060629d9c08Ted Kremenek 414031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu ExplodedNode* generateCaseStmtNode(const iterator& I, const GRState* State); 4151eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 416031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu ExplodedNode* generateDefaultCaseNode(const GRState* State, 417031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu bool isSink = false); 4181eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 41903509aea098772644bf4662dc1c88634818ceeccZhongxing Xu const Expr* getCondition() const { return Condition; } 420daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek 421031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu const GRState* getState() const { return Pred->State; } 422daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek}; 42311062b118476368fa5b294954713e5df97d8599fTed Kremenek 42427c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenekclass GenericNodeBuilderImpl { 42527c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenekprotected: 42627c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek CoreEngine &engine; 42727c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek ExplodedNode *pred; 42827c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek ProgramPoint pp; 42927c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek llvm::SmallVector<ExplodedNode*, 2> sinksGenerated; 43027c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek 43127c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek ExplodedNode *generateNodeImpl(const GRState *state, ExplodedNode *pred, 43227c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek ProgramPoint programPoint, bool asSink); 43327c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek 43427c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek GenericNodeBuilderImpl(CoreEngine &eng, ExplodedNode *pr, ProgramPoint p) 435b4857264b8d3d861f688cdaa174aab30e0729a73Ted Kremenek : engine(eng), pred(pr), pp(p), hasGeneratedNode(false) {} 43627c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek 43727c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenekpublic: 438b4857264b8d3d861f688cdaa174aab30e0729a73Ted Kremenek bool hasGeneratedNode; 43927c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek 44027c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek WorkList &getWorkList() { return *engine.WList; } 44127c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek 44227c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek ExplodedNode* getPredecessor() const { return pred; } 44327c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek 44427c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek BlockCounter getBlockCounter() const { 44527c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek return engine.WList->getBlockCounter(); 44627c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek } 44727c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek 44827c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek const llvm::SmallVectorImpl<ExplodedNode*> &sinks() const { 44927c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek return sinksGenerated; 45027c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek } 45127c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek}; 45227c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek 453b6a2b08a6b3fbce1a6a4b69d4185165de970696cTed Kremenektemplate <typename PP_T> 45427c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenekclass GenericNodeBuilder : public GenericNodeBuilderImpl { 45527c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenekpublic: 456b6a2b08a6b3fbce1a6a4b69d4185165de970696cTed Kremenek GenericNodeBuilder(CoreEngine &eng, ExplodedNode *pr, const PP_T &p) 45727c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek : GenericNodeBuilderImpl(eng, pr, p) {} 45827c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek 45927c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek ExplodedNode *generateNode(const GRState *state, ExplodedNode *pred, 460b6a2b08a6b3fbce1a6a4b69d4185165de970696cTed Kremenek const void *tag, bool asSink) { 461b6a2b08a6b3fbce1a6a4b69d4185165de970696cTed Kremenek return generateNodeImpl(state, pred, cast<PP_T>(pp).withTag(tag), 462b6a2b08a6b3fbce1a6a4b69d4185165de970696cTed Kremenek asSink); 46327c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek } 46427c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek 465b6a2b08a6b3fbce1a6a4b69d4185165de970696cTed Kremenek const PP_T &getProgramPoint() const { return cast<PP_T>(pp); } 46627c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek}; 46727c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek 468e36de1fe51c39d9161915dd3dbef880954af6476Ted Kremenekclass EndOfFunctionNodeBuilder { 469d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis CoreEngine &Eng; 47003509aea098772644bf4662dc1c88634818ceeccZhongxing Xu const CFGBlock& B; 4711eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump ExplodedNode* Pred; 472f178ac8b68b29e44867777232ba8fee59edc4037Argyrios Kyrtzidis void *Tag; 473f605aae3227ffa3a5dae8eb34fdd79ba0a0d19d1Zhongxing Xu 474f605aae3227ffa3a5dae8eb34fdd79ba0a0d19d1Zhongxing Xupublic: 475b4857264b8d3d861f688cdaa174aab30e0729a73Ted Kremenek bool hasGeneratedNode; 4761eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 47711062b118476368fa5b294954713e5df97d8599fTed Kremenekpublic: 478f178ac8b68b29e44867777232ba8fee59edc4037Argyrios Kyrtzidis EndOfFunctionNodeBuilder(const CFGBlock* b, ExplodedNode* N, CoreEngine* e, 479f178ac8b68b29e44867777232ba8fee59edc4037Argyrios Kyrtzidis void *checkerTag = 0) 480f178ac8b68b29e44867777232ba8fee59edc4037Argyrios Kyrtzidis : Eng(*e), B(*b), Pred(N), Tag(checkerTag), hasGeneratedNode(false) {} 4811eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 482e36de1fe51c39d9161915dd3dbef880954af6476Ted Kremenek ~EndOfFunctionNodeBuilder(); 4831eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 484f178ac8b68b29e44867777232ba8fee59edc4037Argyrios Kyrtzidis EndOfFunctionNodeBuilder withCheckerTag(void *tag) { 485f178ac8b68b29e44867777232ba8fee59edc4037Argyrios Kyrtzidis return EndOfFunctionNodeBuilder(&B, Pred, &Eng, tag); 486f178ac8b68b29e44867777232ba8fee59edc4037Argyrios Kyrtzidis } 487f178ac8b68b29e44867777232ba8fee59edc4037Argyrios Kyrtzidis 488d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis WorkList &getWorkList() { return *Eng.WList; } 489598278bee8e5797bc73d24d6ac8a1d6ff6413caeZhongxing Xu 490c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu ExplodedNode* getPredecessor() const { return Pred; } 4911eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 492d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis BlockCounter getBlockCounter() const { 493031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu return Eng.WList->getBlockCounter(); 494031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu } 4951eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 49611062b118476368fa5b294954713e5df97d8599fTed Kremenek unsigned getCurrentBlockCount() const { 497d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu return getBlockCounter().getNumVisited( 498d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu Pred->getLocationContext()->getCurrentStackFrame(), 499d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu B.getBlockID()); 5001eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump } 5011eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 502f178ac8b68b29e44867777232ba8fee59edc4037Argyrios Kyrtzidis ExplodedNode* generateNode(const GRState* State, ExplodedNode *P = 0, 503f178ac8b68b29e44867777232ba8fee59edc4037Argyrios Kyrtzidis const void *tag = 0); 5041eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 505102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor void GenerateCallExitNode(const GRState *state); 506102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 50703509aea098772644bf4662dc1c88634818ceeccZhongxing Xu const CFGBlock* getBlock() const { return &B; } 50811062b118476368fa5b294954713e5df97d8599fTed Kremenek 509031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu const GRState* getState() const { 51011062b118476368fa5b294954713e5df97d8599fTed Kremenek return getPredecessor()->getState(); 51111062b118476368fa5b294954713e5df97d8599fTed Kremenek } 51211062b118476368fa5b294954713e5df97d8599fTed Kremenek}; 513754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek 514d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidisclass CallEnterNodeBuilder { 515d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis CoreEngine &Eng; 516102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 517102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor const ExplodedNode *Pred; 518102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 51919b78d9e3dbbc27bbcbdd8c3017a00fe88849ecdZhongxing Xu // The call site. For implicit automatic object dtor, this is the trigger 52019b78d9e3dbbc27bbcbdd8c3017a00fe88849ecdZhongxing Xu // statement. 521102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor const Stmt *CE; 522102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 52319b78d9e3dbbc27bbcbdd8c3017a00fe88849ecdZhongxing Xu // The context of the callee. 52419b78d9e3dbbc27bbcbdd8c3017a00fe88849ecdZhongxing Xu const StackFrameContext *CalleeCtx; 525102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 526102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor // The parent block of the CallExpr. 527102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor const CFGBlock *Block; 528102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 529102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor // The CFGBlock index of the CallExpr. 530102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor unsigned Index; 531102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 532102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregorpublic: 533d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis CallEnterNodeBuilder(CoreEngine &eng, const ExplodedNode *pred, 53419b78d9e3dbbc27bbcbdd8c3017a00fe88849ecdZhongxing Xu const Stmt *s, const StackFrameContext *callee, 535102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor const CFGBlock *blk, unsigned idx) 536c6238d2786cfd961b94580b3d3675a1b3ff0721cZhongxing Xu : Eng(eng), Pred(pred), CE(s), CalleeCtx(callee), Block(blk), Index(idx) {} 537102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 538102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor const GRState *getState() const { return Pred->getState(); } 539102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 540102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor const LocationContext *getLocationContext() const { 541102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor return Pred->getLocationContext(); 542102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor } 543102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 544102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor const Stmt *getCallExpr() const { return CE; } 545102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 54619b78d9e3dbbc27bbcbdd8c3017a00fe88849ecdZhongxing Xu const StackFrameContext *getCalleeContext() const { return CalleeCtx; } 547102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 548102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor const CFGBlock *getBlock() const { return Block; } 549102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 550102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor unsigned getIndex() const { return Index; } 551102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 552d048c6ef5b6cfaa0cecb8cc1d4bdace32ed21d07Ted Kremenek void generateNode(const GRState *state); 553102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor}; 554102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 555d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidisclass CallExitNodeBuilder { 556d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis CoreEngine &Eng; 557102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor const ExplodedNode *Pred; 558102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 559102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregorpublic: 560d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis CallExitNodeBuilder(CoreEngine &eng, const ExplodedNode *pred) 561102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor : Eng(eng), Pred(pred) {} 562102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 563102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor const ExplodedNode *getPredecessor() const { return Pred; } 564102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 565102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor const GRState *getState() const { return Pred->getState(); } 566102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 567d048c6ef5b6cfaa0cecb8cc1d4bdace32ed21d07Ted Kremenek void generateNode(const GRState *state); 568102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor}; 5695a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis 5705a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis} // end GR namespace 5715a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis 572f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek} // end clang namespace 573f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek 574f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek#endif 575