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