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