CoreEngine.h revision 319a9184d5ca9f77622b45ae15c08f6b9ce01621
1c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch//==- CoreEngine.h - Path-Sensitive Dataflow Engine ----------------*- C++ -*-// 22a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// 32a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// The LLVM Compiler Infrastructure 42a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// 5c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch// This file is distributed under the University of Illinois Open Source 62a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// License. See LICENSE.TXT for details. 71320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci// 81320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci//===----------------------------------------------------------------------===// 91320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci// 101320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci// This file defines a generic engine for intraprocedural, path-sensitive, 111320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci// dataflow analysis via graph reachability. 121320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci// 131320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci//===----------------------------------------------------------------------===// 14f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) 152a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#ifndef LLVM_CLANG_GR_COREENGINE 162a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#define LLVM_CLANG_GR_COREENGINE 17c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 18c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)#include "clang/AST/Expr.h" 191320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci#include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h" 201320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci#include "clang/StaticAnalyzer/Core/PathSensitive/WorkList.h" 211320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci#include "clang/StaticAnalyzer/Core/PathSensitive/BlockCounter.h" 22cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)#include "llvm/ADT/OwningPtr.h" 231320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 241320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tuccinamespace clang { 252a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 262a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)class ProgramPointTag; 272a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 281320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tuccinamespace ento { 291320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 301320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucciclass NodeBuilder; 311320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 321320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci//===----------------------------------------------------------------------===// 331320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci/// CoreEngine - Implements the core logic of the graph-reachability 341320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci/// analysis. It traverses the CFG and generates the ExplodedGraph. 351320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci/// Program "states" are treated as opaque void pointers. 361320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci/// The template class CoreEngine (which subclasses CoreEngine) 371320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci/// provides the matching component to the engine that knows the actual types 381320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci/// for states. Note that this engine only dispatches to transfer functions 391320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci/// at the statement and block-level. The analyses themselves must implement 401320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci/// any transfer function logic and the sub-expression level (if any). 411320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucciclass CoreEngine { 422a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) friend class CommonNodeBuilder; 431320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci friend class NodeBuilder; 441320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci friend class StmtNodeBuilder; 451320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci friend class GenericNodeBuilderImpl; 461320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci friend class BranchNodeBuilder; 471320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci friend class IndirectGotoNodeBuilder; 481320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci friend class SwitchNodeBuilder; 491320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci friend class EndOfFunctionNodeBuilder; 502a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) friend class CallEnterNodeBuilder; 512a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) friend class CallExitNodeBuilder; 521320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 531320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tuccipublic: 541320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci typedef std::vector<std::pair<BlockEdge, const ExplodedNode*> > 551320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci BlocksExhausted; 561320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 571320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci typedef std::vector<std::pair<const CFGBlock*, const ExplodedNode*> > 581320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci BlocksAborted; 591320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 602a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)private: 611320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 621320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci SubEngine& SubEng; 631320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 641320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci /// G - The simulation graph. Each node is a (location,state) pair. 652a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) llvm::OwningPtr<ExplodedGraph> G; 661320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 671320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci /// WList - A set of queued nodes that need to be processed by the 682a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /// worklist algorithm. It is up to the implementation of WList to decide 691320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci /// the order that nodes are processed. 701320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci WorkList* WList; 711320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 721320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci /// BCounterFactory - A factory object for created BlockCounter objects. 732a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /// These are used to record for key nodes in the ExplodedGraph the 742a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /// number of times different CFGBlocks have been visited along a path. 751320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci BlockCounter::Factory BCounterFactory; 761320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 771320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci /// The locations where we stopped doing work because we visited a location 78cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) /// too many times. 79cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) BlocksExhausted blocksExhausted; 801320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 811320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci /// The locations where we stopped because the engine aborted analysis, 822a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /// usually because it could not reason about something. 831320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci BlocksAborted blocksAborted; 842a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 851320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci void generateNode(const ProgramPoint &Loc, 861320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci const ProgramState *State, 871320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci ExplodedNode *Pred); 881320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 891320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci void HandleBlockEdge(const BlockEdge &E, ExplodedNode *Pred); 901320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci void HandleBlockEntrance(const BlockEntrance &E, ExplodedNode *Pred); 912a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void HandleBlockExit(const CFGBlock *B, ExplodedNode *Pred); 921320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci void HandlePostStmt(const CFGBlock *B, unsigned StmtIdx, ExplodedNode *Pred); 931320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 941320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci void HandleBranch(const Stmt *Cond, const Stmt *Term, const CFGBlock *B, 951320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci ExplodedNode *Pred); 962a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void HandleCallEnter(const CallEnter &L, const CFGBlock *Block, 971320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci unsigned Index, ExplodedNode *Pred); 981320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci void HandleCallExit(const CallExit &L, ExplodedNode *Pred); 991320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 1001320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucciprivate: 1011320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci CoreEngine(const CoreEngine&); // Do not implement. 1021320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci CoreEngine& operator=(const CoreEngine&); 1031320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 1041320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tuccipublic: 1051320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci /// Construct a CoreEngine object to analyze the provided CFG using 1061320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci /// a DFS exploration of the exploded graph. 1071320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci CoreEngine(SubEngine& subengine) 1081320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci : SubEng(subengine), G(new ExplodedGraph()), 1091320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci WList(WorkList::makeBFS()), 1101320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci BCounterFactory(G->getAllocator()) {} 1111320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 1121320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci /// Construct a CoreEngine object to analyze the provided CFG and to 1131320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci /// use the provided worklist object to execute the worklist algorithm. 1141320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci /// The CoreEngine object assumes ownership of 'wlist'. 1151320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci CoreEngine(WorkList* wlist, SubEngine& subengine) 1161320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci : SubEng(subengine), G(new ExplodedGraph()), WList(wlist), 1171320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci BCounterFactory(G->getAllocator()) {} 1181320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 1191320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci ~CoreEngine() { 1201320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci delete WList; 1211320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci } 1221320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 1232a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /// getGraph - Returns the exploded graph. 1241320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci ExplodedGraph& getGraph() { return *G.get(); } 1251320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 1261320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci /// takeGraph - Returns the exploded graph. Ownership of the graph is 1271320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci /// transferred to the caller. 1282a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ExplodedGraph* takeGraph() { return G.take(); } 1291320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 1301320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci /// ExecuteWorkList - Run the worklist algorithm for a maximum number of 1312a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /// steps. Returns true if there is still simulation state on the worklist. 1321320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci bool ExecuteWorkList(const LocationContext *L, unsigned Steps, 1331320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci const ProgramState *InitState); 1341320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci void ExecuteWorkListWithInitialState(const LocationContext *L, 1351320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci unsigned Steps, 1362a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const ProgramState *InitState, 137c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) ExplodedNodeSet &Dst); 138c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 139 // Functions for external checking of whether we have unfinished work 140 bool wasBlockAborted() const { return !blocksAborted.empty(); } 141 bool wasBlocksExhausted() const { return !blocksExhausted.empty(); } 142 bool hasWorkRemaining() const { return wasBlocksExhausted() || 143 WList->hasWork() || 144 wasBlockAborted(); } 145 146 /// Inform the CoreEngine that a basic block was aborted because 147 /// it could not be completely analyzed. 148 void addAbortedBlock(const ExplodedNode *node, const CFGBlock *block) { 149 blocksAborted.push_back(std::make_pair(block, node)); 150 } 151 152 WorkList *getWorkList() const { return WList; } 153 154 BlocksExhausted::const_iterator blocks_exhausted_begin() const { 155 return blocksExhausted.begin(); 156 } 157 BlocksExhausted::const_iterator blocks_exhausted_end() const { 158 return blocksExhausted.end(); 159 } 160 BlocksAborted::const_iterator blocks_aborted_begin() const { 161 return blocksAborted.begin(); 162 } 163 BlocksAborted::const_iterator blocks_aborted_end() const { 164 return blocksAborted.end(); 165 } 166 167 /// Enqueue the results of the node builder onto the work list. 168 void enqueue(NodeBuilder &NB); 169}; 170 171struct NodeBuilderContext { 172 CoreEngine &Eng; 173 const CFGBlock *Block; 174 NodeBuilderContext(CoreEngine &E, const CFGBlock *B) 175 : Eng(E), Block(B) { assert(B); } 176}; 177 178/// This is the simplest builder which generates nodes in the ExplodedGraph. 179class NodeBuilder { 180protected: 181 friend class StmtNodeBuilder; 182 183 ExplodedNode *BuilderPred; 184 185// TODO: Context should become protected after refactoring is done. 186public: 187 const NodeBuilderContext &C; 188protected: 189 190 bool Finalized; 191 192 /// \brief The frontier set - a set of nodes which need to be propagated after 193 /// the builder dies. 194 typedef llvm::SmallPtrSet<ExplodedNode*,5> DeferredTy; 195 DeferredTy Deferred; 196 197 BlockCounter getBlockCounter() const { return C.Eng.WList->getBlockCounter();} 198 199 bool checkResults() { 200 if (!Finalized) 201 return false; 202 for (DeferredTy::iterator I=Deferred.begin(), E=Deferred.end(); I!=E; ++I) 203 if ((*I)->isSink()) 204 return false; 205 return true; 206 } 207 208 virtual void finalizeResults() { 209 if (!Finalized) { 210 Finalized = true; 211 } 212 } 213 214 ExplodedNode *generateNodeImpl(const ProgramPoint &PP, 215 const ProgramState *State, 216 ExplodedNode *Pred, 217 bool MarkAsSink = false); 218 219public: 220 NodeBuilder(ExplodedNode *N, NodeBuilderContext &Ctx) 221 : BuilderPred(N), C(Ctx), Finalized(false) { 222 assert(!N->isSink()); 223 Deferred.insert(N); 224 } 225 226 /// Create a new builder using the parent builder's context. 227 NodeBuilder(ExplodedNode *N, const NodeBuilder &ParentBldr) 228 : BuilderPred(N), C(ParentBldr.C), Finalized(false) { 229 assert(!N->isSink()); 230 Deferred.insert(N); 231 } 232 233 virtual ~NodeBuilder() {} 234 235 /// \brief Generates a node in the ExplodedGraph. 236 /// 237 /// When a node is marked as sink, the exploration from the node is stopped - 238 /// the node becomes the last node on the path. 239 ExplodedNode *generateNode(const ProgramPoint &PP, 240 const ProgramState *State, 241 ExplodedNode *Pred, 242 bool MarkAsSink = false) { 243 return generateNodeImpl(PP, State, Pred, MarkAsSink); 244 } 245 246 bool hasGeneratedNodes() const { 247 return (!Deferred.count(BuilderPred)); 248 } 249 250 typedef DeferredTy::iterator iterator; 251 /// \brief Iterators through the results frontier. 252 inline iterator results_begin() { 253 finalizeResults(); 254 assert(checkResults()); 255 return Deferred.begin(); 256 } 257 inline iterator results_end() { 258 finalizeResults(); 259 return Deferred.end(); 260 } 261 262 /// \brief Return the CFGBlock associated with this builder. 263 const CFGBlock *getBlock() const { return C.Block; } 264 265 /// \brief Returns the number of times the current basic block has been 266 /// visited on the exploded graph path. 267 unsigned getCurrentBlockCount() const { 268 return getBlockCounter().getNumVisited( 269 BuilderPred->getLocationContext()->getCurrentStackFrame(), 270 C.Block->getBlockID()); 271 } 272 273 // \brief Get the builder's predecessor - the parent to all the other nodes. 274 ExplodedNode *getPredecessor() const { return BuilderPred; } 275 276 // \brief Returns state of the predecessor. 277 const ProgramState *getState() const { return BuilderPred->getState(); } 278}; 279 280class CommonNodeBuilder { 281protected: 282 ExplodedNode *Pred; 283 CoreEngine& Eng; 284 285 CommonNodeBuilder(CoreEngine* E, ExplodedNode *P) : Pred(P), Eng(*E) {} 286 BlockCounter getBlockCounter() const { return Eng.WList->getBlockCounter(); } 287}; 288 289 290class StmtNodeBuilder: public NodeBuilder { 291 const unsigned Idx; 292 293public: 294 bool PurgingDeadSymbols; 295 bool BuildSinks; 296 // TODO: Remove the flag. We should be able to use the method in the parent. 297 bool hasGeneratedNode; 298 ProgramPoint::Kind PointKind; 299 const ProgramPointTag *Tag; 300 301 void GenerateAutoTransition(ExplodedNode *N); 302 303public: 304 StmtNodeBuilder(ExplodedNode *N, unsigned idx, NodeBuilderContext &Ctx); 305 306 ~StmtNodeBuilder(); 307 308 ExplodedNode *generateNode(const Stmt *S, 309 const ProgramState *St, 310 ExplodedNode *Pred, 311 ProgramPoint::Kind K, 312 const ProgramPointTag *tag = 0, 313 bool MarkAsSink = false) { 314 if (PurgingDeadSymbols) 315 K = ProgramPoint::PostPurgeDeadSymbolsKind; 316 317 const ProgramPoint &L = ProgramPoint::getProgramPoint(S, K, 318 Pred->getLocationContext(), tag ? tag : Tag); 319 return generateNodeImpl(L, St, Pred, MarkAsSink); 320 } 321 322 ExplodedNode *generateNode(const Stmt *S, 323 const ProgramState *St, 324 ExplodedNode *Pred, 325 const ProgramPointTag *tag = 0) { 326 return generateNode(S, St, Pred, PointKind, tag); 327 } 328 329 ExplodedNode *generateNode(const ProgramPoint &PP, 330 const ProgramState *State, 331 ExplodedNode *Pred) { 332 return generateNodeImpl(PP, State, Pred, false); 333 } 334 335 /// getStmt - Return the current block-level expression associated with 336 /// this builder. 337 const Stmt *getStmt() const { 338 const CFGStmt *CS = (*C.Block)[Idx].getAs<CFGStmt>(); 339 return CS ? CS->getStmt() : 0; 340 } 341 342 unsigned getIndex() const { return Idx; } 343 344 ExplodedNode *MakeNode(ExplodedNodeSet &Dst, 345 const Stmt *S, 346 ExplodedNode *Pred, 347 const ProgramState *St) { 348 return MakeNode(Dst, S, Pred, St, PointKind); 349 } 350 351 ExplodedNode *MakeNode(ExplodedNodeSet &Dst, 352 const Stmt *S, 353 ExplodedNode *Pred, 354 const ProgramState *St, 355 ProgramPoint::Kind K); 356 357 ExplodedNode *MakeSinkNode(ExplodedNodeSet &Dst, 358 const Stmt *S, 359 ExplodedNode *Pred, 360 const ProgramState *St) { 361 bool Tmp = BuildSinks; 362 BuildSinks = true; 363 ExplodedNode *N = MakeNode(Dst, S, Pred, St); 364 BuildSinks = Tmp; 365 return N; 366 } 367 368 void importNodesFromBuilder(const NodeBuilder &NB) { 369 ExplodedNode *NBPred = const_cast<ExplodedNode*>(NB.getPredecessor()); 370 if (NB.hasGeneratedNodes()) { 371 Deferred.erase(NBPred); 372 Deferred.insert(NB.Deferred.begin(), NB.Deferred.end()); 373 } 374 } 375}; 376 377class BranchNodeBuilder: public NodeBuilder { 378 const CFGBlock *DstT; 379 const CFGBlock *DstF; 380 381 bool GeneratedTrue; 382 bool GeneratedFalse; 383 bool InFeasibleTrue; 384 bool InFeasibleFalse; 385 386 void finalizeResults() { 387 if (Finalized) 388 return; 389 if (!GeneratedTrue) generateNode(BuilderPred->State, true); 390 if (!GeneratedFalse) generateNode(BuilderPred->State, false); 391 Finalized = true; 392 } 393 394public: 395 BranchNodeBuilder(ExplodedNode *Pred, NodeBuilderContext &C, 396 const CFGBlock *dstT, const CFGBlock *dstF) 397 : NodeBuilder(Pred, C), DstT(dstT), DstF(dstF), 398 GeneratedTrue(false), GeneratedFalse(false), 399 InFeasibleTrue(!DstT), InFeasibleFalse(!DstF) { 400 } 401 402 /// Create a new builder using the parent builder's context. 403 BranchNodeBuilder(ExplodedNode *Pred, BranchNodeBuilder &ParentBldr) 404 : NodeBuilder(Pred, ParentBldr), DstT(ParentBldr.DstT), DstF(ParentBldr.DstF), 405 GeneratedTrue(false), GeneratedFalse(false), 406 InFeasibleTrue(!DstT), InFeasibleFalse(!DstF) { 407 } 408 409 ExplodedNode *generateNode(const ProgramState *State, bool branch, 410 ExplodedNode *Pred = 0); 411 412 const CFGBlock *getTargetBlock(bool branch) const { 413 return branch ? DstT : DstF; 414 } 415 416 void markInfeasible(bool branch) { 417 if (branch) 418 InFeasibleTrue = GeneratedTrue = true; 419 else 420 InFeasibleFalse = GeneratedFalse = true; 421 } 422 423 bool isFeasible(bool branch) { 424 return branch ? !InFeasibleTrue : !InFeasibleFalse; 425 } 426}; 427 428class IndirectGotoNodeBuilder { 429 CoreEngine& Eng; 430 const CFGBlock *Src; 431 const CFGBlock &DispatchBlock; 432 const Expr *E; 433 ExplodedNode *Pred; 434 435public: 436 IndirectGotoNodeBuilder(ExplodedNode *pred, const CFGBlock *src, 437 const Expr *e, const CFGBlock *dispatch, CoreEngine* eng) 438 : Eng(*eng), Src(src), DispatchBlock(*dispatch), E(e), Pred(pred) {} 439 440 class iterator { 441 CFGBlock::const_succ_iterator I; 442 443 friend class IndirectGotoNodeBuilder; 444 iterator(CFGBlock::const_succ_iterator i) : I(i) {} 445 public: 446 447 iterator &operator++() { ++I; return *this; } 448 bool operator!=(const iterator &X) const { return I != X.I; } 449 450 const LabelDecl *getLabel() const { 451 return llvm::cast<LabelStmt>((*I)->getLabel())->getDecl(); 452 } 453 454 const CFGBlock *getBlock() const { 455 return *I; 456 } 457 }; 458 459 iterator begin() { return iterator(DispatchBlock.succ_begin()); } 460 iterator end() { return iterator(DispatchBlock.succ_end()); } 461 462 ExplodedNode *generateNode(const iterator &I, 463 const ProgramState *State, 464 bool isSink = false); 465 466 const Expr *getTarget() const { return E; } 467 468 const ProgramState *getState() const { return Pred->State; } 469}; 470 471class SwitchNodeBuilder { 472 CoreEngine& Eng; 473 const CFGBlock *Src; 474 const Expr *Condition; 475 ExplodedNode *Pred; 476 477public: 478 SwitchNodeBuilder(ExplodedNode *pred, const CFGBlock *src, 479 const Expr *condition, CoreEngine* eng) 480 : Eng(*eng), Src(src), Condition(condition), Pred(pred) {} 481 482 class iterator { 483 CFGBlock::const_succ_reverse_iterator I; 484 485 friend class SwitchNodeBuilder; 486 iterator(CFGBlock::const_succ_reverse_iterator i) : I(i) {} 487 488 public: 489 iterator &operator++() { ++I; return *this; } 490 bool operator!=(const iterator &X) const { return I != X.I; } 491 bool operator==(const iterator &X) const { return I == X.I; } 492 493 const CaseStmt *getCase() const { 494 return llvm::cast<CaseStmt>((*I)->getLabel()); 495 } 496 497 const CFGBlock *getBlock() const { 498 return *I; 499 } 500 }; 501 502 iterator begin() { return iterator(Src->succ_rbegin()+1); } 503 iterator end() { return iterator(Src->succ_rend()); } 504 505 const SwitchStmt *getSwitch() const { 506 return llvm::cast<SwitchStmt>(Src->getTerminator()); 507 } 508 509 ExplodedNode *generateCaseStmtNode(const iterator &I, 510 const ProgramState *State); 511 512 ExplodedNode *generateDefaultCaseNode(const ProgramState *State, 513 bool isSink = false); 514 515 const Expr *getCondition() const { return Condition; } 516 517 const ProgramState *getState() const { return Pred->State; } 518}; 519 520class GenericNodeBuilderImpl { 521protected: 522 CoreEngine &engine; 523 ExplodedNode *pred; 524 ProgramPoint pp; 525 SmallVector<ExplodedNode*, 2> sinksGenerated; 526 527 ExplodedNode *generateNodeImpl(const ProgramState *state, 528 ExplodedNode *pred, 529 ProgramPoint programPoint, 530 bool asSink); 531 532 GenericNodeBuilderImpl(CoreEngine &eng, ExplodedNode *pr, ProgramPoint p) 533 : engine(eng), pred(pr), pp(p), hasGeneratedNode(false) {} 534 535public: 536 bool hasGeneratedNode; 537 538 WorkList &getWorkList() { return *engine.WList; } 539 540 ExplodedNode *getPredecessor() const { return pred; } 541 542 BlockCounter getBlockCounter() const { 543 return engine.WList->getBlockCounter(); 544 } 545 546 const SmallVectorImpl<ExplodedNode*> &sinks() const { 547 return sinksGenerated; 548 } 549}; 550 551template <typename PP_T> 552class GenericNodeBuilder : public GenericNodeBuilderImpl { 553public: 554 GenericNodeBuilder(CoreEngine &eng, ExplodedNode *pr, const PP_T &p) 555 : GenericNodeBuilderImpl(eng, pr, p) {} 556 557 ExplodedNode *generateNode(const ProgramState *state, ExplodedNode *pred, 558 const ProgramPointTag *tag, bool asSink) { 559 return generateNodeImpl(state, pred, cast<PP_T>(pp).withTag(tag), 560 asSink); 561 } 562 563 const PP_T &getProgramPoint() const { return cast<PP_T>(pp); } 564}; 565 566class EndOfFunctionNodeBuilder : public CommonNodeBuilder { 567 const CFGBlock &B; 568 const ProgramPointTag *Tag; 569 570public: 571 bool hasGeneratedNode; 572 573public: 574 EndOfFunctionNodeBuilder(const CFGBlock *b, ExplodedNode *N, CoreEngine* e, 575 const ProgramPointTag *tag = 0) 576 : CommonNodeBuilder(e, N), B(*b), Tag(tag), hasGeneratedNode(false) {} 577 578 ~EndOfFunctionNodeBuilder(); 579 580 EndOfFunctionNodeBuilder withCheckerTag(const ProgramPointTag *tag) { 581 return EndOfFunctionNodeBuilder(&B, Pred, &Eng, tag); 582 } 583 584 WorkList &getWorkList() { return *Eng.WList; } 585 586 ExplodedNode *getPredecessor() const { return Pred; } 587 588 unsigned getCurrentBlockCount() const { 589 return getBlockCounter().getNumVisited( 590 Pred->getLocationContext()->getCurrentStackFrame(), 591 B.getBlockID()); 592 } 593 594 ExplodedNode *generateNode(const ProgramState *State, 595 ExplodedNode *P = 0, 596 const ProgramPointTag *tag = 0); 597 598 void GenerateCallExitNode(const ProgramState *state); 599 600 const CFGBlock *getBlock() const { return &B; } 601 602 const ProgramState *getState() const { 603 return getPredecessor()->getState(); 604 } 605}; 606 607class CallEnterNodeBuilder { 608 CoreEngine &Eng; 609 610 const ExplodedNode *Pred; 611 612 // The call site. For implicit automatic object dtor, this is the trigger 613 // statement. 614 const Stmt *CE; 615 616 // The context of the callee. 617 const StackFrameContext *CalleeCtx; 618 619 // The parent block of the CallExpr. 620 const CFGBlock *Block; 621 622 // The CFGBlock index of the CallExpr. 623 unsigned Index; 624 625public: 626 CallEnterNodeBuilder(CoreEngine &eng, const ExplodedNode *pred, 627 const Stmt *s, const StackFrameContext *callee, 628 const CFGBlock *blk, unsigned idx) 629 : Eng(eng), Pred(pred), CE(s), CalleeCtx(callee), Block(blk), Index(idx) {} 630 631 const ProgramState *getState() const { return Pred->getState(); } 632 633 const LocationContext *getLocationContext() const { 634 return Pred->getLocationContext(); 635 } 636 637 const Stmt *getCallExpr() const { return CE; } 638 639 const StackFrameContext *getCalleeContext() const { return CalleeCtx; } 640 641 const CFGBlock *getBlock() const { return Block; } 642 643 unsigned getIndex() const { return Index; } 644 645 void generateNode(const ProgramState *state); 646}; 647 648class CallExitNodeBuilder { 649 CoreEngine &Eng; 650 const ExplodedNode *Pred; 651 652public: 653 CallExitNodeBuilder(CoreEngine &eng, const ExplodedNode *pred) 654 : Eng(eng), Pred(pred) {} 655 656 const ExplodedNode *getPredecessor() const { return Pred; } 657 658 const ProgramState *getState() const { return Pred->getState(); } 659 660 void generateNode(const ProgramState *state); 661}; 662 663} // end GR namespace 664 665} // end clang namespace 666 667#endif 668