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