CoreEngine.h revision c03a39e16762627b421247b12a2658be630a3300
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 struct NodeBuilderContext; 43 friend class NodeBuilder; 44 friend class CommonNodeBuilder; 45 friend class GenericNodeBuilderImpl; 46 friend class IndirectGotoNodeBuilder; 47 friend class SwitchNodeBuilder; 48 friend class EndOfFunctionNodeBuilder; 49 friend class CallEnterNodeBuilder; 50 friend class CallExitNodeBuilder; 51 friend class ExprEngine; 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(ExplodedNodeSet &NB); 169}; 170 171// TODO: Turn into a calss. 172struct NodeBuilderContext { 173 CoreEngine &Eng; 174 const CFGBlock *Block; 175 ExplodedNode *Pred; 176 NodeBuilderContext(CoreEngine &E, const CFGBlock *B, ExplodedNode *N) 177 : Eng(E), Block(B), Pred(N) { assert(B); assert(!N->isSink()); } 178 179 ExplodedNode *getPred() const { return Pred; } 180 181 /// \brief Return the CFGBlock associated with this builder. 182 const CFGBlock *getBlock() const { return Block; } 183 184 /// \brief Returns the number of times the current basic block has been 185 /// visited on the exploded graph path. 186 unsigned getCurrentBlockCount() const { 187 return Eng.WList->getBlockCounter().getNumVisited( 188 Pred->getLocationContext()->getCurrentStackFrame(), 189 Block->getBlockID()); 190 } 191}; 192 193/// \class NodeBuilder 194/// \brief This is the simplest builder which generates nodes in the 195/// ExplodedGraph. 196/// 197/// The main benefit of the builder is that it automatically tracks the 198/// frontier nodes (or destination set). This is the set of nodes which should 199/// be propagated to the next step / builder. They are the nodes which have been 200/// added to the builder (either as the input node set or as the newly 201/// constructed nodes) but did not have any outgoing transitions added. 202class NodeBuilder { 203protected: 204 const NodeBuilderContext &C; 205 206 /// Specifies if the builder results have been finalized. For example, if it 207 /// is set to false, autotransitions are yet to be generated. 208 bool Finalized; 209 bool HasGeneratedNodes; 210 /// \brief The frontier set - a set of nodes which need to be propagated after 211 /// the builder dies. 212 ExplodedNodeSet &Frontier; 213 214 /// Checkes if the results are ready. 215 virtual bool checkResults() { 216 if (!Finalized) 217 return false; 218 return true; 219 } 220 221 bool hasNoSinksInFrontier() { 222 for (iterator I = Frontier.begin(), E = Frontier.end(); I != E; ++I) { 223 if ((*I)->isSink()) 224 return false; 225 } 226 return true; 227 } 228 229 /// Allow subclasses to finalize results before result_begin() is executed. 230 virtual void finalizeResults() {} 231 232 ExplodedNode *generateNodeImpl(const ProgramPoint &PP, 233 const ProgramState *State, 234 ExplodedNode *Pred, 235 bool MarkAsSink = false); 236 237public: 238 NodeBuilder(ExplodedNode *SrcNode, ExplodedNodeSet &DstSet, 239 const NodeBuilderContext &Ctx, bool F = true) 240 : C(Ctx), Finalized(F), HasGeneratedNodes(false), Frontier(DstSet) { 241 Frontier.Add(SrcNode); 242 } 243 244 NodeBuilder(const ExplodedNodeSet &SrcSet, ExplodedNodeSet &DstSet, 245 const NodeBuilderContext &Ctx, bool F = true) 246 : C(Ctx), Finalized(F), HasGeneratedNodes(false), Frontier(DstSet) { 247 Frontier.insert(SrcSet); 248 assert(hasNoSinksInFrontier()); 249 } 250 251 virtual ~NodeBuilder() {} 252 253 /// \brief Generates a node in the ExplodedGraph. 254 /// 255 /// When a node is marked as sink, the exploration from the node is stopped - 256 /// the node becomes the last node on the path. 257 ExplodedNode *generateNode(const ProgramPoint &PP, 258 const ProgramState *State, 259 ExplodedNode *Pred, 260 bool MarkAsSink = false) { 261 return generateNodeImpl(PP, State, Pred, MarkAsSink); 262 } 263 264 const ExplodedNodeSet &getResults() { 265 finalizeResults(); 266 assert(checkResults()); 267 return Frontier; 268 } 269 270 typedef ExplodedNodeSet::iterator iterator; 271 /// \brief Iterators through the results frontier. 272 inline iterator begin() { 273 finalizeResults(); 274 assert(checkResults()); 275 return Frontier.begin(); 276 } 277 inline iterator end() { 278 finalizeResults(); 279 return Frontier.end(); 280 } 281 282 const NodeBuilderContext &getContext() { return C; } 283 bool hasGeneratedNodes() { return HasGeneratedNodes; } 284 285 void takeNodes(const ExplodedNodeSet &S) { 286 for (ExplodedNodeSet::iterator I = S.begin(), E = S.end(); I != E; ++I ) 287 Frontier.erase(*I); 288 } 289 void takeNodes(ExplodedNode *N) { Frontier.erase(N); } 290 void addNodes(const ExplodedNodeSet &S) { Frontier.insert(S); } 291 void addNodes(ExplodedNode *N) { Frontier.Add(N); } 292}; 293 294/// \class NodeBuilderWithSinks 295/// \brief This node builder keeps track of the generated sink nodes. 296class NodeBuilderWithSinks: public NodeBuilder { 297protected: 298 SmallVector<ExplodedNode*, 2> sinksGenerated; 299 ProgramPoint &Location; 300 301public: 302 NodeBuilderWithSinks(ExplodedNode *Pred, ExplodedNodeSet &DstSet, 303 const NodeBuilderContext &Ctx, ProgramPoint &L) 304 : NodeBuilder(Pred, DstSet, Ctx), Location(L) {} 305 ExplodedNode *generateNode(const ProgramState *State, 306 ExplodedNode *Pred, 307 const ProgramPointTag *Tag = 0, 308 bool MarkAsSink = false) { 309 ProgramPoint LocalLoc = (Tag ? Location.withTag(Tag): Location); 310 311 ExplodedNode *N = generateNodeImpl(LocalLoc, State, Pred, MarkAsSink); 312 if (N && N->isSink()) 313 sinksGenerated.push_back(N); 314 return N; 315 } 316 317 const SmallVectorImpl<ExplodedNode*> &getSinks() const { 318 return sinksGenerated; 319 } 320}; 321 322/// \class StmtNodeBuilder 323/// \brief This builder class is useful for generating nodes that resulted from 324/// visiting a statement. The main difference from it's parent NodeBuilder is 325/// that it creates a statement specific ProgramPoint. 326class StmtNodeBuilder: public NodeBuilder { 327 NodeBuilder *EnclosingBldr; 328public: 329 330 /// \brief Constructs a StmtNodeBuilder. If the builder is going to process 331 /// nodes currently owned by another builder(with larger scope), use 332 /// Enclosing builder to transfer ownership. 333 StmtNodeBuilder(ExplodedNode *SrcNode, ExplodedNodeSet &DstSet, 334 const NodeBuilderContext &Ctx, NodeBuilder *Enclosing = 0) 335 : NodeBuilder(SrcNode, DstSet, Ctx), EnclosingBldr(Enclosing) { 336 if (EnclosingBldr) 337 EnclosingBldr->takeNodes(SrcNode); 338 } 339 340 StmtNodeBuilder(ExplodedNodeSet &SrcSet, ExplodedNodeSet &DstSet, 341 const NodeBuilderContext &Ctx, NodeBuilder *Enclosing = 0) 342 : NodeBuilder(SrcSet, DstSet, Ctx), EnclosingBldr(Enclosing) { 343 if (EnclosingBldr) 344 for (ExplodedNodeSet::iterator I = SrcSet.begin(), 345 E = SrcSet.end(); I != E; ++I ) 346 EnclosingBldr->takeNodes(*I); 347 } 348 349 virtual ~StmtNodeBuilder(); 350 351 ExplodedNode *generateNode(const Stmt *S, 352 ExplodedNode *Pred, 353 const ProgramState *St, 354 bool MarkAsSink = false, 355 const ProgramPointTag *tag = 0, 356 ProgramPoint::Kind K = ProgramPoint::PostStmtKind){ 357 const ProgramPoint &L = ProgramPoint::getProgramPoint(S, K, 358 Pred->getLocationContext(), tag); 359 return generateNodeImpl(L, St, Pred, MarkAsSink); 360 } 361 362 ExplodedNode *generateNode(const ProgramPoint &PP, 363 ExplodedNode *Pred, 364 const ProgramState *State, 365 bool MarkAsSink = false) { 366 return generateNodeImpl(PP, State, Pred, MarkAsSink); 367 } 368}; 369 370class BranchNodeBuilder: public NodeBuilder { 371 const CFGBlock *DstT; 372 const CFGBlock *DstF; 373 374 bool InFeasibleTrue; 375 bool InFeasibleFalse; 376 377public: 378 BranchNodeBuilder(ExplodedNode *SrcNode, ExplodedNodeSet &DstSet, 379 const NodeBuilderContext &C, 380 const CFGBlock *dstT, const CFGBlock *dstF) 381 : NodeBuilder(SrcNode, DstSet, C), DstT(dstT), DstF(dstF), 382 InFeasibleTrue(!DstT), InFeasibleFalse(!DstF) {} 383 384 BranchNodeBuilder(const ExplodedNodeSet &SrcSet, ExplodedNodeSet &DstSet, 385 const NodeBuilderContext &C, 386 const CFGBlock *dstT, const CFGBlock *dstF) 387 : NodeBuilder(SrcSet, DstSet, C), DstT(dstT), DstF(dstF), 388 InFeasibleTrue(!DstT), InFeasibleFalse(!DstF) {} 389 390 ExplodedNode *generateNode(const ProgramState *State, bool branch, 391 ExplodedNode *Pred); 392 393 const CFGBlock *getTargetBlock(bool branch) const { 394 return branch ? DstT : DstF; 395 } 396 397 void markInfeasible(bool branch) { 398 if (branch) 399 InFeasibleTrue = true; 400 else 401 InFeasibleFalse = true; 402 } 403 404 bool isFeasible(bool branch) { 405 return branch ? !InFeasibleTrue : !InFeasibleFalse; 406 } 407}; 408 409class IndirectGotoNodeBuilder { 410 CoreEngine& Eng; 411 const CFGBlock *Src; 412 const CFGBlock &DispatchBlock; 413 const Expr *E; 414 ExplodedNode *Pred; 415 416public: 417 IndirectGotoNodeBuilder(ExplodedNode *pred, const CFGBlock *src, 418 const Expr *e, const CFGBlock *dispatch, CoreEngine* eng) 419 : Eng(*eng), Src(src), DispatchBlock(*dispatch), E(e), Pred(pred) {} 420 421 class iterator { 422 CFGBlock::const_succ_iterator I; 423 424 friend class IndirectGotoNodeBuilder; 425 iterator(CFGBlock::const_succ_iterator i) : I(i) {} 426 public: 427 428 iterator &operator++() { ++I; return *this; } 429 bool operator!=(const iterator &X) const { return I != X.I; } 430 431 const LabelDecl *getLabel() const { 432 return llvm::cast<LabelStmt>((*I)->getLabel())->getDecl(); 433 } 434 435 const CFGBlock *getBlock() const { 436 return *I; 437 } 438 }; 439 440 iterator begin() { return iterator(DispatchBlock.succ_begin()); } 441 iterator end() { return iterator(DispatchBlock.succ_end()); } 442 443 ExplodedNode *generateNode(const iterator &I, 444 const ProgramState *State, 445 bool isSink = false); 446 447 const Expr *getTarget() const { return E; } 448 449 const ProgramState *getState() const { return Pred->State; } 450}; 451 452class SwitchNodeBuilder { 453 CoreEngine& Eng; 454 const CFGBlock *Src; 455 const Expr *Condition; 456 ExplodedNode *Pred; 457 458public: 459 SwitchNodeBuilder(ExplodedNode *pred, const CFGBlock *src, 460 const Expr *condition, CoreEngine* eng) 461 : Eng(*eng), Src(src), Condition(condition), Pred(pred) {} 462 463 class iterator { 464 CFGBlock::const_succ_reverse_iterator I; 465 466 friend class SwitchNodeBuilder; 467 iterator(CFGBlock::const_succ_reverse_iterator i) : I(i) {} 468 469 public: 470 iterator &operator++() { ++I; return *this; } 471 bool operator!=(const iterator &X) const { return I != X.I; } 472 bool operator==(const iterator &X) const { return I == X.I; } 473 474 const CaseStmt *getCase() const { 475 return llvm::cast<CaseStmt>((*I)->getLabel()); 476 } 477 478 const CFGBlock *getBlock() const { 479 return *I; 480 } 481 }; 482 483 iterator begin() { return iterator(Src->succ_rbegin()+1); } 484 iterator end() { return iterator(Src->succ_rend()); } 485 486 const SwitchStmt *getSwitch() const { 487 return llvm::cast<SwitchStmt>(Src->getTerminator()); 488 } 489 490 ExplodedNode *generateCaseStmtNode(const iterator &I, 491 const ProgramState *State); 492 493 ExplodedNode *generateDefaultCaseNode(const ProgramState *State, 494 bool isSink = false); 495 496 const Expr *getCondition() const { return Condition; } 497 498 const ProgramState *getState() const { return Pred->State; } 499}; 500 501class CallEnterNodeBuilder { 502 CoreEngine &Eng; 503 504 const ExplodedNode *Pred; 505 506 // The call site. For implicit automatic object dtor, this is the trigger 507 // statement. 508 const Stmt *CE; 509 510 // The context of the callee. 511 const StackFrameContext *CalleeCtx; 512 513 // The parent block of the CallExpr. 514 const CFGBlock *Block; 515 516 // The CFGBlock index of the CallExpr. 517 unsigned Index; 518 519public: 520 CallEnterNodeBuilder(CoreEngine &eng, const ExplodedNode *pred, 521 const Stmt *s, const StackFrameContext *callee, 522 const CFGBlock *blk, unsigned idx) 523 : Eng(eng), Pred(pred), CE(s), CalleeCtx(callee), Block(blk), Index(idx) {} 524 525 const ProgramState *getState() const { return Pred->getState(); } 526 527 const LocationContext *getLocationContext() const { 528 return Pred->getLocationContext(); 529 } 530 531 const Stmt *getCallExpr() const { return CE; } 532 533 const StackFrameContext *getCalleeContext() const { return CalleeCtx; } 534 535 const CFGBlock *getBlock() const { return Block; } 536 537 unsigned getIndex() const { return Index; } 538 539 void generateNode(const ProgramState *state); 540}; 541 542class CallExitNodeBuilder { 543 CoreEngine &Eng; 544 const ExplodedNode *Pred; 545 546public: 547 CallExitNodeBuilder(CoreEngine &eng, const ExplodedNode *pred) 548 : Eng(eng), Pred(pred) {} 549 550 const ExplodedNode *getPredecessor() const { return Pred; } 551 552 const ProgramState *getState() const { return Pred->getState(); } 553 554 void generateNode(const ProgramState *state); 555}; 556 557} // end GR namespace 558 559} // end clang namespace 560 561#endif 562