ProgramPoint.h revision 331b0ac44b9eb0ffcba66b4f3f3f9adb27c2434f
183c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek//==- ProgramPoint.h - Program Points for Path-Sensitive Analysis --*- C++ -*-// 2eb19188e668d0ad2c968fc0286a6922f9194deb4Ted Kremenek// 3eb19188e668d0ad2c968fc0286a6922f9194deb4Ted Kremenek// The LLVM Compiler Infrastructure 4eb19188e668d0ad2c968fc0286a6922f9194deb4Ted Kremenek// 50bc735ffcfb223c0186419547abaa5c84482663eChris Lattner// This file is distributed under the University of Illinois Open Source 60bc735ffcfb223c0186419547abaa5c84482663eChris Lattner// License. See LICENSE.TXT for details. 7eb19188e668d0ad2c968fc0286a6922f9194deb4Ted Kremenek// 8eb19188e668d0ad2c968fc0286a6922f9194deb4Ted Kremenek//===----------------------------------------------------------------------===// 9eb19188e668d0ad2c968fc0286a6922f9194deb4Ted Kremenek// 1083c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek// This file defines the interface ProgramPoint, which identifies a 1183c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek// distinct location in a function. 12eb19188e668d0ad2c968fc0286a6922f9194deb4Ted Kremenek// 13eb19188e668d0ad2c968fc0286a6922f9194deb4Ted Kremenek//===----------------------------------------------------------------------===// 14eb19188e668d0ad2c968fc0286a6922f9194deb4Ted Kremenek 1583c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek#ifndef LLVM_CLANG_ANALYSIS_PROGRAM_POINT 1683c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek#define LLVM_CLANG_ANALYSIS_PROGRAM_POINT 17eb19188e668d0ad2c968fc0286a6922f9194deb4Ted Kremenek 1805e14cd46ef44c07385aae96ec2fdcb9bf7e9467Ted Kremenek#include "clang/AST/CFG.h" 19eb19188e668d0ad2c968fc0286a6922f9194deb4Ted Kremenek#include "llvm/Support/DataTypes.h" 204c3fbe33194cd9b1bfff773647ed785b403e1ba5Ted Kremenek#include "llvm/ADT/DenseMap.h" 215226755ab5ce6346f98b5f41cdcffbe84c5bb484Ted Kremenek#include "llvm/ADT/FoldingSet.h" 224c3fbe33194cd9b1bfff773647ed785b403e1ba5Ted Kremenek#include <cassert> 23eb19188e668d0ad2c968fc0286a6922f9194deb4Ted Kremenek 24eb19188e668d0ad2c968fc0286a6922f9194deb4Ted Kremeneknamespace clang { 2505e14cd46ef44c07385aae96ec2fdcb9bf7e9467Ted Kremenek 2683c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenekclass ProgramPoint { 27eb19188e668d0ad2c968fc0286a6922f9194deb4Ted Kremenekpublic: 28331b0ac44b9eb0ffcba66b4f3f3f9adb27c2434fTed Kremenek enum Kind { BlockEntranceKind=0, 29331b0ac44b9eb0ffcba66b4f3f3f9adb27c2434fTed Kremenek PostStmtKind=1, PostLoadKind=2, PostPurgeDeadSymbolsKind=3, 30331b0ac44b9eb0ffcba66b4f3f3f9adb27c2434fTed Kremenek BlockExitKind=4, BlockEdgeSrcKind=5, BlockEdgeDstKind=6, 31331b0ac44b9eb0ffcba66b4f3f3f9adb27c2434fTed Kremenek BlockEdgeAuxKind=7 }; 3283c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenekprotected: 3383c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek uintptr_t Data; 344c3fbe33194cd9b1bfff773647ed785b403e1ba5Ted Kremenek 3583c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek ProgramPoint(const void* Ptr, Kind k) { 366e5977f0a8a680191fb4b4d8f32bc2c629faf0c2Argyrios Kyrtzidis setRawData(Ptr, k); 376e5977f0a8a680191fb4b4d8f32bc2c629faf0c2Argyrios Kyrtzidis } 386e5977f0a8a680191fb4b4d8f32bc2c629faf0c2Argyrios Kyrtzidis 396e5977f0a8a680191fb4b4d8f32bc2c629faf0c2Argyrios Kyrtzidis ProgramPoint() : Data(0) {} 406e5977f0a8a680191fb4b4d8f32bc2c629faf0c2Argyrios Kyrtzidis 416e5977f0a8a680191fb4b4d8f32bc2c629faf0c2Argyrios Kyrtzidis void setRawData(const void* Ptr, Kind k) { 4283c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek assert ((reinterpret_cast<uintptr_t>(const_cast<void*>(Ptr)) & 0x7) == 0 4383c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek && "Address must have at least an 8-byte alignment."); 4483c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek 45b365b702229999bf90b668bbe4a95bc0d2293d69Ted Kremenek Data = reinterpret_cast<uintptr_t>(const_cast<void*>(Ptr)) | k; 464c3fbe33194cd9b1bfff773647ed785b403e1ba5Ted Kremenek } 474c3fbe33194cd9b1bfff773647ed785b403e1ba5Ted Kremenek 4883c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenekpublic: 49ea45bb2d3b5e445029ad8f42d88bc1ed5b483a0bTed Kremenek unsigned getKind() const { return Data & 0x7; } 50ea45bb2d3b5e445029ad8f42d88bc1ed5b483a0bTed Kremenek void* getRawPtr() const { return reinterpret_cast<void*>(Data & ~0x7); } 5183c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek void* getRawData() const { return reinterpret_cast<void*>(Data); } 52eb19188e668d0ad2c968fc0286a6922f9194deb4Ted Kremenek 5383c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek static bool classof(const ProgramPoint*) { return true; } 5483c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek bool operator==(const ProgramPoint & RHS) const { return Data == RHS.Data; } 555226755ab5ce6346f98b5f41cdcffbe84c5bb484Ted Kremenek bool operator!=(const ProgramPoint& RHS) const { return Data != RHS.Data; } 565226755ab5ce6346f98b5f41cdcffbe84c5bb484Ted Kremenek 575226755ab5ce6346f98b5f41cdcffbe84c5bb484Ted Kremenek void Profile(llvm::FoldingSetNodeID& ID) const { 585226755ab5ce6346f98b5f41cdcffbe84c5bb484Ted Kremenek ID.AddInteger(getKind()); 595226755ab5ce6346f98b5f41cdcffbe84c5bb484Ted Kremenek ID.AddPointer(getRawPtr()); 605226755ab5ce6346f98b5f41cdcffbe84c5bb484Ted Kremenek } 61eb19188e668d0ad2c968fc0286a6922f9194deb4Ted Kremenek}; 6283c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek 6383c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenekclass BlockEntrance : public ProgramPoint { 64eb19188e668d0ad2c968fc0286a6922f9194deb4Ted Kremenekpublic: 6583c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek BlockEntrance(const CFGBlock* B) : ProgramPoint(B, BlockEntranceKind) {} 6683c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek 6783c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek CFGBlock* getBlock() const { 6883c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek return reinterpret_cast<CFGBlock*>(getRawPtr()); 69bd129696c554fbbcd9405104641e292f0fb4678dTed Kremenek } 70eb19188e668d0ad2c968fc0286a6922f9194deb4Ted Kremenek 7183c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek Stmt* getFirstStmt() const { 7283c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek CFGBlock* B = getBlock(); 7383c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek return B->empty() ? NULL : B->front(); 7483c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek } 75eb19188e668d0ad2c968fc0286a6922f9194deb4Ted Kremenek 7683c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek static bool classof(const ProgramPoint* Location) { 7783c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek return Location->getKind() == BlockEntranceKind; 78bd129696c554fbbcd9405104641e292f0fb4678dTed Kremenek } 79eb19188e668d0ad2c968fc0286a6922f9194deb4Ted Kremenek}; 8083c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek 8183c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenekclass BlockExit : public ProgramPoint { 82eb19188e668d0ad2c968fc0286a6922f9194deb4Ted Kremenekpublic: 8383c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek BlockExit(const CFGBlock* B) : ProgramPoint(B, BlockExitKind) {} 84bd129696c554fbbcd9405104641e292f0fb4678dTed Kremenek 8583c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek CFGBlock* getBlock() const { 8683c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek return reinterpret_cast<CFGBlock*>(getRawPtr()); 87bd129696c554fbbcd9405104641e292f0fb4678dTed Kremenek } 8883c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek 8983c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek Stmt* getLastStmt() const { 9083c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek CFGBlock* B = getBlock(); 9183c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek return B->empty() ? NULL : B->back(); 92bd129696c554fbbcd9405104641e292f0fb4678dTed Kremenek } 93bd129696c554fbbcd9405104641e292f0fb4678dTed Kremenek 9483c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek Stmt* getTerminator() const { 9583c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek return getBlock()->getTerminator(); 96bd129696c554fbbcd9405104641e292f0fb4678dTed Kremenek } 9783c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek 9883c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek static bool classof(const ProgramPoint* Location) { 9983c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek return Location->getKind() == BlockExitKind; 100bd129696c554fbbcd9405104641e292f0fb4678dTed Kremenek } 101bd129696c554fbbcd9405104641e292f0fb4678dTed Kremenek}; 102eb19188e668d0ad2c968fc0286a6922f9194deb4Ted Kremenek 10383c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek 10483c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenekclass PostStmt : public ProgramPoint { 1051b8bd4d71c2098126041b4de4267175a82f0103cTed Kremenekprotected: 1061b8bd4d71c2098126041b4de4267175a82f0103cTed Kremenek PostStmt(const Stmt* S, Kind k) : ProgramPoint(S, k) {} 107eb19188e668d0ad2c968fc0286a6922f9194deb4Ted Kremenekpublic: 10883c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek PostStmt(const Stmt* S) : ProgramPoint(S, PostStmtKind) {} 1091b8bd4d71c2098126041b4de4267175a82f0103cTed Kremenek 11083c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek Stmt* getStmt() const { return (Stmt*) getRawPtr(); } 11183c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek 11283c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek static bool classof(const ProgramPoint* Location) { 1131b8bd4d71c2098126041b4de4267175a82f0103cTed Kremenek unsigned k = Location->getKind(); 114331b0ac44b9eb0ffcba66b4f3f3f9adb27c2434fTed Kremenek return k >= PostStmtKind && k <= PostPurgeDeadSymbolsKind; 1151b8bd4d71c2098126041b4de4267175a82f0103cTed Kremenek } 1161b8bd4d71c2098126041b4de4267175a82f0103cTed Kremenek}; 1171b8bd4d71c2098126041b4de4267175a82f0103cTed Kremenek 1181b8bd4d71c2098126041b4de4267175a82f0103cTed Kremenekclass PostLoad : public PostStmt { 1191b8bd4d71c2098126041b4de4267175a82f0103cTed Kremenekpublic: 1201b8bd4d71c2098126041b4de4267175a82f0103cTed Kremenek PostLoad(const Stmt* S) : PostStmt(S, PostLoadKind) {} 1211b8bd4d71c2098126041b4de4267175a82f0103cTed Kremenek 1221b8bd4d71c2098126041b4de4267175a82f0103cTed Kremenek static bool classof(const ProgramPoint* Location) { 1231b8bd4d71c2098126041b4de4267175a82f0103cTed Kremenek return Location->getKind() == PostLoadKind; 124bd129696c554fbbcd9405104641e292f0fb4678dTed Kremenek } 125eb19188e668d0ad2c968fc0286a6922f9194deb4Ted Kremenek}; 126b6d2360787e5a0bb5d26f3bc7a83059a8b050dc4Ted Kremenek 127331b0ac44b9eb0ffcba66b4f3f3f9adb27c2434fTed Kremenekclass PostPurgeDeadSymbols : public PostStmt { 128331b0ac44b9eb0ffcba66b4f3f3f9adb27c2434fTed Kremenekpublic: 129331b0ac44b9eb0ffcba66b4f3f3f9adb27c2434fTed Kremenek PostPurgeDeadSymbols(const Stmt* S) : PostStmt(S, PostPurgeDeadSymbolsKind) {} 130331b0ac44b9eb0ffcba66b4f3f3f9adb27c2434fTed Kremenek 131331b0ac44b9eb0ffcba66b4f3f3f9adb27c2434fTed Kremenek static bool classof(const ProgramPoint* Location) { 132331b0ac44b9eb0ffcba66b4f3f3f9adb27c2434fTed Kremenek return Location->getKind() == PostPurgeDeadSymbolsKind; 133331b0ac44b9eb0ffcba66b4f3f3f9adb27c2434fTed Kremenek } 134331b0ac44b9eb0ffcba66b4f3f3f9adb27c2434fTed Kremenek}; 135331b0ac44b9eb0ffcba66b4f3f3f9adb27c2434fTed Kremenek 13683c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenekclass BlockEdge : public ProgramPoint { 13783c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek typedef std::pair<CFGBlock*,CFGBlock*> BPair; 138b6d2360787e5a0bb5d26f3bc7a83059a8b050dc4Ted Kremenekpublic: 13983c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek BlockEdge(CFG& cfg, const CFGBlock* B1, const CFGBlock* B2); 140754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek 141754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek /// This ctor forces the BlockEdge to be constructed using an explicitly 142754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek /// allocated pair object that is stored in the CFG. This is usually 143754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek /// used to construct edges representing jumps using computed gotos. 1446e5977f0a8a680191fb4b4d8f32bc2c629faf0c2Argyrios Kyrtzidis BlockEdge(CFG& cfg, const CFGBlock* B1, const CFGBlock* B2, bool) 1456e5977f0a8a680191fb4b4d8f32bc2c629faf0c2Argyrios Kyrtzidis : ProgramPoint(cfg.getBlockEdgeImpl(B1, B2), BlockEdgeAuxKind) {} 146754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek 14783c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek 14883c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek CFGBlock* getSrc() const; 14983c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek CFGBlock* getDst() const; 150b6d2360787e5a0bb5d26f3bc7a83059a8b050dc4Ted Kremenek 15183c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek static bool classof(const ProgramPoint* Location) { 15283c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek unsigned k = Location->getKind(); 15383c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek return k >= BlockEdgeSrcKind && k <= BlockEdgeAuxKind; 154b6d2360787e5a0bb5d26f3bc7a83059a8b050dc4Ted Kremenek } 155b6d2360787e5a0bb5d26f3bc7a83059a8b050dc4Ted Kremenek}; 156b6d2360787e5a0bb5d26f3bc7a83059a8b050dc4Ted Kremenek 15783c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek 15883c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek 159eb19188e668d0ad2c968fc0286a6922f9194deb4Ted Kremenek} // end namespace clang 1604c3fbe33194cd9b1bfff773647ed785b403e1ba5Ted Kremenek 1614c3fbe33194cd9b1bfff773647ed785b403e1ba5Ted Kremenek 1624c3fbe33194cd9b1bfff773647ed785b403e1ba5Ted Kremeneknamespace llvm { // Traits specialization for DenseMap 1634c3fbe33194cd9b1bfff773647ed785b403e1ba5Ted Kremenek 16483c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenektemplate <> struct DenseMapInfo<clang::ProgramPoint> { 1654c3fbe33194cd9b1bfff773647ed785b403e1ba5Ted Kremenek 16683c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek static inline clang::ProgramPoint getEmptyKey() { 16783c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek uintptr_t x = 16883c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek reinterpret_cast<uintptr_t>(DenseMapInfo<void*>::getEmptyKey()) & ~0x7; 16983c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek 17083c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek return clang::BlockEntrance(reinterpret_cast<clang::CFGBlock*>(x)); 1714c3fbe33194cd9b1bfff773647ed785b403e1ba5Ted Kremenek } 1724c3fbe33194cd9b1bfff773647ed785b403e1ba5Ted Kremenek 17383c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek static inline clang::ProgramPoint getTombstoneKey() { 17483c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek uintptr_t x = 17583c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek reinterpret_cast<uintptr_t>(DenseMapInfo<void*>::getTombstoneKey()) & ~0x7; 17683c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek 17783c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek return clang::BlockEntrance(reinterpret_cast<clang::CFGBlock*>(x)); 1784c3fbe33194cd9b1bfff773647ed785b403e1ba5Ted Kremenek } 1794c3fbe33194cd9b1bfff773647ed785b403e1ba5Ted Kremenek 18083c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek static unsigned getHashValue(const clang::ProgramPoint& Loc) { 18183c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek return DenseMapInfo<void*>::getHashValue(Loc.getRawData()); 1824d20f2dd79e7829ade5e23945a2ef65a8fe1cf39Ted Kremenek } 1834d20f2dd79e7829ade5e23945a2ef65a8fe1cf39Ted Kremenek 18483c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek static bool isEqual(const clang::ProgramPoint& L, 18583c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek const clang::ProgramPoint& R) { 18683c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek return L == R; 1874c3fbe33194cd9b1bfff773647ed785b403e1ba5Ted Kremenek } 1884c3fbe33194cd9b1bfff773647ed785b403e1ba5Ted Kremenek 18983c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek static bool isPod() { 19083c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek return true; 19183c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek } 1924c3fbe33194cd9b1bfff773647ed785b403e1ba5Ted Kremenek}; 1934c3fbe33194cd9b1bfff773647ed785b403e1ba5Ted Kremenek} // end namespace llvm 1944c3fbe33194cd9b1bfff773647ed785b403e1ba5Ted Kremenek 195eb19188e668d0ad2c968fc0286a6922f9194deb4Ted Kremenek#endif 196