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 30namespace clang { 31 32class AnalysisDeclContext; 33class FunctionDecl; 34class LocationContext; 35class ProgramPointTag; 36 37class ProgramPoint { 38public: 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 64private: 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 76protected: 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 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. 124 bool isPurgeKind() { 125 Kind K = getKind(); 126 return (K == PostStmtPurgeDeadSymbolsKind || 127 K == PreStmtPurgeDeadSymbolsKind); 128 } 129 130 const ProgramPointTag *getTag() const { return Tag.getPointer(); } 131 132 const LocationContext *getLocationContext() const { 133 return L.getPointer(); 134 } 135 136 // For use with DenseMap. This hash is probably slow. 137 unsigned getHashValue() const { 138 llvm::FoldingSetNodeID ID; 139 Profile(ID); 140 return ID.ComputeHash(); 141 } 142 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 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 172class BlockEntrance : public ProgramPoint { 173public: 174 BlockEntrance(const CFGBlock *B, const LocationContext *L, 175 const ProgramPointTag *tag = 0) 176 : ProgramPoint(B, BlockEntranceKind, L, tag) { 177 assert(B && "BlockEntrance requires non-null block"); 178 } 179 180 const CFGBlock *getBlock() const { 181 return reinterpret_cast<const CFGBlock*>(getData1()); 182 } 183 184 const CFGElement getFirstElement() const { 185 const CFGBlock *B = getBlock(); 186 return B->empty() ? CFGElement() : B->front(); 187 } 188 189 static bool classof(const ProgramPoint* Location) { 190 return Location->getKind() == BlockEntranceKind; 191 } 192}; 193 194class BlockExit : public ProgramPoint { 195public: 196 BlockExit(const CFGBlock *B, const LocationContext *L) 197 : ProgramPoint(B, BlockExitKind, L) {} 198 199 const CFGBlock *getBlock() const { 200 return reinterpret_cast<const CFGBlock*>(getData1()); 201 } 202 203 const Stmt *getTerminator() const { 204 return getBlock()->getTerminator(); 205 } 206 207 static bool classof(const ProgramPoint* Location) { 208 return Location->getKind() == BlockExitKind; 209 } 210}; 211 212class StmtPoint : public ProgramPoint { 213public: 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 220 const Stmt *getStmt() const { return (const Stmt*) getData1(); } 221 222 template <typename T> 223 const T* getStmtAs() const { return llvm::dyn_cast<T>(getStmt()); } 224 225 static bool classof(const ProgramPoint* Location) { 226 unsigned k = Location->getKind(); 227 return k >= PreStmtKind && k <= MaxPostStmtKind; 228 } 229}; 230 231 232class PreStmt : public StmtPoint { 233public: 234 PreStmt(const Stmt *S, const LocationContext *L, const ProgramPointTag *tag, 235 const Stmt *SubStmt = 0) 236 : StmtPoint(S, SubStmt, PreStmtKind, L, tag) {} 237 238 const Stmt *getSubStmt() const { return (const Stmt*) getData2(); } 239 240 static bool classof(const ProgramPoint* Location) { 241 return Location->getKind() == PreStmtKind; 242 } 243}; 244 245class PostStmt : public StmtPoint { 246protected: 247 PostStmt(const Stmt *S, const void *data, Kind k, const LocationContext *L, 248 const ProgramPointTag *tag = 0) 249 : StmtPoint(S, data, k, L, tag) {} 250 251public: 252 explicit PostStmt(const Stmt *S, Kind k, 253 const LocationContext *L, const ProgramPointTag *tag = 0) 254 : StmtPoint(S, NULL, k, L, tag) {} 255 256 explicit PostStmt(const Stmt *S, const LocationContext *L, 257 const ProgramPointTag *tag = 0) 258 : StmtPoint(S, NULL, PostStmtKind, L, tag) {} 259 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. 267class PostCondition : public PostStmt { 268public: 269 PostCondition(const Stmt *S, const LocationContext *L, 270 const ProgramPointTag *tag = 0) 271 : PostStmt(S, PostConditionKind, L, tag) {} 272 273 static bool classof(const ProgramPoint* Location) { 274 return Location->getKind() == PostConditionKind; 275 } 276}; 277 278class LocationCheck : public StmtPoint { 279protected: 280 LocationCheck(const Stmt *S, const LocationContext *L, 281 ProgramPoint::Kind K, const ProgramPointTag *tag) 282 : StmtPoint(S, NULL, K, L, tag) {} 283 284 static bool classof(const ProgramPoint *location) { 285 unsigned k = location->getKind(); 286 return k == PreLoadKind || k == PreStoreKind; 287 } 288}; 289 290class PreLoad : public LocationCheck { 291public: 292 PreLoad(const Stmt *S, const LocationContext *L, 293 const ProgramPointTag *tag = 0) 294 : LocationCheck(S, L, PreLoadKind, tag) {} 295 296 static bool classof(const ProgramPoint *location) { 297 return location->getKind() == PreLoadKind; 298 } 299}; 300 301class PreStore : public LocationCheck { 302public: 303 PreStore(const Stmt *S, const LocationContext *L, 304 const ProgramPointTag *tag = 0) 305 : LocationCheck(S, L, PreStoreKind, tag) {} 306 307 static bool classof(const ProgramPoint *location) { 308 return location->getKind() == PreStoreKind; 309 } 310}; 311 312class PostLoad : public PostStmt { 313public: 314 PostLoad(const Stmt *S, const LocationContext *L, 315 const ProgramPointTag *tag = 0) 316 : PostStmt(S, PostLoadKind, L, tag) {} 317 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. 324class PostStore : public PostStmt { 325public: 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) 331 : PostStmt(S, PostStoreKind, L, tag) { 332 assert(getData2() == 0); 333 setData2(Loc); 334 } 335 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. 342 const void *getLocationValue() const { 343 return getData2(); 344 } 345 346}; 347 348class PostLValue : public PostStmt { 349public: 350 PostLValue(const Stmt *S, const LocationContext *L, 351 const ProgramPointTag *tag = 0) 352 : PostStmt(S, PostLValueKind, L, tag) {} 353 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. 361class PreStmtPurgeDeadSymbols : public StmtPoint { 362public: 363 PreStmtPurgeDeadSymbols(const Stmt *S, const LocationContext *L, 364 const ProgramPointTag *tag = 0) 365 : StmtPoint(S, 0, PreStmtPurgeDeadSymbolsKind, L, tag) { } 366 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. 374class PostStmtPurgeDeadSymbols : public StmtPoint { 375public: 376 PostStmtPurgeDeadSymbols(const Stmt *S, const LocationContext *L, 377 const ProgramPointTag *tag = 0) 378 : StmtPoint(S, 0, PostStmtPurgeDeadSymbolsKind, L, tag) { } 379 380 static bool classof(const ProgramPoint* Location) { 381 return Location->getKind() == PostStmtPurgeDeadSymbolsKind; 382 } 383}; 384 385class BlockEdge : public ProgramPoint { 386public: 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 393 const CFGBlock *getSrc() const { 394 return static_cast<const CFGBlock*>(getData1()); 395 } 396 397 const CFGBlock *getDst() const { 398 return static_cast<const CFGBlock*>(getData2()); 399 } 400 401 static bool classof(const ProgramPoint* Location) { 402 return Location->getKind() == BlockEdgeKind; 403 } 404}; 405 406class PostInitializer : public ProgramPoint { 407public: 408 PostInitializer(const CXXCtorInitializer *I, 409 const LocationContext *L) 410 : ProgramPoint(I, PostInitializerKind, L) {} 411 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. 420class ImplicitCallPoint : public ProgramPoint { 421public: 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 426 const Decl *getDecl() const { return static_cast<const Decl *>(getData2()); } 427 SourceLocation getLocation() const { 428 return SourceLocation::getFromPtrEncoding(getData1()); 429 } 430 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. 440class PreImplicitCall : public ImplicitCallPoint { 441public: 442 PreImplicitCall(const Decl *D, SourceLocation Loc, 443 const LocationContext *L, const ProgramPointTag *Tag = 0) 444 : ImplicitCallPoint(D, Loc, PreImplicitCallKind, L, Tag) {} 445 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. 454class PostImplicitCall : public ImplicitCallPoint { 455public: 456 PostImplicitCall(const Decl *D, SourceLocation Loc, 457 const LocationContext *L, const ProgramPointTag *Tag = 0) 458 : ImplicitCallPoint(D, Loc, PostImplicitCallKind, L, Tag) {} 459 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. 467class CallEnter : public ProgramPoint { 468public: 469 CallEnter(const Stmt *stmt, const StackFrameContext *calleeCtx, 470 const LocationContext *callerCtx) 471 : ProgramPoint(stmt, calleeCtx, CallEnterKind, callerCtx, 0) {} 472 473 const Stmt *getCallExpr() const { 474 return static_cast<const Stmt *>(getData1()); 475 } 476 477 const StackFrameContext *getCalleeContext() const { 478 return static_cast<const StackFrameContext *>(getData2()); 479 } 480 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 495class CallExitBegin : public ProgramPoint { 496public: 497 // CallExitBegin uses the callee's location context. 498 CallExitBegin(const StackFrameContext *L) 499 : ProgramPoint(0, CallExitBeginKind, L, 0) {} 500 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 508class CallExitEnd : public ProgramPoint { 509public: 510 // CallExitEnd uses the caller's location context. 511 CallExitEnd(const StackFrameContext *CalleeCtx, 512 const LocationContext *CallerCtx) 513 : ProgramPoint(CalleeCtx, CallExitEndKind, CallerCtx, 0) {} 514 515 const StackFrameContext *getCalleeContext() const { 516 return static_cast<const StackFrameContext *>(getData1()); 517 } 518 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. 526class EpsilonPoint : public ProgramPoint { 527public: 528 EpsilonPoint(const LocationContext *L, const void *Data1, 529 const void *Data2 = 0, const ProgramPointTag *tag = 0) 530 : ProgramPoint(Data1, Data2, EpsilonKind, L, tag) {} 531 532 const void *getData() const { return getData1(); } 533 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. 542class ProgramPointTag { 543public: 544 ProgramPointTag(void *tagKind = 0) : TagKind(tagKind) {} 545 virtual ~ProgramPointTag(); 546 virtual StringRef getTagDescription() const = 0; 547 548protected: 549 /// Used to implement 'classof' in subclasses. 550 const void *getTagKind() { return TagKind; } 551 552private: 553 const void *TagKind; 554}; 555 556class SimpleProgramPointTag : public ProgramPointTag { 557 std::string desc; 558public: 559 SimpleProgramPointTag(StringRef description); 560 StringRef getTagDescription() const; 561}; 562 563} // end namespace clang 564 565 566namespace llvm { // Traits specialization for DenseMap 567 568template <> struct DenseMapInfo<clang::ProgramPoint> { 569 570static 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 576static 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 582static unsigned getHashValue(const clang::ProgramPoint &Loc) { 583 return Loc.getHashValue(); 584} 585 586static bool isEqual(const clang::ProgramPoint &L, 587 const clang::ProgramPoint &R) { 588 return L == R; 589} 590 591}; 592 593template <> 594struct isPodLike<clang::ProgramPoint> { static const bool value = true; }; 595 596} // end namespace llvm 597 598#endif 599