ProgramPoint.h revision 8083414ee7cc8f5c807ed6a4e120fb4e0ab50ff8
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 PostConditionKind, 47 PostLValueKind, 48 PostInitializerKind, 49 CallEnterKind, 50 CallExitKind, 51 MinPostStmtKind = PostStmtKind, 52 MaxPostStmtKind = CallExitKind }; 53 54private: 55 std::pair<const void *, const void *> Data; 56 Kind K; 57 58 // The LocationContext could be NULL to allow ProgramPoint to be used in 59 // context insensitive analysis. 60 const LocationContext *L; 61 const void *Tag; 62 63protected: 64 ProgramPoint(const void* P, Kind k, const LocationContext *l, 65 const void *tag = 0) 66 : Data(P, static_cast<const void*>(NULL)), K(k), L(l), Tag(tag) {} 67 68 ProgramPoint(const void* P1, const void* P2, Kind k, const LocationContext *l, 69 const void *tag = 0) 70 : Data(P1, P2), K(k), L(l), Tag(tag) {} 71 72protected: 73 const void* getData1() const { return Data.first; } 74 const void* getData2() const { return Data.second; } 75 76public: 77 Kind getKind() const { return K; } 78 79 const void *getTag() const { return Tag; } 80 81 const LocationContext *getLocationContext() const { return L; } 82 83 // For use with DenseMap. This hash is probably slow. 84 unsigned getHashValue() const { 85 llvm::FoldingSetNodeID ID; 86 Profile(ID); 87 return ID.ComputeHash(); 88 } 89 90 static bool classof(const ProgramPoint*) { return true; } 91 92 bool operator==(const ProgramPoint & RHS) const { 93 return K == RHS.K && Data == RHS.Data && L == RHS.L && Tag == RHS.Tag; 94 } 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 void Profile(llvm::FoldingSetNodeID& ID) const { 101 ID.AddInteger((unsigned) K); 102 ID.AddPointer(Data.first); 103 ID.AddPointer(Data.second); 104 ID.AddPointer(L); 105 ID.AddPointer(Tag); 106 } 107}; 108 109class BlockEntrance : public ProgramPoint { 110public: 111 BlockEntrance(const CFGBlock* B, const LocationContext *L, 112 const void *tag = 0) 113 : ProgramPoint(B, BlockEntranceKind, L, tag) {} 114 115 const CFGBlock* getBlock() const { 116 return reinterpret_cast<const CFGBlock*>(getData1()); 117 } 118 119 const CFGElement getFirstElement() const { 120 const CFGBlock* B = getBlock(); 121 return B->empty() ? CFGElement() : B->front(); 122 } 123 124 /// Create a new BlockEntrance object that is the same as the original 125 /// except for using the specified tag value. 126 BlockEntrance withTag(const void *tag) { 127 return BlockEntrance(getBlock(), getLocationContext(), tag); 128 } 129 130 static bool classof(const ProgramPoint* Location) { 131 return Location->getKind() == BlockEntranceKind; 132 } 133}; 134 135class BlockExit : public ProgramPoint { 136public: 137 BlockExit(const CFGBlock* B, const LocationContext *L) 138 : ProgramPoint(B, BlockExitKind, L) {} 139 140 const CFGBlock* getBlock() const { 141 return reinterpret_cast<const CFGBlock*>(getData1()); 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, const void* data, Kind k, const LocationContext *L, 187 const void *tag =0) 188 : StmtPoint(S, data, k, L, tag) {} 189 190public: 191 explicit PostStmt(const Stmt* S, Kind k, 192 const LocationContext *L, const void *tag = 0) 193 : StmtPoint(S, NULL, k, L, tag) {} 194 195 explicit PostStmt(const Stmt* S, const LocationContext *L,const void *tag = 0) 196 : StmtPoint(S, NULL, PostStmtKind, L, tag) {} 197 198 static bool classof(const ProgramPoint* Location) { 199 unsigned k = Location->getKind(); 200 return k >= MinPostStmtKind && k <= MaxPostStmtKind; 201 } 202}; 203 204class PostStmtCustom : public PostStmt { 205public: 206 PostStmtCustom(const Stmt* S, 207 const std::pair<const void*, const void*>* TaggedData,\ 208 const LocationContext *L) 209 : PostStmt(S, TaggedData, PostStmtCustomKind, L) {} 210 211 const std::pair<const void*, const void*>& getTaggedPair() const { 212 return 213 *reinterpret_cast<const std::pair<const void*, const void*>*>(getData2()); 214 } 215 216 const void* getTag() const { return getTaggedPair().first; } 217 218 const void* getTaggedData() const { return getTaggedPair().second; } 219 220 static bool classof(const ProgramPoint* Location) { 221 return Location->getKind() == PostStmtCustomKind; 222 } 223}; 224 225// PostCondition represents the post program point of a branch condition. 226class PostCondition : public PostStmt { 227public: 228 PostCondition(const Stmt* S, const LocationContext *L, const void *tag = 0) 229 : PostStmt(S, PostConditionKind, L, tag) {} 230 231 static bool classof(const ProgramPoint* Location) { 232 return Location->getKind() == PostConditionKind; 233 } 234}; 235 236class LocationCheck : public StmtPoint { 237protected: 238 LocationCheck(const Stmt *S, const LocationContext *L, 239 ProgramPoint::Kind K, const void *tag) 240 : StmtPoint(S, NULL, K, L, tag) {} 241 242 static bool classof(const ProgramPoint *location) { 243 unsigned k = location->getKind(); 244 return k == PreLoadKind || k == PreStoreKind; 245 } 246}; 247 248class PreLoad : public LocationCheck { 249public: 250 PreLoad(const Stmt *S, const LocationContext *L, const void *tag = 0) 251 : LocationCheck(S, L, PreLoadKind, tag) {} 252 253 static bool classof(const ProgramPoint *location) { 254 return location->getKind() == PreLoadKind; 255 } 256}; 257 258class PreStore : public LocationCheck { 259public: 260 PreStore(const Stmt *S, const LocationContext *L, const void *tag = 0) 261 : LocationCheck(S, L, PreStoreKind, tag) {} 262 263 static bool classof(const ProgramPoint *location) { 264 return location->getKind() == PreStoreKind; 265 } 266}; 267 268class PostLoad : public PostStmt { 269public: 270 PostLoad(const Stmt* S, const LocationContext *L, const void *tag = 0) 271 : PostStmt(S, PostLoadKind, L, tag) {} 272 273 static bool classof(const ProgramPoint* Location) { 274 return Location->getKind() == PostLoadKind; 275 } 276}; 277 278class PostStore : public PostStmt { 279public: 280 PostStore(const Stmt* S, const LocationContext *L, const void *tag = 0) 281 : PostStmt(S, PostStoreKind, L, tag) {} 282 283 static bool classof(const ProgramPoint* Location) { 284 return Location->getKind() == PostStoreKind; 285 } 286}; 287 288class PostLValue : public PostStmt { 289public: 290 PostLValue(const Stmt* S, const LocationContext *L, const void *tag = 0) 291 : PostStmt(S, PostLValueKind, L, tag) {} 292 293 static bool classof(const ProgramPoint* Location) { 294 return Location->getKind() == PostLValueKind; 295 } 296}; 297 298class PostPurgeDeadSymbols : public PostStmt { 299public: 300 PostPurgeDeadSymbols(const Stmt* S, const LocationContext *L, 301 const void *tag = 0) 302 : PostStmt(S, PostPurgeDeadSymbolsKind, L, tag) {} 303 304 static bool classof(const ProgramPoint* Location) { 305 return Location->getKind() == PostPurgeDeadSymbolsKind; 306 } 307}; 308 309class BlockEdge : public ProgramPoint { 310public: 311 BlockEdge(const CFGBlock* B1, const CFGBlock* B2, const LocationContext *L) 312 : ProgramPoint(B1, B2, BlockEdgeKind, L) {} 313 314 const CFGBlock* getSrc() const { 315 return static_cast<const CFGBlock*>(getData1()); 316 } 317 318 const CFGBlock* getDst() const { 319 return static_cast<const CFGBlock*>(getData2()); 320 } 321 322 static bool classof(const ProgramPoint* Location) { 323 return Location->getKind() == BlockEdgeKind; 324 } 325}; 326 327class PostInitializer : public ProgramPoint { 328public: 329 PostInitializer(const CXXCtorInitializer *I, 330 const LocationContext *L) 331 : ProgramPoint(I, PostInitializerKind, L) {} 332 333 static bool classof(const ProgramPoint *Location) { 334 return Location->getKind() == PostInitializerKind; 335 } 336}; 337 338class CallEnter : public StmtPoint { 339public: 340 CallEnter(const Stmt *stmt, const StackFrameContext *calleeCtx, 341 const LocationContext *callerCtx) 342 : StmtPoint(stmt, calleeCtx, CallEnterKind, callerCtx, 0) {} 343 344 const Stmt *getCallExpr() const { 345 return static_cast<const Stmt *>(getData1()); 346 } 347 348 const StackFrameContext *getCalleeContext() const { 349 return static_cast<const StackFrameContext *>(getData2()); 350 } 351 352 static bool classof(const ProgramPoint *Location) { 353 return Location->getKind() == CallEnterKind; 354 } 355}; 356 357class CallExit : public StmtPoint { 358public: 359 // CallExit uses the callee's location context. 360 CallExit(const Stmt *S, const LocationContext *L) 361 : StmtPoint(S, 0, CallExitKind, L, 0) {} 362 363 static bool classof(const ProgramPoint *Location) { 364 return Location->getKind() == CallExitKind; 365 } 366}; 367 368 369} // end namespace clang 370 371 372namespace llvm { // Traits specialization for DenseMap 373 374template <> struct DenseMapInfo<clang::ProgramPoint> { 375 376static inline clang::ProgramPoint getEmptyKey() { 377 uintptr_t x = 378 reinterpret_cast<uintptr_t>(DenseMapInfo<void*>::getEmptyKey()) & ~0x7; 379 return clang::BlockEntrance(reinterpret_cast<clang::CFGBlock*>(x), 0); 380} 381 382static inline clang::ProgramPoint getTombstoneKey() { 383 uintptr_t x = 384 reinterpret_cast<uintptr_t>(DenseMapInfo<void*>::getTombstoneKey()) & ~0x7; 385 return clang::BlockEntrance(reinterpret_cast<clang::CFGBlock*>(x), 0); 386} 387 388static unsigned getHashValue(const clang::ProgramPoint& Loc) { 389 return Loc.getHashValue(); 390} 391 392static bool isEqual(const clang::ProgramPoint& L, 393 const clang::ProgramPoint& R) { 394 return L == R; 395} 396 397}; 398 399template <> 400struct isPodLike<clang::ProgramPoint> { static const bool value = true; }; 401 402} // end namespace llvm 403 404#endif 405