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