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