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