1 //==- ProgramPoint.h - Program Points for Path-Sensitive Analysis --*- 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 the interface ProgramPoint, which identifies a 11 // distinct location in a function. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #ifndef LLVM_CLANG_ANALYSIS_PROGRAM_POINT 16 #define LLVM_CLANG_ANALYSIS_PROGRAM_POINT 17 18 #include "clang/Analysis/AnalysisContext.h" 19 #include "clang/Analysis/CFG.h" 20 #include "llvm/Support/DataTypes.h" 21 #include "llvm/ADT/DenseMap.h" 22 #include "llvm/ADT/PointerIntPair.h" 23 #include "llvm/ADT/FoldingSet.h" 24 #include "llvm/Support/Casting.h" 25 #include "llvm/ADT/StringRef.h" 26 #include <cassert> 27 #include <utility> 28 #include <string> 29 30 namespace clang { 31 32 class AnalysisDeclContext; 33 class FunctionDecl; 34 class LocationContext; 35 class ProgramPointTag; 36 37 class ProgramPoint { 38 public: 39 enum Kind { BlockEdgeKind, 40 BlockEntranceKind, 41 BlockExitKind, 42 PreStmtKind, 43 PreStmtPurgeDeadSymbolsKind, 44 PostStmtPurgeDeadSymbolsKind, 45 PostStmtKind, 46 PreLoadKind, 47 PostLoadKind, 48 PreStoreKind, 49 PostStoreKind, 50 PostConditionKind, 51 PostLValueKind, 52 MinPostStmtKind = PostStmtKind, 53 MaxPostStmtKind = PostLValueKind, 54 PostInitializerKind, 55 CallEnterKind, 56 CallExitBeginKind, 57 CallExitEndKind, 58 PreImplicitCallKind, 59 PostImplicitCallKind, 60 MinImplicitCallKind = PreImplicitCallKind, 61 MaxImplicitCallKind = PostImplicitCallKind, 62 EpsilonKind}; 63 64 private: 65 const void *Data1; 66 llvm::PointerIntPair<const void *, 2, unsigned> Data2; 67 68 // The LocationContext could be NULL to allow ProgramPoint to be used in 69 // context insensitive analysis. 70 llvm::PointerIntPair<const LocationContext *, 2, unsigned> L; 71 72 llvm::PointerIntPair<const ProgramPointTag *, 2, unsigned> Tag; 73 74 ProgramPoint(); 75 76 protected: 77 ProgramPoint(const void *P, 78 Kind k, 79 const LocationContext *l, 80 const ProgramPointTag *tag = 0) Data1(P)81 : Data1(P), 82 Data2(0, (((unsigned) k) >> 0) & 0x3), 83 L(l, (((unsigned) k) >> 2) & 0x3), 84 Tag(tag, (((unsigned) k) >> 4) & 0x3) { 85 assert(getKind() == k); 86 assert(getLocationContext() == l); 87 assert(getData1() == P); 88 } 89 90 ProgramPoint(const void *P1, 91 const void *P2, 92 Kind k, 93 const LocationContext *l, 94 const ProgramPointTag *tag = 0) Data1(P1)95 : Data1(P1), 96 Data2(P2, (((unsigned) k) >> 0) & 0x3), 97 L(l, (((unsigned) k) >> 2) & 0x3), 98 Tag(tag, (((unsigned) k) >> 4) & 0x3) {} 99 100 protected: getData1()101 const void *getData1() const { return Data1; } getData2()102 const void *getData2() const { return Data2.getPointer(); } setData2(const void * d)103 void setData2(const void *d) { Data2.setPointer(d); } 104 105 public: 106 /// Create a new ProgramPoint object that is the same as the original 107 /// except for using the specified tag value. withTag(const ProgramPointTag * tag)108 ProgramPoint withTag(const ProgramPointTag *tag) const { 109 return ProgramPoint(getData1(), getData2(), getKind(), 110 getLocationContext(), tag); 111 } 112 getKind()113 Kind getKind() const { 114 unsigned x = Tag.getInt(); 115 x <<= 2; 116 x |= L.getInt(); 117 x <<= 2; 118 x |= Data2.getInt(); 119 return (Kind) x; 120 } 121 122 /// \brief Is this a program point corresponding to purge/removal of dead 123 /// symbols and bindings. isPurgeKind()124 bool isPurgeKind() { 125 Kind K = getKind(); 126 return (K == PostStmtPurgeDeadSymbolsKind || 127 K == PreStmtPurgeDeadSymbolsKind); 128 } 129 getTag()130 const ProgramPointTag *getTag() const { return Tag.getPointer(); } 131 getLocationContext()132 const LocationContext *getLocationContext() const { 133 return L.getPointer(); 134 } 135 136 // For use with DenseMap. This hash is probably slow. getHashValue()137 unsigned getHashValue() const { 138 llvm::FoldingSetNodeID ID; 139 Profile(ID); 140 return ID.ComputeHash(); 141 } 142 classof(const ProgramPoint *)143 static bool classof(const ProgramPoint*) { return true; } 144 145 bool operator==(const ProgramPoint & RHS) const { 146 return Data1 == RHS.Data1 && 147 Data2 == RHS.Data2 && 148 L == RHS.L && 149 Tag == RHS.Tag; 150 } 151 152 bool operator!=(const ProgramPoint &RHS) const { 153 return Data1 != RHS.Data1 || 154 Data2 != RHS.Data2 || 155 L != RHS.L || 156 Tag != RHS.Tag; 157 } 158 Profile(llvm::FoldingSetNodeID & ID)159 void Profile(llvm::FoldingSetNodeID& ID) const { 160 ID.AddInteger((unsigned) getKind()); 161 ID.AddPointer(getData1()); 162 ID.AddPointer(getData2()); 163 ID.AddPointer(getLocationContext()); 164 ID.AddPointer(getTag()); 165 } 166 167 static ProgramPoint getProgramPoint(const Stmt *S, ProgramPoint::Kind K, 168 const LocationContext *LC, 169 const ProgramPointTag *tag); 170 }; 171 172 class BlockEntrance : public ProgramPoint { 173 public: 174 BlockEntrance(const CFGBlock *B, const LocationContext *L, 175 const ProgramPointTag *tag = 0) ProgramPoint(B,BlockEntranceKind,L,tag)176 : ProgramPoint(B, BlockEntranceKind, L, tag) { 177 assert(B && "BlockEntrance requires non-null block"); 178 } 179 getBlock()180 const CFGBlock *getBlock() const { 181 return reinterpret_cast<const CFGBlock*>(getData1()); 182 } 183 getFirstElement()184 const CFGElement getFirstElement() const { 185 const CFGBlock *B = getBlock(); 186 return B->empty() ? CFGElement() : B->front(); 187 } 188 classof(const ProgramPoint * Location)189 static bool classof(const ProgramPoint* Location) { 190 return Location->getKind() == BlockEntranceKind; 191 } 192 }; 193 194 class BlockExit : public ProgramPoint { 195 public: BlockExit(const CFGBlock * B,const LocationContext * L)196 BlockExit(const CFGBlock *B, const LocationContext *L) 197 : ProgramPoint(B, BlockExitKind, L) {} 198 getBlock()199 const CFGBlock *getBlock() const { 200 return reinterpret_cast<const CFGBlock*>(getData1()); 201 } 202 getTerminator()203 const Stmt *getTerminator() const { 204 return getBlock()->getTerminator(); 205 } 206 classof(const ProgramPoint * Location)207 static bool classof(const ProgramPoint* Location) { 208 return Location->getKind() == BlockExitKind; 209 } 210 }; 211 212 class StmtPoint : public ProgramPoint { 213 public: StmtPoint(const Stmt * S,const void * p2,Kind k,const LocationContext * L,const ProgramPointTag * tag)214 StmtPoint(const Stmt *S, const void *p2, Kind k, const LocationContext *L, 215 const ProgramPointTag *tag) 216 : ProgramPoint(S, p2, k, L, tag) { 217 assert(S); 218 } 219 getStmt()220 const Stmt *getStmt() const { return (const Stmt*) getData1(); } 221 222 template <typename T> getStmtAs()223 const T* getStmtAs() const { return llvm::dyn_cast<T>(getStmt()); } 224 classof(const ProgramPoint * Location)225 static bool classof(const ProgramPoint* Location) { 226 unsigned k = Location->getKind(); 227 return k >= PreStmtKind && k <= MaxPostStmtKind; 228 } 229 }; 230 231 232 class PreStmt : public StmtPoint { 233 public: 234 PreStmt(const Stmt *S, const LocationContext *L, const ProgramPointTag *tag, 235 const Stmt *SubStmt = 0) StmtPoint(S,SubStmt,PreStmtKind,L,tag)236 : StmtPoint(S, SubStmt, PreStmtKind, L, tag) {} 237 getSubStmt()238 const Stmt *getSubStmt() const { return (const Stmt*) getData2(); } 239 classof(const ProgramPoint * Location)240 static bool classof(const ProgramPoint* Location) { 241 return Location->getKind() == PreStmtKind; 242 } 243 }; 244 245 class PostStmt : public StmtPoint { 246 protected: 247 PostStmt(const Stmt *S, const void *data, Kind k, const LocationContext *L, 248 const ProgramPointTag *tag = 0) StmtPoint(S,data,k,L,tag)249 : StmtPoint(S, data, k, L, tag) {} 250 251 public: 252 explicit PostStmt(const Stmt *S, Kind k, 253 const LocationContext *L, const ProgramPointTag *tag = 0) StmtPoint(S,NULL,k,L,tag)254 : StmtPoint(S, NULL, k, L, tag) {} 255 256 explicit PostStmt(const Stmt *S, const LocationContext *L, 257 const ProgramPointTag *tag = 0) StmtPoint(S,NULL,PostStmtKind,L,tag)258 : StmtPoint(S, NULL, PostStmtKind, L, tag) {} 259 classof(const ProgramPoint * Location)260 static bool classof(const ProgramPoint* Location) { 261 unsigned k = Location->getKind(); 262 return k >= MinPostStmtKind && k <= MaxPostStmtKind; 263 } 264 }; 265 266 // PostCondition represents the post program point of a branch condition. 267 class PostCondition : public PostStmt { 268 public: 269 PostCondition(const Stmt *S, const LocationContext *L, 270 const ProgramPointTag *tag = 0) PostStmt(S,PostConditionKind,L,tag)271 : PostStmt(S, PostConditionKind, L, tag) {} 272 classof(const ProgramPoint * Location)273 static bool classof(const ProgramPoint* Location) { 274 return Location->getKind() == PostConditionKind; 275 } 276 }; 277 278 class LocationCheck : public StmtPoint { 279 protected: LocationCheck(const Stmt * S,const LocationContext * L,ProgramPoint::Kind K,const ProgramPointTag * tag)280 LocationCheck(const Stmt *S, const LocationContext *L, 281 ProgramPoint::Kind K, const ProgramPointTag *tag) 282 : StmtPoint(S, NULL, K, L, tag) {} 283 classof(const ProgramPoint * location)284 static bool classof(const ProgramPoint *location) { 285 unsigned k = location->getKind(); 286 return k == PreLoadKind || k == PreStoreKind; 287 } 288 }; 289 290 class PreLoad : public LocationCheck { 291 public: 292 PreLoad(const Stmt *S, const LocationContext *L, 293 const ProgramPointTag *tag = 0) LocationCheck(S,L,PreLoadKind,tag)294 : LocationCheck(S, L, PreLoadKind, tag) {} 295 classof(const ProgramPoint * location)296 static bool classof(const ProgramPoint *location) { 297 return location->getKind() == PreLoadKind; 298 } 299 }; 300 301 class PreStore : public LocationCheck { 302 public: 303 PreStore(const Stmt *S, const LocationContext *L, 304 const ProgramPointTag *tag = 0) LocationCheck(S,L,PreStoreKind,tag)305 : LocationCheck(S, L, PreStoreKind, tag) {} 306 classof(const ProgramPoint * location)307 static bool classof(const ProgramPoint *location) { 308 return location->getKind() == PreStoreKind; 309 } 310 }; 311 312 class PostLoad : public PostStmt { 313 public: 314 PostLoad(const Stmt *S, const LocationContext *L, 315 const ProgramPointTag *tag = 0) PostStmt(S,PostLoadKind,L,tag)316 : PostStmt(S, PostLoadKind, L, tag) {} 317 classof(const ProgramPoint * Location)318 static bool classof(const ProgramPoint* Location) { 319 return Location->getKind() == PostLoadKind; 320 } 321 }; 322 323 /// \brief Represents a program point after a store evaluation. 324 class PostStore : public PostStmt { 325 public: 326 /// Construct the post store point. 327 /// \param Loc can be used to store the information about the location 328 /// used in the form it was uttered in the code. 329 PostStore(const Stmt *S, const LocationContext *L, const void *Loc, 330 const ProgramPointTag *tag = 0) PostStmt(S,PostStoreKind,L,tag)331 : PostStmt(S, PostStoreKind, L, tag) { 332 assert(getData2() == 0); 333 setData2(Loc); 334 } 335 classof(const ProgramPoint * Location)336 static bool classof(const ProgramPoint* Location) { 337 return Location->getKind() == PostStoreKind; 338 } 339 340 /// \brief Returns the information about the location used in the store, 341 /// how it was uttered in the code. getLocationValue()342 const void *getLocationValue() const { 343 return getData2(); 344 } 345 346 }; 347 348 class PostLValue : public PostStmt { 349 public: 350 PostLValue(const Stmt *S, const LocationContext *L, 351 const ProgramPointTag *tag = 0) PostStmt(S,PostLValueKind,L,tag)352 : PostStmt(S, PostLValueKind, L, tag) {} 353 classof(const ProgramPoint * Location)354 static bool classof(const ProgramPoint* Location) { 355 return Location->getKind() == PostLValueKind; 356 } 357 }; 358 359 /// Represents a point after we ran remove dead bindings BEFORE 360 /// processing the given statement. 361 class PreStmtPurgeDeadSymbols : public StmtPoint { 362 public: 363 PreStmtPurgeDeadSymbols(const Stmt *S, const LocationContext *L, 364 const ProgramPointTag *tag = 0) 365 : StmtPoint(S, 0, PreStmtPurgeDeadSymbolsKind, L, tag) { } 366 classof(const ProgramPoint * Location)367 static bool classof(const ProgramPoint* Location) { 368 return Location->getKind() == PreStmtPurgeDeadSymbolsKind; 369 } 370 }; 371 372 /// Represents a point after we ran remove dead bindings AFTER 373 /// processing the given statement. 374 class PostStmtPurgeDeadSymbols : public StmtPoint { 375 public: 376 PostStmtPurgeDeadSymbols(const Stmt *S, const LocationContext *L, 377 const ProgramPointTag *tag = 0) 378 : StmtPoint(S, 0, PostStmtPurgeDeadSymbolsKind, L, tag) { } 379 classof(const ProgramPoint * Location)380 static bool classof(const ProgramPoint* Location) { 381 return Location->getKind() == PostStmtPurgeDeadSymbolsKind; 382 } 383 }; 384 385 class BlockEdge : public ProgramPoint { 386 public: BlockEdge(const CFGBlock * B1,const CFGBlock * B2,const LocationContext * L)387 BlockEdge(const CFGBlock *B1, const CFGBlock *B2, const LocationContext *L) 388 : ProgramPoint(B1, B2, BlockEdgeKind, L) { 389 assert(B1 && "BlockEdge: source block must be non-null"); 390 assert(B2 && "BlockEdge: destination block must be non-null"); 391 } 392 getSrc()393 const CFGBlock *getSrc() const { 394 return static_cast<const CFGBlock*>(getData1()); 395 } 396 getDst()397 const CFGBlock *getDst() const { 398 return static_cast<const CFGBlock*>(getData2()); 399 } 400 classof(const ProgramPoint * Location)401 static bool classof(const ProgramPoint* Location) { 402 return Location->getKind() == BlockEdgeKind; 403 } 404 }; 405 406 class PostInitializer : public ProgramPoint { 407 public: PostInitializer(const CXXCtorInitializer * I,const LocationContext * L)408 PostInitializer(const CXXCtorInitializer *I, 409 const LocationContext *L) 410 : ProgramPoint(I, PostInitializerKind, L) {} 411 classof(const ProgramPoint * Location)412 static bool classof(const ProgramPoint *Location) { 413 return Location->getKind() == PostInitializerKind; 414 } 415 }; 416 417 /// Represents an implicit call event. 418 /// 419 /// The nearest statement is provided for diagnostic purposes. 420 class ImplicitCallPoint : public ProgramPoint { 421 public: ImplicitCallPoint(const Decl * D,SourceLocation Loc,Kind K,const LocationContext * L,const ProgramPointTag * Tag)422 ImplicitCallPoint(const Decl *D, SourceLocation Loc, Kind K, 423 const LocationContext *L, const ProgramPointTag *Tag) 424 : ProgramPoint(Loc.getPtrEncoding(), D, K, L, Tag) {} 425 getDecl()426 const Decl *getDecl() const { return static_cast<const Decl *>(getData2()); } getLocation()427 SourceLocation getLocation() const { 428 return SourceLocation::getFromPtrEncoding(getData1()); 429 } 430 classof(const ProgramPoint * Location)431 static bool classof(const ProgramPoint *Location) { 432 return Location->getKind() >= MinImplicitCallKind && 433 Location->getKind() <= MaxImplicitCallKind; 434 } 435 }; 436 437 /// Represents a program point just before an implicit call event. 438 /// 439 /// Explicit calls will appear as PreStmt program points. 440 class PreImplicitCall : public ImplicitCallPoint { 441 public: 442 PreImplicitCall(const Decl *D, SourceLocation Loc, 443 const LocationContext *L, const ProgramPointTag *Tag = 0) ImplicitCallPoint(D,Loc,PreImplicitCallKind,L,Tag)444 : ImplicitCallPoint(D, Loc, PreImplicitCallKind, L, Tag) {} 445 classof(const ProgramPoint * Location)446 static bool classof(const ProgramPoint *Location) { 447 return Location->getKind() == PreImplicitCallKind; 448 } 449 }; 450 451 /// Represents a program point just after an implicit call event. 452 /// 453 /// Explicit calls will appear as PostStmt program points. 454 class PostImplicitCall : public ImplicitCallPoint { 455 public: 456 PostImplicitCall(const Decl *D, SourceLocation Loc, 457 const LocationContext *L, const ProgramPointTag *Tag = 0) ImplicitCallPoint(D,Loc,PostImplicitCallKind,L,Tag)458 : ImplicitCallPoint(D, Loc, PostImplicitCallKind, L, Tag) {} 459 classof(const ProgramPoint * Location)460 static bool classof(const ProgramPoint *Location) { 461 return Location->getKind() == PostImplicitCallKind; 462 } 463 }; 464 465 /// Represents a point when we begin processing an inlined call. 466 /// CallEnter uses the caller's location context. 467 class CallEnter : public ProgramPoint { 468 public: CallEnter(const Stmt * stmt,const StackFrameContext * calleeCtx,const LocationContext * callerCtx)469 CallEnter(const Stmt *stmt, const StackFrameContext *calleeCtx, 470 const LocationContext *callerCtx) 471 : ProgramPoint(stmt, calleeCtx, CallEnterKind, callerCtx, 0) {} 472 getCallExpr()473 const Stmt *getCallExpr() const { 474 return static_cast<const Stmt *>(getData1()); 475 } 476 getCalleeContext()477 const StackFrameContext *getCalleeContext() const { 478 return static_cast<const StackFrameContext *>(getData2()); 479 } 480 classof(const ProgramPoint * Location)481 static bool classof(const ProgramPoint *Location) { 482 return Location->getKind() == CallEnterKind; 483 } 484 }; 485 486 /// Represents a point when we start the call exit sequence (for inlined call). 487 /// 488 /// The call exit is simulated with a sequence of nodes, which occur between 489 /// CallExitBegin and CallExitEnd. The following operations occur between the 490 /// two program points: 491 /// - CallExitBegin 492 /// - Bind the return value 493 /// - Run Remove dead bindings (to clean up the dead symbols from the callee). 494 /// - CallExitEnd 495 class CallExitBegin : public ProgramPoint { 496 public: 497 // CallExitBegin uses the callee's location context. CallExitBegin(const StackFrameContext * L)498 CallExitBegin(const StackFrameContext *L) 499 : ProgramPoint(0, CallExitBeginKind, L, 0) {} 500 classof(const ProgramPoint * Location)501 static bool classof(const ProgramPoint *Location) { 502 return Location->getKind() == CallExitBeginKind; 503 } 504 }; 505 506 /// Represents a point when we finish the call exit sequence (for inlined call). 507 /// \sa CallExitBegin 508 class CallExitEnd : public ProgramPoint { 509 public: 510 // CallExitEnd uses the caller's location context. CallExitEnd(const StackFrameContext * CalleeCtx,const LocationContext * CallerCtx)511 CallExitEnd(const StackFrameContext *CalleeCtx, 512 const LocationContext *CallerCtx) 513 : ProgramPoint(CalleeCtx, CallExitEndKind, CallerCtx, 0) {} 514 getCalleeContext()515 const StackFrameContext *getCalleeContext() const { 516 return static_cast<const StackFrameContext *>(getData1()); 517 } 518 classof(const ProgramPoint * Location)519 static bool classof(const ProgramPoint *Location) { 520 return Location->getKind() == CallExitEndKind; 521 } 522 }; 523 524 /// This is a meta program point, which should be skipped by all the diagnostic 525 /// reasoning etc. 526 class EpsilonPoint : public ProgramPoint { 527 public: 528 EpsilonPoint(const LocationContext *L, const void *Data1, 529 const void *Data2 = 0, const ProgramPointTag *tag = 0) ProgramPoint(Data1,Data2,EpsilonKind,L,tag)530 : ProgramPoint(Data1, Data2, EpsilonKind, L, tag) {} 531 getData()532 const void *getData() const { return getData1(); } 533 classof(const ProgramPoint * Location)534 static bool classof(const ProgramPoint* Location) { 535 return Location->getKind() == EpsilonKind; 536 } 537 }; 538 539 /// ProgramPoints can be "tagged" as representing points specific to a given 540 /// analysis entity. Tags are abstract annotations, with an associated 541 /// description and potentially other information. 542 class ProgramPointTag { 543 public: TagKind(tagKind)544 ProgramPointTag(void *tagKind = 0) : TagKind(tagKind) {} 545 virtual ~ProgramPointTag(); 546 virtual StringRef getTagDescription() const = 0; 547 548 protected: 549 /// Used to implement 'classof' in subclasses. getTagKind()550 const void *getTagKind() { return TagKind; } 551 552 private: 553 const void *TagKind; 554 }; 555 556 class SimpleProgramPointTag : public ProgramPointTag { 557 std::string desc; 558 public: 559 SimpleProgramPointTag(StringRef description); 560 StringRef getTagDescription() const; 561 }; 562 563 } // end namespace clang 564 565 566 namespace llvm { // Traits specialization for DenseMap 567 568 template <> struct DenseMapInfo<clang::ProgramPoint> { 569 570 static inline clang::ProgramPoint getEmptyKey() { 571 uintptr_t x = 572 reinterpret_cast<uintptr_t>(DenseMapInfo<void*>::getEmptyKey()) & ~0x7; 573 return clang::BlockEntrance(reinterpret_cast<clang::CFGBlock*>(x), 0); 574 } 575 576 static inline clang::ProgramPoint getTombstoneKey() { 577 uintptr_t x = 578 reinterpret_cast<uintptr_t>(DenseMapInfo<void*>::getTombstoneKey()) & ~0x7; 579 return clang::BlockEntrance(reinterpret_cast<clang::CFGBlock*>(x), 0); 580 } 581 582 static unsigned getHashValue(const clang::ProgramPoint &Loc) { 583 return Loc.getHashValue(); 584 } 585 586 static bool isEqual(const clang::ProgramPoint &L, 587 const clang::ProgramPoint &R) { 588 return L == R; 589 } 590 591 }; 592 593 template <> 594 struct isPodLike<clang::ProgramPoint> { static const bool value = true; }; 595 596 } // end namespace llvm 597 598 #endif 599