CoreEngine.h revision 253955ca25c7e7049963b5db613c0cd15d66e4f8
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/Analysis/AnalysisContext.h" 20#include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h" 21#include "clang/StaticAnalyzer/Core/PathSensitive/WorkList.h" 22#include "clang/StaticAnalyzer/Core/PathSensitive/BlockCounter.h" 23#include "llvm/ADT/OwningPtr.h" 24 25namespace clang { 26 27class ProgramPointTag; 28 29namespace ento { 30 31class NodeBuilder; 32 33//===----------------------------------------------------------------------===// 34/// CoreEngine - Implements the core logic of the graph-reachability 35/// analysis. It traverses the CFG and generates the ExplodedGraph. 36/// Program "states" are treated as opaque void pointers. 37/// The template class CoreEngine (which subclasses CoreEngine) 38/// provides the matching component to the engine that knows the actual types 39/// for states. Note that this engine only dispatches to transfer functions 40/// at the statement and block-level. The analyses themselves must implement 41/// any transfer function logic and the sub-expression level (if any). 42class CoreEngine { 43 friend struct NodeBuilderContext; 44 friend class NodeBuilder; 45 friend class ExprEngine; 46 friend class CommonNodeBuilder; 47 friend class IndirectGotoNodeBuilder; 48 friend class SwitchNodeBuilder; 49 friend class EndOfFunctionNodeBuilder; 50public: 51 typedef std::vector<std::pair<BlockEdge, const ExplodedNode*> > 52 BlocksExhausted; 53 54 typedef std::vector<std::pair<const CFGBlock*, const ExplodedNode*> > 55 BlocksAborted; 56 57private: 58 59 SubEngine& SubEng; 60 61 /// G - The simulation graph. Each node is a (location,state) pair. 62 OwningPtr<ExplodedGraph> G; 63 64 /// WList - A set of queued nodes that need to be processed by the 65 /// worklist algorithm. It is up to the implementation of WList to decide 66 /// the order that nodes are processed. 67 WorkList* WList; 68 69 /// BCounterFactory - A factory object for created BlockCounter objects. 70 /// These are used to record for key nodes in the ExplodedGraph the 71 /// number of times different CFGBlocks have been visited along a path. 72 BlockCounter::Factory BCounterFactory; 73 74 /// The locations where we stopped doing work because we visited a location 75 /// too many times. 76 BlocksExhausted blocksExhausted; 77 78 /// The locations where we stopped because the engine aborted analysis, 79 /// usually because it could not reason about something. 80 BlocksAborted blocksAborted; 81 82 /// The functions which have been analyzed through inlining. This is owned by 83 /// AnalysisConsumer. It can be null. 84 SetOfDecls *AnalyzedCallees; 85 86 void generateNode(const ProgramPoint &Loc, 87 ProgramStateRef State, 88 ExplodedNode *Pred); 89 90 void HandleBlockEdge(const BlockEdge &E, ExplodedNode *Pred); 91 void HandleBlockEntrance(const BlockEntrance &E, ExplodedNode *Pred); 92 void HandleBlockExit(const CFGBlock *B, ExplodedNode *Pred); 93 void HandlePostStmt(const CFGBlock *B, unsigned StmtIdx, ExplodedNode *Pred); 94 95 void HandleBranch(const Stmt *Cond, const Stmt *Term, const CFGBlock *B, 96 ExplodedNode *Pred); 97 98private: 99 CoreEngine(const CoreEngine&); // Do not implement. 100 CoreEngine& operator=(const CoreEngine&); 101 102 ExplodedNode *generateCallExitNode(ExplodedNode *N); 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, SetOfDecls *VisitedCallees) 108 : SubEng(subengine), G(new ExplodedGraph()), 109 WList(WorkList::makeBFS()), 110 BCounterFactory(G->getAllocator()), 111 AnalyzedCallees(VisitedCallees) {} 112 113 ~CoreEngine() { 114 delete WList; 115 } 116 117 /// getGraph - Returns the exploded graph. 118 ExplodedGraph& getGraph() { return *G.get(); } 119 120 /// takeGraph - Returns the exploded graph. Ownership of the graph is 121 /// transferred to the caller. 122 ExplodedGraph* takeGraph() { return G.take(); } 123 124 /// ExecuteWorkList - Run the worklist algorithm for a maximum number of 125 /// steps. Returns true if there is still simulation state on the worklist. 126 bool ExecuteWorkList(const LocationContext *L, unsigned Steps, 127 ProgramStateRef InitState); 128 /// Returns true if there is still simulation state on the worklist. 129 bool ExecuteWorkListWithInitialState(const LocationContext *L, 130 unsigned Steps, 131 ProgramStateRef InitState, 132 ExplodedNodeSet &Dst); 133 134 /// Dispatch the work list item based on the given location information. 135 /// Use Pred parameter as the predecessor state. 136 void dispatchWorkItem(ExplodedNode* Pred, ProgramPoint Loc, 137 const WorkListUnit& WU); 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 /// \brief Enqueue the given set of nodes onto the work list. 168 void enqueue(ExplodedNodeSet &Set); 169 170 /// \brief Enqueue nodes that were created as a result of processing 171 /// a statement onto the work list. 172 void enqueue(ExplodedNodeSet &Set, const CFGBlock *Block, unsigned Idx); 173 174 /// \brief enqueue the nodes corresponding to the end of function onto the 175 /// end of path / work list. 176 void enqueueEndOfFunction(ExplodedNodeSet &Set); 177 178 /// \brief Enqueue a single node created as a result of statement processing. 179 void enqueueStmtNode(ExplodedNode *N, const CFGBlock *Block, unsigned Idx); 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 { 214 virtual void anchor(); 215protected: 216 const NodeBuilderContext &C; 217 218 /// Specifies if the builder results have been finalized. For example, if it 219 /// is set to false, autotransitions are yet to be generated. 220 bool Finalized; 221 bool HasGeneratedNodes; 222 /// \brief The frontier set - a set of nodes which need to be propagated after 223 /// the builder dies. 224 ExplodedNodeSet &Frontier; 225 226 /// Checkes if the results are ready. 227 virtual bool checkResults() { 228 if (!Finalized) 229 return false; 230 return true; 231 } 232 233 bool hasNoSinksInFrontier() { 234 for (iterator I = Frontier.begin(), E = Frontier.end(); I != E; ++I) { 235 if ((*I)->isSink()) 236 return false; 237 } 238 return true; 239 } 240 241 /// Allow subclasses to finalize results before result_begin() is executed. 242 virtual void finalizeResults() {} 243 244 ExplodedNode *generateNodeImpl(const ProgramPoint &PP, 245 ProgramStateRef State, 246 ExplodedNode *Pred, 247 bool MarkAsSink = false); 248 249public: 250 NodeBuilder(ExplodedNode *SrcNode, ExplodedNodeSet &DstSet, 251 const NodeBuilderContext &Ctx, bool F = true) 252 : C(Ctx), Finalized(F), HasGeneratedNodes(false), Frontier(DstSet) { 253 Frontier.Add(SrcNode); 254 } 255 256 NodeBuilder(const ExplodedNodeSet &SrcSet, ExplodedNodeSet &DstSet, 257 const NodeBuilderContext &Ctx, bool F = true) 258 : C(Ctx), Finalized(F), HasGeneratedNodes(false), Frontier(DstSet) { 259 Frontier.insert(SrcSet); 260 assert(hasNoSinksInFrontier()); 261 } 262 263 virtual ~NodeBuilder() {} 264 265 /// \brief Generates a node in the ExplodedGraph. 266 /// 267 /// When a node is marked as sink, the exploration from the node is stopped - 268 /// the node becomes the last node on the path. 269 ExplodedNode *generateNode(const ProgramPoint &PP, 270 ProgramStateRef State, 271 ExplodedNode *Pred, 272 bool MarkAsSink = false) { 273 return generateNodeImpl(PP, State, Pred, MarkAsSink); 274 } 275 276 const ExplodedNodeSet &getResults() { 277 finalizeResults(); 278 assert(checkResults()); 279 return Frontier; 280 } 281 282 typedef ExplodedNodeSet::iterator iterator; 283 /// \brief Iterators through the results frontier. 284 inline iterator begin() { 285 finalizeResults(); 286 assert(checkResults()); 287 return Frontier.begin(); 288 } 289 inline iterator end() { 290 finalizeResults(); 291 return Frontier.end(); 292 } 293 294 const NodeBuilderContext &getContext() { return C; } 295 bool hasGeneratedNodes() { return HasGeneratedNodes; } 296 297 void takeNodes(const ExplodedNodeSet &S) { 298 for (ExplodedNodeSet::iterator I = S.begin(), E = S.end(); I != E; ++I ) 299 Frontier.erase(*I); 300 } 301 void takeNodes(ExplodedNode *N) { Frontier.erase(N); } 302 void addNodes(const ExplodedNodeSet &S) { Frontier.insert(S); } 303 void addNodes(ExplodedNode *N) { Frontier.Add(N); } 304}; 305 306/// \class NodeBuilderWithSinks 307/// \brief This node builder keeps track of the generated sink nodes. 308class NodeBuilderWithSinks: public NodeBuilder { 309 virtual void anchor(); 310protected: 311 SmallVector<ExplodedNode*, 2> sinksGenerated; 312 ProgramPoint &Location; 313 314public: 315 NodeBuilderWithSinks(ExplodedNode *Pred, ExplodedNodeSet &DstSet, 316 const NodeBuilderContext &Ctx, ProgramPoint &L) 317 : NodeBuilder(Pred, DstSet, Ctx), Location(L) {} 318 ExplodedNode *generateNode(ProgramStateRef State, 319 ExplodedNode *Pred, 320 const ProgramPointTag *Tag = 0, 321 bool MarkAsSink = false) { 322 ProgramPoint LocalLoc = (Tag ? Location.withTag(Tag): Location); 323 324 ExplodedNode *N = generateNodeImpl(LocalLoc, State, Pred, MarkAsSink); 325 if (N && N->isSink()) 326 sinksGenerated.push_back(N); 327 return N; 328 } 329 330 const SmallVectorImpl<ExplodedNode*> &getSinks() const { 331 return sinksGenerated; 332 } 333}; 334 335/// \class StmtNodeBuilder 336/// \brief This builder class is useful for generating nodes that resulted from 337/// visiting a statement. The main difference from it's parent NodeBuilder is 338/// that it creates a statement specific ProgramPoint. 339class StmtNodeBuilder: public NodeBuilder { 340 NodeBuilder *EnclosingBldr; 341public: 342 343 /// \brief Constructs a StmtNodeBuilder. If the builder is going to process 344 /// nodes currently owned by another builder(with larger scope), use 345 /// Enclosing builder to transfer ownership. 346 StmtNodeBuilder(ExplodedNode *SrcNode, ExplodedNodeSet &DstSet, 347 const NodeBuilderContext &Ctx, NodeBuilder *Enclosing = 0) 348 : NodeBuilder(SrcNode, DstSet, Ctx), EnclosingBldr(Enclosing) { 349 if (EnclosingBldr) 350 EnclosingBldr->takeNodes(SrcNode); 351 } 352 353 StmtNodeBuilder(ExplodedNodeSet &SrcSet, ExplodedNodeSet &DstSet, 354 const NodeBuilderContext &Ctx, NodeBuilder *Enclosing = 0) 355 : NodeBuilder(SrcSet, DstSet, Ctx), EnclosingBldr(Enclosing) { 356 if (EnclosingBldr) 357 for (ExplodedNodeSet::iterator I = SrcSet.begin(), 358 E = SrcSet.end(); I != E; ++I ) 359 EnclosingBldr->takeNodes(*I); 360 } 361 362 virtual ~StmtNodeBuilder(); 363 364 ExplodedNode *generateNode(const Stmt *S, 365 ExplodedNode *Pred, 366 ProgramStateRef St, 367 bool MarkAsSink = false, 368 const ProgramPointTag *tag = 0, 369 ProgramPoint::Kind K = ProgramPoint::PostStmtKind){ 370 const ProgramPoint &L = ProgramPoint::getProgramPoint(S, K, 371 Pred->getLocationContext(), tag); 372 return generateNodeImpl(L, St, Pred, MarkAsSink); 373 } 374 375 ExplodedNode *generateNode(const ProgramPoint &PP, 376 ExplodedNode *Pred, 377 ProgramStateRef State, 378 bool MarkAsSink = false) { 379 return generateNodeImpl(PP, State, Pred, MarkAsSink); 380 } 381}; 382 383/// \brief BranchNodeBuilder is responsible for constructing the nodes 384/// corresponding to the two branches of the if statement - true and false. 385class BranchNodeBuilder: public NodeBuilder { 386 virtual void anchor(); 387 const CFGBlock *DstT; 388 const CFGBlock *DstF; 389 390 bool InFeasibleTrue; 391 bool InFeasibleFalse; 392 393public: 394 BranchNodeBuilder(ExplodedNode *SrcNode, ExplodedNodeSet &DstSet, 395 const NodeBuilderContext &C, 396 const CFGBlock *dstT, const CFGBlock *dstF) 397 : NodeBuilder(SrcNode, DstSet, C), DstT(dstT), DstF(dstF), 398 InFeasibleTrue(!DstT), InFeasibleFalse(!DstF) { 399 // The branch node builder does not generate autotransitions. 400 // If there are no successors it means that both branches are infeasible. 401 takeNodes(SrcNode); 402 } 403 404 BranchNodeBuilder(const ExplodedNodeSet &SrcSet, ExplodedNodeSet &DstSet, 405 const NodeBuilderContext &C, 406 const CFGBlock *dstT, const CFGBlock *dstF) 407 : NodeBuilder(SrcSet, DstSet, C), DstT(dstT), DstF(dstF), 408 InFeasibleTrue(!DstT), InFeasibleFalse(!DstF) { 409 takeNodes(SrcSet); 410 } 411 412 ExplodedNode *generateNode(ProgramStateRef State, bool branch, 413 ExplodedNode *Pred); 414 415 const CFGBlock *getTargetBlock(bool branch) const { 416 return branch ? DstT : DstF; 417 } 418 419 void markInfeasible(bool branch) { 420 if (branch) 421 InFeasibleTrue = true; 422 else 423 InFeasibleFalse = true; 424 } 425 426 bool isFeasible(bool branch) { 427 return branch ? !InFeasibleTrue : !InFeasibleFalse; 428 } 429}; 430 431class IndirectGotoNodeBuilder { 432 CoreEngine& Eng; 433 const CFGBlock *Src; 434 const CFGBlock &DispatchBlock; 435 const Expr *E; 436 ExplodedNode *Pred; 437 438public: 439 IndirectGotoNodeBuilder(ExplodedNode *pred, const CFGBlock *src, 440 const Expr *e, const CFGBlock *dispatch, CoreEngine* eng) 441 : Eng(*eng), Src(src), DispatchBlock(*dispatch), E(e), Pred(pred) {} 442 443 class iterator { 444 CFGBlock::const_succ_iterator I; 445 446 friend class IndirectGotoNodeBuilder; 447 iterator(CFGBlock::const_succ_iterator i) : I(i) {} 448 public: 449 450 iterator &operator++() { ++I; return *this; } 451 bool operator!=(const iterator &X) const { return I != X.I; } 452 453 const LabelDecl *getLabel() const { 454 return llvm::cast<LabelStmt>((*I)->getLabel())->getDecl(); 455 } 456 457 const CFGBlock *getBlock() const { 458 return *I; 459 } 460 }; 461 462 iterator begin() { return iterator(DispatchBlock.succ_begin()); } 463 iterator end() { return iterator(DispatchBlock.succ_end()); } 464 465 ExplodedNode *generateNode(const iterator &I, 466 ProgramStateRef State, 467 bool isSink = false); 468 469 const Expr *getTarget() const { return E; } 470 471 ProgramStateRef getState() const { return Pred->State; } 472 473 const LocationContext *getLocationContext() const { 474 return Pred->getLocationContext(); 475 } 476}; 477 478class SwitchNodeBuilder { 479 CoreEngine& Eng; 480 const CFGBlock *Src; 481 const Expr *Condition; 482 ExplodedNode *Pred; 483 484public: 485 SwitchNodeBuilder(ExplodedNode *pred, const CFGBlock *src, 486 const Expr *condition, CoreEngine* eng) 487 : Eng(*eng), Src(src), Condition(condition), Pred(pred) {} 488 489 class iterator { 490 CFGBlock::const_succ_reverse_iterator I; 491 492 friend class SwitchNodeBuilder; 493 iterator(CFGBlock::const_succ_reverse_iterator i) : I(i) {} 494 495 public: 496 iterator &operator++() { ++I; return *this; } 497 bool operator!=(const iterator &X) const { return I != X.I; } 498 bool operator==(const iterator &X) const { return I == X.I; } 499 500 const CaseStmt *getCase() const { 501 return llvm::cast<CaseStmt>((*I)->getLabel()); 502 } 503 504 const CFGBlock *getBlock() const { 505 return *I; 506 } 507 }; 508 509 iterator begin() { return iterator(Src->succ_rbegin()+1); } 510 iterator end() { return iterator(Src->succ_rend()); } 511 512 const SwitchStmt *getSwitch() const { 513 return llvm::cast<SwitchStmt>(Src->getTerminator()); 514 } 515 516 ExplodedNode *generateCaseStmtNode(const iterator &I, 517 ProgramStateRef State); 518 519 ExplodedNode *generateDefaultCaseNode(ProgramStateRef State, 520 bool isSink = false); 521 522 const Expr *getCondition() const { return Condition; } 523 524 ProgramStateRef getState() const { return Pred->State; } 525 526 const LocationContext *getLocationContext() const { 527 return Pred->getLocationContext(); 528 } 529}; 530 531} // end ento namespace 532} // end clang namespace 533 534#endif 535