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