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