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