ProgramPoint.h revision 2b706e56b57c9646dae8c9134d8614fe815a1873
13c827367444ee418f129b2c238299f49d3264554Jarkko Poyry//==- ProgramPoint.h - Program Points for Path-Sensitive Analysis --*- C++ -*-// 23c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// 33c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// The LLVM Compiler Infrastructure 43c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// 53c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// This file is distributed under the University of Illinois Open Source 63c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// License. See LICENSE.TXT for details. 73c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// 83c827367444ee418f129b2c238299f49d3264554Jarkko Poyry//===----------------------------------------------------------------------===// 93c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// 103c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// This file defines the interface ProgramPoint, which identifies a 113c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// distinct location in a function. 123c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// 133c827367444ee418f129b2c238299f49d3264554Jarkko Poyry//===----------------------------------------------------------------------===// 143c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 153c827367444ee418f129b2c238299f49d3264554Jarkko Poyry#ifndef LLVM_CLANG_ANALYSIS_PROGRAM_POINT 163c827367444ee418f129b2c238299f49d3264554Jarkko Poyry#define LLVM_CLANG_ANALYSIS_PROGRAM_POINT 173c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 183c827367444ee418f129b2c238299f49d3264554Jarkko Poyry#include "clang/Analysis/CFG.h" 193c827367444ee418f129b2c238299f49d3264554Jarkko Poyry#include "llvm/System/DataTypes.h" 203c827367444ee418f129b2c238299f49d3264554Jarkko Poyry#include "llvm/ADT/DenseMap.h" 213c827367444ee418f129b2c238299f49d3264554Jarkko Poyry#include "llvm/ADT/FoldingSet.h" 223c827367444ee418f129b2c238299f49d3264554Jarkko Poyry#include "llvm/Support/Casting.h" 233c827367444ee418f129b2c238299f49d3264554Jarkko Poyry#include <cassert> 243c827367444ee418f129b2c238299f49d3264554Jarkko Poyry#include <utility> 253c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 263c827367444ee418f129b2c238299f49d3264554Jarkko Poyrynamespace clang { 273c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 283c827367444ee418f129b2c238299f49d3264554Jarkko Poyryclass LocationContext; 293c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 303c827367444ee418f129b2c238299f49d3264554Jarkko Poyryclass ProgramPoint { 313c827367444ee418f129b2c238299f49d3264554Jarkko Poyrypublic: 323c827367444ee418f129b2c238299f49d3264554Jarkko Poyry enum Kind { BlockEdgeKind, 333c827367444ee418f129b2c238299f49d3264554Jarkko Poyry BlockEntranceKind, 343c827367444ee418f129b2c238299f49d3264554Jarkko Poyry BlockExitKind, 353c827367444ee418f129b2c238299f49d3264554Jarkko Poyry PreStmtKind, 363c827367444ee418f129b2c238299f49d3264554Jarkko Poyry PostStmtKind, 373c827367444ee418f129b2c238299f49d3264554Jarkko Poyry PreLoadKind, 383c827367444ee418f129b2c238299f49d3264554Jarkko Poyry PostLoadKind, 393c827367444ee418f129b2c238299f49d3264554Jarkko Poyry PreStoreKind, 403c827367444ee418f129b2c238299f49d3264554Jarkko Poyry PostStoreKind, 413c827367444ee418f129b2c238299f49d3264554Jarkko Poyry PostPurgeDeadSymbolsKind, 423c827367444ee418f129b2c238299f49d3264554Jarkko Poyry PostStmtCustomKind, 433c827367444ee418f129b2c238299f49d3264554Jarkko Poyry PostLValueKind, 443c827367444ee418f129b2c238299f49d3264554Jarkko Poyry MinPostStmtKind = PostStmtKind, 453c827367444ee418f129b2c238299f49d3264554Jarkko Poyry MaxPostStmtKind = PostLValueKind }; 463c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 473c827367444ee418f129b2c238299f49d3264554Jarkko Poyryprivate: 483c827367444ee418f129b2c238299f49d3264554Jarkko Poyry std::pair<const void *, const void *> Data; 493c827367444ee418f129b2c238299f49d3264554Jarkko Poyry Kind K; 503c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 513c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // The LocationContext could be NULL to allow ProgramPoint to be used in 523c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // context insensitive analysis. 533c827367444ee418f129b2c238299f49d3264554Jarkko Poyry const LocationContext *L; 54 const void *Tag; 55 56protected: 57 ProgramPoint(const void* P, Kind k, const LocationContext *l, 58 const void *tag = 0) 59 : Data(P, NULL), K(k), L(l), Tag(tag) {} 60 61 ProgramPoint(const void* P1, const void* P2, Kind k, const LocationContext *l, 62 const void *tag = 0) 63 : Data(P1, P2), K(k), L(l), Tag(tag) {} 64 65protected: 66 const void* getData1() const { return Data.first; } 67 const void* getData2() const { return Data.second; } 68 const void *getTag() const { return Tag; } 69 70public: 71 Kind getKind() const { return K; } 72 73 const LocationContext *getLocationContext() const { return L; } 74 75 // For use with DenseMap. This hash is probably slow. 76 unsigned getHashValue() const { 77 llvm::FoldingSetNodeID ID; 78 Profile(ID); 79 return ID.ComputeHash(); 80 } 81 82 static bool classof(const ProgramPoint*) { return true; } 83 84 bool operator==(const ProgramPoint & RHS) const { 85 return K == RHS.K && Data == RHS.Data && L == RHS.L && Tag == RHS.Tag; 86 } 87 88 bool operator!=(const ProgramPoint& RHS) const { 89 return K != RHS.K || Data != RHS.Data || L != RHS.L || Tag != RHS.Tag; 90 } 91 92 void Profile(llvm::FoldingSetNodeID& ID) const { 93 ID.AddInteger((unsigned) K); 94 ID.AddPointer(Data.first); 95 ID.AddPointer(Data.second); 96 ID.AddPointer(L); 97 ID.AddPointer(Tag); 98 } 99}; 100 101class BlockEntrance : public ProgramPoint { 102public: 103 BlockEntrance(const CFGBlock* B, const LocationContext *L, 104 const void *tag = 0) 105 : ProgramPoint(B, BlockEntranceKind, L, tag) {} 106 107 CFGBlock* getBlock() const { 108 return const_cast<CFGBlock*>(reinterpret_cast<const CFGBlock*>(getData1())); 109 } 110 111 CFGElement getFirstElement() const { 112 const CFGBlock* B = getBlock(); 113 return B->empty() ? CFGElement() : B->front(); 114 } 115 116 Stmt *getFirstStmt() const { 117 return getFirstElement().getStmt(); 118 } 119 120 static bool classof(const ProgramPoint* Location) { 121 return Location->getKind() == BlockEntranceKind; 122 } 123}; 124 125class BlockExit : public ProgramPoint { 126public: 127 BlockExit(const CFGBlock* B, const LocationContext *L) 128 : ProgramPoint(B, BlockExitKind, L) {} 129 130 CFGBlock* getBlock() const { 131 return const_cast<CFGBlock*>(reinterpret_cast<const CFGBlock*>(getData1())); 132 } 133 134 Stmt* getLastStmt() const { 135 const CFGBlock* B = getBlock(); 136 return B->empty() ? CFGElement() : B->back(); 137 } 138 139 Stmt* getTerminator() const { 140 return getBlock()->getTerminator(); 141 } 142 143 static bool classof(const ProgramPoint* Location) { 144 return Location->getKind() == BlockExitKind; 145 } 146}; 147 148class StmtPoint : public ProgramPoint { 149public: 150 StmtPoint(const Stmt *S, const void *p2, Kind k, const LocationContext *L, 151 const void *tag) 152 : ProgramPoint(S, p2, k, L, tag) {} 153 154 const Stmt *getStmt() const { return (const Stmt*) getData1(); } 155 156 template <typename T> 157 const T* getStmtAs() const { return llvm::dyn_cast<T>(getStmt()); } 158 159 static bool classof(const ProgramPoint* Location) { 160 unsigned k = Location->getKind(); 161 return k >= PreStmtKind && k <= MaxPostStmtKind; 162 } 163}; 164 165 166class PreStmt : public StmtPoint { 167public: 168 PreStmt(const Stmt *S, const LocationContext *L, const void *tag, 169 const Stmt *SubStmt = 0) 170 : StmtPoint(S, SubStmt, PreStmtKind, L, tag) {} 171 172 const Stmt *getSubStmt() const { return (const Stmt*) getData2(); } 173 174 static bool classof(const ProgramPoint* Location) { 175 return Location->getKind() == PreStmtKind; 176 } 177}; 178 179class PostStmt : public StmtPoint { 180protected: 181 PostStmt(const Stmt* S, Kind k, const LocationContext *L, const void *tag = 0) 182 : StmtPoint(S, NULL, k, L, tag) {} 183 184 PostStmt(const Stmt* S, const void* data, Kind k, const LocationContext *L, 185 const void *tag =0) 186 : StmtPoint(S, data, k, L, tag) {} 187 188public: 189 explicit PostStmt(const Stmt* S, const LocationContext *L,const void *tag = 0) 190 : StmtPoint(S, NULL, PostStmtKind, L, tag) {} 191 192 static bool classof(const ProgramPoint* Location) { 193 unsigned k = Location->getKind(); 194 return k >= MinPostStmtKind && k <= MaxPostStmtKind; 195 } 196}; 197 198class PostStmtCustom : public PostStmt { 199public: 200 PostStmtCustom(const Stmt* S, 201 const std::pair<const void*, const void*>* TaggedData,\ 202 const LocationContext *L) 203 : PostStmt(S, TaggedData, PostStmtCustomKind, L) {} 204 205 const std::pair<const void*, const void*>& getTaggedPair() const { 206 return 207 *reinterpret_cast<const std::pair<const void*, const void*>*>(getData2()); 208 } 209 210 const void* getTag() const { return getTaggedPair().first; } 211 212 const void* getTaggedData() const { return getTaggedPair().second; } 213 214 static bool classof(const ProgramPoint* Location) { 215 return Location->getKind() == PostStmtCustomKind; 216 } 217}; 218 219 220class LocationCheck : public StmtPoint { 221protected: 222 LocationCheck(const Stmt *S, const LocationContext *L, 223 ProgramPoint::Kind K, const void *tag) 224 : StmtPoint(S, NULL, K, L, tag) {} 225 226 static bool classof(const ProgramPoint *location) { 227 unsigned k = location->getKind(); 228 return k == PreLoadKind || k == PreStoreKind; 229 } 230}; 231 232class PreLoad : public LocationCheck { 233public: 234 PreLoad(const Stmt *S, const LocationContext *L, const void *tag = 0) 235 : LocationCheck(S, L, PreLoadKind, tag) {} 236 237 static bool classof(const ProgramPoint *location) { 238 return location->getKind() == PreLoadKind; 239 } 240}; 241 242class PreStore : public LocationCheck { 243public: 244 PreStore(const Stmt *S, const LocationContext *L, const void *tag = 0) 245 : LocationCheck(S, L, PreStoreKind, tag) {} 246 247 static bool classof(const ProgramPoint *location) { 248 return location->getKind() == PreStoreKind; 249 } 250}; 251 252class PostLoad : public PostStmt { 253public: 254 PostLoad(const Stmt* S, const LocationContext *L, const void *tag = 0) 255 : PostStmt(S, PostLoadKind, L, tag) {} 256 257 static bool classof(const ProgramPoint* Location) { 258 return Location->getKind() == PostLoadKind; 259 } 260}; 261 262class PostStore : public PostStmt { 263public: 264 PostStore(const Stmt* S, const LocationContext *L, const void *tag = 0) 265 : PostStmt(S, PostStoreKind, L, tag) {} 266 267 static bool classof(const ProgramPoint* Location) { 268 return Location->getKind() == PostStoreKind; 269 } 270}; 271 272class PostLValue : public PostStmt { 273public: 274 PostLValue(const Stmt* S, const LocationContext *L, const void *tag = 0) 275 : PostStmt(S, PostLValueKind, L, tag) {} 276 277 static bool classof(const ProgramPoint* Location) { 278 return Location->getKind() == PostLValueKind; 279 } 280}; 281 282class PostPurgeDeadSymbols : public PostStmt { 283public: 284 PostPurgeDeadSymbols(const Stmt* S, const LocationContext *L, 285 const void *tag = 0) 286 : PostStmt(S, PostPurgeDeadSymbolsKind, L, tag) {} 287 288 static bool classof(const ProgramPoint* Location) { 289 return Location->getKind() == PostPurgeDeadSymbolsKind; 290 } 291}; 292 293class BlockEdge : public ProgramPoint { 294public: 295 BlockEdge(const CFGBlock* B1, const CFGBlock* B2, const LocationContext *L) 296 : ProgramPoint(B1, B2, BlockEdgeKind, L) {} 297 298 CFGBlock* getSrc() const { 299 return const_cast<CFGBlock*>(static_cast<const CFGBlock*>(getData1())); 300 } 301 302 CFGBlock* getDst() const { 303 return const_cast<CFGBlock*>(static_cast<const CFGBlock*>(getData2())); 304 } 305 306 static bool classof(const ProgramPoint* Location) { 307 return Location->getKind() == BlockEdgeKind; 308 } 309}; 310 311 312} // end namespace clang 313 314 315namespace llvm { // Traits specialization for DenseMap 316 317template <> struct DenseMapInfo<clang::ProgramPoint> { 318 319static inline clang::ProgramPoint getEmptyKey() { 320 uintptr_t x = 321 reinterpret_cast<uintptr_t>(DenseMapInfo<void*>::getEmptyKey()) & ~0x7; 322 return clang::BlockEntrance(reinterpret_cast<clang::CFGBlock*>(x), 0); 323} 324 325static inline clang::ProgramPoint getTombstoneKey() { 326 uintptr_t x = 327 reinterpret_cast<uintptr_t>(DenseMapInfo<void*>::getTombstoneKey()) & ~0x7; 328 return clang::BlockEntrance(reinterpret_cast<clang::CFGBlock*>(x), 0); 329} 330 331static unsigned getHashValue(const clang::ProgramPoint& Loc) { 332 return Loc.getHashValue(); 333} 334 335static bool isEqual(const clang::ProgramPoint& L, 336 const clang::ProgramPoint& R) { 337 return L == R; 338} 339 340}; 341 342template <> 343struct isPodLike<clang::ProgramPoint> { static const bool value = true; }; 344 345} // end namespace llvm 346 347#endif 348