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