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