ProgramPoint.h revision 03509aea098772644bf4662dc1c88634818ceecc
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/System/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 CallEnterKind, 48 CallExitKind, 49 MinPostStmtKind = PostStmtKind, 50 MaxPostStmtKind = PostLValueKind }; 51 52private: 53 std::pair<const void *, const void *> Data; 54 Kind K; 55 56 // The LocationContext could be NULL to allow ProgramPoint to be used in 57 // context insensitive analysis. 58 const LocationContext *L; 59 const void *Tag; 60 61protected: 62 ProgramPoint(const void* P, Kind k, const LocationContext *l, 63 const void *tag = 0) 64 : Data(P, static_cast<const void*>(NULL)), K(k), L(l), Tag(tag) {} 65 66 ProgramPoint(const void* P1, const void* P2, Kind k, const LocationContext *l, 67 const void *tag = 0) 68 : Data(P1, P2), K(k), L(l), Tag(tag) {} 69 70protected: 71 const void* getData1() const { return Data.first; } 72 const void* getData2() const { return Data.second; } 73 const void *getTag() const { return Tag; } 74 75public: 76 Kind getKind() const { return K; } 77 78 const LocationContext *getLocationContext() const { return L; } 79 80 // For use with DenseMap. This hash is probably slow. 81 unsigned getHashValue() const { 82 llvm::FoldingSetNodeID ID; 83 Profile(ID); 84 return ID.ComputeHash(); 85 } 86 87 static bool classof(const ProgramPoint*) { return true; } 88 89 bool operator==(const ProgramPoint & RHS) const { 90 return K == RHS.K && Data == RHS.Data && L == RHS.L && Tag == RHS.Tag; 91 } 92 93 bool operator!=(const ProgramPoint& RHS) const { 94 return K != RHS.K || Data != RHS.Data || L != RHS.L || Tag != RHS.Tag; 95 } 96 97 void Profile(llvm::FoldingSetNodeID& ID) const { 98 ID.AddInteger((unsigned) K); 99 ID.AddPointer(Data.first); 100 ID.AddPointer(Data.second); 101 ID.AddPointer(L); 102 ID.AddPointer(Tag); 103 } 104}; 105 106class BlockEntrance : public ProgramPoint { 107public: 108 BlockEntrance(const CFGBlock* B, const LocationContext *L, 109 const void *tag = 0) 110 : ProgramPoint(B, BlockEntranceKind, L, tag) {} 111 112 const CFGBlock* getBlock() const { 113 return reinterpret_cast<const CFGBlock*>(getData1()); 114 } 115 116 const CFGElement getFirstElement() const { 117 const CFGBlock* B = getBlock(); 118 return B->empty() ? CFGElement() : B->front(); 119 } 120 121 const Stmt *getFirstStmt() const { 122 return getFirstElement().getStmt(); 123 } 124 125 static bool classof(const ProgramPoint* Location) { 126 return Location->getKind() == BlockEntranceKind; 127 } 128}; 129 130class BlockExit : public ProgramPoint { 131public: 132 BlockExit(const CFGBlock* B, const LocationContext *L) 133 : ProgramPoint(B, BlockExitKind, L) {} 134 135 const CFGBlock* getBlock() const { 136 return reinterpret_cast<const CFGBlock*>(getData1()); 137 } 138 139 const Stmt* getLastStmt() const { 140 const CFGBlock* B = getBlock(); 141 return B->empty() ? CFGElement() : B->back(); 142 } 143 144 const Stmt* getTerminator() const { 145 return getBlock()->getTerminator(); 146 } 147 148 static bool classof(const ProgramPoint* Location) { 149 return Location->getKind() == BlockExitKind; 150 } 151}; 152 153class StmtPoint : public ProgramPoint { 154public: 155 StmtPoint(const Stmt *S, const void *p2, Kind k, const LocationContext *L, 156 const void *tag) 157 : ProgramPoint(S, p2, k, L, tag) {} 158 159 const Stmt *getStmt() const { return (const Stmt*) getData1(); } 160 161 template <typename T> 162 const T* getStmtAs() const { return llvm::dyn_cast<T>(getStmt()); } 163 164 static bool classof(const ProgramPoint* Location) { 165 unsigned k = Location->getKind(); 166 return k >= PreStmtKind && k <= MaxPostStmtKind; 167 } 168}; 169 170 171class PreStmt : public StmtPoint { 172public: 173 PreStmt(const Stmt *S, const LocationContext *L, const void *tag, 174 const Stmt *SubStmt = 0) 175 : StmtPoint(S, SubStmt, PreStmtKind, L, tag) {} 176 177 const Stmt *getSubStmt() const { return (const Stmt*) getData2(); } 178 179 static bool classof(const ProgramPoint* Location) { 180 return Location->getKind() == PreStmtKind; 181 } 182}; 183 184class PostStmt : public StmtPoint { 185protected: 186 PostStmt(const Stmt* S, Kind k, const LocationContext *L, const void *tag = 0) 187 : StmtPoint(S, NULL, k, L, tag) {} 188 189 PostStmt(const Stmt* S, const void* data, Kind k, const LocationContext *L, 190 const void *tag =0) 191 : StmtPoint(S, data, k, L, tag) {} 192 193public: 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 CallEnter : public StmtPoint { 317public: 318 // L is caller's location context. AC is callee's AnalysisContext. 319 CallEnter(const Stmt *S, const AnalysisContext *AC, const LocationContext *L) 320 : StmtPoint(S, AC, CallEnterKind, L, 0) {} 321 322 const Stmt *getCallExpr() const { 323 return static_cast<const Stmt *>(getData1()); 324 } 325 326 const AnalysisContext *getCalleeContext() const { 327 return static_cast<const AnalysisContext *>(getData2()); 328 } 329 330 static bool classof(const ProgramPoint *Location) { 331 return Location->getKind() == CallEnterKind; 332 } 333}; 334 335class CallExit : public StmtPoint { 336public: 337 // CallExit uses the callee's location context. 338 CallExit(const Stmt *S, const LocationContext *L) 339 : StmtPoint(S, 0, CallExitKind, L, 0) {} 340 341 static bool classof(const ProgramPoint *Location) { 342 return Location->getKind() == CallExitKind; 343 } 344}; 345 346 347} // end namespace clang 348 349 350namespace llvm { // Traits specialization for DenseMap 351 352template <> struct DenseMapInfo<clang::ProgramPoint> { 353 354static inline clang::ProgramPoint getEmptyKey() { 355 uintptr_t x = 356 reinterpret_cast<uintptr_t>(DenseMapInfo<void*>::getEmptyKey()) & ~0x7; 357 return clang::BlockEntrance(reinterpret_cast<clang::CFGBlock*>(x), 0); 358} 359 360static inline clang::ProgramPoint getTombstoneKey() { 361 uintptr_t x = 362 reinterpret_cast<uintptr_t>(DenseMapInfo<void*>::getTombstoneKey()) & ~0x7; 363 return clang::BlockEntrance(reinterpret_cast<clang::CFGBlock*>(x), 0); 364} 365 366static unsigned getHashValue(const clang::ProgramPoint& Loc) { 367 return Loc.getHashValue(); 368} 369 370static bool isEqual(const clang::ProgramPoint& L, 371 const clang::ProgramPoint& R) { 372 return L == R; 373} 374 375}; 376 377template <> 378struct isPodLike<clang::ProgramPoint> { static const bool value = true; }; 379 380} // end namespace llvm 381 382#endif 383