CoreEngine.h revision 0e89061a399bae32f0eca5b85658ad66a58c504d
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 /// transferred 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 typedef llvm::SmallPtrSet<ExplodedNode*,5> DeferredTy; 176 DeferredTy Deferred; 177 178 void GenerateAutoTransition(ExplodedNode* N); 179 180public: 181 StmtNodeBuilder(const CFGBlock* b, unsigned idx, ExplodedNode* N, 182 CoreEngine* e, GRStateManager &mgr); 183 184 ~StmtNodeBuilder(); 185 186 ExplodedNode* getPredecessor() const { return Pred; } 187 188 // FIXME: This should not be exposed. 189 WorkList *getWorkList() { return Eng.WList; } 190 191 BlockCounter getBlockCounter() const { return Eng.WList->getBlockCounter();} 192 193 unsigned getCurrentBlockCount() const { 194 return getBlockCounter().getNumVisited( 195 Pred->getLocationContext()->getCurrentStackFrame(), 196 B.getBlockID()); 197 } 198 199 ExplodedNode* generateNode(PostStmt PP,const GRState* St,ExplodedNode* Pred) { 200 hasGeneratedNode = true; 201 return generateNodeInternal(PP, St, Pred); 202 } 203 204 ExplodedNode* generateNode(const Stmt *S, const GRState *St, 205 ExplodedNode *Pred, ProgramPoint::Kind K, 206 const void *tag = 0) { 207 hasGeneratedNode = true; 208 209 if (PurgingDeadSymbols) 210 K = ProgramPoint::PostPurgeDeadSymbolsKind; 211 212 return generateNodeInternal(S, St, Pred, K, tag ? tag : Tag); 213 } 214 215 ExplodedNode* generateNode(const Stmt *S, const GRState *St, 216 ExplodedNode *Pred, const void *tag = 0) { 217 return generateNode(S, St, Pred, PointKind, tag); 218 } 219 220 ExplodedNode *generateNode(const ProgramPoint &PP, const GRState* State, 221 ExplodedNode* Pred) { 222 hasGeneratedNode = true; 223 return generateNodeInternal(PP, State, Pred); 224 } 225 226 ExplodedNode* 227 generateNodeInternal(const ProgramPoint &PP, const GRState* State, 228 ExplodedNode* Pred); 229 230 ExplodedNode* 231 generateNodeInternal(const Stmt* S, const GRState* State, ExplodedNode* Pred, 232 ProgramPoint::Kind K = ProgramPoint::PostStmtKind, 233 const void *tag = 0); 234 235 /// getStmt - Return the current block-level expression associated with 236 /// this builder. 237 const Stmt* getStmt() const { 238 const CFGStmt *CS = B[Idx].getAs<CFGStmt>(); 239 return CS ? CS->getStmt() : 0; 240 } 241 242 /// getBlock - Return the CFGBlock associated with the block-level expression 243 /// of this builder. 244 const CFGBlock* getBlock() const { return &B; } 245 246 unsigned getIndex() const { return Idx; } 247 248 ExplodedNode* MakeNode(ExplodedNodeSet& Dst, const Stmt* S, 249 ExplodedNode* Pred, const GRState* St) { 250 return MakeNode(Dst, S, Pred, St, PointKind); 251 } 252 253 ExplodedNode* MakeNode(ExplodedNodeSet& Dst, const Stmt* S,ExplodedNode* Pred, 254 const GRState* St, ProgramPoint::Kind K); 255 256 ExplodedNode* MakeSinkNode(ExplodedNodeSet& Dst, const Stmt* S, 257 ExplodedNode* Pred, const GRState* St) { 258 bool Tmp = BuildSinks; 259 BuildSinks = true; 260 ExplodedNode* N = MakeNode(Dst, S, Pred, St); 261 BuildSinks = Tmp; 262 return N; 263 } 264}; 265 266class BranchNodeBuilder { 267 CoreEngine& Eng; 268 const CFGBlock* Src; 269 const CFGBlock* DstT; 270 const CFGBlock* DstF; 271 ExplodedNode* Pred; 272 273 typedef SmallVector<ExplodedNode*,3> DeferredTy; 274 DeferredTy Deferred; 275 276 bool GeneratedTrue; 277 bool GeneratedFalse; 278 bool InFeasibleTrue; 279 bool InFeasibleFalse; 280 281public: 282 BranchNodeBuilder(const CFGBlock* src, const CFGBlock* dstT, 283 const CFGBlock* dstF, ExplodedNode* pred, CoreEngine* e) 284 : Eng(*e), Src(src), DstT(dstT), DstF(dstF), Pred(pred), 285 GeneratedTrue(false), GeneratedFalse(false), 286 InFeasibleTrue(!DstT), InFeasibleFalse(!DstF) {} 287 288 ~BranchNodeBuilder(); 289 290 ExplodedNode* getPredecessor() const { return Pred; } 291 292 const ExplodedGraph& getGraph() const { return *Eng.G; } 293 294 BlockCounter getBlockCounter() const { return Eng.WList->getBlockCounter();} 295 296 ExplodedNode* generateNode(const Stmt *Condition, const GRState* State); 297 298 ExplodedNode* generateNode(const GRState* State, bool branch); 299 300 const CFGBlock* getTargetBlock(bool branch) const { 301 return branch ? DstT : DstF; 302 } 303 304 void markInfeasible(bool branch) { 305 if (branch) 306 InFeasibleTrue = GeneratedTrue = true; 307 else 308 InFeasibleFalse = GeneratedFalse = true; 309 } 310 311 bool isFeasible(bool branch) { 312 return branch ? !InFeasibleTrue : !InFeasibleFalse; 313 } 314 315 const GRState* getState() const { 316 return getPredecessor()->getState(); 317 } 318}; 319 320class IndirectGotoNodeBuilder { 321 CoreEngine& Eng; 322 const CFGBlock* Src; 323 const CFGBlock& DispatchBlock; 324 const Expr* E; 325 ExplodedNode* Pred; 326 327public: 328 IndirectGotoNodeBuilder(ExplodedNode* pred, const CFGBlock* src, 329 const Expr* e, const CFGBlock* dispatch, CoreEngine* eng) 330 : Eng(*eng), Src(src), DispatchBlock(*dispatch), E(e), Pred(pred) {} 331 332 class iterator { 333 CFGBlock::const_succ_iterator I; 334 335 friend class IndirectGotoNodeBuilder; 336 iterator(CFGBlock::const_succ_iterator i) : I(i) {} 337 public: 338 339 iterator& operator++() { ++I; return *this; } 340 bool operator!=(const iterator& X) const { return I != X.I; } 341 342 const LabelDecl *getLabel() const { 343 return llvm::cast<LabelStmt>((*I)->getLabel())->getDecl(); 344 } 345 346 const CFGBlock *getBlock() const { 347 return *I; 348 } 349 }; 350 351 iterator begin() { return iterator(DispatchBlock.succ_begin()); } 352 iterator end() { return iterator(DispatchBlock.succ_end()); } 353 354 ExplodedNode* generateNode(const iterator& I, const GRState* State, 355 bool isSink = false); 356 357 const Expr* getTarget() const { return E; } 358 359 const GRState* getState() const { return Pred->State; } 360}; 361 362class SwitchNodeBuilder { 363 CoreEngine& Eng; 364 const CFGBlock* Src; 365 const Expr* Condition; 366 ExplodedNode* Pred; 367 368public: 369 SwitchNodeBuilder(ExplodedNode* pred, const CFGBlock* src, 370 const Expr* condition, CoreEngine* eng) 371 : Eng(*eng), Src(src), Condition(condition), Pred(pred) {} 372 373 class iterator { 374 CFGBlock::const_succ_reverse_iterator I; 375 376 friend class SwitchNodeBuilder; 377 iterator(CFGBlock::const_succ_reverse_iterator i) : I(i) {} 378 379 public: 380 iterator& operator++() { ++I; return *this; } 381 bool operator!=(const iterator &X) const { return I != X.I; } 382 bool operator==(const iterator &X) const { return I == X.I; } 383 384 const CaseStmt* getCase() const { 385 return llvm::cast<CaseStmt>((*I)->getLabel()); 386 } 387 388 const CFGBlock* getBlock() const { 389 return *I; 390 } 391 }; 392 393 iterator begin() { return iterator(Src->succ_rbegin()+1); } 394 iterator end() { return iterator(Src->succ_rend()); } 395 396 const SwitchStmt *getSwitch() const { 397 return llvm::cast<SwitchStmt>(Src->getTerminator()); 398 } 399 400 ExplodedNode* generateCaseStmtNode(const iterator& I, const GRState* State); 401 402 ExplodedNode* generateDefaultCaseNode(const GRState* State, 403 bool isSink = false); 404 405 const Expr* getCondition() const { return Condition; } 406 407 const GRState* getState() const { return Pred->State; } 408}; 409 410class GenericNodeBuilderImpl { 411protected: 412 CoreEngine &engine; 413 ExplodedNode *pred; 414 ProgramPoint pp; 415 SmallVector<ExplodedNode*, 2> sinksGenerated; 416 417 ExplodedNode *generateNodeImpl(const GRState *state, ExplodedNode *pred, 418 ProgramPoint programPoint, bool asSink); 419 420 GenericNodeBuilderImpl(CoreEngine &eng, ExplodedNode *pr, ProgramPoint p) 421 : engine(eng), pred(pr), pp(p), hasGeneratedNode(false) {} 422 423public: 424 bool hasGeneratedNode; 425 426 WorkList &getWorkList() { return *engine.WList; } 427 428 ExplodedNode* getPredecessor() const { return pred; } 429 430 BlockCounter getBlockCounter() const { 431 return engine.WList->getBlockCounter(); 432 } 433 434 const SmallVectorImpl<ExplodedNode*> &sinks() const { 435 return sinksGenerated; 436 } 437}; 438 439template <typename PP_T> 440class GenericNodeBuilder : public GenericNodeBuilderImpl { 441public: 442 GenericNodeBuilder(CoreEngine &eng, ExplodedNode *pr, const PP_T &p) 443 : GenericNodeBuilderImpl(eng, pr, p) {} 444 445 ExplodedNode *generateNode(const GRState *state, ExplodedNode *pred, 446 const void *tag, bool asSink) { 447 return generateNodeImpl(state, pred, cast<PP_T>(pp).withTag(tag), 448 asSink); 449 } 450 451 const PP_T &getProgramPoint() const { return cast<PP_T>(pp); } 452}; 453 454class EndOfFunctionNodeBuilder { 455 CoreEngine &Eng; 456 const CFGBlock& B; 457 ExplodedNode* Pred; 458 void *Tag; 459 460public: 461 bool hasGeneratedNode; 462 463public: 464 EndOfFunctionNodeBuilder(const CFGBlock* b, ExplodedNode* N, CoreEngine* e, 465 void *checkerTag = 0) 466 : Eng(*e), B(*b), Pred(N), Tag(checkerTag), hasGeneratedNode(false) {} 467 468 ~EndOfFunctionNodeBuilder(); 469 470 EndOfFunctionNodeBuilder withCheckerTag(void *tag) { 471 return EndOfFunctionNodeBuilder(&B, Pred, &Eng, tag); 472 } 473 474 WorkList &getWorkList() { return *Eng.WList; } 475 476 ExplodedNode* getPredecessor() const { return Pred; } 477 478 BlockCounter getBlockCounter() const { 479 return Eng.WList->getBlockCounter(); 480 } 481 482 unsigned getCurrentBlockCount() const { 483 return getBlockCounter().getNumVisited( 484 Pred->getLocationContext()->getCurrentStackFrame(), 485 B.getBlockID()); 486 } 487 488 ExplodedNode* generateNode(const GRState* State, ExplodedNode *P = 0, 489 const void *tag = 0); 490 491 void GenerateCallExitNode(const GRState *state); 492 493 const CFGBlock* getBlock() const { return &B; } 494 495 const GRState* getState() const { 496 return getPredecessor()->getState(); 497 } 498}; 499 500class CallEnterNodeBuilder { 501 CoreEngine &Eng; 502 503 const ExplodedNode *Pred; 504 505 // The call site. For implicit automatic object dtor, this is the trigger 506 // statement. 507 const Stmt *CE; 508 509 // The context of the callee. 510 const StackFrameContext *CalleeCtx; 511 512 // The parent block of the CallExpr. 513 const CFGBlock *Block; 514 515 // The CFGBlock index of the CallExpr. 516 unsigned Index; 517 518public: 519 CallEnterNodeBuilder(CoreEngine &eng, const ExplodedNode *pred, 520 const Stmt *s, const StackFrameContext *callee, 521 const CFGBlock *blk, unsigned idx) 522 : Eng(eng), Pred(pred), CE(s), CalleeCtx(callee), Block(blk), Index(idx) {} 523 524 const GRState *getState() const { return Pred->getState(); } 525 526 const LocationContext *getLocationContext() const { 527 return Pred->getLocationContext(); 528 } 529 530 const Stmt *getCallExpr() const { return CE; } 531 532 const StackFrameContext *getCalleeContext() const { return CalleeCtx; } 533 534 const CFGBlock *getBlock() const { return Block; } 535 536 unsigned getIndex() const { return Index; } 537 538 void generateNode(const GRState *state); 539}; 540 541class CallExitNodeBuilder { 542 CoreEngine &Eng; 543 const ExplodedNode *Pred; 544 545public: 546 CallExitNodeBuilder(CoreEngine &eng, const ExplodedNode *pred) 547 : Eng(eng), Pred(pred) {} 548 549 const ExplodedNode *getPredecessor() const { return Pred; } 550 551 const GRState *getState() const { return Pred->getState(); } 552 553 void generateNode(const GRState *state); 554}; 555 556} // end GR namespace 557 558} // end clang namespace 559 560#endif 561