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