ProgramPoint.h revision cdd4f1783da7c7565be2376d14ca6ab2625aa4b6
1579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson//==- ProgramPoint.h - Program Points for Path-Sensitive Analysis --*- C++ -*-// 2579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson// 3579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson// The LLVM Compiler Infrastructure 4579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson// 5579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson// This file is distributed under the University of Illinois Open Source 6579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson// License. See LICENSE.TXT for details. 7579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson// 8579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson//===----------------------------------------------------------------------===// 9579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson// 10579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson// This file defines the interface ProgramPoint, which identifies a 11579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson// distinct location in a function. 12579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson// 13579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson//===----------------------------------------------------------------------===// 14579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 15579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson#ifndef LLVM_CLANG_ANALYSIS_PROGRAM_POINT 16579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson#define LLVM_CLANG_ANALYSIS_PROGRAM_POINT 17579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 18579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson#include "clang/Analysis/CFG.h" 19579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson#include "llvm/Support/DataTypes.h" 20579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson#include "llvm/ADT/DenseMap.h" 21579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson#include "llvm/ADT/FoldingSet.h" 22579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson#include "llvm/Support/Casting.h" 23579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson#include <cassert> 24579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson#include <utility> 25579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 26579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonnamespace clang { 27579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 28579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonclass ProgramPoint { 29579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonpublic: 30579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson enum Kind { BlockEdgeKind, 31579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson BlockEntranceKind, 32579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson BlockExitKind, 33579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson PreStmtKind, 34579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Keep the following together and in this order. 35579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson PostStmtKind, 36579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson PostLocationChecksSucceedKind, 37579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson PostOutOfBoundsCheckFailedKind, 38579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson PostNullCheckFailedKind, 39579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson PostUndefLocationCheckFailedKind, 40579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson PostLoadKind, 41579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson PostStoreKind, 42579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson PostPurgeDeadSymbolsKind, 43579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson PostStmtCustomKind, 44579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson PostLValueKind, 45579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson MinPostStmtKind = PostStmtKind, 46579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson MaxPostStmtKind = PostLValueKind }; 47579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 48579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonprivate: 49579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson std::pair<const void *, const void *> Data; 50579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson Kind K; 51579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson const void *Tag; 52579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 53579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonprotected: 54579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ProgramPoint(const void* P, Kind k, const void *tag = 0) 55579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson : Data(P, NULL), K(k), Tag(tag) {} 56579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 57579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ProgramPoint(const void* P1, const void* P2, Kind k, const void *tag = 0) 58579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson : Data(P1, P2), K(k), Tag(tag) {} 59579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 60579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonprotected: 61579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson const void* getData1() const { return Data.first; } 62579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson const void* getData2() const { return Data.second; } 63579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson const void *getTag() const { return Tag; } 64579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 65579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonpublic: 66579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson Kind getKind() const { return K; } 67579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 68579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // For use with DenseMap. This hash is probably slow. 69579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson unsigned getHashValue() const { 70579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson llvm::FoldingSetNodeID ID; 71579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson Profile(ID); 72579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return ID.ComputeHash(); 73579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 74579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 75579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson static bool classof(const ProgramPoint*) { return true; } 76579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 77579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson bool operator==(const ProgramPoint & RHS) const { 78579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return K == RHS.K && Data == RHS.Data && Tag == RHS.Tag; 79579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 80579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 81579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson bool operator!=(const ProgramPoint& RHS) const { 82579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return K != RHS.K || Data != RHS.Data || Tag != RHS.Tag; 83579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 84579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 85579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson void Profile(llvm::FoldingSetNodeID& ID) const { 86579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ID.AddInteger((unsigned) K); 87579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ID.AddPointer(Data.first); 88579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ID.AddPointer(Data.second); 89579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ID.AddPointer(Tag); 90579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 91579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson}; 92579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 93579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonclass BlockEntrance : public ProgramPoint { 94579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonpublic: 95579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson BlockEntrance(const CFGBlock* B, const void *tag = 0) 96579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson : ProgramPoint(B, BlockEntranceKind, tag) {} 97579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 98579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson CFGBlock* getBlock() const { 99579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return const_cast<CFGBlock*>(reinterpret_cast<const CFGBlock*>(getData1())); 100579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 101579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 102579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson Stmt* getFirstStmt() const { 103579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson const CFGBlock* B = getBlock(); 104579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return B->empty() ? NULL : B->front(); 105579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 106579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 107579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson static bool classof(const ProgramPoint* Location) { 108579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return Location->getKind() == BlockEntranceKind; 109579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 110579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson}; 111579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 112579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonclass BlockExit : public ProgramPoint { 113579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonpublic: 114579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson BlockExit(const CFGBlock* B) : ProgramPoint(B, BlockExitKind) {} 115579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 116579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson CFGBlock* getBlock() const { 117579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return const_cast<CFGBlock*>(reinterpret_cast<const CFGBlock*>(getData1())); 118579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 119579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 120579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson Stmt* getLastStmt() const { 121579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson const CFGBlock* B = getBlock(); 122579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return B->empty() ? NULL : B->back(); 123579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 124579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 125579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson Stmt* getTerminator() const { 126579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return getBlock()->getTerminator(); 127579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 128579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 129579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson static bool classof(const ProgramPoint* Location) { 130579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return Location->getKind() == BlockExitKind; 131579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 132579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson}; 133579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 134579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonclass PreStmt : public ProgramPoint { 135579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonpublic: 136579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson PreStmt(const Stmt *S, const void *tag, const Stmt *SubStmt = 0) 137579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson : ProgramPoint(S, SubStmt, PreStmtKind, tag) {} 138579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 139579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson const Stmt *getStmt() const { return (const Stmt*) getData1(); } 140 const Stmt *getSubStmt() const { return (const Stmt*) getData2(); } 141 142 template <typename T> 143 const T* getStmtAs() const { return llvm::dyn_cast<T>(getStmt()); } 144 145 static bool classof(const ProgramPoint* Location) { 146 return Location->getKind() == PreStmtKind; 147 } 148}; 149 150class PostStmt : public ProgramPoint { 151protected: 152 PostStmt(const Stmt* S, Kind k, const void *tag = 0) 153 : ProgramPoint(S, k, tag) {} 154 155 PostStmt(const Stmt* S, const void* data, Kind k, const void *tag =0) 156 : ProgramPoint(S, data, k, tag) {} 157 158public: 159 PostStmt(const Stmt* S, const void *tag = 0) 160 : ProgramPoint(S, PostStmtKind, tag) {} 161 162 163 Stmt* getStmt() const { return (Stmt*) getData1(); } 164 165 template <typename T> 166 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 >= MinPostStmtKind && k <= MaxPostStmtKind; 171 } 172}; 173 174class PostLocationChecksSucceed : public PostStmt { 175public: 176 PostLocationChecksSucceed(const Stmt* S, const void *tag = 0) 177 : PostStmt(S, PostLocationChecksSucceedKind, tag) {} 178 179 static bool classof(const ProgramPoint* Location) { 180 return Location->getKind() == PostLocationChecksSucceedKind; 181 } 182}; 183 184class PostStmtCustom : public PostStmt { 185public: 186 PostStmtCustom(const Stmt* S, 187 const std::pair<const void*, const void*>* TaggedData) 188 : PostStmt(S, TaggedData, PostStmtCustomKind) {} 189 190 const std::pair<const void*, const void*>& getTaggedPair() const { 191 return 192 *reinterpret_cast<const std::pair<const void*, const void*>*>(getData2()); 193 } 194 195 const void* getTag() const { return getTaggedPair().first; } 196 197 const void* getTaggedData() const { return getTaggedPair().second; } 198 199 static bool classof(const ProgramPoint* Location) { 200 return Location->getKind() == PostStmtCustomKind; 201 } 202}; 203 204class PostOutOfBoundsCheckFailed : public PostStmt { 205public: 206 PostOutOfBoundsCheckFailed(const Stmt* S, const void *tag = 0) 207 : PostStmt(S, PostOutOfBoundsCheckFailedKind, tag) {} 208 209 static bool classof(const ProgramPoint* Location) { 210 return Location->getKind() == PostOutOfBoundsCheckFailedKind; 211 } 212}; 213 214class PostUndefLocationCheckFailed : public PostStmt { 215public: 216 PostUndefLocationCheckFailed(const Stmt* S, const void *tag = 0) 217 : PostStmt(S, PostUndefLocationCheckFailedKind, tag) {} 218 219 static bool classof(const ProgramPoint* Location) { 220 return Location->getKind() == PostUndefLocationCheckFailedKind; 221 } 222}; 223 224class PostNullCheckFailed : public PostStmt { 225public: 226 PostNullCheckFailed(const Stmt* S, const void *tag = 0) 227 : PostStmt(S, PostNullCheckFailedKind, tag) {} 228 229 static bool classof(const ProgramPoint* Location) { 230 return Location->getKind() == PostNullCheckFailedKind; 231 } 232}; 233 234class PostLoad : public PostStmt { 235public: 236 PostLoad(const Stmt* S, const void *tag = 0) 237 : PostStmt(S, PostLoadKind, tag) {} 238 239 static bool classof(const ProgramPoint* Location) { 240 return Location->getKind() == PostLoadKind; 241 } 242}; 243 244class PostStore : public PostStmt { 245public: 246 PostStore(const Stmt* S, const void *tag = 0) 247 : PostStmt(S, PostStoreKind, tag) {} 248 249 static bool classof(const ProgramPoint* Location) { 250 return Location->getKind() == PostStoreKind; 251 } 252}; 253 254class PostLValue : public PostStmt { 255public: 256 PostLValue(const Stmt* S, const void *tag = 0) 257 : PostStmt(S, PostLValueKind, tag) {} 258 259 static bool classof(const ProgramPoint* Location) { 260 return Location->getKind() == PostLValueKind; 261 } 262}; 263 264class PostPurgeDeadSymbols : public PostStmt { 265public: 266 PostPurgeDeadSymbols(const Stmt* S, const void *tag = 0) 267 : PostStmt(S, PostPurgeDeadSymbolsKind, tag) {} 268 269 static bool classof(const ProgramPoint* Location) { 270 return Location->getKind() == PostPurgeDeadSymbolsKind; 271 } 272}; 273 274class BlockEdge : public ProgramPoint { 275public: 276 BlockEdge(const CFGBlock* B1, const CFGBlock* B2) 277 : ProgramPoint(B1, B2, BlockEdgeKind) {} 278 279 CFGBlock* getSrc() const { 280 return const_cast<CFGBlock*>(static_cast<const CFGBlock*>(getData1())); 281 } 282 283 CFGBlock* getDst() const { 284 return const_cast<CFGBlock*>(static_cast<const CFGBlock*>(getData2())); 285 } 286 287 static bool classof(const ProgramPoint* Location) { 288 return Location->getKind() == BlockEdgeKind; 289 } 290}; 291 292 293} // end namespace clang 294 295 296namespace llvm { // Traits specialization for DenseMap 297 298template <> struct DenseMapInfo<clang::ProgramPoint> { 299 300static inline clang::ProgramPoint getEmptyKey() { 301 uintptr_t x = 302 reinterpret_cast<uintptr_t>(DenseMapInfo<void*>::getEmptyKey()) & ~0x7; 303 return clang::BlockEntrance(reinterpret_cast<clang::CFGBlock*>(x)); 304} 305 306static inline clang::ProgramPoint getTombstoneKey() { 307 uintptr_t x = 308 reinterpret_cast<uintptr_t>(DenseMapInfo<void*>::getTombstoneKey()) & ~0x7; 309 return clang::BlockEntrance(reinterpret_cast<clang::CFGBlock*>(x)); 310} 311 312static unsigned getHashValue(const clang::ProgramPoint& Loc) { 313 return Loc.getHashValue(); 314} 315 316static bool isEqual(const clang::ProgramPoint& L, 317 const clang::ProgramPoint& R) { 318 return L == R; 319} 320 321static bool isPod() { 322 return true; 323} 324}; 325} // end namespace llvm 326 327#endif 328