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