ProgramPoint.h revision 852274d4257134906995cb252fb3dfd2d71deae8
1f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org//==- ProgramPoint.h - Program Points for Path-Sensitive Analysis --*- C++ -*-// 2f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org// 3f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org// The LLVM Compiler Infrastructure 4f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org// 5f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org// This file is distributed under the University of Illinois Open Source 6f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org// License. See LICENSE.TXT for details. 7f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org// 8f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org//===----------------------------------------------------------------------===// 9f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org// 10f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org// This file defines the interface ProgramPoint, which identifies a 11f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org// distinct location in a function. 12f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org// 13f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org//===----------------------------------------------------------------------===// 14f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 15f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#ifndef LLVM_CLANG_ANALYSIS_PROGRAM_POINT 16f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#define LLVM_CLANG_ANALYSIS_PROGRAM_POINT 17f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 18f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#include "clang/Analysis/CFG.h" 19f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#include "llvm/System/DataTypes.h" 20f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#include "llvm/ADT/DenseMap.h" 21f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#include "llvm/ADT/FoldingSet.h" 22f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#include "llvm/Support/Casting.h" 23f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#include <cassert> 24f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#include <utility> 25f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 26f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgnamespace clang { 27f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 28f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgclass LocationContext; 29f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 30f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgclass ProgramPoint { 31f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgpublic: 32f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org enum Kind { BlockEdgeKind, 33f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org BlockEntranceKind, 34f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org BlockExitKind, 35f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org PreStmtKind, 36f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org PostStmtKind, 37f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org PreLoadKind, 38f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org PostLoadKind, 39f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org PreStoreKind, 40f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org PostStoreKind, 41f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org PostPurgeDeadSymbolsKind, 42f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org PostStmtCustomKind, 43f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org PostLValueKind, 44f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org MinPostStmtKind = PostStmtKind, 45f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org MaxPostStmtKind = PostLValueKind }; 46f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 47f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgprivate: 48f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org std::pair<const void *, const void *> Data; 49f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Kind K; 50f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 51f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org // The LocationContext could be NULL to allow ProgramPoint to be used in 52f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org // context insensitive analysis. 53f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org const LocationContext *L; 54f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org const void *Tag; 55f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 56f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgprotected: 57f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ProgramPoint(const void* P, Kind k, const LocationContext *l, 58f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org const void *tag = 0) 59f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org : Data(P, NULL), K(k), L(l), Tag(tag) {} 60f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 61f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ProgramPoint(const void* P1, const void* P2, Kind k, const LocationContext *l, 62f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org const void *tag = 0) 63f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org : Data(P1, P2), K(k), L(l), Tag(tag) {} 64f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 65f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgprotected: 66f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org const void* getData1() const { return Data.first; } 67f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org const void* getData2() const { return Data.second; } 68f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org const void *getTag() const { return Tag; } 69f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 70f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgpublic: 71f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Kind getKind() const { return K; } 72f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 73f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org const LocationContext *getLocationContext() const { return L; } 74f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 75f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org // For use with DenseMap. This hash is probably slow. 76f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org unsigned getHashValue() const { 77f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org llvm::FoldingSetNodeID ID; 78f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Profile(ID); 79f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return ID.ComputeHash(); 80f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 81f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 82f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org static bool classof(const ProgramPoint*) { return true; } 83f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 84f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org bool operator==(const ProgramPoint & RHS) const { 85f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return K == RHS.K && Data == RHS.Data && L == RHS.L && Tag == RHS.Tag; 86f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 87f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 88f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org bool operator!=(const ProgramPoint& RHS) const { 89f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return K != RHS.K || Data != RHS.Data || L != RHS.L || Tag != RHS.Tag; 90f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 91f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 92f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org void Profile(llvm::FoldingSetNodeID& ID) const { 93f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ID.AddInteger((unsigned) K); 94f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ID.AddPointer(Data.first); 95f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ID.AddPointer(Data.second); 96f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ID.AddPointer(L); 97f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ID.AddPointer(Tag); 98f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 99f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org}; 100f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 101f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgclass BlockEntrance : public ProgramPoint { 102f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgpublic: 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