CoreEngine.h revision 4e82d3cf6fd4c907265e3fa3aac0a835c35dc759
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 "llvm/ADT/OwningPtr.h" 23 24namespace clang { 25 26class ProgramPointTag; 27 28namespace ento { 29 30class NodeBuilder; 31 32//===----------------------------------------------------------------------===// 33/// CoreEngine - Implements the core logic of the graph-reachability 34/// analysis. It traverses the CFG and generates the ExplodedGraph. 35/// Program "states" are treated as opaque void pointers. 36/// The template class CoreEngine (which subclasses CoreEngine) 37/// provides the matching component to the engine that knows the actual types 38/// for states. Note that this engine only dispatches to transfer functions 39/// at the statement and block-level. The analyses themselves must implement 40/// any transfer function logic and the sub-expression level (if any). 41class CoreEngine { 42 friend class CommonNodeBuilder; 43 friend class NodeBuilder; 44 friend class StmtNodeBuilder; 45 friend class GenericNodeBuilderImpl; 46 friend class BranchNodeBuilder; 47 friend class IndirectGotoNodeBuilder; 48 friend class SwitchNodeBuilder; 49 friend class EndOfFunctionNodeBuilder; 50 friend class CallEnterNodeBuilder; 51 friend class CallExitNodeBuilder; 52 53public: 54 typedef std::vector<std::pair<BlockEdge, const ExplodedNode*> > 55 BlocksExhausted; 56 57 typedef std::vector<std::pair<const CFGBlock*, const ExplodedNode*> > 58 BlocksAborted; 59 60private: 61 62 SubEngine& SubEng; 63 64 /// G - The simulation graph. Each node is a (location,state) pair. 65 llvm::OwningPtr<ExplodedGraph> G; 66 67 /// WList - A set of queued nodes that need to be processed by the 68 /// worklist algorithm. It is up to the implementation of WList to decide 69 /// the order that nodes are processed. 70 WorkList* WList; 71 72 /// BCounterFactory - A factory object for created BlockCounter objects. 73 /// These are used to record for key nodes in the ExplodedGraph the 74 /// number of times different CFGBlocks have been visited along a path. 75 BlockCounter::Factory BCounterFactory; 76 77 /// The locations where we stopped doing work because we visited a location 78 /// too many times. 79 BlocksExhausted blocksExhausted; 80 81 /// The locations where we stopped because the engine aborted analysis, 82 /// usually because it could not reason about something. 83 BlocksAborted blocksAborted; 84 85 void generateNode(const ProgramPoint &Loc, 86 const ProgramState *State, 87 ExplodedNode *Pred); 88 89 void HandleBlockEdge(const BlockEdge &E, ExplodedNode *Pred); 90 void HandleBlockEntrance(const BlockEntrance &E, ExplodedNode *Pred); 91 void HandleBlockExit(const CFGBlock *B, ExplodedNode *Pred); 92 void HandlePostStmt(const CFGBlock *B, unsigned StmtIdx, ExplodedNode *Pred); 93 94 void HandleBranch(const Stmt *Cond, const Stmt *Term, const CFGBlock *B, 95 ExplodedNode *Pred); 96 void HandleCallEnter(const CallEnter &L, const CFGBlock *Block, 97 unsigned Index, ExplodedNode *Pred); 98 void HandleCallExit(const CallExit &L, ExplodedNode *Pred); 99 100private: 101 CoreEngine(const CoreEngine&); // Do not implement. 102 CoreEngine& operator=(const CoreEngine&); 103 104public: 105 /// Construct a CoreEngine object to analyze the provided CFG using 106 /// a DFS exploration of the exploded graph. 107 CoreEngine(SubEngine& subengine) 108 : SubEng(subengine), G(new ExplodedGraph()), 109 WList(WorkList::makeBFS()), 110 BCounterFactory(G->getAllocator()) {} 111 112 /// Construct a CoreEngine object to analyze the provided CFG and to 113 /// use the provided worklist object to execute the worklist algorithm. 114 /// The CoreEngine object assumes ownership of 'wlist'. 115 CoreEngine(WorkList* wlist, SubEngine& subengine) 116 : SubEng(subengine), G(new ExplodedGraph()), WList(wlist), 117 BCounterFactory(G->getAllocator()) {} 118 119 ~CoreEngine() { 120 delete WList; 121 } 122 123 /// getGraph - Returns the exploded graph. 124 ExplodedGraph& getGraph() { return *G.get(); } 125 126 /// takeGraph - Returns the exploded graph. Ownership of the graph is 127 /// transferred to the caller. 128 ExplodedGraph* takeGraph() { return G.take(); } 129 130 /// ExecuteWorkList - Run the worklist algorithm for a maximum number of 131 /// steps. Returns true if there is still simulation state on the worklist. 132 bool ExecuteWorkList(const LocationContext *L, unsigned Steps, 133 const ProgramState *InitState); 134 void ExecuteWorkListWithInitialState(const LocationContext *L, 135 unsigned Steps, 136 const ProgramState *InitState, 137 ExplodedNodeSet &Dst); 138 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 /// Specifies if the builder results have been finalized. For example, if it 191 /// is set to false, autotransitions are yet to be generated. 192 bool Finalized; 193 194 bool HasGeneratedNodes; 195 196 /// \brief The frontier set - a set of nodes which need to be propagated after 197 /// the builder dies. 198 typedef llvm::SmallPtrSet<ExplodedNode*,5> DeferredTy; 199 DeferredTy Deferred; 200 201 BlockCounter getBlockCounter() const { return C.Eng.WList->getBlockCounter();} 202 203 /// Checkes if the results are ready. 204 virtual bool checkResults() { 205 if (!Finalized) 206 return false; 207 for (DeferredTy::iterator I=Deferred.begin(), E=Deferred.end(); I!=E; ++I) 208 if ((*I)->isSink()) 209 return false; 210 return true; 211 } 212 213 /// Allow subclasses to finalize results before result_begin() is executed. 214 virtual void finalizeResults() {} 215 216 ExplodedNode *generateNodeImpl(const ProgramPoint &PP, 217 const ProgramState *State, 218 ExplodedNode *Pred, 219 bool MarkAsSink = false); 220 221public: 222 NodeBuilder(ExplodedNode *N, NodeBuilderContext &Ctx, bool F = true) 223 : BuilderPred(N), C(Ctx), Finalized(F), HasGeneratedNodes(false) { 224 assert(!N->isSink()); 225 Deferred.insert(N); 226 } 227 228 /// Create a new builder using the parent builder's context. 229 NodeBuilder(ExplodedNode *N, const NodeBuilder &ParentBldr, bool F = true) 230 : BuilderPred(N), C(ParentBldr.C), Finalized(F), HasGeneratedNodes(false) { 231 assert(!N->isSink()); 232 Deferred.insert(N); 233 } 234 235 virtual ~NodeBuilder() {} 236 237 /// \brief Generates a node in the ExplodedGraph. 238 /// 239 /// When a node is marked as sink, the exploration from the node is stopped - 240 /// the node becomes the last node on the path. 241 ExplodedNode *generateNode(const ProgramPoint &PP, 242 const ProgramState *State, 243 ExplodedNode *Pred, 244 bool MarkAsSink = false) { 245 return generateNodeImpl(PP, State, Pred, MarkAsSink); 246 } 247 248 // TODO: will get removed. 249 bool hasGeneratedNodes() const { 250 return HasGeneratedNodes; 251 } 252 253 typedef DeferredTy::iterator iterator; 254 /// \brief Iterators through the results frontier. 255 inline iterator results_begin() { 256 finalizeResults(); 257 assert(checkResults()); 258 return Deferred.begin(); 259 } 260 inline iterator results_end() { 261 finalizeResults(); 262 return Deferred.end(); 263 } 264 265 /// \brief Return the CFGBlock associated with this builder. 266 const CFGBlock *getBlock() const { return C.Block; } 267 268 /// \brief Returns the number of times the current basic block has been 269 /// visited on the exploded graph path. 270 unsigned getCurrentBlockCount() const { 271 return getBlockCounter().getNumVisited( 272 BuilderPred->getLocationContext()->getCurrentStackFrame(), 273 C.Block->getBlockID()); 274 } 275}; 276 277class CommonNodeBuilder { 278protected: 279 ExplodedNode *Pred; 280 CoreEngine& Eng; 281 282 CommonNodeBuilder(CoreEngine* E, ExplodedNode *P) : Pred(P), Eng(*E) {} 283 BlockCounter getBlockCounter() const { return Eng.WList->getBlockCounter(); } 284}; 285 286 287class StmtNodeBuilder: public NodeBuilder { 288 const unsigned Idx; 289 290public: 291 bool PurgingDeadSymbols; 292 bool BuildSinks; 293 // TODO: Remove the flag. We should be able to use the method in the parent. 294 bool hasGeneratedNode; 295 ProgramPoint::Kind PointKind; 296 const ProgramPointTag *Tag; 297 298 void GenerateAutoTransition(ExplodedNode *N); 299 300public: 301 StmtNodeBuilder(ExplodedNode *N, unsigned idx, NodeBuilderContext &Ctx); 302 303 ~StmtNodeBuilder(); 304 305 ExplodedNode *generateNode(const Stmt *S, 306 const ProgramState *St, 307 ExplodedNode *Pred, 308 ProgramPoint::Kind K, 309 const ProgramPointTag *tag = 0, 310 bool MarkAsSink = false) { 311 if (PurgingDeadSymbols) 312 K = ProgramPoint::PostPurgeDeadSymbolsKind; 313 314 const ProgramPoint &L = ProgramPoint::getProgramPoint(S, K, 315 Pred->getLocationContext(), tag ? tag : Tag); 316 return generateNodeImpl(L, St, Pred, MarkAsSink); 317 } 318 319 ExplodedNode *generateNode(const Stmt *S, 320 const ProgramState *St, 321 ExplodedNode *Pred, 322 const ProgramPointTag *tag = 0) { 323 return generateNode(S, St, Pred, PointKind, tag); 324 } 325 326 ExplodedNode *generateNode(const ProgramPoint &PP, 327 const ProgramState *State, 328 ExplodedNode *Pred) { 329 return generateNodeImpl(PP, State, Pred, false); 330 } 331 332 /// getStmt - Return the current block-level expression associated with 333 /// this builder. 334 const Stmt *getStmt() const { 335 const CFGStmt *CS = (*C.Block)[Idx].getAs<CFGStmt>(); 336 return CS ? CS->getStmt() : 0; 337 } 338 339 unsigned getIndex() const { return Idx; } 340 341 ExplodedNode *MakeNode(ExplodedNodeSet &Dst, 342 const Stmt *S, 343 ExplodedNode *Pred, 344 const ProgramState *St) { 345 return MakeNode(Dst, S, Pred, St, PointKind); 346 } 347 348 ExplodedNode *MakeNode(ExplodedNodeSet &Dst, 349 const Stmt *S, 350 ExplodedNode *Pred, 351 const ProgramState *St, 352 ProgramPoint::Kind K); 353 354 ExplodedNode *MakeSinkNode(ExplodedNodeSet &Dst, 355 const Stmt *S, 356 ExplodedNode *Pred, 357 const ProgramState *St) { 358 bool Tmp = BuildSinks; 359 BuildSinks = true; 360 ExplodedNode *N = MakeNode(Dst, S, Pred, St); 361 BuildSinks = Tmp; 362 return N; 363 } 364 365 void importNodesFromBuilder(const NodeBuilder &NB) { 366 ExplodedNode *NBPred = const_cast<ExplodedNode*>(NB.BuilderPred); 367 if (NB.hasGeneratedNodes()) { 368 Deferred.erase(NBPred); 369 Deferred.insert(NB.Deferred.begin(), NB.Deferred.end()); 370 } 371 } 372}; 373 374class BranchNodeBuilder: public NodeBuilder { 375 const CFGBlock *DstT; 376 const CFGBlock *DstF; 377 378 bool InFeasibleTrue; 379 bool InFeasibleFalse; 380 381public: 382 BranchNodeBuilder(ExplodedNode *Pred, NodeBuilderContext &C, 383 const CFGBlock *dstT, const CFGBlock *dstF) 384 : NodeBuilder(Pred, C), DstT(dstT), DstF(dstF), 385 InFeasibleTrue(!DstT), InFeasibleFalse(!DstF) {} 386 387 /// Create a new builder using the parent builder's context. 388 BranchNodeBuilder(ExplodedNode *Pred, BranchNodeBuilder &ParentBldr) 389 : NodeBuilder(Pred, ParentBldr), DstT(ParentBldr.DstT), 390 DstF(ParentBldr.DstF), 391 InFeasibleTrue(!DstT), InFeasibleFalse(!DstF) {} 392 393 ExplodedNode *generateNode(const ProgramState *State, bool branch, 394 ExplodedNode *Pred = 0); 395 396 const CFGBlock *getTargetBlock(bool branch) const { 397 return branch ? DstT : DstF; 398 } 399 400 void markInfeasible(bool branch) { 401 if (branch) 402 InFeasibleTrue = true; 403 else 404 InFeasibleFalse = true; 405 } 406 407 bool isFeasible(bool branch) { 408 return branch ? !InFeasibleTrue : !InFeasibleFalse; 409 } 410}; 411 412class IndirectGotoNodeBuilder { 413 CoreEngine& Eng; 414 const CFGBlock *Src; 415 const CFGBlock &DispatchBlock; 416 const Expr *E; 417 ExplodedNode *Pred; 418 419public: 420 IndirectGotoNodeBuilder(ExplodedNode *pred, const CFGBlock *src, 421 const Expr *e, const CFGBlock *dispatch, CoreEngine* eng) 422 : Eng(*eng), Src(src), DispatchBlock(*dispatch), E(e), Pred(pred) {} 423 424 class iterator { 425 CFGBlock::const_succ_iterator I; 426 427 friend class IndirectGotoNodeBuilder; 428 iterator(CFGBlock::const_succ_iterator i) : I(i) {} 429 public: 430 431 iterator &operator++() { ++I; return *this; } 432 bool operator!=(const iterator &X) const { return I != X.I; } 433 434 const LabelDecl *getLabel() const { 435 return llvm::cast<LabelStmt>((*I)->getLabel())->getDecl(); 436 } 437 438 const CFGBlock *getBlock() const { 439 return *I; 440 } 441 }; 442 443 iterator begin() { return iterator(DispatchBlock.succ_begin()); } 444 iterator end() { return iterator(DispatchBlock.succ_end()); } 445 446 ExplodedNode *generateNode(const iterator &I, 447 const ProgramState *State, 448 bool isSink = false); 449 450 const Expr *getTarget() const { return E; } 451 452 const ProgramState *getState() const { return Pred->State; } 453}; 454 455class SwitchNodeBuilder { 456 CoreEngine& Eng; 457 const CFGBlock *Src; 458 const Expr *Condition; 459 ExplodedNode *Pred; 460 461public: 462 SwitchNodeBuilder(ExplodedNode *pred, const CFGBlock *src, 463 const Expr *condition, CoreEngine* eng) 464 : Eng(*eng), Src(src), Condition(condition), Pred(pred) {} 465 466 class iterator { 467 CFGBlock::const_succ_reverse_iterator I; 468 469 friend class SwitchNodeBuilder; 470 iterator(CFGBlock::const_succ_reverse_iterator i) : I(i) {} 471 472 public: 473 iterator &operator++() { ++I; return *this; } 474 bool operator!=(const iterator &X) const { return I != X.I; } 475 bool operator==(const iterator &X) const { return I == X.I; } 476 477 const CaseStmt *getCase() const { 478 return llvm::cast<CaseStmt>((*I)->getLabel()); 479 } 480 481 const CFGBlock *getBlock() const { 482 return *I; 483 } 484 }; 485 486 iterator begin() { return iterator(Src->succ_rbegin()+1); } 487 iterator end() { return iterator(Src->succ_rend()); } 488 489 const SwitchStmt *getSwitch() const { 490 return llvm::cast<SwitchStmt>(Src->getTerminator()); 491 } 492 493 ExplodedNode *generateCaseStmtNode(const iterator &I, 494 const ProgramState *State); 495 496 ExplodedNode *generateDefaultCaseNode(const ProgramState *State, 497 bool isSink = false); 498 499 const Expr *getCondition() const { return Condition; } 500 501 const ProgramState *getState() const { return Pred->State; } 502}; 503 504class GenericNodeBuilderImpl { 505protected: 506 CoreEngine &engine; 507 ExplodedNode *pred; 508 ProgramPoint pp; 509 SmallVector<ExplodedNode*, 2> sinksGenerated; 510 511 ExplodedNode *generateNodeImpl(const ProgramState *state, 512 ExplodedNode *pred, 513 ProgramPoint programPoint, 514 bool asSink); 515 516 GenericNodeBuilderImpl(CoreEngine &eng, ExplodedNode *pr, ProgramPoint p) 517 : engine(eng), pred(pr), pp(p), hasGeneratedNode(false) {} 518 519public: 520 bool hasGeneratedNode; 521 522 WorkList &getWorkList() { return *engine.WList; } 523 524 ExplodedNode *getPredecessor() const { return pred; } 525 526 BlockCounter getBlockCounter() const { 527 return engine.WList->getBlockCounter(); 528 } 529 530 const SmallVectorImpl<ExplodedNode*> &sinks() const { 531 return sinksGenerated; 532 } 533}; 534 535template <typename PP_T> 536class GenericNodeBuilder : public GenericNodeBuilderImpl { 537public: 538 GenericNodeBuilder(CoreEngine &eng, ExplodedNode *pr, const PP_T &p) 539 : GenericNodeBuilderImpl(eng, pr, p) {} 540 541 ExplodedNode *generateNode(const ProgramState *state, ExplodedNode *pred, 542 const ProgramPointTag *tag, bool asSink) { 543 return generateNodeImpl(state, pred, cast<PP_T>(pp).withTag(tag), 544 asSink); 545 } 546 547 const PP_T &getProgramPoint() const { return cast<PP_T>(pp); } 548}; 549 550class EndOfFunctionNodeBuilder : public CommonNodeBuilder { 551 const CFGBlock &B; 552 const ProgramPointTag *Tag; 553 554public: 555 bool hasGeneratedNode; 556 557public: 558 EndOfFunctionNodeBuilder(const CFGBlock *b, ExplodedNode *N, CoreEngine* e, 559 const ProgramPointTag *tag = 0) 560 : CommonNodeBuilder(e, N), B(*b), Tag(tag), hasGeneratedNode(false) {} 561 562 ~EndOfFunctionNodeBuilder(); 563 564 EndOfFunctionNodeBuilder withCheckerTag(const ProgramPointTag *tag) { 565 return EndOfFunctionNodeBuilder(&B, Pred, &Eng, tag); 566 } 567 568 WorkList &getWorkList() { return *Eng.WList; } 569 570 ExplodedNode *getPredecessor() const { return Pred; } 571 572 unsigned getCurrentBlockCount() const { 573 return getBlockCounter().getNumVisited( 574 Pred->getLocationContext()->getCurrentStackFrame(), 575 B.getBlockID()); 576 } 577 578 ExplodedNode *generateNode(const ProgramState *State, 579 ExplodedNode *P = 0, 580 const ProgramPointTag *tag = 0); 581 582 void GenerateCallExitNode(const ProgramState *state); 583 584 const CFGBlock *getBlock() const { return &B; } 585 586 const ProgramState *getState() const { 587 return getPredecessor()->getState(); 588 } 589}; 590 591class CallEnterNodeBuilder { 592 CoreEngine &Eng; 593 594 const ExplodedNode *Pred; 595 596 // The call site. For implicit automatic object dtor, this is the trigger 597 // statement. 598 const Stmt *CE; 599 600 // The context of the callee. 601 const StackFrameContext *CalleeCtx; 602 603 // The parent block of the CallExpr. 604 const CFGBlock *Block; 605 606 // The CFGBlock index of the CallExpr. 607 unsigned Index; 608 609public: 610 CallEnterNodeBuilder(CoreEngine &eng, const ExplodedNode *pred, 611 const Stmt *s, const StackFrameContext *callee, 612 const CFGBlock *blk, unsigned idx) 613 : Eng(eng), Pred(pred), CE(s), CalleeCtx(callee), Block(blk), Index(idx) {} 614 615 const ProgramState *getState() const { return Pred->getState(); } 616 617 const LocationContext *getLocationContext() const { 618 return Pred->getLocationContext(); 619 } 620 621 const Stmt *getCallExpr() const { return CE; } 622 623 const StackFrameContext *getCalleeContext() const { return CalleeCtx; } 624 625 const CFGBlock *getBlock() const { return Block; } 626 627 unsigned getIndex() const { return Index; } 628 629 void generateNode(const ProgramState *state); 630}; 631 632class CallExitNodeBuilder { 633 CoreEngine &Eng; 634 const ExplodedNode *Pred; 635 636public: 637 CallExitNodeBuilder(CoreEngine &eng, const ExplodedNode *pred) 638 : Eng(eng), Pred(pred) {} 639 640 const ExplodedNode *getPredecessor() const { return Pred; } 641 642 const ProgramState *getState() const { return Pred->getState(); } 643 644 void generateNode(const ProgramState *state); 645}; 646 647} // end GR namespace 648 649} // end clang namespace 650 651#endif 652