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 24 namespace clang { 25 26 class ProgramPointTag; 27 28 namespace ento { 29 30 class 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). 41 class 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 53 public: 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 60 private: 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 100 private: 101 CoreEngine(const CoreEngine&); // Do not implement. 102 CoreEngine& operator=(const CoreEngine&); 103 104 public: 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 171 struct NodeBuilderContext { 172 CoreEngine &Eng; 173 const CFGBlock *Block; 174 ExplodedNode *ContextPred; 175 NodeBuilderContext(CoreEngine &E, const CFGBlock *B, ExplodedNode *N) 176 : Eng(E), Block(B), ContextPred(N) { assert(B); assert(!N->isSink()); } 177 }; 178 179 /// This is the simplest builder which generates nodes in the ExplodedGraph. 180 class NodeBuilder { 181 protected: 182 friend class StmtNodeBuilder; 183 184 ExplodedNode *BuilderPred; 185 186 // TODO: Context should become protected after refactoring is done. 187 public: 188 const NodeBuilderContext &C; 189 protected: 190 191 /// Specifies if the builder results have been finalized. For example, if it 192 /// is set to false, autotransitions are yet to be generated. 193 bool Finalized; 194 195 bool HasGeneratedNodes; 196 197 /// \brief The frontier set - a set of nodes which need to be propagated after 198 /// the builder dies. 199 typedef llvm::SmallPtrSet<ExplodedNode*,5> DeferredTy; 200 DeferredTy Deferred; 201 202 BlockCounter getBlockCounter() const { return C.Eng.WList->getBlockCounter();} 203 204 /// Checkes if the results are ready. 205 virtual bool checkResults() { 206 if (!Finalized) 207 return false; 208 for (DeferredTy::iterator I=Deferred.begin(), E=Deferred.end(); I!=E; ++I) 209 if ((*I)->isSink()) 210 return false; 211 return true; 212 } 213 214 /// Allow subclasses to finalize results before result_begin() is executed. 215 virtual void finalizeResults() {} 216 217 ExplodedNode *generateNodeImpl(const ProgramPoint &PP, 218 const ProgramState *State, 219 ExplodedNode *Pred, 220 bool MarkAsSink = false); 221 222 public: 223 NodeBuilder(NodeBuilderContext &Ctx, bool F = true) 224 : C(Ctx), Finalized(F), HasGeneratedNodes(false) { 225 Deferred.insert(C.ContextPred); 226 } 227 228 /// Create a new builder using the parent builder's context. 229 NodeBuilder(const NodeBuilder &ParentBldr, bool F = true) 230 : C(ParentBldr.C), Finalized(F), HasGeneratedNodes(false) { 231 Deferred.insert(C.ContextPred); 232 } 233 234 virtual ~NodeBuilder() {} 235 236 /// \brief Generates a node in the ExplodedGraph. 237 /// 238 /// When a node is marked as sink, the exploration from the node is stopped - 239 /// the node becomes the last node on the path. 240 ExplodedNode *generateNode(const ProgramPoint &PP, 241 const ProgramState *State, 242 ExplodedNode *Pred, 243 bool MarkAsSink = false) { 244 return generateNodeImpl(PP, State, Pred, MarkAsSink); 245 } 246 247 // TODO: will get removed. 248 bool hasGeneratedNodes() const { 249 return HasGeneratedNodes; 250 } 251 252 typedef DeferredTy::iterator iterator; 253 /// \brief Iterators through the results frontier. 254 inline iterator results_begin() { 255 finalizeResults(); 256 assert(checkResults()); 257 return Deferred.begin(); 258 } 259 inline iterator results_end() { 260 finalizeResults(); 261 return Deferred.end(); 262 } 263 264 /// \brief Return the CFGBlock associated with this builder. 265 const CFGBlock *getBlock() const { return C.Block; } 266 267 /// \brief Returns the number of times the current basic block has been 268 /// visited on the exploded graph path. 269 unsigned getCurrentBlockCount() const { 270 return getBlockCounter().getNumVisited( 271 C.ContextPred->getLocationContext()->getCurrentStackFrame(), 272 C.Block->getBlockID()); 273 } 274 }; 275 276 class CommonNodeBuilder { 277 protected: 278 ExplodedNode *Pred; 279 CoreEngine& Eng; 280 281 CommonNodeBuilder(CoreEngine* E, ExplodedNode *P) : Pred(P), Eng(*E) {} 282 BlockCounter getBlockCounter() const { return Eng.WList->getBlockCounter(); } 283 }; 284 285 286 class StmtNodeBuilder: public NodeBuilder { 287 const unsigned Idx; 288 289 public: 290 bool PurgingDeadSymbols; 291 bool BuildSinks; 292 // TODO: Remove the flag. We should be able to use the method in the parent. 293 bool hasGeneratedNode; 294 ProgramPoint::Kind PointKind; 295 const ProgramPointTag *Tag; 296 297 void GenerateAutoTransition(ExplodedNode *N); 298 299 public: 300 StmtNodeBuilder(ExplodedNode *N, unsigned idx, NodeBuilderContext &Ctx); 301 302 ~StmtNodeBuilder(); 303 304 ExplodedNode *generateNode(const Stmt *S, 305 const ProgramState *St, 306 ExplodedNode *Pred, 307 ProgramPoint::Kind K, 308 const ProgramPointTag *tag = 0, 309 bool MarkAsSink = false) { 310 if (PurgingDeadSymbols) 311 K = ProgramPoint::PostPurgeDeadSymbolsKind; 312 313 const ProgramPoint &L = ProgramPoint::getProgramPoint(S, K, 314 Pred->getLocationContext(), tag ? tag : Tag); 315 return generateNodeImpl(L, St, Pred, MarkAsSink); 316 } 317 318 ExplodedNode *generateNode(const Stmt *S, 319 const ProgramState *St, 320 ExplodedNode *Pred, 321 const ProgramPointTag *tag = 0) { 322 return generateNode(S, St, Pred, PointKind, tag); 323 } 324 325 ExplodedNode *generateNode(const ProgramPoint &PP, 326 const ProgramState *State, 327 ExplodedNode *Pred) { 328 return generateNodeImpl(PP, State, Pred, false); 329 } 330 331 /// getStmt - Return the current block-level expression associated with 332 /// this builder. 333 const Stmt *getStmt() const { 334 const CFGStmt *CS = (*C.Block)[Idx].getAs<CFGStmt>(); 335 return CS ? CS->getStmt() : 0; 336 } 337 338 unsigned getIndex() const { return Idx; } 339 340 ExplodedNode *MakeNode(ExplodedNodeSet &Dst, 341 const Stmt *S, 342 ExplodedNode *Pred, 343 const ProgramState *St) { 344 return MakeNode(Dst, S, Pred, St, PointKind); 345 } 346 347 ExplodedNode *MakeNode(ExplodedNodeSet &Dst, 348 const Stmt *S, 349 ExplodedNode *Pred, 350 const ProgramState *St, 351 ProgramPoint::Kind K); 352 353 ExplodedNode *MakeSinkNode(ExplodedNodeSet &Dst, 354 const Stmt *S, 355 ExplodedNode *Pred, 356 const ProgramState *St) { 357 bool Tmp = BuildSinks; 358 BuildSinks = true; 359 ExplodedNode *N = MakeNode(Dst, S, Pred, St); 360 BuildSinks = Tmp; 361 return N; 362 } 363 364 void importNodesFromBuilder(const NodeBuilder &NB) { 365 ExplodedNode *NBPred = const_cast<ExplodedNode*>(NB.C.ContextPred); 366 if (NB.hasGeneratedNodes()) { 367 Deferred.erase(NBPred); 368 Deferred.insert(NB.Deferred.begin(), NB.Deferred.end()); 369 } 370 } 371 }; 372 373 class BranchNodeBuilder: public NodeBuilder { 374 const CFGBlock *DstT; 375 const CFGBlock *DstF; 376 377 bool InFeasibleTrue; 378 bool InFeasibleFalse; 379 380 public: 381 BranchNodeBuilder(NodeBuilderContext &C, 382 const CFGBlock *dstT, const CFGBlock *dstF) 383 : NodeBuilder(C), DstT(dstT), DstF(dstF), 384 InFeasibleTrue(!DstT), InFeasibleFalse(!DstF) {} 385 386 /// Create a new builder using the parent builder's context. 387 BranchNodeBuilder(BranchNodeBuilder &ParentBldr) 388 : NodeBuilder(ParentBldr), DstT(ParentBldr.DstT), 389 DstF(ParentBldr.DstF), 390 InFeasibleTrue(!DstT), InFeasibleFalse(!DstF) {} 391 392 ExplodedNode *generateNode(const ProgramState *State, bool branch, 393 ExplodedNode *Pred); 394 395 const CFGBlock *getTargetBlock(bool branch) const { 396 return branch ? DstT : DstF; 397 } 398 399 void markInfeasible(bool branch) { 400 if (branch) 401 InFeasibleTrue = true; 402 else 403 InFeasibleFalse = true; 404 } 405 406 bool isFeasible(bool branch) { 407 return branch ? !InFeasibleTrue : !InFeasibleFalse; 408 } 409 }; 410 411 class IndirectGotoNodeBuilder { 412 CoreEngine& Eng; 413 const CFGBlock *Src; 414 const CFGBlock &DispatchBlock; 415 const Expr *E; 416 ExplodedNode *Pred; 417 418 public: 419 IndirectGotoNodeBuilder(ExplodedNode *pred, const CFGBlock *src, 420 const Expr *e, const CFGBlock *dispatch, CoreEngine* eng) 421 : Eng(*eng), Src(src), DispatchBlock(*dispatch), E(e), Pred(pred) {} 422 423 class iterator { 424 CFGBlock::const_succ_iterator I; 425 426 friend class IndirectGotoNodeBuilder; 427 iterator(CFGBlock::const_succ_iterator i) : I(i) {} 428 public: 429 430 iterator &operator++() { ++I; return *this; } 431 bool operator!=(const iterator &X) const { return I != X.I; } 432 433 const LabelDecl *getLabel() const { 434 return llvm::cast<LabelStmt>((*I)->getLabel())->getDecl(); 435 } 436 437 const CFGBlock *getBlock() const { 438 return *I; 439 } 440 }; 441 442 iterator begin() { return iterator(DispatchBlock.succ_begin()); } 443 iterator end() { return iterator(DispatchBlock.succ_end()); } 444 445 ExplodedNode *generateNode(const iterator &I, 446 const ProgramState *State, 447 bool isSink = false); 448 449 const Expr *getTarget() const { return E; } 450 451 const ProgramState *getState() const { return Pred->State; } 452 }; 453 454 class SwitchNodeBuilder { 455 CoreEngine& Eng; 456 const CFGBlock *Src; 457 const Expr *Condition; 458 ExplodedNode *Pred; 459 460 public: 461 SwitchNodeBuilder(ExplodedNode *pred, const CFGBlock *src, 462 const Expr *condition, CoreEngine* eng) 463 : Eng(*eng), Src(src), Condition(condition), Pred(pred) {} 464 465 class iterator { 466 CFGBlock::const_succ_reverse_iterator I; 467 468 friend class SwitchNodeBuilder; 469 iterator(CFGBlock::const_succ_reverse_iterator i) : I(i) {} 470 471 public: 472 iterator &operator++() { ++I; return *this; } 473 bool operator!=(const iterator &X) const { return I != X.I; } 474 bool operator==(const iterator &X) const { return I == X.I; } 475 476 const CaseStmt *getCase() const { 477 return llvm::cast<CaseStmt>((*I)->getLabel()); 478 } 479 480 const CFGBlock *getBlock() const { 481 return *I; 482 } 483 }; 484 485 iterator begin() { return iterator(Src->succ_rbegin()+1); } 486 iterator end() { return iterator(Src->succ_rend()); } 487 488 const SwitchStmt *getSwitch() const { 489 return llvm::cast<SwitchStmt>(Src->getTerminator()); 490 } 491 492 ExplodedNode *generateCaseStmtNode(const iterator &I, 493 const ProgramState *State); 494 495 ExplodedNode *generateDefaultCaseNode(const ProgramState *State, 496 bool isSink = false); 497 498 const Expr *getCondition() const { return Condition; } 499 500 const ProgramState *getState() const { return Pred->State; } 501 }; 502 503 class GenericNodeBuilderImpl { 504 protected: 505 CoreEngine &engine; 506 ExplodedNode *pred; 507 ProgramPoint pp; 508 SmallVector<ExplodedNode*, 2> sinksGenerated; 509 510 ExplodedNode *generateNodeImpl(const ProgramState *state, 511 ExplodedNode *pred, 512 ProgramPoint programPoint, 513 bool asSink); 514 515 GenericNodeBuilderImpl(CoreEngine &eng, ExplodedNode *pr, ProgramPoint p) 516 : engine(eng), pred(pr), pp(p), hasGeneratedNode(false) {} 517 518 public: 519 bool hasGeneratedNode; 520 521 WorkList &getWorkList() { return *engine.WList; } 522 523 ExplodedNode *getPredecessor() const { return pred; } 524 525 BlockCounter getBlockCounter() const { 526 return engine.WList->getBlockCounter(); 527 } 528 529 const SmallVectorImpl<ExplodedNode*> &sinks() const { 530 return sinksGenerated; 531 } 532 }; 533 534 template <typename PP_T> 535 class GenericNodeBuilder : public GenericNodeBuilderImpl { 536 public: 537 GenericNodeBuilder(CoreEngine &eng, ExplodedNode *pr, const PP_T &p) 538 : GenericNodeBuilderImpl(eng, pr, p) {} 539 540 ExplodedNode *generateNode(const ProgramState *state, ExplodedNode *pred, 541 const ProgramPointTag *tag, bool asSink) { 542 return generateNodeImpl(state, pred, cast<PP_T>(pp).withTag(tag), 543 asSink); 544 } 545 546 const PP_T &getProgramPoint() const { return cast<PP_T>(pp); } 547 }; 548 549 class EndOfFunctionNodeBuilder : public CommonNodeBuilder { 550 const CFGBlock &B; 551 const ProgramPointTag *Tag; 552 553 public: 554 bool hasGeneratedNode; 555 556 public: 557 EndOfFunctionNodeBuilder(const CFGBlock *b, ExplodedNode *N, CoreEngine* e, 558 const ProgramPointTag *tag = 0) 559 : CommonNodeBuilder(e, N), B(*b), Tag(tag), hasGeneratedNode(false) {} 560 561 ~EndOfFunctionNodeBuilder(); 562 563 EndOfFunctionNodeBuilder withCheckerTag(const ProgramPointTag *tag) { 564 return EndOfFunctionNodeBuilder(&B, Pred, &Eng, tag); 565 } 566 567 WorkList &getWorkList() { return *Eng.WList; } 568 569 ExplodedNode *getPredecessor() const { return Pred; } 570 571 unsigned getCurrentBlockCount() const { 572 return getBlockCounter().getNumVisited( 573 Pred->getLocationContext()->getCurrentStackFrame(), 574 B.getBlockID()); 575 } 576 577 ExplodedNode *generateNode(const ProgramState *State, 578 ExplodedNode *P = 0, 579 const ProgramPointTag *tag = 0); 580 581 void GenerateCallExitNode(const ProgramState *state); 582 583 const CFGBlock *getBlock() const { return &B; } 584 585 const ProgramState *getState() const { 586 return getPredecessor()->getState(); 587 } 588 }; 589 590 class CallEnterNodeBuilder { 591 CoreEngine &Eng; 592 593 const ExplodedNode *Pred; 594 595 // The call site. For implicit automatic object dtor, this is the trigger 596 // statement. 597 const Stmt *CE; 598 599 // The context of the callee. 600 const StackFrameContext *CalleeCtx; 601 602 // The parent block of the CallExpr. 603 const CFGBlock *Block; 604 605 // The CFGBlock index of the CallExpr. 606 unsigned Index; 607 608 public: 609 CallEnterNodeBuilder(CoreEngine &eng, const ExplodedNode *pred, 610 const Stmt *s, const StackFrameContext *callee, 611 const CFGBlock *blk, unsigned idx) 612 : Eng(eng), Pred(pred), CE(s), CalleeCtx(callee), Block(blk), Index(idx) {} 613 614 const ProgramState *getState() const { return Pred->getState(); } 615 616 const LocationContext *getLocationContext() const { 617 return Pred->getLocationContext(); 618 } 619 620 const Stmt *getCallExpr() const { return CE; } 621 622 const StackFrameContext *getCalleeContext() const { return CalleeCtx; } 623 624 const CFGBlock *getBlock() const { return Block; } 625 626 unsigned getIndex() const { return Index; } 627 628 void generateNode(const ProgramState *state); 629 }; 630 631 class CallExitNodeBuilder { 632 CoreEngine &Eng; 633 const ExplodedNode *Pred; 634 635 public: 636 CallExitNodeBuilder(CoreEngine &eng, const ExplodedNode *pred) 637 : Eng(eng), Pred(pred) {} 638 639 const ExplodedNode *getPredecessor() const { return Pred; } 640 641 const ProgramState *getState() const { return Pred->getState(); } 642 643 void generateNode(const ProgramState *state); 644 }; 645 646 } // end GR namespace 647 648 } // end clang namespace 649 650 #endif 651