ProgramPoint.h revision 05e14cd46ef44c07385aae96ec2fdcb9bf7e9467
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" 214c3fbe33194cd9b1bfff773647ed785b403e1ba5Ted Kremenek#include <cassert> 22eb19188e668d0ad2c968fc0286a6922f9194deb4Ted Kremenek 23eb19188e668d0ad2c968fc0286a6922f9194deb4Ted Kremeneknamespace clang { 2405e14cd46ef44c07385aae96ec2fdcb9bf7e9467Ted Kremenek 2583c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenekclass ProgramPoint { 26eb19188e668d0ad2c968fc0286a6922f9194deb4Ted Kremenekpublic: 2783c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek enum Kind { BlockEntranceKind=0, PostStmtKind=1, BlockExitKind=2, 2883c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek BlockEdgeSrcKind=3, BlockEdgeDstKind=4, BlockEdgeAuxKind=5 }; 2983c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenekprotected: 3083c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek uintptr_t Data; 314c3fbe33194cd9b1bfff773647ed785b403e1ba5Ted Kremenek 3283c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek ProgramPoint(const void* Ptr, Kind k) { 3383c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek assert ((reinterpret_cast<uintptr_t>(const_cast<void*>(Ptr)) & 0x7) == 0 3483c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek && "Address must have at least an 8-byte alignment."); 3583c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek 3683c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek Data = reinterpret_cast<uintptr_t>(const_cast<void*>(Ptr)) & k; 374c3fbe33194cd9b1bfff773647ed785b403e1ba5Ted Kremenek } 384c3fbe33194cd9b1bfff773647ed785b403e1ba5Ted Kremenek 3983c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek ProgramPoint() : Data(0) {} 404d20f2dd79e7829ade5e23945a2ef65a8fe1cf39Ted Kremenek 4183c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenekpublic: 4283c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek unsigned getKind() const { return Data & 0x5; } 4383c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek void* getRawPtr() const { return reinterpret_cast<void*>(Data & ~0x7); } 4483c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek void* getRawData() const { return reinterpret_cast<void*>(Data); } 45eb19188e668d0ad2c968fc0286a6922f9194deb4Ted Kremenek 4683c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek static bool classof(const ProgramPoint*) { return true; } 4783c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek bool operator==(const ProgramPoint & RHS) const { return Data == RHS.Data; } 4883c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek bool operator!=(const ProgramPoint& RHS) const { return Data != RHS.Data; } 49eb19188e668d0ad2c968fc0286a6922f9194deb4Ted Kremenek}; 5083c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek 5183c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenekclass BlockEntrance : public ProgramPoint { 52eb19188e668d0ad2c968fc0286a6922f9194deb4Ted Kremenekpublic: 5383c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek BlockEntrance(const CFGBlock* B) : ProgramPoint(B, BlockEntranceKind) {} 5483c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek 5583c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek CFGBlock* getBlock() const { 5683c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek return reinterpret_cast<CFGBlock*>(getRawPtr()); 57bd129696c554fbbcd9405104641e292f0fb4678dTed Kremenek } 58eb19188e668d0ad2c968fc0286a6922f9194deb4Ted Kremenek 5983c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek Stmt* getFirstStmt() const { 6083c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek CFGBlock* B = getBlock(); 6183c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek return B->empty() ? NULL : B->front(); 6283c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek } 63eb19188e668d0ad2c968fc0286a6922f9194deb4Ted Kremenek 6483c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek static bool classof(const ProgramPoint* Location) { 6583c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek return Location->getKind() == BlockEntranceKind; 66bd129696c554fbbcd9405104641e292f0fb4678dTed Kremenek } 67eb19188e668d0ad2c968fc0286a6922f9194deb4Ted Kremenek}; 6883c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek 6983c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenekclass BlockExit : public ProgramPoint { 70eb19188e668d0ad2c968fc0286a6922f9194deb4Ted Kremenekpublic: 7183c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek BlockExit(const CFGBlock* B) : ProgramPoint(B, BlockExitKind) {} 72bd129696c554fbbcd9405104641e292f0fb4678dTed Kremenek 7383c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek CFGBlock* getBlock() const { 7483c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek return reinterpret_cast<CFGBlock*>(getRawPtr()); 75bd129696c554fbbcd9405104641e292f0fb4678dTed Kremenek } 7683c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek 7783c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek Stmt* getLastStmt() const { 7883c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek CFGBlock* B = getBlock(); 7983c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek return B->empty() ? NULL : B->back(); 80bd129696c554fbbcd9405104641e292f0fb4678dTed Kremenek } 81bd129696c554fbbcd9405104641e292f0fb4678dTed Kremenek 8283c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek Stmt* getTerminator() const { 8383c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek return getBlock()->getTerminator(); 84bd129696c554fbbcd9405104641e292f0fb4678dTed Kremenek } 8583c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek 8683c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek static bool classof(const ProgramPoint* Location) { 8783c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek return Location->getKind() == BlockExitKind; 88bd129696c554fbbcd9405104641e292f0fb4678dTed Kremenek } 89bd129696c554fbbcd9405104641e292f0fb4678dTed Kremenek}; 90eb19188e668d0ad2c968fc0286a6922f9194deb4Ted Kremenek 9183c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek 9283c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenekclass PostStmt : public ProgramPoint { 93eb19188e668d0ad2c968fc0286a6922f9194deb4Ted Kremenekpublic: 9483c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek PostStmt(const Stmt* S) : ProgramPoint(S, PostStmtKind) {} 95eb19188e668d0ad2c968fc0286a6922f9194deb4Ted Kremenek 9683c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek Stmt* getStmt() const { return (Stmt*) getRawPtr(); } 9783c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek 9883c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek static bool classof(const ProgramPoint* Location) { 9983c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek return Location->getKind() == PostStmtKind; 100bd129696c554fbbcd9405104641e292f0fb4678dTed Kremenek } 101eb19188e668d0ad2c968fc0286a6922f9194deb4Ted Kremenek}; 102b6d2360787e5a0bb5d26f3bc7a83059a8b050dc4Ted Kremenek 10383c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenekclass BlockEdge : public ProgramPoint { 10483c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek typedef std::pair<CFGBlock*,CFGBlock*> BPair; 105b6d2360787e5a0bb5d26f3bc7a83059a8b050dc4Ted Kremenekpublic: 10683c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek BlockEdge(CFG& cfg, const CFGBlock* B1, const CFGBlock* B2); 10783c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek 10883c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek CFGBlock* getSrc() const; 10983c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek CFGBlock* getDst() const; 110b6d2360787e5a0bb5d26f3bc7a83059a8b050dc4Ted Kremenek 11183c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek static bool classof(const ProgramPoint* Location) { 11283c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek unsigned k = Location->getKind(); 11383c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek return k >= BlockEdgeSrcKind && k <= BlockEdgeAuxKind; 114b6d2360787e5a0bb5d26f3bc7a83059a8b050dc4Ted Kremenek } 115b6d2360787e5a0bb5d26f3bc7a83059a8b050dc4Ted Kremenek}; 116b6d2360787e5a0bb5d26f3bc7a83059a8b050dc4Ted Kremenek 11783c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek 11883c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek 119eb19188e668d0ad2c968fc0286a6922f9194deb4Ted Kremenek} // end namespace clang 1204c3fbe33194cd9b1bfff773647ed785b403e1ba5Ted Kremenek 1214c3fbe33194cd9b1bfff773647ed785b403e1ba5Ted Kremenek 1224c3fbe33194cd9b1bfff773647ed785b403e1ba5Ted Kremeneknamespace llvm { // Traits specialization for DenseMap 1234c3fbe33194cd9b1bfff773647ed785b403e1ba5Ted Kremenek 12483c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenektemplate <> struct DenseMapInfo<clang::ProgramPoint> { 1254c3fbe33194cd9b1bfff773647ed785b403e1ba5Ted Kremenek 12683c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek static inline clang::ProgramPoint getEmptyKey() { 12783c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek uintptr_t x = 12883c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek reinterpret_cast<uintptr_t>(DenseMapInfo<void*>::getEmptyKey()) & ~0x7; 12983c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek 13083c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek return clang::BlockEntrance(reinterpret_cast<clang::CFGBlock*>(x)); 1314c3fbe33194cd9b1bfff773647ed785b403e1ba5Ted Kremenek } 1324c3fbe33194cd9b1bfff773647ed785b403e1ba5Ted Kremenek 13383c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek static inline clang::ProgramPoint getTombstoneKey() { 13483c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek uintptr_t x = 13583c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek reinterpret_cast<uintptr_t>(DenseMapInfo<void*>::getTombstoneKey()) & ~0x7; 13683c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek 13783c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek return clang::BlockEntrance(reinterpret_cast<clang::CFGBlock*>(x)); 1384c3fbe33194cd9b1bfff773647ed785b403e1ba5Ted Kremenek } 1394c3fbe33194cd9b1bfff773647ed785b403e1ba5Ted Kremenek 14083c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek static unsigned getHashValue(const clang::ProgramPoint& Loc) { 14183c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek return DenseMapInfo<void*>::getHashValue(Loc.getRawData()); 1424d20f2dd79e7829ade5e23945a2ef65a8fe1cf39Ted Kremenek } 1434d20f2dd79e7829ade5e23945a2ef65a8fe1cf39Ted Kremenek 14483c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek static bool isEqual(const clang::ProgramPoint& L, 14583c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek const clang::ProgramPoint& R) { 14683c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek return L == R; 1474c3fbe33194cd9b1bfff773647ed785b403e1ba5Ted Kremenek } 1484c3fbe33194cd9b1bfff773647ed785b403e1ba5Ted Kremenek 14983c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek static bool isPod() { 15083c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek return true; 15183c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek } 1524c3fbe33194cd9b1bfff773647ed785b403e1ba5Ted Kremenek}; 1534c3fbe33194cd9b1bfff773647ed785b403e1ba5Ted Kremenek} // end namespace llvm 1544c3fbe33194cd9b1bfff773647ed785b403e1ba5Ted Kremenek 155eb19188e668d0ad2c968fc0286a6922f9194deb4Ted Kremenek#endif 156