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