CoreEngine.h revision 1e9775d36de8edbc665c0f0bf4dae1400e3d2112
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/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h" 20#include "clang/StaticAnalyzer/Core/PathSensitive/WorkList.h" 21#include "clang/StaticAnalyzer/Core/PathSensitive/BlockCounter.h" 22#include "llvm/ADT/OwningPtr.h" 23 24namespace clang { 25 26class ProgramPointTag; 27 28namespace ento { 29 30//===----------------------------------------------------------------------===// 31/// CoreEngine - Implements the core logic of the graph-reachability 32/// analysis. It traverses the CFG and generates the ExplodedGraph. 33/// Program "states" are treated as opaque void pointers. 34/// The template class CoreEngine (which subclasses CoreEngine) 35/// provides the matching component to the engine that knows the actual types 36/// for states. Note that this engine only dispatches to transfer functions 37/// at the statement and block-level. The analyses themselves must implement 38/// any transfer function logic and the sub-expression level (if any). 39class CoreEngine { 40 friend class StmtNodeBuilder; 41 friend class GenericNodeBuilderImpl; 42 friend class BranchNodeBuilder; 43 friend class IndirectGotoNodeBuilder; 44 friend class SwitchNodeBuilder; 45 friend class EndOfFunctionNodeBuilder; 46 friend class CallEnterNodeBuilder; 47 friend class CallExitNodeBuilder; 48 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 void HandleCallEnter(const CallEnter &L, const CFGBlock *Block, 93 unsigned Index, ExplodedNode *Pred); 94 void HandleCallExit(const CallExit &L, ExplodedNode *Pred); 95 96private: 97 CoreEngine(const CoreEngine&); // Do not implement. 98 CoreEngine& operator=(const CoreEngine&); 99 100public: 101 /// Construct a CoreEngine object to analyze the provided CFG using 102 /// a DFS exploration of the exploded graph. 103 CoreEngine(SubEngine& subengine) 104 : SubEng(subengine), G(new ExplodedGraph()), 105 WList(WorkList::makeBFS()), 106 BCounterFactory(G->getAllocator()) {} 107 108 /// Construct a CoreEngine object to analyze the provided CFG and to 109 /// use the provided worklist object to execute the worklist algorithm. 110 /// The CoreEngine object assumes ownership of 'wlist'. 111 CoreEngine(WorkList* wlist, SubEngine& subengine) 112 : SubEng(subengine), G(new ExplodedGraph()), WList(wlist), 113 BCounterFactory(G->getAllocator()) {} 114 115 ~CoreEngine() { 116 delete WList; 117 } 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 const ProgramState *InitState); 130 void ExecuteWorkListWithInitialState(const LocationContext *L, 131 unsigned Steps, 132 const ProgramState *InitState, 133 ExplodedNodeSet &Dst); 134 135 // Functions for external checking of whether we have unfinished work 136 bool wasBlockAborted() const { return !blocksAborted.empty(); } 137 bool wasBlocksExhausted() const { return !blocksExhausted.empty(); } 138 bool hasWorkRemaining() const { return wasBlocksExhausted() || 139 WList->hasWork() || 140 wasBlockAborted(); } 141 142 /// Inform the CoreEngine that a basic block was aborted because 143 /// it could not be completely analyzed. 144 void addAbortedBlock(const ExplodedNode *node, const CFGBlock *block) { 145 blocksAborted.push_back(std::make_pair(block, node)); 146 } 147 148 WorkList *getWorkList() const { return WList; } 149 150 BlocksExhausted::const_iterator blocks_exhausted_begin() const { 151 return blocksExhausted.begin(); 152 } 153 BlocksExhausted::const_iterator blocks_exhausted_end() const { 154 return blocksExhausted.end(); 155 } 156 BlocksAborted::const_iterator blocks_aborted_begin() const { 157 return blocksAborted.begin(); 158 } 159 BlocksAborted::const_iterator blocks_aborted_end() const { 160 return blocksAborted.end(); 161 } 162}; 163 164class StmtNodeBuilder { 165 CoreEngine& Eng; 166 const CFGBlock &B; 167 const unsigned Idx; 168 ExplodedNode *Pred; 169 ProgramStateManager& Mgr; 170 171public: 172 bool PurgingDeadSymbols; 173 bool BuildSinks; 174 bool hasGeneratedNode; 175 ProgramPoint::Kind PointKind; 176 const ProgramPointTag *Tag; 177 178 typedef llvm::SmallPtrSet<ExplodedNode*,5> DeferredTy; 179 DeferredTy Deferred; 180 181 void GenerateAutoTransition(ExplodedNode *N); 182 183public: 184 StmtNodeBuilder(const CFGBlock *b, 185 unsigned idx, 186 ExplodedNode *N, 187 CoreEngine* e, 188 ProgramStateManager &mgr); 189 190 ~StmtNodeBuilder(); 191 192 ExplodedNode *getPredecessor() const { return Pred; } 193 194 // FIXME: This should not be exposed. 195 WorkList *getWorkList() { return Eng.WList; } 196 197 BlockCounter getBlockCounter() const { return Eng.WList->getBlockCounter();} 198 199 unsigned getCurrentBlockCount() const { 200 return getBlockCounter().getNumVisited( 201 Pred->getLocationContext()->getCurrentStackFrame(), 202 B.getBlockID()); 203 } 204 205 ExplodedNode *generateNode(PostStmt PP, 206 const ProgramState *St, 207 ExplodedNode *Pred) { 208 hasGeneratedNode = true; 209 return generateNodeInternal(PP, St, Pred); 210 } 211 212 ExplodedNode *generateNode(const Stmt *S, 213 const ProgramState *St, 214 ExplodedNode *Pred, 215 ProgramPoint::Kind K, 216 const ProgramPointTag *tag = 0) { 217 hasGeneratedNode = true; 218 219 if (PurgingDeadSymbols) 220 K = ProgramPoint::PostPurgeDeadSymbolsKind; 221 222 return generateNodeInternal(S, St, Pred, K, tag ? tag : Tag); 223 } 224 225 ExplodedNode *generateNode(const Stmt *S, 226 const ProgramState *St, 227 ExplodedNode *Pred, 228 const ProgramPointTag *tag = 0) { 229 return generateNode(S, St, Pred, PointKind, tag); 230 } 231 232 ExplodedNode *generateNode(const ProgramPoint &PP, 233 const ProgramState *State, 234 ExplodedNode *Pred) { 235 hasGeneratedNode = true; 236 return generateNodeInternal(PP, State, Pred); 237 } 238 239 ExplodedNode* 240 generateNodeInternal(const ProgramPoint &PP, 241 const ProgramState *State, 242 ExplodedNode *Pred); 243 244 ExplodedNode* 245 generateNodeInternal(const Stmt *S, 246 const ProgramState *State, 247 ExplodedNode *Pred, 248 ProgramPoint::Kind K = ProgramPoint::PostStmtKind, 249 const ProgramPointTag *tag = 0); 250 251 /// getStmt - Return the current block-level expression associated with 252 /// this builder. 253 const Stmt *getStmt() const { 254 const CFGStmt *CS = B[Idx].getAs<CFGStmt>(); 255 return CS ? CS->getStmt() : 0; 256 } 257 258 /// getBlock - Return the CFGBlock associated with the block-level expression 259 /// of this builder. 260 const CFGBlock *getBlock() const { return &B; } 261 262 unsigned getIndex() const { return Idx; } 263 264 ExplodedNode *MakeNode(ExplodedNodeSet &Dst, 265 const Stmt *S, 266 ExplodedNode *Pred, 267 const ProgramState *St) { 268 return MakeNode(Dst, S, Pred, St, PointKind); 269 } 270 271 ExplodedNode *MakeNode(ExplodedNodeSet &Dst, 272 const Stmt *S, 273 ExplodedNode *Pred, 274 const ProgramState *St, 275 ProgramPoint::Kind K); 276 277 ExplodedNode *MakeSinkNode(ExplodedNodeSet &Dst, 278 const Stmt *S, 279 ExplodedNode *Pred, 280 const ProgramState *St) { 281 bool Tmp = BuildSinks; 282 BuildSinks = true; 283 ExplodedNode *N = MakeNode(Dst, S, Pred, St); 284 BuildSinks = Tmp; 285 return N; 286 } 287}; 288 289class BranchNodeBuilder { 290 CoreEngine& Eng; 291 const CFGBlock *Src; 292 const CFGBlock *DstT; 293 const CFGBlock *DstF; 294 ExplodedNode *Pred; 295 296 typedef SmallVector<ExplodedNode*,3> DeferredTy; 297 DeferredTy Deferred; 298 299 bool GeneratedTrue; 300 bool GeneratedFalse; 301 bool InFeasibleTrue; 302 bool InFeasibleFalse; 303 304public: 305 BranchNodeBuilder(const CFGBlock *src, const CFGBlock *dstT, 306 const CFGBlock *dstF, ExplodedNode *pred, CoreEngine* e) 307 : Eng(*e), Src(src), DstT(dstT), DstF(dstF), Pred(pred), 308 GeneratedTrue(false), GeneratedFalse(false), 309 InFeasibleTrue(!DstT), InFeasibleFalse(!DstF) {} 310 311 ~BranchNodeBuilder(); 312 313 ExplodedNode *getPredecessor() const { return Pred; } 314 315 const ExplodedGraph& getGraph() const { return *Eng.G; } 316 317 BlockCounter getBlockCounter() const { return Eng.WList->getBlockCounter();} 318 319 /// This function generates a new ExplodedNode but not a new 320 /// branch(block edge). 321 ExplodedNode *generateNode(const Stmt *Condition, const ProgramState *State); 322 323 ExplodedNode *generateNode(const ProgramState *State, bool branch); 324 325 const CFGBlock *getTargetBlock(bool branch) const { 326 return branch ? DstT : DstF; 327 } 328 329 void markInfeasible(bool branch) { 330 if (branch) 331 InFeasibleTrue = GeneratedTrue = true; 332 else 333 InFeasibleFalse = GeneratedFalse = true; 334 } 335 336 bool isFeasible(bool branch) { 337 return branch ? !InFeasibleTrue : !InFeasibleFalse; 338 } 339 340 const ProgramState *getState() const { 341 return getPredecessor()->getState(); 342 } 343}; 344 345class IndirectGotoNodeBuilder { 346 CoreEngine& Eng; 347 const CFGBlock *Src; 348 const CFGBlock &DispatchBlock; 349 const Expr *E; 350 ExplodedNode *Pred; 351 352public: 353 IndirectGotoNodeBuilder(ExplodedNode *pred, const CFGBlock *src, 354 const Expr *e, const CFGBlock *dispatch, CoreEngine* eng) 355 : Eng(*eng), Src(src), DispatchBlock(*dispatch), E(e), Pred(pred) {} 356 357 class iterator { 358 CFGBlock::const_succ_iterator I; 359 360 friend class IndirectGotoNodeBuilder; 361 iterator(CFGBlock::const_succ_iterator i) : I(i) {} 362 public: 363 364 iterator &operator++() { ++I; return *this; } 365 bool operator!=(const iterator &X) const { return I != X.I; } 366 367 const LabelDecl *getLabel() const { 368 return llvm::cast<LabelStmt>((*I)->getLabel())->getDecl(); 369 } 370 371 const CFGBlock *getBlock() const { 372 return *I; 373 } 374 }; 375 376 iterator begin() { return iterator(DispatchBlock.succ_begin()); } 377 iterator end() { return iterator(DispatchBlock.succ_end()); } 378 379 ExplodedNode *generateNode(const iterator &I, 380 const ProgramState *State, 381 bool isSink = false); 382 383 const Expr *getTarget() const { return E; } 384 385 const ProgramState *getState() const { return Pred->State; } 386}; 387 388class SwitchNodeBuilder { 389 CoreEngine& Eng; 390 const CFGBlock *Src; 391 const Expr *Condition; 392 ExplodedNode *Pred; 393 394public: 395 SwitchNodeBuilder(ExplodedNode *pred, const CFGBlock *src, 396 const Expr *condition, CoreEngine* eng) 397 : Eng(*eng), Src(src), Condition(condition), Pred(pred) {} 398 399 class iterator { 400 CFGBlock::const_succ_reverse_iterator I; 401 402 friend class SwitchNodeBuilder; 403 iterator(CFGBlock::const_succ_reverse_iterator i) : I(i) {} 404 405 public: 406 iterator &operator++() { ++I; return *this; } 407 bool operator!=(const iterator &X) const { return I != X.I; } 408 bool operator==(const iterator &X) const { return I == X.I; } 409 410 const CaseStmt *getCase() const { 411 return llvm::cast<CaseStmt>((*I)->getLabel()); 412 } 413 414 const CFGBlock *getBlock() const { 415 return *I; 416 } 417 }; 418 419 iterator begin() { return iterator(Src->succ_rbegin()+1); } 420 iterator end() { return iterator(Src->succ_rend()); } 421 422 const SwitchStmt *getSwitch() const { 423 return llvm::cast<SwitchStmt>(Src->getTerminator()); 424 } 425 426 ExplodedNode *generateCaseStmtNode(const iterator &I, 427 const ProgramState *State); 428 429 ExplodedNode *generateDefaultCaseNode(const ProgramState *State, 430 bool isSink = false); 431 432 const Expr *getCondition() const { return Condition; } 433 434 const ProgramState *getState() const { return Pred->State; } 435}; 436 437class GenericNodeBuilderImpl { 438protected: 439 CoreEngine &engine; 440 ExplodedNode *pred; 441 ProgramPoint pp; 442 SmallVector<ExplodedNode*, 2> sinksGenerated; 443 444 ExplodedNode *generateNodeImpl(const ProgramState *state, 445 ExplodedNode *pred, 446 ProgramPoint programPoint, 447 bool asSink); 448 449 GenericNodeBuilderImpl(CoreEngine &eng, ExplodedNode *pr, ProgramPoint p) 450 : engine(eng), pred(pr), pp(p), hasGeneratedNode(false) {} 451 452public: 453 bool hasGeneratedNode; 454 455 WorkList &getWorkList() { return *engine.WList; } 456 457 ExplodedNode *getPredecessor() const { return pred; } 458 459 BlockCounter getBlockCounter() const { 460 return engine.WList->getBlockCounter(); 461 } 462 463 const SmallVectorImpl<ExplodedNode*> &sinks() const { 464 return sinksGenerated; 465 } 466}; 467 468template <typename PP_T> 469class GenericNodeBuilder : public GenericNodeBuilderImpl { 470public: 471 GenericNodeBuilder(CoreEngine &eng, ExplodedNode *pr, const PP_T &p) 472 : GenericNodeBuilderImpl(eng, pr, p) {} 473 474 ExplodedNode *generateNode(const ProgramState *state, ExplodedNode *pred, 475 const ProgramPointTag *tag, bool asSink) { 476 return generateNodeImpl(state, pred, cast<PP_T>(pp).withTag(tag), 477 asSink); 478 } 479 480 const PP_T &getProgramPoint() const { return cast<PP_T>(pp); } 481}; 482 483class EndOfFunctionNodeBuilder { 484 CoreEngine &Eng; 485 const CFGBlock &B; 486 ExplodedNode *Pred; 487 const ProgramPointTag *Tag; 488 489public: 490 bool hasGeneratedNode; 491 492public: 493 EndOfFunctionNodeBuilder(const CFGBlock *b, ExplodedNode *N, CoreEngine* e, 494 const ProgramPointTag *tag = 0) 495 : Eng(*e), B(*b), Pred(N), Tag(tag), hasGeneratedNode(false) {} 496 497 ~EndOfFunctionNodeBuilder(); 498 499 EndOfFunctionNodeBuilder withCheckerTag(const ProgramPointTag *tag) { 500 return EndOfFunctionNodeBuilder(&B, Pred, &Eng, tag); 501 } 502 503 WorkList &getWorkList() { return *Eng.WList; } 504 505 ExplodedNode *getPredecessor() const { return Pred; } 506 507 BlockCounter getBlockCounter() const { 508 return Eng.WList->getBlockCounter(); 509 } 510 511 unsigned getCurrentBlockCount() const { 512 return getBlockCounter().getNumVisited( 513 Pred->getLocationContext()->getCurrentStackFrame(), 514 B.getBlockID()); 515 } 516 517 ExplodedNode *generateNode(const ProgramState *State, 518 ExplodedNode *P = 0, 519 const ProgramPointTag *tag = 0); 520 521 void GenerateCallExitNode(const ProgramState *state); 522 523 const CFGBlock *getBlock() const { return &B; } 524 525 const ProgramState *getState() const { 526 return getPredecessor()->getState(); 527 } 528}; 529 530class CallEnterNodeBuilder { 531 CoreEngine &Eng; 532 533 const ExplodedNode *Pred; 534 535 // The call site. For implicit automatic object dtor, this is the trigger 536 // statement. 537 const Stmt *CE; 538 539 // The context of the callee. 540 const StackFrameContext *CalleeCtx; 541 542 // The parent block of the CallExpr. 543 const CFGBlock *Block; 544 545 // The CFGBlock index of the CallExpr. 546 unsigned Index; 547 548public: 549 CallEnterNodeBuilder(CoreEngine &eng, const ExplodedNode *pred, 550 const Stmt *s, const StackFrameContext *callee, 551 const CFGBlock *blk, unsigned idx) 552 : Eng(eng), Pred(pred), CE(s), CalleeCtx(callee), Block(blk), Index(idx) {} 553 554 const ProgramState *getState() const { return Pred->getState(); } 555 556 const LocationContext *getLocationContext() const { 557 return Pred->getLocationContext(); 558 } 559 560 const Stmt *getCallExpr() const { return CE; } 561 562 const StackFrameContext *getCalleeContext() const { return CalleeCtx; } 563 564 const CFGBlock *getBlock() const { return Block; } 565 566 unsigned getIndex() const { return Index; } 567 568 void generateNode(const ProgramState *state); 569}; 570 571class CallExitNodeBuilder { 572 CoreEngine &Eng; 573 const ExplodedNode *Pred; 574 575public: 576 CallExitNodeBuilder(CoreEngine &eng, const ExplodedNode *pred) 577 : Eng(eng), Pred(pred) {} 578 579 const ExplodedNode *getPredecessor() const { return Pred; } 580 581 const ProgramState *getState() const { return Pred->getState(); } 582 583 void generateNode(const ProgramState *state); 584}; 585 586} // end GR namespace 587 588} // end clang namespace 589 590#endif 591