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