CoreEngine.h revision ad8dcf4a9df0e24051dc31bf9e6f3cd138a34298
1//==- CoreEngine.h - Path-Sensitive Dataflow Engine ----------------*- C++ -*-// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file defines a generic engine for intraprocedural, path-sensitive, 11// dataflow analysis via graph reachability. 12// 13//===----------------------------------------------------------------------===// 14 15#ifndef LLVM_CLANG_GR_COREENGINE 16#define LLVM_CLANG_GR_COREENGINE 17 18#include "clang/AST/Expr.h" 19#include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h" 20#include "clang/StaticAnalyzer/Core/PathSensitive/WorkList.h" 21#include "clang/StaticAnalyzer/Core/PathSensitive/BlockCounter.h" 22#include "clang/StaticAnalyzer/Core/PathSensitive/SubEngine.h" 23#include "llvm/ADT/OwningPtr.h" 24 25namespace clang { 26 27namespace ento { 28 29//===----------------------------------------------------------------------===// 30/// CoreEngine - Implements the core logic of the graph-reachability 31/// analysis. It traverses the CFG and generates the ExplodedGraph. 32/// Program "states" are treated as opaque void pointers. 33/// The template class CoreEngine (which subclasses CoreEngine) 34/// provides the matching component to the engine that knows the actual types 35/// for states. Note that this engine only dispatches to transfer functions 36/// at the statement and block-level. The analyses themselves must implement 37/// any transfer function logic and the sub-expression level (if any). 38class CoreEngine { 39 friend class StmtNodeBuilder; 40 friend class GenericNodeBuilderImpl; 41 friend class BranchNodeBuilder; 42 friend class IndirectGotoNodeBuilder; 43 friend class SwitchNodeBuilder; 44 friend class EndOfFunctionNodeBuilder; 45 friend class CallEnterNodeBuilder; 46 friend class CallExitNodeBuilder; 47 48public: 49 typedef std::vector<std::pair<BlockEdge, const ExplodedNode*> > 50 BlocksAborted; 51private: 52 53 SubEngine& SubEng; 54 55 /// G - The simulation graph. Each node is a (location,state) pair. 56 llvm::OwningPtr<ExplodedGraph> G; 57 58 /// WList - A set of queued nodes that need to be processed by the 59 /// worklist algorithm. It is up to the implementation of WList to decide 60 /// the order that nodes are processed. 61 WorkList* WList; 62 63 /// BCounterFactory - A factory object for created BlockCounter objects. 64 /// These are used to record for key nodes in the ExplodedGraph the 65 /// number of times different CFGBlocks have been visited along a path. 66 BlockCounter::Factory BCounterFactory; 67 68 /// The locations where we stopped doing work because we visited a location 69 /// too many times. 70 BlocksAborted blocksAborted; 71 72 void generateNode(const ProgramPoint& Loc, const GRState* State, 73 ExplodedNode* Pred); 74 75 void HandleBlockEdge(const BlockEdge& E, ExplodedNode* Pred); 76 void HandleBlockEntrance(const BlockEntrance& E, ExplodedNode* Pred); 77 void HandleBlockExit(const CFGBlock* B, ExplodedNode* Pred); 78 void HandlePostStmt(const CFGBlock* B, unsigned StmtIdx, ExplodedNode *Pred); 79 80 void HandleBranch(const Stmt* Cond, const Stmt* Term, const CFGBlock* B, 81 ExplodedNode* Pred); 82 void HandleCallEnter(const CallEnter &L, const CFGBlock *Block, 83 unsigned Index, ExplodedNode *Pred); 84 void HandleCallExit(const CallExit &L, ExplodedNode *Pred); 85 86private: 87 CoreEngine(const CoreEngine&); // Do not implement. 88 CoreEngine& operator=(const CoreEngine&); 89 90public: 91 /// Construct a CoreEngine object to analyze the provided CFG using 92 /// a DFS exploration of the exploded graph. 93 CoreEngine(SubEngine& subengine) 94 : SubEng(subengine), G(new ExplodedGraph()), 95 WList(WorkList::makeBFS()), 96 BCounterFactory(G->getAllocator()) {} 97 98 /// Construct a CoreEngine object to analyze the provided CFG and to 99 /// use the provided worklist object to execute the worklist algorithm. 100 /// The CoreEngine object assumes ownership of 'wlist'. 101 CoreEngine(WorkList* wlist, SubEngine& subengine) 102 : SubEng(subengine), G(new ExplodedGraph()), WList(wlist), 103 BCounterFactory(G->getAllocator()) {} 104 105 ~CoreEngine() { 106 delete WList; 107 } 108 109 /// getGraph - Returns the exploded graph. 110 ExplodedGraph& getGraph() { return *G.get(); } 111 112 /// takeGraph - Returns the exploded graph. Ownership of the graph is 113 /// transfered to the caller. 114 ExplodedGraph* takeGraph() { return G.take(); } 115 116 /// ExecuteWorkList - Run the worklist algorithm for a maximum number of 117 /// steps. Returns true if there is still simulation state on the worklist. 118 bool ExecuteWorkList(const LocationContext *L, unsigned Steps, 119 const GRState *InitState); 120 void ExecuteWorkListWithInitialState(const LocationContext *L, unsigned Steps, 121 const GRState *InitState, 122 ExplodedNodeSet &Dst); 123 124 // Functions for external checking of whether we have unfinished work 125 bool wasBlockAborted() const { return !blocksAborted.empty(); } 126 bool hasWorkRemaining() const { return wasBlockAborted() || WList->hasWork(); } 127 128 WorkList *getWorkList() const { return WList; } 129 130 BlocksAborted::const_iterator blocks_aborted_begin() const { 131 return blocksAborted.begin(); 132 } 133 BlocksAborted::const_iterator blocks_aborted_end() const { 134 return blocksAborted.end(); 135 } 136}; 137 138class StmtNodeBuilder { 139 CoreEngine& Eng; 140 const CFGBlock& B; 141 const unsigned Idx; 142 ExplodedNode* Pred; 143 GRStateManager& Mgr; 144 145public: 146 bool PurgingDeadSymbols; 147 bool BuildSinks; 148 bool hasGeneratedNode; 149 ProgramPoint::Kind PointKind; 150 const void *Tag; 151 152 const GRState* CleanedState; 153 154 155 typedef llvm::SmallPtrSet<ExplodedNode*,5> DeferredTy; 156 DeferredTy Deferred; 157 158 void GenerateAutoTransition(ExplodedNode* N); 159 160public: 161 StmtNodeBuilder(const CFGBlock* b, unsigned idx, ExplodedNode* N, 162 CoreEngine* e, GRStateManager &mgr); 163 164 ~StmtNodeBuilder(); 165 166 ExplodedNode* getPredecessor() const { return Pred; } 167 168 // FIXME: This should not be exposed. 169 WorkList *getWorkList() { return Eng.WList; } 170 171 void SetCleanedState(const GRState* St) { 172 CleanedState = St; 173 } 174 175 BlockCounter getBlockCounter() const { return Eng.WList->getBlockCounter();} 176 177 unsigned getCurrentBlockCount() const { 178 return getBlockCounter().getNumVisited( 179 Pred->getLocationContext()->getCurrentStackFrame(), 180 B.getBlockID()); 181 } 182 183 ExplodedNode* generateNode(PostStmt PP,const GRState* St,ExplodedNode* Pred) { 184 hasGeneratedNode = true; 185 return generateNodeInternal(PP, St, Pred); 186 } 187 188 ExplodedNode* generateNode(const Stmt *S, const GRState *St, 189 ExplodedNode *Pred, ProgramPoint::Kind K, 190 const void *tag = 0) { 191 hasGeneratedNode = true; 192 193 if (PurgingDeadSymbols) 194 K = ProgramPoint::PostPurgeDeadSymbolsKind; 195 196 return generateNodeInternal(S, St, Pred, K, tag ? tag : Tag); 197 } 198 199 ExplodedNode* generateNode(const Stmt *S, const GRState *St, 200 ExplodedNode *Pred, const void *tag = 0) { 201 return generateNode(S, St, Pred, PointKind, tag); 202 } 203 204 ExplodedNode *generateNode(const ProgramPoint &PP, const GRState* State, 205 ExplodedNode* Pred) { 206 hasGeneratedNode = true; 207 return generateNodeInternal(PP, State, Pred); 208 } 209 210 ExplodedNode* 211 generateNodeInternal(const ProgramPoint &PP, const GRState* State, 212 ExplodedNode* Pred); 213 214 ExplodedNode* 215 generateNodeInternal(const Stmt* S, const GRState* State, ExplodedNode* Pred, 216 ProgramPoint::Kind K = ProgramPoint::PostStmtKind, 217 const void *tag = 0); 218 219 /// getStmt - Return the current block-level expression associated with 220 /// this builder. 221 const Stmt* getStmt() const { 222 CFGStmt CS = B[Idx].getAs<CFGStmt>(); 223 if (CS) 224 return CS.getStmt(); 225 else 226 return 0; 227 } 228 229 /// getBlock - Return the CFGBlock associated with the block-level expression 230 /// of this builder. 231 const CFGBlock* getBlock() const { return &B; } 232 233 unsigned getIndex() const { return Idx; } 234 235 const GRState* GetState(ExplodedNode* Pred) const { 236 if (Pred == getPredecessor()) 237 return CleanedState; 238 else 239 return Pred->getState(); 240 } 241 242 ExplodedNode* MakeNode(ExplodedNodeSet& Dst, const Stmt* S, 243 ExplodedNode* Pred, const GRState* St) { 244 return MakeNode(Dst, S, Pred, St, PointKind); 245 } 246 247 ExplodedNode* MakeNode(ExplodedNodeSet& Dst, const Stmt* S,ExplodedNode* Pred, 248 const GRState* St, ProgramPoint::Kind K); 249 250 ExplodedNode* MakeSinkNode(ExplodedNodeSet& Dst, const Stmt* S, 251 ExplodedNode* Pred, const GRState* St) { 252 bool Tmp = BuildSinks; 253 BuildSinks = true; 254 ExplodedNode* N = MakeNode(Dst, S, Pred, St); 255 BuildSinks = Tmp; 256 return N; 257 } 258}; 259 260class BranchNodeBuilder { 261 CoreEngine& Eng; 262 const CFGBlock* Src; 263 const CFGBlock* DstT; 264 const CFGBlock* DstF; 265 ExplodedNode* Pred; 266 267 typedef llvm::SmallVector<ExplodedNode*,3> DeferredTy; 268 DeferredTy Deferred; 269 270 bool GeneratedTrue; 271 bool GeneratedFalse; 272 bool InFeasibleTrue; 273 bool InFeasibleFalse; 274 275public: 276 BranchNodeBuilder(const CFGBlock* src, const CFGBlock* dstT, 277 const CFGBlock* dstF, ExplodedNode* pred, CoreEngine* e) 278 : Eng(*e), Src(src), DstT(dstT), DstF(dstF), Pred(pred), 279 GeneratedTrue(false), GeneratedFalse(false), 280 InFeasibleTrue(!DstT), InFeasibleFalse(!DstF) {} 281 282 ~BranchNodeBuilder(); 283 284 ExplodedNode* getPredecessor() const { return Pred; } 285 286 const ExplodedGraph& getGraph() const { return *Eng.G; } 287 288 BlockCounter getBlockCounter() const { return Eng.WList->getBlockCounter();} 289 290 ExplodedNode* generateNode(const GRState* State, bool branch); 291 292 const CFGBlock* getTargetBlock(bool branch) const { 293 return branch ? DstT : DstF; 294 } 295 296 void markInfeasible(bool branch) { 297 if (branch) 298 InFeasibleTrue = GeneratedTrue = true; 299 else 300 InFeasibleFalse = GeneratedFalse = true; 301 } 302 303 bool isFeasible(bool branch) { 304 return branch ? !InFeasibleTrue : !InFeasibleFalse; 305 } 306 307 const GRState* getState() const { 308 return getPredecessor()->getState(); 309 } 310}; 311 312class IndirectGotoNodeBuilder { 313 CoreEngine& Eng; 314 const CFGBlock* Src; 315 const CFGBlock& DispatchBlock; 316 const Expr* E; 317 ExplodedNode* Pred; 318 319public: 320 IndirectGotoNodeBuilder(ExplodedNode* pred, const CFGBlock* src, 321 const Expr* e, const CFGBlock* dispatch, CoreEngine* eng) 322 : Eng(*eng), Src(src), DispatchBlock(*dispatch), E(e), Pred(pred) {} 323 324 class iterator { 325 CFGBlock::const_succ_iterator I; 326 327 friend class IndirectGotoNodeBuilder; 328 iterator(CFGBlock::const_succ_iterator i) : I(i) {} 329 public: 330 331 iterator& operator++() { ++I; return *this; } 332 bool operator!=(const iterator& X) const { return I != X.I; } 333 334 const LabelDecl *getLabel() const { 335 return llvm::cast<LabelStmt>((*I)->getLabel())->getDecl(); 336 } 337 338 const CFGBlock *getBlock() const { 339 return *I; 340 } 341 }; 342 343 iterator begin() { return iterator(DispatchBlock.succ_begin()); } 344 iterator end() { return iterator(DispatchBlock.succ_end()); } 345 346 ExplodedNode* generateNode(const iterator& I, const GRState* State, 347 bool isSink = false); 348 349 const Expr* getTarget() const { return E; } 350 351 const GRState* getState() const { return Pred->State; } 352}; 353 354class SwitchNodeBuilder { 355 CoreEngine& Eng; 356 const CFGBlock* Src; 357 const Expr* Condition; 358 ExplodedNode* Pred; 359 360public: 361 SwitchNodeBuilder(ExplodedNode* pred, const CFGBlock* src, 362 const Expr* condition, CoreEngine* eng) 363 : Eng(*eng), Src(src), Condition(condition), Pred(pred) {} 364 365 class iterator { 366 CFGBlock::const_succ_reverse_iterator I; 367 368 friend class SwitchNodeBuilder; 369 iterator(CFGBlock::const_succ_reverse_iterator i) : I(i) {} 370 371 public: 372 iterator& operator++() { ++I; return *this; } 373 bool operator!=(const iterator &X) const { return I != X.I; } 374 bool operator==(const iterator &X) const { return I == X.I; } 375 376 const CaseStmt* getCase() const { 377 return llvm::cast<CaseStmt>((*I)->getLabel()); 378 } 379 380 const CFGBlock* getBlock() const { 381 return *I; 382 } 383 }; 384 385 iterator begin() { return iterator(Src->succ_rbegin()+1); } 386 iterator end() { return iterator(Src->succ_rend()); } 387 388 const SwitchStmt *getSwitch() const { 389 return llvm::cast<SwitchStmt>(Src->getTerminator()); 390 } 391 392 ExplodedNode* generateCaseStmtNode(const iterator& I, const GRState* State); 393 394 ExplodedNode* generateDefaultCaseNode(const GRState* State, 395 bool isSink = false); 396 397 const Expr* getCondition() const { return Condition; } 398 399 const GRState* getState() const { return Pred->State; } 400}; 401 402class GenericNodeBuilderImpl { 403protected: 404 CoreEngine &engine; 405 ExplodedNode *pred; 406 ProgramPoint pp; 407 llvm::SmallVector<ExplodedNode*, 2> sinksGenerated; 408 409 ExplodedNode *generateNodeImpl(const GRState *state, ExplodedNode *pred, 410 ProgramPoint programPoint, bool asSink); 411 412 GenericNodeBuilderImpl(CoreEngine &eng, ExplodedNode *pr, ProgramPoint p) 413 : engine(eng), pred(pr), pp(p), hasGeneratedNode(false) {} 414 415public: 416 bool hasGeneratedNode; 417 418 WorkList &getWorkList() { return *engine.WList; } 419 420 ExplodedNode* getPredecessor() const { return pred; } 421 422 BlockCounter getBlockCounter() const { 423 return engine.WList->getBlockCounter(); 424 } 425 426 const llvm::SmallVectorImpl<ExplodedNode*> &sinks() const { 427 return sinksGenerated; 428 } 429}; 430 431template <typename PP_T> 432class GenericNodeBuilder : public GenericNodeBuilderImpl { 433public: 434 GenericNodeBuilder(CoreEngine &eng, ExplodedNode *pr, const PP_T &p) 435 : GenericNodeBuilderImpl(eng, pr, p) {} 436 437 ExplodedNode *generateNode(const GRState *state, ExplodedNode *pred, 438 const void *tag, bool asSink) { 439 return generateNodeImpl(state, pred, cast<PP_T>(pp).withTag(tag), 440 asSink); 441 } 442 443 const PP_T &getProgramPoint() const { return cast<PP_T>(pp); } 444}; 445 446class EndOfFunctionNodeBuilder { 447 CoreEngine &Eng; 448 const CFGBlock& B; 449 ExplodedNode* Pred; 450 451public: 452 bool hasGeneratedNode; 453 454public: 455 EndOfFunctionNodeBuilder(const CFGBlock* b, ExplodedNode* N, CoreEngine* e) 456 : Eng(*e), B(*b), Pred(N), hasGeneratedNode(false) {} 457 458 ~EndOfFunctionNodeBuilder(); 459 460 WorkList &getWorkList() { return *Eng.WList; } 461 462 ExplodedNode* getPredecessor() const { return Pred; } 463 464 BlockCounter getBlockCounter() const { 465 return Eng.WList->getBlockCounter(); 466 } 467 468 unsigned getCurrentBlockCount() const { 469 return getBlockCounter().getNumVisited( 470 Pred->getLocationContext()->getCurrentStackFrame(), 471 B.getBlockID()); 472 } 473 474 ExplodedNode* generateNode(const GRState* State, const void *tag = 0, 475 ExplodedNode *P = 0); 476 477 void GenerateCallExitNode(const GRState *state); 478 479 const CFGBlock* getBlock() const { return &B; } 480 481 const GRState* getState() const { 482 return getPredecessor()->getState(); 483 } 484}; 485 486class CallEnterNodeBuilder { 487 CoreEngine &Eng; 488 489 const ExplodedNode *Pred; 490 491 // The call site. For implicit automatic object dtor, this is the trigger 492 // statement. 493 const Stmt *CE; 494 495 // The context of the callee. 496 const StackFrameContext *CalleeCtx; 497 498 // The parent block of the CallExpr. 499 const CFGBlock *Block; 500 501 // The CFGBlock index of the CallExpr. 502 unsigned Index; 503 504public: 505 CallEnterNodeBuilder(CoreEngine &eng, const ExplodedNode *pred, 506 const Stmt *s, const StackFrameContext *callee, 507 const CFGBlock *blk, unsigned idx) 508 : Eng(eng), Pred(pred), CE(s), CalleeCtx(callee), Block(blk), Index(idx) {} 509 510 const GRState *getState() const { return Pred->getState(); } 511 512 const LocationContext *getLocationContext() const { 513 return Pred->getLocationContext(); 514 } 515 516 const Stmt *getCallExpr() const { return CE; } 517 518 const StackFrameContext *getCalleeContext() const { return CalleeCtx; } 519 520 const CFGBlock *getBlock() const { return Block; } 521 522 unsigned getIndex() const { return Index; } 523 524 void generateNode(const GRState *state); 525}; 526 527class CallExitNodeBuilder { 528 CoreEngine &Eng; 529 const ExplodedNode *Pred; 530 531public: 532 CallExitNodeBuilder(CoreEngine &eng, const ExplodedNode *pred) 533 : Eng(eng), Pred(pred) {} 534 535 const ExplodedNode *getPredecessor() const { return Pred; } 536 537 const GRState *getState() const { return Pred->getState(); } 538 539 void generateNode(const GRState *state); 540}; 541 542} // end GR namespace 543 544} // end clang namespace 545 546#endif 547