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