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