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