ProgramPoint.h revision d452758bb6b59340528a26def9ecc24b329d4ecf
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: 28d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek enum Kind { BlockEdgeKind=0, BlockEntranceKind, BlockExitKind, 29d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek // Keep the following three together and in this order. 30d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek PostStmtKind, PostLoadKind, PostPurgeDeadSymbolsKind }; 314c3fbe33194cd9b1bfff773647ed785b403e1ba5Ted Kremenek 32d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenekprivate: 33d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek std::pair<uintptr_t,uintptr_t> Data; 34d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek 35d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenekprotected: 36d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek ProgramPoint(const void* P, Kind k) 37d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek : Data(reinterpret_cast<uintptr_t>(P), (uintptr_t) k) {} 38d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek 39d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek ProgramPoint(const void* P1, const void* P2) 40d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek : Data(reinterpret_cast<uintptr_t>(P1) | 0x1, 41d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek reinterpret_cast<uintptr_t>(P2)) {} 42d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek 43d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenekprotected: 44d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek void* getData1NoMask() const { 45d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek assert (getKind() != BlockEdgeKind); 46d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek return reinterpret_cast<void*>(Data.first); 476e5977f0a8a680191fb4b4d8f32bc2c629faf0c2Argyrios Kyrtzidis } 486e5977f0a8a680191fb4b4d8f32bc2c629faf0c2Argyrios Kyrtzidis 49d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek void* getData1() const { 50d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek assert (getKind() == BlockEdgeKind); 51d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek return reinterpret_cast<void*>(Data.first & ~0x1); 52d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek } 536e5977f0a8a680191fb4b4d8f32bc2c629faf0c2Argyrios Kyrtzidis 54d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek void* getData2() const { 55d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek assert (getKind() == BlockEdgeKind); 56d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek return reinterpret_cast<void*>(Data.second); 574c3fbe33194cd9b1bfff773647ed785b403e1ba5Ted Kremenek } 584c3fbe33194cd9b1bfff773647ed785b403e1ba5Ted Kremenek 5983c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenekpublic: 60d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek 61d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek uintptr_t getKind() const { 62d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek return Data.first & 0x1 ? (uintptr_t) BlockEdgeKind : Data.second; 63d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek } 64d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek 65d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek // For use with DenseMap. 66d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek unsigned getHashValue() const { 67d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek std::pair<void*,void*> P(reinterpret_cast<void*>(Data.first), 68d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek reinterpret_cast<void*>(Data.second)); 69d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek return llvm::DenseMapInfo<std::pair<void*,void*> >::getHashValue(P); 70d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek } 71eb19188e668d0ad2c968fc0286a6922f9194deb4Ted Kremenek 7283c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek static bool classof(const ProgramPoint*) { return true; } 73d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek 74d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek bool operator==(const ProgramPoint & RHS) const { 75d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek return Data == RHS.Data; 76d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek } 77d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek 78d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek bool operator!=(const ProgramPoint& RHS) const { 79d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek return Data != RHS.Data; 80d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek } 81d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek 82d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek bool operator<(const ProgramPoint& RHS) const { 83d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek return Data < RHS.Data; 84d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek } 855226755ab5ce6346f98b5f41cdcffbe84c5bb484Ted Kremenek 865226755ab5ce6346f98b5f41cdcffbe84c5bb484Ted Kremenek void Profile(llvm::FoldingSetNodeID& ID) const { 87d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek ID.AddPointer(reinterpret_cast<void*>(Data.first)); 88d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek ID.AddPointer(reinterpret_cast<void*>(Data.second)); 895226755ab5ce6346f98b5f41cdcffbe84c5bb484Ted Kremenek } 90eb19188e668d0ad2c968fc0286a6922f9194deb4Ted Kremenek}; 9183c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek 9283c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenekclass BlockEntrance : public ProgramPoint { 93eb19188e668d0ad2c968fc0286a6922f9194deb4Ted Kremenekpublic: 9483c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek BlockEntrance(const CFGBlock* B) : ProgramPoint(B, BlockEntranceKind) {} 9583c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek 9683c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek CFGBlock* getBlock() const { 97d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek return reinterpret_cast<CFGBlock*>(getData1NoMask()); 98bd129696c554fbbcd9405104641e292f0fb4678dTed Kremenek } 99eb19188e668d0ad2c968fc0286a6922f9194deb4Ted Kremenek 10083c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek Stmt* getFirstStmt() const { 10183c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek CFGBlock* B = getBlock(); 10283c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek return B->empty() ? NULL : B->front(); 10383c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek } 104eb19188e668d0ad2c968fc0286a6922f9194deb4Ted Kremenek 10583c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek static bool classof(const ProgramPoint* Location) { 10683c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek return Location->getKind() == BlockEntranceKind; 107bd129696c554fbbcd9405104641e292f0fb4678dTed Kremenek } 108eb19188e668d0ad2c968fc0286a6922f9194deb4Ted Kremenek}; 10983c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek 11083c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenekclass BlockExit : public ProgramPoint { 111eb19188e668d0ad2c968fc0286a6922f9194deb4Ted Kremenekpublic: 11283c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek BlockExit(const CFGBlock* B) : ProgramPoint(B, BlockExitKind) {} 113bd129696c554fbbcd9405104641e292f0fb4678dTed Kremenek 11483c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek CFGBlock* getBlock() const { 115d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek return reinterpret_cast<CFGBlock*>(getData1NoMask()); 116bd129696c554fbbcd9405104641e292f0fb4678dTed Kremenek } 11783c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek 11883c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek Stmt* getLastStmt() const { 11983c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek CFGBlock* B = getBlock(); 12083c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek return B->empty() ? NULL : B->back(); 121bd129696c554fbbcd9405104641e292f0fb4678dTed Kremenek } 122bd129696c554fbbcd9405104641e292f0fb4678dTed Kremenek 12383c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek Stmt* getTerminator() const { 12483c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek return getBlock()->getTerminator(); 125bd129696c554fbbcd9405104641e292f0fb4678dTed Kremenek } 12683c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek 12783c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek static bool classof(const ProgramPoint* Location) { 12883c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek return Location->getKind() == BlockExitKind; 129bd129696c554fbbcd9405104641e292f0fb4678dTed Kremenek } 130bd129696c554fbbcd9405104641e292f0fb4678dTed Kremenek}; 131eb19188e668d0ad2c968fc0286a6922f9194deb4Ted Kremenek 13283c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek 13383c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenekclass PostStmt : public ProgramPoint { 1341b8bd4d71c2098126041b4de4267175a82f0103cTed Kremenekprotected: 1351b8bd4d71c2098126041b4de4267175a82f0103cTed Kremenek PostStmt(const Stmt* S, Kind k) : ProgramPoint(S, k) {} 136eb19188e668d0ad2c968fc0286a6922f9194deb4Ted Kremenekpublic: 13783c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek PostStmt(const Stmt* S) : ProgramPoint(S, PostStmtKind) {} 1381b8bd4d71c2098126041b4de4267175a82f0103cTed Kremenek 139d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek Stmt* getStmt() const { return (Stmt*) getData1NoMask(); } 14083c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek 14183c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek static bool classof(const ProgramPoint* Location) { 1421b8bd4d71c2098126041b4de4267175a82f0103cTed Kremenek unsigned k = Location->getKind(); 143331b0ac44b9eb0ffcba66b4f3f3f9adb27c2434fTed Kremenek return k >= PostStmtKind && k <= PostPurgeDeadSymbolsKind; 1441b8bd4d71c2098126041b4de4267175a82f0103cTed Kremenek } 1451b8bd4d71c2098126041b4de4267175a82f0103cTed Kremenek}; 1461b8bd4d71c2098126041b4de4267175a82f0103cTed Kremenek 1471b8bd4d71c2098126041b4de4267175a82f0103cTed Kremenekclass PostLoad : public PostStmt { 1481b8bd4d71c2098126041b4de4267175a82f0103cTed Kremenekpublic: 1491b8bd4d71c2098126041b4de4267175a82f0103cTed Kremenek PostLoad(const Stmt* S) : PostStmt(S, PostLoadKind) {} 1501b8bd4d71c2098126041b4de4267175a82f0103cTed Kremenek 1511b8bd4d71c2098126041b4de4267175a82f0103cTed Kremenek static bool classof(const ProgramPoint* Location) { 1521b8bd4d71c2098126041b4de4267175a82f0103cTed Kremenek return Location->getKind() == PostLoadKind; 153bd129696c554fbbcd9405104641e292f0fb4678dTed Kremenek } 154eb19188e668d0ad2c968fc0286a6922f9194deb4Ted Kremenek}; 155b6d2360787e5a0bb5d26f3bc7a83059a8b050dc4Ted Kremenek 156331b0ac44b9eb0ffcba66b4f3f3f9adb27c2434fTed Kremenekclass PostPurgeDeadSymbols : public PostStmt { 157331b0ac44b9eb0ffcba66b4f3f3f9adb27c2434fTed Kremenekpublic: 158331b0ac44b9eb0ffcba66b4f3f3f9adb27c2434fTed Kremenek PostPurgeDeadSymbols(const Stmt* S) : PostStmt(S, PostPurgeDeadSymbolsKind) {} 159331b0ac44b9eb0ffcba66b4f3f3f9adb27c2434fTed Kremenek 160331b0ac44b9eb0ffcba66b4f3f3f9adb27c2434fTed Kremenek static bool classof(const ProgramPoint* Location) { 161331b0ac44b9eb0ffcba66b4f3f3f9adb27c2434fTed Kremenek return Location->getKind() == PostPurgeDeadSymbolsKind; 162331b0ac44b9eb0ffcba66b4f3f3f9adb27c2434fTed Kremenek } 163331b0ac44b9eb0ffcba66b4f3f3f9adb27c2434fTed Kremenek}; 164331b0ac44b9eb0ffcba66b4f3f3f9adb27c2434fTed Kremenek 16583c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenekclass BlockEdge : public ProgramPoint { 166b6d2360787e5a0bb5d26f3bc7a83059a8b050dc4Ted Kremenekpublic: 167d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek BlockEdge(const CFGBlock* B1, const CFGBlock* B2) 168d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek : ProgramPoint(B1, B2) {} 169d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek 170d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek CFGBlock* getSrc() const { 171d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek return static_cast<CFGBlock*>(getData1()); 172d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek } 173d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek 174d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek CFGBlock* getDst() const { 175d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek return static_cast<CFGBlock*>(getData2()); 176d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek } 177b6d2360787e5a0bb5d26f3bc7a83059a8b050dc4Ted Kremenek 17883c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek static bool classof(const ProgramPoint* Location) { 179d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek return Location->getKind() == BlockEdgeKind; 180b6d2360787e5a0bb5d26f3bc7a83059a8b050dc4Ted Kremenek } 181b6d2360787e5a0bb5d26f3bc7a83059a8b050dc4Ted Kremenek}; 18283c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek 18383c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek 184eb19188e668d0ad2c968fc0286a6922f9194deb4Ted Kremenek} // end namespace clang 1854c3fbe33194cd9b1bfff773647ed785b403e1ba5Ted Kremenek 1864c3fbe33194cd9b1bfff773647ed785b403e1ba5Ted Kremenek 1874c3fbe33194cd9b1bfff773647ed785b403e1ba5Ted Kremeneknamespace llvm { // Traits specialization for DenseMap 1884c3fbe33194cd9b1bfff773647ed785b403e1ba5Ted Kremenek 18983c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenektemplate <> struct DenseMapInfo<clang::ProgramPoint> { 1904c3fbe33194cd9b1bfff773647ed785b403e1ba5Ted Kremenek 191d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenekstatic inline clang::ProgramPoint getEmptyKey() { 192d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek uintptr_t x = 193d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek reinterpret_cast<uintptr_t>(DenseMapInfo<void*>::getEmptyKey()) & ~0x7; 194d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek return clang::BlockEntrance(reinterpret_cast<clang::CFGBlock*>(x)); 195d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek} 196d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek 197d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenekstatic inline clang::ProgramPoint getTombstoneKey() { 198d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek uintptr_t x = 199d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek reinterpret_cast<uintptr_t>(DenseMapInfo<void*>::getTombstoneKey()) & ~0x7; 200d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek return clang::BlockEntrance(reinterpret_cast<clang::CFGBlock*>(x)); 201d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek} 202d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek 203d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenekstatic unsigned getHashValue(const clang::ProgramPoint& Loc) { 204d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek return Loc.getHashValue(); 205d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek} 206d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek 207d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenekstatic bool isEqual(const clang::ProgramPoint& L, 208d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek const clang::ProgramPoint& R) { 209d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek return L == R; 210d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek} 211d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek 212d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenekstatic bool isPod() { 213d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek return true; 214d452758bb6b59340528a26def9ecc24b329d4ecfTed Kremenek} 2154c3fbe33194cd9b1bfff773647ed785b403e1ba5Ted Kremenek}; 2164c3fbe33194cd9b1bfff773647ed785b403e1ba5Ted Kremenek} // end namespace llvm 2174c3fbe33194cd9b1bfff773647ed785b403e1ba5Ted Kremenek 218eb19188e668d0ad2c968fc0286a6922f9194deb4Ted Kremenek#endif 219