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