CoreEngine.h revision dd7ddf2b2296f95e7591ca3f9791f0eb9a15ee42
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 IndirectGotoNodeBuilder; 46 friend class SwitchNodeBuilder; 47 friend class EndOfFunctionNodeBuilder; 48 friend class CallEnterNodeBuilder; 49 friend class CallExitNodeBuilder; 50 friend class ExprEngine; 51 52public: 53 typedef std::vector<std::pair<BlockEdge, const ExplodedNode*> > 54 BlocksExhausted; 55 56 typedef std::vector<std::pair<const CFGBlock*, const ExplodedNode*> > 57 BlocksAborted; 58 59private: 60 61 SubEngine& SubEng; 62 63 /// G - The simulation graph. Each node is a (location,state) pair. 64 llvm::OwningPtr<ExplodedGraph> G; 65 66 /// WList - A set of queued nodes that need to be processed by the 67 /// worklist algorithm. It is up to the implementation of WList to decide 68 /// the order that nodes are processed. 69 WorkList* WList; 70 71 /// BCounterFactory - A factory object for created BlockCounter objects. 72 /// These are used to record for key nodes in the ExplodedGraph the 73 /// number of times different CFGBlocks have been visited along a path. 74 BlockCounter::Factory BCounterFactory; 75 76 /// The locations where we stopped doing work because we visited a location 77 /// too many times. 78 BlocksExhausted blocksExhausted; 79 80 /// The locations where we stopped because the engine aborted analysis, 81 /// usually because it could not reason about something. 82 BlocksAborted blocksAborted; 83 84 void generateNode(const ProgramPoint &Loc, 85 const ProgramState *State, 86 ExplodedNode *Pred); 87 88 void HandleBlockEdge(const BlockEdge &E, ExplodedNode *Pred); 89 void HandleBlockEntrance(const BlockEntrance &E, ExplodedNode *Pred); 90 void HandleBlockExit(const CFGBlock *B, ExplodedNode *Pred); 91 void HandlePostStmt(const CFGBlock *B, unsigned StmtIdx, ExplodedNode *Pred); 92 93 void HandleBranch(const Stmt *Cond, const Stmt *Term, const CFGBlock *B, 94 ExplodedNode *Pred); 95 void HandleCallEnter(const CallEnter &L, const CFGBlock *Block, 96 unsigned Index, ExplodedNode *Pred); 97 void HandleCallExit(const CallExit &L, ExplodedNode *Pred); 98 99private: 100 CoreEngine(const CoreEngine&); // Do not implement. 101 CoreEngine& operator=(const CoreEngine&); 102 103 void enqueueStmtNode(ExplodedNode *N, 104 const CFGBlock *Block, unsigned Idx); 105 106public: 107 /// Construct a CoreEngine object to analyze the provided CFG using 108 /// a DFS exploration of the exploded graph. 109 CoreEngine(SubEngine& subengine) 110 : SubEng(subengine), G(new ExplodedGraph()), 111 WList(WorkList::makeBFS()), 112 BCounterFactory(G->getAllocator()) {} 113 114 /// Construct a CoreEngine object to analyze the provided CFG and to 115 /// use the provided worklist object to execute the worklist algorithm. 116 /// The CoreEngine object assumes ownership of 'wlist'. 117 CoreEngine(WorkList* wlist, SubEngine& subengine) 118 : SubEng(subengine), G(new ExplodedGraph()), WList(wlist), 119 BCounterFactory(G->getAllocator()) {} 120 121 ~CoreEngine() { 122 delete WList; 123 } 124 125 /// getGraph - Returns the exploded graph. 126 ExplodedGraph& getGraph() { return *G.get(); } 127 128 /// takeGraph - Returns the exploded graph. Ownership of the graph is 129 /// transferred to the caller. 130 ExplodedGraph* takeGraph() { return G.take(); } 131 132 /// ExecuteWorkList - Run the worklist algorithm for a maximum number of 133 /// steps. Returns true if there is still simulation state on the worklist. 134 bool ExecuteWorkList(const LocationContext *L, unsigned Steps, 135 const ProgramState *InitState); 136 void ExecuteWorkListWithInitialState(const LocationContext *L, 137 unsigned Steps, 138 const ProgramState *InitState, 139 ExplodedNodeSet &Dst); 140 141 // Functions for external checking of whether we have unfinished work 142 bool wasBlockAborted() const { return !blocksAborted.empty(); } 143 bool wasBlocksExhausted() const { return !blocksExhausted.empty(); } 144 bool hasWorkRemaining() const { return wasBlocksExhausted() || 145 WList->hasWork() || 146 wasBlockAborted(); } 147 148 /// Inform the CoreEngine that a basic block was aborted because 149 /// it could not be completely analyzed. 150 void addAbortedBlock(const ExplodedNode *node, const CFGBlock *block) { 151 blocksAborted.push_back(std::make_pair(block, node)); 152 } 153 154 WorkList *getWorkList() const { return WList; } 155 156 BlocksExhausted::const_iterator blocks_exhausted_begin() const { 157 return blocksExhausted.begin(); 158 } 159 BlocksExhausted::const_iterator blocks_exhausted_end() const { 160 return blocksExhausted.end(); 161 } 162 BlocksAborted::const_iterator blocks_aborted_begin() const { 163 return blocksAborted.begin(); 164 } 165 BlocksAborted::const_iterator blocks_aborted_end() const { 166 return blocksAborted.end(); 167 } 168 169 /// \brief Enqueue the given set of nodes onto the work list. 170 void enqueue(ExplodedNodeSet &NB); 171 172 /// \brief Enqueue nodes that were created as a result of processing 173 /// a statement onto the work list. 174 void enqueue(ExplodedNodeSet &Set, const CFGBlock *Block, unsigned Idx); 175}; 176 177// TODO: Turn into a calss. 178struct NodeBuilderContext { 179 CoreEngine &Eng; 180 const CFGBlock *Block; 181 ExplodedNode *Pred; 182 NodeBuilderContext(CoreEngine &E, const CFGBlock *B, ExplodedNode *N) 183 : Eng(E), Block(B), Pred(N) { assert(B); assert(!N->isSink()); } 184 185 ExplodedNode *getPred() const { return Pred; } 186 187 /// \brief Return the CFGBlock associated with this builder. 188 const CFGBlock *getBlock() const { return Block; } 189 190 /// \brief Returns the number of times the current basic block has been 191 /// visited on the exploded graph path. 192 unsigned getCurrentBlockCount() const { 193 return Eng.WList->getBlockCounter().getNumVisited( 194 Pred->getLocationContext()->getCurrentStackFrame(), 195 Block->getBlockID()); 196 } 197}; 198 199/// \class NodeBuilder 200/// \brief This is the simplest builder which generates nodes in the 201/// ExplodedGraph. 202/// 203/// The main benefit of the builder is that it automatically tracks the 204/// frontier nodes (or destination set). This is the set of nodes which should 205/// be propagated to the next step / builder. They are the nodes which have been 206/// added to the builder (either as the input node set or as the newly 207/// constructed nodes) but did not have any outgoing transitions added. 208class NodeBuilder { 209protected: 210 const NodeBuilderContext &C; 211 212 /// Specifies if the builder results have been finalized. For example, if it 213 /// is set to false, autotransitions are yet to be generated. 214 bool Finalized; 215 bool HasGeneratedNodes; 216 /// \brief The frontier set - a set of nodes which need to be propagated after 217 /// the builder dies. 218 ExplodedNodeSet &Frontier; 219 220 /// Checkes if the results are ready. 221 virtual bool checkResults() { 222 if (!Finalized) 223 return false; 224 return true; 225 } 226 227 bool hasNoSinksInFrontier() { 228 for (iterator I = Frontier.begin(), E = Frontier.end(); I != E; ++I) { 229 if ((*I)->isSink()) 230 return false; 231 } 232 return true; 233 } 234 235 /// Allow subclasses to finalize results before result_begin() is executed. 236 virtual void finalizeResults() {} 237 238 ExplodedNode *generateNodeImpl(const ProgramPoint &PP, 239 const ProgramState *State, 240 ExplodedNode *Pred, 241 bool MarkAsSink = false); 242 243public: 244 NodeBuilder(ExplodedNode *SrcNode, ExplodedNodeSet &DstSet, 245 const NodeBuilderContext &Ctx, bool F = true) 246 : C(Ctx), Finalized(F), HasGeneratedNodes(false), Frontier(DstSet) { 247 Frontier.Add(SrcNode); 248 } 249 250 NodeBuilder(const ExplodedNodeSet &SrcSet, ExplodedNodeSet &DstSet, 251 const NodeBuilderContext &Ctx, bool F = true) 252 : C(Ctx), Finalized(F), HasGeneratedNodes(false), Frontier(DstSet) { 253 Frontier.insert(SrcSet); 254 assert(hasNoSinksInFrontier()); 255 } 256 257 virtual ~NodeBuilder() {} 258 259 /// \brief Generates a node in the ExplodedGraph. 260 /// 261 /// When a node is marked as sink, the exploration from the node is stopped - 262 /// the node becomes the last node on the path. 263 ExplodedNode *generateNode(const ProgramPoint &PP, 264 const ProgramState *State, 265 ExplodedNode *Pred, 266 bool MarkAsSink = false) { 267 return generateNodeImpl(PP, State, Pred, MarkAsSink); 268 } 269 270 const ExplodedNodeSet &getResults() { 271 finalizeResults(); 272 assert(checkResults()); 273 return Frontier; 274 } 275 276 typedef ExplodedNodeSet::iterator iterator; 277 /// \brief Iterators through the results frontier. 278 inline iterator begin() { 279 finalizeResults(); 280 assert(checkResults()); 281 return Frontier.begin(); 282 } 283 inline iterator end() { 284 finalizeResults(); 285 return Frontier.end(); 286 } 287 288 const NodeBuilderContext &getContext() { return C; } 289 bool hasGeneratedNodes() { return HasGeneratedNodes; } 290 291 void takeNodes(const ExplodedNodeSet &S) { 292 for (ExplodedNodeSet::iterator I = S.begin(), E = S.end(); I != E; ++I ) 293 Frontier.erase(*I); 294 } 295 void takeNodes(ExplodedNode *N) { Frontier.erase(N); } 296 void addNodes(const ExplodedNodeSet &S) { Frontier.insert(S); } 297 void addNodes(ExplodedNode *N) { Frontier.Add(N); } 298}; 299 300/// \class NodeBuilderWithSinks 301/// \brief This node builder keeps track of the generated sink nodes. 302class NodeBuilderWithSinks: public NodeBuilder { 303protected: 304 SmallVector<ExplodedNode*, 2> sinksGenerated; 305 ProgramPoint &Location; 306 307public: 308 NodeBuilderWithSinks(ExplodedNode *Pred, ExplodedNodeSet &DstSet, 309 const NodeBuilderContext &Ctx, ProgramPoint &L) 310 : NodeBuilder(Pred, DstSet, Ctx), Location(L) {} 311 ExplodedNode *generateNode(const ProgramState *State, 312 ExplodedNode *Pred, 313 const ProgramPointTag *Tag = 0, 314 bool MarkAsSink = false) { 315 ProgramPoint LocalLoc = (Tag ? Location.withTag(Tag): Location); 316 317 ExplodedNode *N = generateNodeImpl(LocalLoc, State, Pred, MarkAsSink); 318 if (N && N->isSink()) 319 sinksGenerated.push_back(N); 320 return N; 321 } 322 323 const SmallVectorImpl<ExplodedNode*> &getSinks() const { 324 return sinksGenerated; 325 } 326}; 327 328/// \class StmtNodeBuilder 329/// \brief This builder class is useful for generating nodes that resulted from 330/// visiting a statement. The main difference from it's parent NodeBuilder is 331/// that it creates a statement specific ProgramPoint. 332class StmtNodeBuilder: public NodeBuilder { 333 NodeBuilder *EnclosingBldr; 334public: 335 336 /// \brief Constructs a StmtNodeBuilder. If the builder is going to process 337 /// nodes currently owned by another builder(with larger scope), use 338 /// Enclosing builder to transfer ownership. 339 StmtNodeBuilder(ExplodedNode *SrcNode, ExplodedNodeSet &DstSet, 340 const NodeBuilderContext &Ctx, NodeBuilder *Enclosing = 0) 341 : NodeBuilder(SrcNode, DstSet, Ctx), EnclosingBldr(Enclosing) { 342 if (EnclosingBldr) 343 EnclosingBldr->takeNodes(SrcNode); 344 } 345 346 StmtNodeBuilder(ExplodedNodeSet &SrcSet, ExplodedNodeSet &DstSet, 347 const NodeBuilderContext &Ctx, NodeBuilder *Enclosing = 0) 348 : NodeBuilder(SrcSet, DstSet, Ctx), EnclosingBldr(Enclosing) { 349 if (EnclosingBldr) 350 for (ExplodedNodeSet::iterator I = SrcSet.begin(), 351 E = SrcSet.end(); I != E; ++I ) 352 EnclosingBldr->takeNodes(*I); 353 } 354 355 virtual ~StmtNodeBuilder(); 356 357 ExplodedNode *generateNode(const Stmt *S, 358 ExplodedNode *Pred, 359 const ProgramState *St, 360 bool MarkAsSink = false, 361 const ProgramPointTag *tag = 0, 362 ProgramPoint::Kind K = ProgramPoint::PostStmtKind){ 363 const ProgramPoint &L = ProgramPoint::getProgramPoint(S, K, 364 Pred->getLocationContext(), tag); 365 return generateNodeImpl(L, St, Pred, MarkAsSink); 366 } 367 368 ExplodedNode *generateNode(const ProgramPoint &PP, 369 ExplodedNode *Pred, 370 const ProgramState *State, 371 bool MarkAsSink = false) { 372 return generateNodeImpl(PP, State, Pred, MarkAsSink); 373 } 374}; 375 376class BranchNodeBuilder: public NodeBuilder { 377 const CFGBlock *DstT; 378 const CFGBlock *DstF; 379 380 bool InFeasibleTrue; 381 bool InFeasibleFalse; 382 383public: 384 BranchNodeBuilder(ExplodedNode *SrcNode, ExplodedNodeSet &DstSet, 385 const NodeBuilderContext &C, 386 const CFGBlock *dstT, const CFGBlock *dstF) 387 : NodeBuilder(SrcNode, DstSet, C), DstT(dstT), DstF(dstF), 388 InFeasibleTrue(!DstT), InFeasibleFalse(!DstF) {} 389 390 BranchNodeBuilder(const ExplodedNodeSet &SrcSet, ExplodedNodeSet &DstSet, 391 const NodeBuilderContext &C, 392 const CFGBlock *dstT, const CFGBlock *dstF) 393 : NodeBuilder(SrcSet, DstSet, C), DstT(dstT), DstF(dstF), 394 InFeasibleTrue(!DstT), InFeasibleFalse(!DstF) {} 395 396 ExplodedNode *generateNode(const ProgramState *State, bool branch, 397 ExplodedNode *Pred); 398 399 const CFGBlock *getTargetBlock(bool branch) const { 400 return branch ? DstT : DstF; 401 } 402 403 void markInfeasible(bool branch) { 404 if (branch) 405 InFeasibleTrue = true; 406 else 407 InFeasibleFalse = true; 408 } 409 410 bool isFeasible(bool branch) { 411 return branch ? !InFeasibleTrue : !InFeasibleFalse; 412 } 413}; 414 415class IndirectGotoNodeBuilder { 416 CoreEngine& Eng; 417 const CFGBlock *Src; 418 const CFGBlock &DispatchBlock; 419 const Expr *E; 420 ExplodedNode *Pred; 421 422public: 423 IndirectGotoNodeBuilder(ExplodedNode *pred, const CFGBlock *src, 424 const Expr *e, const CFGBlock *dispatch, CoreEngine* eng) 425 : Eng(*eng), Src(src), DispatchBlock(*dispatch), E(e), Pred(pred) {} 426 427 class iterator { 428 CFGBlock::const_succ_iterator I; 429 430 friend class IndirectGotoNodeBuilder; 431 iterator(CFGBlock::const_succ_iterator i) : I(i) {} 432 public: 433 434 iterator &operator++() { ++I; return *this; } 435 bool operator!=(const iterator &X) const { return I != X.I; } 436 437 const LabelDecl *getLabel() const { 438 return llvm::cast<LabelStmt>((*I)->getLabel())->getDecl(); 439 } 440 441 const CFGBlock *getBlock() const { 442 return *I; 443 } 444 }; 445 446 iterator begin() { return iterator(DispatchBlock.succ_begin()); } 447 iterator end() { return iterator(DispatchBlock.succ_end()); } 448 449 ExplodedNode *generateNode(const iterator &I, 450 const ProgramState *State, 451 bool isSink = false); 452 453 const Expr *getTarget() const { return E; } 454 455 const ProgramState *getState() const { return Pred->State; } 456}; 457 458class SwitchNodeBuilder { 459 CoreEngine& Eng; 460 const CFGBlock *Src; 461 const Expr *Condition; 462 ExplodedNode *Pred; 463 464public: 465 SwitchNodeBuilder(ExplodedNode *pred, const CFGBlock *src, 466 const Expr *condition, CoreEngine* eng) 467 : Eng(*eng), Src(src), Condition(condition), Pred(pred) {} 468 469 class iterator { 470 CFGBlock::const_succ_reverse_iterator I; 471 472 friend class SwitchNodeBuilder; 473 iterator(CFGBlock::const_succ_reverse_iterator i) : I(i) {} 474 475 public: 476 iterator &operator++() { ++I; return *this; } 477 bool operator!=(const iterator &X) const { return I != X.I; } 478 bool operator==(const iterator &X) const { return I == X.I; } 479 480 const CaseStmt *getCase() const { 481 return llvm::cast<CaseStmt>((*I)->getLabel()); 482 } 483 484 const CFGBlock *getBlock() const { 485 return *I; 486 } 487 }; 488 489 iterator begin() { return iterator(Src->succ_rbegin()+1); } 490 iterator end() { return iterator(Src->succ_rend()); } 491 492 const SwitchStmt *getSwitch() const { 493 return llvm::cast<SwitchStmt>(Src->getTerminator()); 494 } 495 496 ExplodedNode *generateCaseStmtNode(const iterator &I, 497 const ProgramState *State); 498 499 ExplodedNode *generateDefaultCaseNode(const ProgramState *State, 500 bool isSink = false); 501 502 const Expr *getCondition() const { return Condition; } 503 504 const ProgramState *getState() const { return Pred->State; } 505}; 506 507class CallEnterNodeBuilder { 508 CoreEngine &Eng; 509 510 const ExplodedNode *Pred; 511 512 // The call site. For implicit automatic object dtor, this is the trigger 513 // statement. 514 const Stmt *CE; 515 516 // The context of the callee. 517 const StackFrameContext *CalleeCtx; 518 519 // The parent block of the CallExpr. 520 const CFGBlock *Block; 521 522 // The CFGBlock index of the CallExpr. 523 unsigned Index; 524 525public: 526 CallEnterNodeBuilder(CoreEngine &eng, const ExplodedNode *pred, 527 const Stmt *s, const StackFrameContext *callee, 528 const CFGBlock *blk, unsigned idx) 529 : Eng(eng), Pred(pred), CE(s), CalleeCtx(callee), Block(blk), Index(idx) {} 530 531 const ProgramState *getState() const { return Pred->getState(); } 532 533 const LocationContext *getLocationContext() const { 534 return Pred->getLocationContext(); 535 } 536 537 const Stmt *getCallExpr() const { return CE; } 538 539 const StackFrameContext *getCalleeContext() const { return CalleeCtx; } 540 541 const CFGBlock *getBlock() const { return Block; } 542 543 unsigned getIndex() const { return Index; } 544 545 void generateNode(const ProgramState *state); 546}; 547 548class CallExitNodeBuilder { 549 CoreEngine &Eng; 550 const ExplodedNode *Pred; 551 552public: 553 CallExitNodeBuilder(CoreEngine &eng, const ExplodedNode *pred) 554 : Eng(eng), Pred(pred) {} 555 556 const ExplodedNode *getPredecessor() const { return Pred; } 557 558 const ProgramState *getState() const { return Pred->getState(); } 559 560 void generateNode(const ProgramState *state); 561}; 562 563} // end GR namespace 564 565} // end clang namespace 566 567#endif 568