CoreEngine.h revision 18c66fdc3c4008d335885695fe36fb5353c5f672
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 27ca804539d908d3a0e8c72a0df5f1f571d29490bbTed Kremenekclass ProgramPointTag; 28ca804539d908d3a0e8c72a0df5f1f571d29490bbTed Kremenek 299ef6537a894c33003359b1f9b9676e9178e028b7Ted Kremeneknamespace ento { 305a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis 3124f1a967741ff9f8025ee23be12ba6feacc31f77Ted Kremenek//===----------------------------------------------------------------------===// 32d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis/// CoreEngine - Implements the core logic of the graph-reachability 33922059dec59c7bed235da01aff75ae522a369811Ted Kremenek/// analysis. It traverses the CFG and generates the ExplodedGraph. 34922059dec59c7bed235da01aff75ae522a369811Ted Kremenek/// Program "states" are treated as opaque void pointers. 35d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis/// The template class CoreEngine (which subclasses CoreEngine) 36922059dec59c7bed235da01aff75ae522a369811Ted Kremenek/// provides the matching component to the engine that knows the actual types 37922059dec59c7bed235da01aff75ae522a369811Ted Kremenek/// for states. Note that this engine only dispatches to transfer functions 38922059dec59c7bed235da01aff75ae522a369811Ted Kremenek/// at the statement and block-level. The analyses themselves must implement 39922059dec59c7bed235da01aff75ae522a369811Ted Kremenek/// any transfer function logic and the sub-expression level (if any). 40d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidisclass CoreEngine { 41d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis friend class StmtNodeBuilder; 4227c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek friend class GenericNodeBuilderImpl; 43d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis friend class BranchNodeBuilder; 44d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis friend class IndirectGotoNodeBuilder; 45d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis friend class SwitchNodeBuilder; 46e36de1fe51c39d9161915dd3dbef880954af6476Ted Kremenek friend class EndOfFunctionNodeBuilder; 47d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis friend class CallEnterNodeBuilder; 48d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis friend class CallExitNodeBuilder; 490111f575b968e423dccae439e501225b8314b257Zhongxing Xu 50a7a8a450d908b34fa5f569f2e694ebd4b61aae2fTom Carepublic: 51a7a8a450d908b34fa5f569f2e694ebd4b61aae2fTom Care typedef std::vector<std::pair<BlockEdge, const ExplodedNode*> > 5266750fa464ace9f8c41666c8585ec71a248c1ccaTed Kremenek BlocksExhausted; 53422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek 54422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek typedef std::vector<std::pair<const CFGBlock*, const ExplodedNode*> > 55422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek BlocksAborted; 56422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek 57a7a8a450d908b34fa5f569f2e694ebd4b61aae2fTom Careprivate: 58a7a8a450d908b34fa5f569f2e694ebd4b61aae2fTom Care 59d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis SubEngine& SubEng; 600111f575b968e423dccae439e501225b8314b257Zhongxing Xu 61f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek /// G - The simulation graph. Each node is a (location,state) pair. 6238b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu llvm::OwningPtr<ExplodedGraph> G; 631eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 64f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek /// WList - A set of queued nodes that need to be processed by the 65f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek /// worklist algorithm. It is up to the implementation of WList to decide 66f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek /// the order that nodes are processed. 67d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis WorkList* WList; 681eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 69d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis /// BCounterFactory - A factory object for created BlockCounter objects. 708e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek /// These are used to record for key nodes in the ExplodedGraph the 718e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek /// number of times different CFGBlocks have been visited along a path. 72d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis BlockCounter::Factory BCounterFactory; 73f598087b4adfea164acdd5b53ea2951bde740a2dTed Kremenek 74f598087b4adfea164acdd5b53ea2951bde740a2dTed Kremenek /// The locations where we stopped doing work because we visited a location 75f598087b4adfea164acdd5b53ea2951bde740a2dTed Kremenek /// too many times. 7666750fa464ace9f8c41666c8585ec71a248c1ccaTed Kremenek BlocksExhausted blocksExhausted; 77422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek 78422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek /// The locations where we stopped because the engine aborted analysis, 79422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek /// usually because it could not reason about something. 80422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek BlocksAborted blocksAborted; 811eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 8218c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek void generateNode(const ProgramPoint &Loc, 8318c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const ProgramState *State, 849c378f705405d37f49795d5e915989de774fe11fTed Kremenek ExplodedNode *Pred); 851eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 869c378f705405d37f49795d5e915989de774fe11fTed Kremenek void HandleBlockEdge(const BlockEdge &E, ExplodedNode *Pred); 879c378f705405d37f49795d5e915989de774fe11fTed Kremenek void HandleBlockEntrance(const BlockEntrance &E, ExplodedNode *Pred); 889c378f705405d37f49795d5e915989de774fe11fTed Kremenek void HandleBlockExit(const CFGBlock *B, ExplodedNode *Pred); 899c378f705405d37f49795d5e915989de774fe11fTed Kremenek void HandlePostStmt(const CFGBlock *B, unsigned StmtIdx, ExplodedNode *Pred); 901eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 919c378f705405d37f49795d5e915989de774fe11fTed Kremenek void HandleBranch(const Stmt *Cond, const Stmt *Term, const CFGBlock *B, 929c378f705405d37f49795d5e915989de774fe11fTed Kremenek ExplodedNode *Pred); 93102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor void HandleCallEnter(const CallEnter &L, const CFGBlock *Block, 94102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor unsigned Index, ExplodedNode *Pred); 95102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor void HandleCallExit(const CallExit &L, ExplodedNode *Pred); 960111f575b968e423dccae439e501225b8314b257Zhongxing Xu 97f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenekprivate: 98d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis CoreEngine(const CoreEngine&); // Do not implement. 99d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis CoreEngine& operator=(const CoreEngine&); 1001eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 101f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenekpublic: 102d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis /// Construct a CoreEngine object to analyze the provided CFG using 1030111f575b968e423dccae439e501225b8314b257Zhongxing Xu /// a DFS exploration of the exploded graph. 104d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis CoreEngine(SubEngine& subengine) 105d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis : SubEng(subengine), G(new ExplodedGraph()), 10655825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek WList(WorkList::makeBFS()), 107f598087b4adfea164acdd5b53ea2951bde740a2dTed Kremenek BCounterFactory(G->getAllocator()) {} 1080111f575b968e423dccae439e501225b8314b257Zhongxing Xu 109d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis /// Construct a CoreEngine object to analyze the provided CFG and to 1100111f575b968e423dccae439e501225b8314b257Zhongxing Xu /// use the provided worklist object to execute the worklist algorithm. 111d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis /// The CoreEngine object assumes ownership of 'wlist'. 112d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis CoreEngine(WorkList* wlist, SubEngine& subengine) 113d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis : SubEng(subengine), G(new ExplodedGraph()), WList(wlist), 114f598087b4adfea164acdd5b53ea2951bde740a2dTed Kremenek BCounterFactory(G->getAllocator()) {} 1150111f575b968e423dccae439e501225b8314b257Zhongxing Xu 116d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis ~CoreEngine() { 1170111f575b968e423dccae439e501225b8314b257Zhongxing Xu delete WList; 1180111f575b968e423dccae439e501225b8314b257Zhongxing Xu } 1190111f575b968e423dccae439e501225b8314b257Zhongxing Xu 1200111f575b968e423dccae439e501225b8314b257Zhongxing Xu /// getGraph - Returns the exploded graph. 121031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu ExplodedGraph& getGraph() { return *G.get(); } 1221eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1230111f575b968e423dccae439e501225b8314b257Zhongxing Xu /// takeGraph - Returns the exploded graph. Ownership of the graph is 124fc8f0e14ad142ed811e90fbd9a30e419e301c717Chris Lattner /// transferred to the caller. 125031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu ExplodedGraph* takeGraph() { return G.take(); } 1260111f575b968e423dccae439e501225b8314b257Zhongxing Xu 127f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek /// ExecuteWorkList - Run the worklist algorithm for a maximum number of 128f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek /// steps. Returns true if there is still simulation state on the worklist. 1292ce43c8f43254a9edea53a20dc0e69195bc82ae0Zhongxing Xu bool ExecuteWorkList(const LocationContext *L, unsigned Steps, 13018c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const ProgramState *InitState); 13118c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek void ExecuteWorkListWithInitialState(const LocationContext *L, 13218c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek unsigned Steps, 13318c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const ProgramState *InitState, 1342ce43c8f43254a9edea53a20dc0e69195bc82ae0Zhongxing Xu ExplodedNodeSet &Dst); 135bc42c533e7d3d946704a49e242939dd232f33072Tom Care 136bc42c533e7d3d946704a49e242939dd232f33072Tom Care // Functions for external checking of whether we have unfinished work 137422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek bool wasBlockAborted() const { return !blocksAborted.empty(); } 138422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek bool wasBlocksExhausted() const { return !blocksExhausted.empty(); } 139422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek bool hasWorkRemaining() const { return wasBlocksExhausted() || 140422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek WList->hasWork() || 141422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek wasBlockAborted(); } 142422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek 143422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek /// Inform the CoreEngine that a basic block was aborted because 144422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek /// it could not be completely analyzed. 145422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek void addAbortedBlock(const ExplodedNode *node, const CFGBlock *block) { 146422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek blocksAborted.push_back(std::make_pair(block, node)); 147422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek } 148422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek 149d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis WorkList *getWorkList() const { return WList; } 150f598087b4adfea164acdd5b53ea2951bde740a2dTed Kremenek 151422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek BlocksExhausted::const_iterator blocks_exhausted_begin() const { 15266750fa464ace9f8c41666c8585ec71a248c1ccaTed Kremenek return blocksExhausted.begin(); 153f598087b4adfea164acdd5b53ea2951bde740a2dTed Kremenek } 154422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek BlocksExhausted::const_iterator blocks_exhausted_end() const { 15566750fa464ace9f8c41666c8585ec71a248c1ccaTed Kremenek return blocksExhausted.end(); 156f598087b4adfea164acdd5b53ea2951bde740a2dTed Kremenek } 157422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek BlocksAborted::const_iterator blocks_aborted_begin() const { 158422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek return blocksAborted.begin(); 159422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek } 160422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek BlocksAborted::const_iterator blocks_aborted_end() const { 161422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek return blocksAborted.end(); 162422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek } 163f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek}; 1641eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 165d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidisclass StmtNodeBuilder { 166d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis CoreEngine& Eng; 1679c378f705405d37f49795d5e915989de774fe11fTed Kremenek const CFGBlock &B; 168f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek const unsigned Idx; 1699c378f705405d37f49795d5e915989de774fe11fTed Kremenek ExplodedNode *Pred; 17018c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ProgramStateManager& Mgr; 171031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu 172031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xupublic: 173031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu bool PurgingDeadSymbols; 174031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu bool BuildSinks; 175b4857264b8d3d861f688cdaa174aab30e0729a73Ted Kremenek bool hasGeneratedNode; 176031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu ProgramPoint::Kind PointKind; 177ca804539d908d3a0e8c72a0df5f1f571d29490bbTed Kremenek const ProgramPointTag *Tag; 1781eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 179c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu typedef llvm::SmallPtrSet<ExplodedNode*,5> DeferredTy; 180f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek DeferredTy Deferred; 1811eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1829c378f705405d37f49795d5e915989de774fe11fTed Kremenek void GenerateAutoTransition(ExplodedNode *N); 1831eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 184f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenekpublic: 18518c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek StmtNodeBuilder(const CFGBlock *b, 18618c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek unsigned idx, 18718c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *N, 18818c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek CoreEngine* e, 18918c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ProgramStateManager &mgr); 1901eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 191d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis ~StmtNodeBuilder(); 1921eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1939c378f705405d37f49795d5e915989de774fe11fTed Kremenek ExplodedNode *getPredecessor() const { return Pred; } 1941eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 195798d2ca60d1cd6de70d28a5ce60337a2b03a663fZhongxing Xu // FIXME: This should not be exposed. 196d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis WorkList *getWorkList() { return Eng.WList; } 197798d2ca60d1cd6de70d28a5ce60337a2b03a663fZhongxing 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 20618c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *generateNode(PostStmt PP, 20718c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const ProgramState *St, 20818c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *Pred) { 209b4857264b8d3d861f688cdaa174aab30e0729a73Ted Kremenek hasGeneratedNode = true; 210031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu return generateNodeInternal(PP, St, Pred); 211031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu } 2121eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 21318c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *generateNode(const Stmt *S, 21418c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const ProgramState *St, 21518c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *Pred, 21618c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ProgramPoint::Kind K, 217ca804539d908d3a0e8c72a0df5f1f571d29490bbTed Kremenek const ProgramPointTag *tag = 0) { 218b4857264b8d3d861f688cdaa174aab30e0729a73Ted Kremenek hasGeneratedNode = true; 219031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu 2201eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump if (PurgingDeadSymbols) 2211eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump K = ProgramPoint::PostPurgeDeadSymbolsKind; 222031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu 2234bac726dadb09ee38bab8147f1e706380368b362Ted Kremenek return generateNodeInternal(S, St, Pred, K, tag ? tag : Tag); 224031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu } 2251eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 22618c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *generateNode(const Stmt *S, 22718c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const ProgramState *St, 228ca804539d908d3a0e8c72a0df5f1f571d29490bbTed Kremenek ExplodedNode *Pred, 229ca804539d908d3a0e8c72a0df5f1f571d29490bbTed Kremenek const ProgramPointTag *tag = 0) { 2304bac726dadb09ee38bab8147f1e706380368b362Ted Kremenek return generateNode(S, St, Pred, PointKind, tag); 231031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu } 232031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu 23318c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *generateNode(const ProgramPoint &PP, 23418c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const ProgramState *State, 2359c378f705405d37f49795d5e915989de774fe11fTed Kremenek ExplodedNode *Pred) { 236b4857264b8d3d861f688cdaa174aab30e0729a73Ted Kremenek hasGeneratedNode = true; 237102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor return generateNodeInternal(PP, State, Pred); 238102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor } 239102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 240c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu ExplodedNode* 24118c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek generateNodeInternal(const ProgramPoint &PP, 24218c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const ProgramState *State, 2439c378f705405d37f49795d5e915989de774fe11fTed Kremenek ExplodedNode *Pred); 2441eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 245c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu ExplodedNode* 24618c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek generateNodeInternal(const Stmt *S, 24718c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const ProgramState *State, 24818c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *Pred, 24918c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ProgramPoint::Kind K = ProgramPoint::PostStmtKind, 25018c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const ProgramPointTag *tag = 0); 2511eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 252331b0ac44b9eb0ffcba66b4f3f3f9adb27c2434fTed Kremenek /// getStmt - Return the current block-level expression associated with 253331b0ac44b9eb0ffcba66b4f3f3f9adb27c2434fTed Kremenek /// this builder. 2549c378f705405d37f49795d5e915989de774fe11fTed Kremenek const Stmt *getStmt() const { 2553c0349e87cdbd7316d06d2411d86ee1086e717a5Ted Kremenek const CFGStmt *CS = B[Idx].getAs<CFGStmt>(); 2563c0349e87cdbd7316d06d2411d86ee1086e717a5Ted Kremenek return CS ? CS->getStmt() : 0; 257b36cd3e1757fb4fcd9509f35558c847b04bef35fZhongxing Xu } 2581eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 259331b0ac44b9eb0ffcba66b4f3f3f9adb27c2434fTed Kremenek /// getBlock - Return the CFGBlock associated with the block-level expression 260331b0ac44b9eb0ffcba66b4f3f3f9adb27c2434fTed Kremenek /// of this builder. 2619c378f705405d37f49795d5e915989de774fe11fTed Kremenek const CFGBlock *getBlock() const { return &B; } 262bdb435ddaafd5069becd543d638112f68825b89dTed Kremenek 263598278bee8e5797bc73d24d6ac8a1d6ff6413caeZhongxing Xu unsigned getIndex() const { return Idx; } 264598278bee8e5797bc73d24d6ac8a1d6ff6413caeZhongxing Xu 26518c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *MakeNode(ExplodedNodeSet &Dst, 26618c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const Stmt *S, 26718c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *Pred, 26818c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const ProgramState *St) { 269bf4e419d996bf42e4933cada610d973a0fcc40ebTed Kremenek return MakeNode(Dst, S, Pred, St, PointKind); 270bf4e419d996bf42e4933cada610d973a0fcc40ebTed Kremenek } 2711eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 27218c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *MakeNode(ExplodedNodeSet &Dst, 27318c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const Stmt *S, 27418c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *Pred, 27518c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const ProgramState *St, 27618c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ProgramPoint::Kind K); 2771eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 27818c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *MakeSinkNode(ExplodedNodeSet &Dst, 27918c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const Stmt *S, 28018c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *Pred, 28118c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const ProgramState *St) { 28270a733e64e2379a654631a14fa29e46761d5f80dTed Kremenek bool Tmp = BuildSinks; 28370a733e64e2379a654631a14fa29e46761d5f80dTed Kremenek BuildSinks = true; 2849c378f705405d37f49795d5e915989de774fe11fTed Kremenek ExplodedNode *N = MakeNode(Dst, S, Pred, St); 28570a733e64e2379a654631a14fa29e46761d5f80dTed Kremenek BuildSinks = Tmp; 28670a733e64e2379a654631a14fa29e46761d5f80dTed Kremenek return N; 28770a733e64e2379a654631a14fa29e46761d5f80dTed Kremenek } 288f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek}; 2891eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 290d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidisclass BranchNodeBuilder { 291d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis CoreEngine& Eng; 2929c378f705405d37f49795d5e915989de774fe11fTed Kremenek const CFGBlock *Src; 2939c378f705405d37f49795d5e915989de774fe11fTed Kremenek const CFGBlock *DstT; 2949c378f705405d37f49795d5e915989de774fe11fTed Kremenek const CFGBlock *DstF; 2959c378f705405d37f49795d5e915989de774fe11fTed Kremenek ExplodedNode *Pred; 29652a16499df87730c0252b431abdf2b2e32d756a6Ted Kremenek 297686775deca8b8685eb90801495880e3abdd844c2Chris Lattner typedef SmallVector<ExplodedNode*,3> DeferredTy; 2983b4f6702860208692f6ef28401e68de4e3ff9af9Ted Kremenek DeferredTy Deferred; 2991eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 30071c29bdc931bc49644c581ec7d698f0dbf01a0aaTed Kremenek bool GeneratedTrue; 30171c29bdc931bc49644c581ec7d698f0dbf01a0aaTed Kremenek bool GeneratedFalse; 302520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek bool InFeasibleTrue; 303520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek bool InFeasibleFalse; 3041eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3057d7fe6d539b3bdb1701835223cca306c325614a7Ted Kremenekpublic: 3069c378f705405d37f49795d5e915989de774fe11fTed Kremenek BranchNodeBuilder(const CFGBlock *src, const CFGBlock *dstT, 3079c378f705405d37f49795d5e915989de774fe11fTed Kremenek const CFGBlock *dstF, ExplodedNode *pred, CoreEngine* e) 30871c29bdc931bc49644c581ec7d698f0dbf01a0aaTed Kremenek : Eng(*e), Src(src), DstT(dstT), DstF(dstF), Pred(pred), 309520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek GeneratedTrue(false), GeneratedFalse(false), 310520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek InFeasibleTrue(!DstT), InFeasibleFalse(!DstF) {} 3111eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 312d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis ~BranchNodeBuilder(); 3131eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3149c378f705405d37f49795d5e915989de774fe11fTed Kremenek ExplodedNode *getPredecessor() const { return Pred; } 315031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu 31638b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu const ExplodedGraph& getGraph() const { return *Eng.G; } 317031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu 318d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis BlockCounter getBlockCounter() const { return Eng.WList->getBlockCounter();} 3191eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 32018c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *generateNode(const Stmt *Condition, const ProgramState *State); 3218083414ee7cc8f5c807ed6a4e120fb4e0ab50ff8Ted Kremenek 32218c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *generateNode(const ProgramState *State, bool branch); 3231eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3249c378f705405d37f49795d5e915989de774fe11fTed Kremenek const CFGBlock *getTargetBlock(bool branch) const { 3258e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek return branch ? DstT : DstF; 3261eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump } 3271eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 32852a16499df87730c0252b431abdf2b2e32d756a6Ted Kremenek void markInfeasible(bool branch) { 329520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek if (branch) 330520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek InFeasibleTrue = GeneratedTrue = true; 331520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek else 332520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek InFeasibleFalse = GeneratedFalse = true; 333520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek } 3341eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 335520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek bool isFeasible(bool branch) { 336520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek return branch ? !InFeasibleTrue : !InFeasibleFalse; 33752a16499df87730c0252b431abdf2b2e32d756a6Ted Kremenek } 3381eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 33918c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const ProgramState *getState() const { 340b38911f16b4943548db6a3695fc6ae23070b25d2Ted Kremenek return getPredecessor()->getState(); 341b38911f16b4943548db6a3695fc6ae23070b25d2Ted Kremenek } 3427d7fe6d539b3bdb1701835223cca306c325614a7Ted Kremenek}; 343031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu 344d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidisclass IndirectGotoNodeBuilder { 345d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis CoreEngine& Eng; 3469c378f705405d37f49795d5e915989de774fe11fTed Kremenek const CFGBlock *Src; 3479c378f705405d37f49795d5e915989de774fe11fTed Kremenek const CFGBlock &DispatchBlock; 3489c378f705405d37f49795d5e915989de774fe11fTed Kremenek const Expr *E; 3499c378f705405d37f49795d5e915989de774fe11fTed Kremenek ExplodedNode *Pred; 350031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu 351754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenekpublic: 3529c378f705405d37f49795d5e915989de774fe11fTed Kremenek IndirectGotoNodeBuilder(ExplodedNode *pred, const CFGBlock *src, 3539c378f705405d37f49795d5e915989de774fe11fTed Kremenek const Expr *e, const CFGBlock *dispatch, CoreEngine* eng) 35403509aea098772644bf4662dc1c88634818ceeccZhongxing Xu : Eng(*eng), Src(src), DispatchBlock(*dispatch), E(e), Pred(pred) {} 355754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek 356031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu class iterator { 35703509aea098772644bf4662dc1c88634818ceeccZhongxing Xu CFGBlock::const_succ_iterator I; 3581eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 359d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis friend class IndirectGotoNodeBuilder; 36003509aea098772644bf4662dc1c88634818ceeccZhongxing Xu iterator(CFGBlock::const_succ_iterator i) : I(i) {} 361754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek public: 3621eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3639c378f705405d37f49795d5e915989de774fe11fTed Kremenek iterator &operator++() { ++I; return *this; } 3649c378f705405d37f49795d5e915989de774fe11fTed Kremenek bool operator!=(const iterator &X) const { return I != X.I; } 3651eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 366ad8dcf4a9df0e24051dc31bf9e6f3cd138a34298Chris Lattner const LabelDecl *getLabel() const { 367ad8dcf4a9df0e24051dc31bf9e6f3cd138a34298Chris Lattner return llvm::cast<LabelStmt>((*I)->getLabel())->getDecl(); 36824f1a967741ff9f8025ee23be12ba6feacc31f77Ted Kremenek } 3691eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 370ad8dcf4a9df0e24051dc31bf9e6f3cd138a34298Chris Lattner const CFGBlock *getBlock() const { 37124f1a967741ff9f8025ee23be12ba6feacc31f77Ted Kremenek return *I; 37224f1a967741ff9f8025ee23be12ba6feacc31f77Ted Kremenek } 373754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek }; 3741eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 375031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu iterator begin() { return iterator(DispatchBlock.succ_begin()); } 376031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu iterator end() { return iterator(DispatchBlock.succ_end()); } 3771eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 37818c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *generateNode(const iterator &I, 37918c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const ProgramState *State, 380031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu bool isSink = false); 3811eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3829c378f705405d37f49795d5e915989de774fe11fTed Kremenek const Expr *getTarget() const { return E; } 383754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek 38418c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const ProgramState *getState() const { return Pred->State; } 385754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek}; 3861eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 387d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidisclass SwitchNodeBuilder { 388d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis CoreEngine& Eng; 3899c378f705405d37f49795d5e915989de774fe11fTed Kremenek const CFGBlock *Src; 3909c378f705405d37f49795d5e915989de774fe11fTed Kremenek const Expr *Condition; 3919c378f705405d37f49795d5e915989de774fe11fTed Kremenek ExplodedNode *Pred; 392031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu 393daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenekpublic: 3949c378f705405d37f49795d5e915989de774fe11fTed Kremenek SwitchNodeBuilder(ExplodedNode *pred, const CFGBlock *src, 3959c378f705405d37f49795d5e915989de774fe11fTed Kremenek const Expr *condition, CoreEngine* eng) 396daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek : Eng(*eng), Src(src), Condition(condition), Pred(pred) {} 3971eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 398031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu class iterator { 39903509aea098772644bf4662dc1c88634818ceeccZhongxing Xu CFGBlock::const_succ_reverse_iterator I; 4001eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 401d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis friend class SwitchNodeBuilder; 40203509aea098772644bf4662dc1c88634818ceeccZhongxing Xu iterator(CFGBlock::const_succ_reverse_iterator i) : I(i) {} 403031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu 404daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek public: 4059c378f705405d37f49795d5e915989de774fe11fTed Kremenek iterator &operator++() { ++I; return *this; } 40634feff654c6304e0a59ceb1376989d28dbc956ffTed Kremenek bool operator!=(const iterator &X) const { return I != X.I; } 40734feff654c6304e0a59ceb1376989d28dbc956ffTed Kremenek bool operator==(const iterator &X) const { return I == X.I; } 4081eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4099c378f705405d37f49795d5e915989de774fe11fTed Kremenek const CaseStmt *getCase() const { 410daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek return llvm::cast<CaseStmt>((*I)->getLabel()); 411daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek } 4121eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4139c378f705405d37f49795d5e915989de774fe11fTed Kremenek const CFGBlock *getBlock() const { 414daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek return *I; 415daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek } 416daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek }; 4171eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 418031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu iterator begin() { return iterator(Src->succ_rbegin()+1); } 419031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu iterator end() { return iterator(Src->succ_rend()); } 4201eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4214d3175c1e5a44251ea97b0c81e80f060629d9c08Ted Kremenek const SwitchStmt *getSwitch() const { 4224d3175c1e5a44251ea97b0c81e80f060629d9c08Ted Kremenek return llvm::cast<SwitchStmt>(Src->getTerminator()); 4234d3175c1e5a44251ea97b0c81e80f060629d9c08Ted Kremenek } 4244d3175c1e5a44251ea97b0c81e80f060629d9c08Ted Kremenek 42518c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *generateCaseStmtNode(const iterator &I, 42618c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const ProgramState *State); 4271eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 42818c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *generateDefaultCaseNode(const ProgramState *State, 429031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu bool isSink = false); 4301eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4319c378f705405d37f49795d5e915989de774fe11fTed Kremenek const Expr *getCondition() const { return Condition; } 432daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek 43318c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const ProgramState *getState() const { return Pred->State; } 434daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek}; 43511062b118476368fa5b294954713e5df97d8599fTed Kremenek 43627c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenekclass GenericNodeBuilderImpl { 43727c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenekprotected: 43827c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek CoreEngine &engine; 43927c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek ExplodedNode *pred; 44027c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek ProgramPoint pp; 441686775deca8b8685eb90801495880e3abdd844c2Chris Lattner SmallVector<ExplodedNode*, 2> sinksGenerated; 44227c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek 44318c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *generateNodeImpl(const ProgramState *state, 44418c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *pred, 44518c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ProgramPoint programPoint, 44618c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek bool asSink); 44727c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek 44827c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek GenericNodeBuilderImpl(CoreEngine &eng, ExplodedNode *pr, ProgramPoint p) 449b4857264b8d3d861f688cdaa174aab30e0729a73Ted Kremenek : engine(eng), pred(pr), pp(p), hasGeneratedNode(false) {} 45027c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek 45127c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenekpublic: 452b4857264b8d3d861f688cdaa174aab30e0729a73Ted Kremenek bool hasGeneratedNode; 45327c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek 45427c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek WorkList &getWorkList() { return *engine.WList; } 45527c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek 4569c378f705405d37f49795d5e915989de774fe11fTed Kremenek ExplodedNode *getPredecessor() const { return pred; } 45727c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek 45827c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek BlockCounter getBlockCounter() const { 45927c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek return engine.WList->getBlockCounter(); 46027c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek } 46127c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek 462686775deca8b8685eb90801495880e3abdd844c2Chris Lattner const SmallVectorImpl<ExplodedNode*> &sinks() const { 46327c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek return sinksGenerated; 46427c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek } 46527c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek}; 46627c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek 467b6a2b08a6b3fbce1a6a4b69d4185165de970696cTed Kremenektemplate <typename PP_T> 46827c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenekclass GenericNodeBuilder : public GenericNodeBuilderImpl { 46927c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenekpublic: 470b6a2b08a6b3fbce1a6a4b69d4185165de970696cTed Kremenek GenericNodeBuilder(CoreEngine &eng, ExplodedNode *pr, const PP_T &p) 47127c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek : GenericNodeBuilderImpl(eng, pr, p) {} 47227c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek 47318c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *generateNode(const ProgramState *state, ExplodedNode *pred, 474ca804539d908d3a0e8c72a0df5f1f571d29490bbTed Kremenek const ProgramPointTag *tag, bool asSink) { 475b6a2b08a6b3fbce1a6a4b69d4185165de970696cTed Kremenek return generateNodeImpl(state, pred, cast<PP_T>(pp).withTag(tag), 476b6a2b08a6b3fbce1a6a4b69d4185165de970696cTed Kremenek asSink); 47727c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek } 47827c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek 479b6a2b08a6b3fbce1a6a4b69d4185165de970696cTed Kremenek const PP_T &getProgramPoint() const { return cast<PP_T>(pp); } 48027c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek}; 48127c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek 482e36de1fe51c39d9161915dd3dbef880954af6476Ted Kremenekclass EndOfFunctionNodeBuilder { 483d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis CoreEngine &Eng; 4849c378f705405d37f49795d5e915989de774fe11fTed Kremenek const CFGBlock &B; 4859c378f705405d37f49795d5e915989de774fe11fTed Kremenek ExplodedNode *Pred; 486ca804539d908d3a0e8c72a0df5f1f571d29490bbTed Kremenek const ProgramPointTag *Tag; 487f605aae3227ffa3a5dae8eb34fdd79ba0a0d19d1Zhongxing Xu 488f605aae3227ffa3a5dae8eb34fdd79ba0a0d19d1Zhongxing Xupublic: 489b4857264b8d3d861f688cdaa174aab30e0729a73Ted Kremenek bool hasGeneratedNode; 4901eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 49111062b118476368fa5b294954713e5df97d8599fTed Kremenekpublic: 4929c378f705405d37f49795d5e915989de774fe11fTed Kremenek EndOfFunctionNodeBuilder(const CFGBlock *b, ExplodedNode *N, CoreEngine* e, 493ca804539d908d3a0e8c72a0df5f1f571d29490bbTed Kremenek const ProgramPointTag *tag = 0) 494ca804539d908d3a0e8c72a0df5f1f571d29490bbTed Kremenek : Eng(*e), B(*b), Pred(N), Tag(tag), hasGeneratedNode(false) {} 4951eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 496e36de1fe51c39d9161915dd3dbef880954af6476Ted Kremenek ~EndOfFunctionNodeBuilder(); 4971eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 498ca804539d908d3a0e8c72a0df5f1f571d29490bbTed Kremenek EndOfFunctionNodeBuilder withCheckerTag(const ProgramPointTag *tag) { 499f178ac8b68b29e44867777232ba8fee59edc4037Argyrios Kyrtzidis return EndOfFunctionNodeBuilder(&B, Pred, &Eng, tag); 500f178ac8b68b29e44867777232ba8fee59edc4037Argyrios Kyrtzidis } 501f178ac8b68b29e44867777232ba8fee59edc4037Argyrios Kyrtzidis 502d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis WorkList &getWorkList() { return *Eng.WList; } 503598278bee8e5797bc73d24d6ac8a1d6ff6413caeZhongxing Xu 5049c378f705405d37f49795d5e915989de774fe11fTed Kremenek ExplodedNode *getPredecessor() const { return Pred; } 5051eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 506d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis BlockCounter getBlockCounter() const { 507031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu return Eng.WList->getBlockCounter(); 508031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu } 5091eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 51011062b118476368fa5b294954713e5df97d8599fTed Kremenek unsigned getCurrentBlockCount() const { 511d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu return getBlockCounter().getNumVisited( 512d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu Pred->getLocationContext()->getCurrentStackFrame(), 513d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu B.getBlockID()); 5141eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump } 5151eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 51618c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *generateNode(const ProgramState *State, 51718c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *P = 0, 518ca804539d908d3a0e8c72a0df5f1f571d29490bbTed Kremenek const ProgramPointTag *tag = 0); 5191eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 52018c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek void GenerateCallExitNode(const ProgramState *state); 521102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 5229c378f705405d37f49795d5e915989de774fe11fTed Kremenek const CFGBlock *getBlock() const { return &B; } 52311062b118476368fa5b294954713e5df97d8599fTed Kremenek 52418c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const ProgramState *getState() const { 52511062b118476368fa5b294954713e5df97d8599fTed Kremenek return getPredecessor()->getState(); 52611062b118476368fa5b294954713e5df97d8599fTed Kremenek } 52711062b118476368fa5b294954713e5df97d8599fTed Kremenek}; 528754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek 529d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidisclass CallEnterNodeBuilder { 530d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis CoreEngine &Eng; 531102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 532102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor const ExplodedNode *Pred; 533102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 53419b78d9e3dbbc27bbcbdd8c3017a00fe88849ecdZhongxing Xu // The call site. For implicit automatic object dtor, this is the trigger 53519b78d9e3dbbc27bbcbdd8c3017a00fe88849ecdZhongxing Xu // statement. 536102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor const Stmt *CE; 537102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 53819b78d9e3dbbc27bbcbdd8c3017a00fe88849ecdZhongxing Xu // The context of the callee. 53919b78d9e3dbbc27bbcbdd8c3017a00fe88849ecdZhongxing Xu const StackFrameContext *CalleeCtx; 540102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 541102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor // The parent block of the CallExpr. 542102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor const CFGBlock *Block; 543102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 544102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor // The CFGBlock index of the CallExpr. 545102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor unsigned Index; 546102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 547102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregorpublic: 548d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis CallEnterNodeBuilder(CoreEngine &eng, const ExplodedNode *pred, 54919b78d9e3dbbc27bbcbdd8c3017a00fe88849ecdZhongxing Xu const Stmt *s, const StackFrameContext *callee, 550102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor const CFGBlock *blk, unsigned idx) 551c6238d2786cfd961b94580b3d3675a1b3ff0721cZhongxing Xu : Eng(eng), Pred(pred), CE(s), CalleeCtx(callee), Block(blk), Index(idx) {} 552102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 55318c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const ProgramState *getState() const { return Pred->getState(); } 554102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 555102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor const LocationContext *getLocationContext() const { 556102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor return Pred->getLocationContext(); 557102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor } 558102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 559102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor const Stmt *getCallExpr() const { return CE; } 560102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 56119b78d9e3dbbc27bbcbdd8c3017a00fe88849ecdZhongxing Xu const StackFrameContext *getCalleeContext() const { return CalleeCtx; } 562102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 563102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor const CFGBlock *getBlock() const { return Block; } 564102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 565102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor unsigned getIndex() const { return Index; } 566102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 56718c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek void generateNode(const ProgramState *state); 568102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor}; 569102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 570d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidisclass CallExitNodeBuilder { 571d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis CoreEngine &Eng; 572102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor const ExplodedNode *Pred; 573102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 574102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregorpublic: 575d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis CallExitNodeBuilder(CoreEngine &eng, const ExplodedNode *pred) 576102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor : Eng(eng), Pred(pred) {} 577102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 578102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor const ExplodedNode *getPredecessor() const { return Pred; } 579102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 58018c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const ProgramState *getState() const { return Pred->getState(); } 581102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 58218c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek void generateNode(const ProgramState *state); 583102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor}; 5845a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis 5855a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis} // end GR namespace 5865a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis 587f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek} // end clang namespace 588f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek 589f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek#endif 590