ProgramPoint.h revision 3d7c44e01d568e5d5c0fac9c6ccb3f080157ba19
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 AnalysisDeclContext; 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 void setData2(const void *d) { Data.second = d; } 80 81public: 82 /// Create a new ProgramPoint object that is the same as the original 83 /// except for using the specified tag value. 84 ProgramPoint withTag(const ProgramPointTag *tag) const { 85 return ProgramPoint(Data.first, Data.second, K, L, tag); 86 } 87 88 Kind getKind() const { return K; } 89 90 const ProgramPointTag *getTag() const { return Tag; } 91 92 const LocationContext *getLocationContext() const { return L; } 93 94 // For use with DenseMap. This hash is probably slow. 95 unsigned getHashValue() const { 96 llvm::FoldingSetNodeID ID; 97 Profile(ID); 98 return ID.ComputeHash(); 99 } 100 101 static bool classof(const ProgramPoint*) { return true; } 102 103 bool operator==(const ProgramPoint & RHS) const { 104 return K == RHS.K && Data == RHS.Data && L == RHS.L && Tag == RHS.Tag; 105 } 106 107 bool operator!=(const ProgramPoint &RHS) const { 108 return K != RHS.K || Data != RHS.Data || L != RHS.L || Tag != RHS.Tag; 109 } 110 111 void Profile(llvm::FoldingSetNodeID& ID) const { 112 ID.AddInteger((unsigned) K); 113 ID.AddPointer(Data.first); 114 ID.AddPointer(Data.second); 115 ID.AddPointer(L); 116 ID.AddPointer(Tag); 117 } 118 119 static ProgramPoint getProgramPoint(const Stmt *S, ProgramPoint::Kind K, 120 const LocationContext *LC, 121 const ProgramPointTag *tag); 122 123}; 124 125class BlockEntrance : public ProgramPoint { 126public: 127 BlockEntrance(const CFGBlock *B, const LocationContext *L, 128 const ProgramPointTag *tag = 0) 129 : ProgramPoint(B, BlockEntranceKind, L, tag) { 130 assert(B && "BlockEntrance requires non-null block"); 131 } 132 133 const CFGBlock *getBlock() const { 134 return reinterpret_cast<const CFGBlock*>(getData1()); 135 } 136 137 const CFGElement getFirstElement() const { 138 const CFGBlock *B = getBlock(); 139 return B->empty() ? CFGElement() : B->front(); 140 } 141 142 static bool classof(const ProgramPoint* Location) { 143 return Location->getKind() == BlockEntranceKind; 144 } 145}; 146 147class BlockExit : public ProgramPoint { 148public: 149 BlockExit(const CFGBlock *B, const LocationContext *L) 150 : ProgramPoint(B, BlockExitKind, L) {} 151 152 const CFGBlock *getBlock() const { 153 return reinterpret_cast<const CFGBlock*>(getData1()); 154 } 155 156 const Stmt *getTerminator() const { 157 return getBlock()->getTerminator(); 158 } 159 160 static bool classof(const ProgramPoint* Location) { 161 return Location->getKind() == BlockExitKind; 162 } 163}; 164 165class StmtPoint : public ProgramPoint { 166public: 167 StmtPoint(const Stmt *S, const void *p2, Kind k, const LocationContext *L, 168 const ProgramPointTag *tag) 169 : ProgramPoint(S, p2, k, L, tag) {} 170 171 const Stmt *getStmt() const { return (const Stmt*) getData1(); } 172 173 template <typename T> 174 const T* getStmtAs() const { return llvm::dyn_cast<T>(getStmt()); } 175 176 static bool classof(const ProgramPoint* Location) { 177 unsigned k = Location->getKind(); 178 return k >= PreStmtKind && k <= MaxPostStmtKind; 179 } 180}; 181 182 183class PreStmt : public StmtPoint { 184public: 185 PreStmt(const Stmt *S, const LocationContext *L, const ProgramPointTag *tag, 186 const Stmt *SubStmt = 0) 187 : StmtPoint(S, SubStmt, PreStmtKind, L, tag) {} 188 189 const Stmt *getSubStmt() const { return (const Stmt*) getData2(); } 190 191 static bool classof(const ProgramPoint* Location) { 192 return Location->getKind() == PreStmtKind; 193 } 194}; 195 196class PostStmt : public StmtPoint { 197protected: 198 PostStmt(const Stmt *S, const void *data, Kind k, const LocationContext *L, 199 const ProgramPointTag *tag = 0) 200 : StmtPoint(S, data, k, L, tag) {} 201 202public: 203 explicit PostStmt(const Stmt *S, Kind k, 204 const LocationContext *L, const ProgramPointTag *tag = 0) 205 : StmtPoint(S, NULL, k, L, tag) {} 206 207 explicit PostStmt(const Stmt *S, const LocationContext *L, 208 const ProgramPointTag *tag = 0) 209 : StmtPoint(S, NULL, PostStmtKind, L, tag) {} 210 211 static bool classof(const ProgramPoint* Location) { 212 unsigned k = Location->getKind(); 213 return k >= MinPostStmtKind && k <= MaxPostStmtKind; 214 } 215}; 216 217// PostCondition represents the post program point of a branch condition. 218class PostCondition : public PostStmt { 219public: 220 PostCondition(const Stmt *S, const LocationContext *L, 221 const ProgramPointTag *tag = 0) 222 : PostStmt(S, PostConditionKind, L, tag) {} 223 224 static bool classof(const ProgramPoint* Location) { 225 return Location->getKind() == PostConditionKind; 226 } 227}; 228 229class LocationCheck : public StmtPoint { 230protected: 231 LocationCheck(const Stmt *S, const LocationContext *L, 232 ProgramPoint::Kind K, const ProgramPointTag *tag) 233 : StmtPoint(S, NULL, K, L, tag) {} 234 235 static bool classof(const ProgramPoint *location) { 236 unsigned k = location->getKind(); 237 return k == PreLoadKind || k == PreStoreKind; 238 } 239}; 240 241class PreLoad : public LocationCheck { 242public: 243 PreLoad(const Stmt *S, const LocationContext *L, 244 const ProgramPointTag *tag = 0) 245 : LocationCheck(S, L, PreLoadKind, tag) {} 246 247 static bool classof(const ProgramPoint *location) { 248 return location->getKind() == PreLoadKind; 249 } 250}; 251 252class PreStore : public LocationCheck { 253public: 254 PreStore(const Stmt *S, const LocationContext *L, 255 const ProgramPointTag *tag = 0) 256 : LocationCheck(S, L, PreStoreKind, tag) {} 257 258 static bool classof(const ProgramPoint *location) { 259 return location->getKind() == PreStoreKind; 260 } 261}; 262 263class PostLoad : public PostStmt { 264public: 265 PostLoad(const Stmt *S, const LocationContext *L, 266 const ProgramPointTag *tag = 0) 267 : PostStmt(S, PostLoadKind, L, tag) {} 268 269 static bool classof(const ProgramPoint* Location) { 270 return Location->getKind() == PostLoadKind; 271 } 272}; 273 274/// \class Represents a program point after a store evaluation. 275class PostStore : public PostStmt { 276public: 277 /// Construct the post store point. 278 /// \param Loc can be used to store the information about the location 279 /// used in the form it was uttered in the code. 280 PostStore(const Stmt *S, const LocationContext *L, const void *Loc, 281 const ProgramPointTag *tag = 0) 282 : PostStmt(S, PostStoreKind, L, tag) { 283 assert(getData2() == 0); 284 setData2(Loc); 285 } 286 287 static bool classof(const ProgramPoint* Location) { 288 return Location->getKind() == PostStoreKind; 289 } 290 291 /// \brief Returns the information about the location used in the store, 292 /// how it was uttered in the code. 293 const void *getLocationValue() const { 294 return getData2(); 295 } 296 297}; 298 299class PostLValue : public PostStmt { 300public: 301 PostLValue(const Stmt *S, const LocationContext *L, 302 const ProgramPointTag *tag = 0) 303 : PostStmt(S, PostLValueKind, L, tag) {} 304 305 static bool classof(const ProgramPoint* Location) { 306 return Location->getKind() == PostLValueKind; 307 } 308}; 309 310class PostPurgeDeadSymbols : public PostStmt { 311public: 312 PostPurgeDeadSymbols(const Stmt *S, const LocationContext *L, 313 const ProgramPointTag *tag = 0) 314 : PostStmt(S, PostPurgeDeadSymbolsKind, L, tag) {} 315 316 static bool classof(const ProgramPoint* Location) { 317 return Location->getKind() == PostPurgeDeadSymbolsKind; 318 } 319}; 320 321class BlockEdge : public ProgramPoint { 322public: 323 BlockEdge(const CFGBlock *B1, const CFGBlock *B2, const LocationContext *L) 324 : ProgramPoint(B1, B2, BlockEdgeKind, L) { 325 assert(B1 && "BlockEdge: source block must be non-null"); 326 assert(B2 && "BlockEdge: destination block must be non-null"); 327 } 328 329 const CFGBlock *getSrc() const { 330 return static_cast<const CFGBlock*>(getData1()); 331 } 332 333 const CFGBlock *getDst() const { 334 return static_cast<const CFGBlock*>(getData2()); 335 } 336 337 static bool classof(const ProgramPoint* Location) { 338 return Location->getKind() == BlockEdgeKind; 339 } 340}; 341 342class PostInitializer : public ProgramPoint { 343public: 344 PostInitializer(const CXXCtorInitializer *I, 345 const LocationContext *L) 346 : ProgramPoint(I, PostInitializerKind, L) {} 347 348 static bool classof(const ProgramPoint *Location) { 349 return Location->getKind() == PostInitializerKind; 350 } 351}; 352 353class CallEnter : public StmtPoint { 354public: 355 CallEnter(const Stmt *stmt, const StackFrameContext *calleeCtx, 356 const LocationContext *callerCtx) 357 : StmtPoint(stmt, calleeCtx, CallEnterKind, callerCtx, 0) {} 358 359 const Stmt *getCallExpr() const { 360 return static_cast<const Stmt *>(getData1()); 361 } 362 363 const StackFrameContext *getCalleeContext() const { 364 return static_cast<const StackFrameContext *>(getData2()); 365 } 366 367 static bool classof(const ProgramPoint *Location) { 368 return Location->getKind() == CallEnterKind; 369 } 370}; 371 372class CallExit : public StmtPoint { 373public: 374 // CallExit uses the callee's location context. 375 CallExit(const Stmt *S, const LocationContext *L) 376 : StmtPoint(S, 0, CallExitKind, L, 0) {} 377 378 static bool classof(const ProgramPoint *Location) { 379 return Location->getKind() == CallExitKind; 380 } 381}; 382 383/// ProgramPoints can be "tagged" as representing points specific to a given 384/// analysis entity. Tags are abstract annotations, with an associated 385/// description and potentially other information. 386class ProgramPointTag { 387public: 388 ProgramPointTag(void *tagKind = 0) : TagKind(tagKind) {} 389 virtual ~ProgramPointTag(); 390 virtual StringRef getTagDescription() const = 0; 391 392protected: 393 /// Used to implement 'classof' in subclasses. 394 const void *getTagKind() { return TagKind; } 395 396private: 397 const void *TagKind; 398}; 399 400class SimpleProgramPointTag : public ProgramPointTag { 401 std::string desc; 402public: 403 SimpleProgramPointTag(StringRef description); 404 StringRef getTagDescription() const; 405}; 406 407} // end namespace clang 408 409 410namespace llvm { // Traits specialization for DenseMap 411 412template <> struct DenseMapInfo<clang::ProgramPoint> { 413 414static inline clang::ProgramPoint getEmptyKey() { 415 uintptr_t x = 416 reinterpret_cast<uintptr_t>(DenseMapInfo<void*>::getEmptyKey()) & ~0x7; 417 return clang::BlockEntrance(reinterpret_cast<clang::CFGBlock*>(x), 0); 418} 419 420static inline clang::ProgramPoint getTombstoneKey() { 421 uintptr_t x = 422 reinterpret_cast<uintptr_t>(DenseMapInfo<void*>::getTombstoneKey()) & ~0x7; 423 return clang::BlockEntrance(reinterpret_cast<clang::CFGBlock*>(x), 0); 424} 425 426static unsigned getHashValue(const clang::ProgramPoint &Loc) { 427 return Loc.getHashValue(); 428} 429 430static bool isEqual(const clang::ProgramPoint &L, 431 const clang::ProgramPoint &R) { 432 return L == R; 433} 434 435}; 436 437template <> 438struct isPodLike<clang::ProgramPoint> { static const bool value = true; }; 439 440} // end namespace llvm 441 442#endif 443