CoreEngine.h revision fa06f0464a04bb7fce1fcfb3780d151bb029e00c
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 ExplodedNode *generateNode(const ProgramPoint &PP, 269 ProgramStateRef State, 270 ExplodedNode *Pred) { 271 return generateNodeImpl(PP, State, Pred, false); 272 } 273 274 /// \brief Generates a sink in the ExplodedGraph. 275 /// 276 /// When a node is marked as sink, the exploration from the node is stopped - 277 /// the node becomes the last node on the path and certain kinds of bugs are 278 /// suppressed. 279 ExplodedNode *generateSink(const ProgramPoint &PP, 280 ProgramStateRef State, 281 ExplodedNode *Pred) { 282 return generateNodeImpl(PP, State, Pred, true); 283 } 284 285 const ExplodedNodeSet &getResults() { 286 finalizeResults(); 287 assert(checkResults()); 288 return Frontier; 289 } 290 291 typedef ExplodedNodeSet::iterator iterator; 292 /// \brief Iterators through the results frontier. 293 inline iterator begin() { 294 finalizeResults(); 295 assert(checkResults()); 296 return Frontier.begin(); 297 } 298 inline iterator end() { 299 finalizeResults(); 300 return Frontier.end(); 301 } 302 303 const NodeBuilderContext &getContext() { return C; } 304 bool hasGeneratedNodes() { return HasGeneratedNodes; } 305 306 void takeNodes(const ExplodedNodeSet &S) { 307 for (ExplodedNodeSet::iterator I = S.begin(), E = S.end(); I != E; ++I ) 308 Frontier.erase(*I); 309 } 310 void takeNodes(ExplodedNode *N) { Frontier.erase(N); } 311 void addNodes(const ExplodedNodeSet &S) { Frontier.insert(S); } 312 void addNodes(ExplodedNode *N) { Frontier.Add(N); } 313}; 314 315/// \class NodeBuilderWithSinks 316/// \brief This node builder keeps track of the generated sink nodes. 317class NodeBuilderWithSinks: public NodeBuilder { 318 virtual void anchor(); 319protected: 320 SmallVector<ExplodedNode*, 2> sinksGenerated; 321 ProgramPoint &Location; 322 323public: 324 NodeBuilderWithSinks(ExplodedNode *Pred, ExplodedNodeSet &DstSet, 325 const NodeBuilderContext &Ctx, ProgramPoint &L) 326 : NodeBuilder(Pred, DstSet, Ctx), Location(L) {} 327 328 ExplodedNode *generateNode(ProgramStateRef State, 329 ExplodedNode *Pred, 330 const ProgramPointTag *Tag = 0) { 331 const ProgramPoint &LocalLoc = (Tag ? Location.withTag(Tag) : Location); 332 return NodeBuilder::generateNode(LocalLoc, State, Pred); 333 } 334 335 ExplodedNode *generateSink(ProgramStateRef State, ExplodedNode *Pred, 336 const ProgramPointTag *Tag = 0) { 337 const ProgramPoint &LocalLoc = (Tag ? Location.withTag(Tag) : Location); 338 ExplodedNode *N = NodeBuilder::generateSink(LocalLoc, State, Pred); 339 if (N && N->isSink()) 340 sinksGenerated.push_back(N); 341 return N; 342 } 343 344 const SmallVectorImpl<ExplodedNode*> &getSinks() const { 345 return sinksGenerated; 346 } 347}; 348 349/// \class StmtNodeBuilder 350/// \brief This builder class is useful for generating nodes that resulted from 351/// visiting a statement. The main difference from its parent NodeBuilder is 352/// that it creates a statement specific ProgramPoint. 353class StmtNodeBuilder: public NodeBuilder { 354 NodeBuilder *EnclosingBldr; 355public: 356 357 /// \brief Constructs a StmtNodeBuilder. If the builder is going to process 358 /// nodes currently owned by another builder(with larger scope), use 359 /// Enclosing builder to transfer ownership. 360 StmtNodeBuilder(ExplodedNode *SrcNode, ExplodedNodeSet &DstSet, 361 const NodeBuilderContext &Ctx, NodeBuilder *Enclosing = 0) 362 : NodeBuilder(SrcNode, DstSet, Ctx), EnclosingBldr(Enclosing) { 363 if (EnclosingBldr) 364 EnclosingBldr->takeNodes(SrcNode); 365 } 366 367 StmtNodeBuilder(ExplodedNodeSet &SrcSet, ExplodedNodeSet &DstSet, 368 const NodeBuilderContext &Ctx, NodeBuilder *Enclosing = 0) 369 : NodeBuilder(SrcSet, DstSet, Ctx), EnclosingBldr(Enclosing) { 370 if (EnclosingBldr) 371 for (ExplodedNodeSet::iterator I = SrcSet.begin(), 372 E = SrcSet.end(); I != E; ++I ) 373 EnclosingBldr->takeNodes(*I); 374 } 375 376 virtual ~StmtNodeBuilder(); 377 378 using NodeBuilder::generateNode; 379 using NodeBuilder::generateSink; 380 381 ExplodedNode *generateNode(const Stmt *S, 382 ExplodedNode *Pred, 383 ProgramStateRef St, 384 const ProgramPointTag *tag = 0, 385 ProgramPoint::Kind K = ProgramPoint::PostStmtKind){ 386 const ProgramPoint &L = ProgramPoint::getProgramPoint(S, K, 387 Pred->getLocationContext(), tag); 388 return NodeBuilder::generateNode(L, St, Pred); 389 } 390 391 ExplodedNode *generateSink(const Stmt *S, 392 ExplodedNode *Pred, 393 ProgramStateRef St, 394 const ProgramPointTag *tag = 0, 395 ProgramPoint::Kind K = ProgramPoint::PostStmtKind){ 396 const ProgramPoint &L = ProgramPoint::getProgramPoint(S, K, 397 Pred->getLocationContext(), tag); 398 return NodeBuilder::generateSink(L, St, Pred); 399 } 400}; 401 402/// \brief BranchNodeBuilder is responsible for constructing the nodes 403/// corresponding to the two branches of the if statement - true and false. 404class BranchNodeBuilder: public NodeBuilder { 405 virtual void anchor(); 406 const CFGBlock *DstT; 407 const CFGBlock *DstF; 408 409 bool InFeasibleTrue; 410 bool InFeasibleFalse; 411 412public: 413 BranchNodeBuilder(ExplodedNode *SrcNode, ExplodedNodeSet &DstSet, 414 const NodeBuilderContext &C, 415 const CFGBlock *dstT, const CFGBlock *dstF) 416 : NodeBuilder(SrcNode, DstSet, C), DstT(dstT), DstF(dstF), 417 InFeasibleTrue(!DstT), InFeasibleFalse(!DstF) { 418 // The branch node builder does not generate autotransitions. 419 // If there are no successors it means that both branches are infeasible. 420 takeNodes(SrcNode); 421 } 422 423 BranchNodeBuilder(const ExplodedNodeSet &SrcSet, ExplodedNodeSet &DstSet, 424 const NodeBuilderContext &C, 425 const CFGBlock *dstT, const CFGBlock *dstF) 426 : NodeBuilder(SrcSet, DstSet, C), DstT(dstT), DstF(dstF), 427 InFeasibleTrue(!DstT), InFeasibleFalse(!DstF) { 428 takeNodes(SrcSet); 429 } 430 431 ExplodedNode *generateNode(ProgramStateRef State, bool branch, 432 ExplodedNode *Pred); 433 434 const CFGBlock *getTargetBlock(bool branch) const { 435 return branch ? DstT : DstF; 436 } 437 438 void markInfeasible(bool branch) { 439 if (branch) 440 InFeasibleTrue = true; 441 else 442 InFeasibleFalse = true; 443 } 444 445 bool isFeasible(bool branch) { 446 return branch ? !InFeasibleTrue : !InFeasibleFalse; 447 } 448}; 449 450class IndirectGotoNodeBuilder { 451 CoreEngine& Eng; 452 const CFGBlock *Src; 453 const CFGBlock &DispatchBlock; 454 const Expr *E; 455 ExplodedNode *Pred; 456 457public: 458 IndirectGotoNodeBuilder(ExplodedNode *pred, const CFGBlock *src, 459 const Expr *e, const CFGBlock *dispatch, CoreEngine* eng) 460 : Eng(*eng), Src(src), DispatchBlock(*dispatch), E(e), Pred(pred) {} 461 462 class iterator { 463 CFGBlock::const_succ_iterator I; 464 465 friend class IndirectGotoNodeBuilder; 466 iterator(CFGBlock::const_succ_iterator i) : I(i) {} 467 public: 468 469 iterator &operator++() { ++I; return *this; } 470 bool operator!=(const iterator &X) const { return I != X.I; } 471 472 const LabelDecl *getLabel() const { 473 return llvm::cast<LabelStmt>((*I)->getLabel())->getDecl(); 474 } 475 476 const CFGBlock *getBlock() const { 477 return *I; 478 } 479 }; 480 481 iterator begin() { return iterator(DispatchBlock.succ_begin()); } 482 iterator end() { return iterator(DispatchBlock.succ_end()); } 483 484 ExplodedNode *generateNode(const iterator &I, 485 ProgramStateRef State, 486 bool isSink = false); 487 488 const Expr *getTarget() const { return E; } 489 490 ProgramStateRef getState() const { return Pred->State; } 491 492 const LocationContext *getLocationContext() const { 493 return Pred->getLocationContext(); 494 } 495}; 496 497class SwitchNodeBuilder { 498 CoreEngine& Eng; 499 const CFGBlock *Src; 500 const Expr *Condition; 501 ExplodedNode *Pred; 502 503public: 504 SwitchNodeBuilder(ExplodedNode *pred, const CFGBlock *src, 505 const Expr *condition, CoreEngine* eng) 506 : Eng(*eng), Src(src), Condition(condition), Pred(pred) {} 507 508 class iterator { 509 CFGBlock::const_succ_reverse_iterator I; 510 511 friend class SwitchNodeBuilder; 512 iterator(CFGBlock::const_succ_reverse_iterator i) : I(i) {} 513 514 public: 515 iterator &operator++() { ++I; return *this; } 516 bool operator!=(const iterator &X) const { return I != X.I; } 517 bool operator==(const iterator &X) const { return I == X.I; } 518 519 const CaseStmt *getCase() const { 520 return llvm::cast<CaseStmt>((*I)->getLabel()); 521 } 522 523 const CFGBlock *getBlock() const { 524 return *I; 525 } 526 }; 527 528 iterator begin() { return iterator(Src->succ_rbegin()+1); } 529 iterator end() { return iterator(Src->succ_rend()); } 530 531 const SwitchStmt *getSwitch() const { 532 return llvm::cast<SwitchStmt>(Src->getTerminator()); 533 } 534 535 ExplodedNode *generateCaseStmtNode(const iterator &I, 536 ProgramStateRef State); 537 538 ExplodedNode *generateDefaultCaseNode(ProgramStateRef State, 539 bool isSink = false); 540 541 const Expr *getCondition() const { return Condition; } 542 543 ProgramStateRef getState() const { return Pred->State; } 544 545 const LocationContext *getLocationContext() const { 546 return Pred->getLocationContext(); 547 } 548}; 549 550} // end ento namespace 551} // end clang namespace 552 553#endif 554