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