ProgramPoint.h revision 8c354758c2d39db87c77c723d81e34b4d967f762 
1//==- ProgramPoint.h - Program Points for Path-Sensitive Analysis --*- C++ -*-//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10//  This file defines the interface ProgramPoint, which identifies a
11//  distinct location in a function.
12//
13//===----------------------------------------------------------------------===//
14
15#ifndef LLVM_CLANG_ANALYSIS_PROGRAM_POINT
16#define LLVM_CLANG_ANALYSIS_PROGRAM_POINT
17
18#include "clang/AST/CFG.h"
19#include "llvm/Support/DataTypes.h"
20#include "llvm/ADT/DenseMap.h"
21#include "llvm/ADT/FoldingSet.h"
22#include <cassert>
23
24namespace clang {
25
26class ProgramPoint {
27public:
28  enum Kind { BlockEdgeKind=0, BlockEntranceKind, BlockExitKind,
29              // Keep the following four together and in this order.
30              PostStmtKind,
31              PostLocationChecksSucceedKind,
32              PostOutOfBoundsCheckFailedKind,
33              PostNullCheckFailedKind,
34              PostUndefLocationCheckFailedKind,
35              PostLoadKind, PostStoreKind,
36              PostPurgeDeadSymbolsKind };
37
38private:
39  std::pair<uintptr_t,uintptr_t> Data;
40
41protected:
42  ProgramPoint(const void* P, Kind k)
43    : Data(reinterpret_cast<uintptr_t>(P), (uintptr_t) k) {}
44
45  ProgramPoint(const void* P1, const void* P2)
46    : Data(reinterpret_cast<uintptr_t>(P1) | 0x1,
47           reinterpret_cast<uintptr_t>(P2)) {}
48
49protected:
50  void* getData1NoMask() const {
51    assert (getKind() != BlockEdgeKind);
52    return reinterpret_cast<void*>(Data.first);
53  }
54
55  void* getData1() const {
56    assert (getKind() == BlockEdgeKind);
57    return reinterpret_cast<void*>(Data.first & ~0x1);
58  }
59
60  void* getData2() const {
61    assert (getKind() == BlockEdgeKind);
62    return reinterpret_cast<void*>(Data.second);
63  }
64
65public:
66
67  uintptr_t getKind() const {
68    return Data.first & 0x1 ? (uintptr_t) BlockEdgeKind : Data.second;
69  }
70
71  // For use with DenseMap.
72  unsigned getHashValue() const {
73    std::pair<void*,void*> P(reinterpret_cast<void*>(Data.first),
74                             reinterpret_cast<void*>(Data.second));
75    return llvm::DenseMapInfo<std::pair<void*,void*> >::getHashValue(P);
76  }
77
78  static bool classof(const ProgramPoint*) { return true; }
79
80  bool operator==(const ProgramPoint & RHS) const {
81    return Data == RHS.Data;
82  }
83
84  bool operator!=(const ProgramPoint& RHS) const {
85    return Data != RHS.Data;
86  }
87
88  bool operator<(const ProgramPoint& RHS) const {
89    return Data < RHS.Data;
90  }
91
92  void Profile(llvm::FoldingSetNodeID& ID) const {
93    ID.AddPointer(reinterpret_cast<void*>(Data.first));
94    ID.AddPointer(reinterpret_cast<void*>(Data.second));
95  }
96};
97
98class BlockEntrance : public ProgramPoint {
99public:
100  BlockEntrance(const CFGBlock* B) : ProgramPoint(B, BlockEntranceKind) {}
101
102  CFGBlock* getBlock() const {
103    return reinterpret_cast<CFGBlock*>(getData1NoMask());
104  }
105
106  Stmt* getFirstStmt() const {
107    CFGBlock* B = getBlock();
108    return B->empty() ? NULL : B->front();
109  }
110
111  static bool classof(const ProgramPoint* Location) {
112    return Location->getKind() == BlockEntranceKind;
113  }
114};
115
116class BlockExit : public ProgramPoint {
117public:
118  BlockExit(const CFGBlock* B) : ProgramPoint(B, BlockExitKind) {}
119
120  CFGBlock* getBlock() const {
121    return reinterpret_cast<CFGBlock*>(getData1NoMask());
122  }
123
124  Stmt* getLastStmt() const {
125    CFGBlock* B = getBlock();
126    return B->empty() ? NULL : B->back();
127  }
128
129  Stmt* getTerminator() const {
130    return getBlock()->getTerminator();
131  }
132
133  static bool classof(const ProgramPoint* Location) {
134    return Location->getKind() == BlockExitKind;
135  }
136};
137
138
139class PostStmt : public ProgramPoint {
140protected:
141  PostStmt(const Stmt* S, Kind k) : ProgramPoint(S, k) {}
142public:
143  PostStmt(const Stmt* S) : ProgramPoint(S, PostStmtKind) {}
144
145  Stmt* getStmt() const { return (Stmt*) getData1NoMask(); }
146
147  static bool classof(const ProgramPoint* Location) {
148    unsigned k = Location->getKind();
149    return k >= PostStmtKind && k <= PostPurgeDeadSymbolsKind;
150  }
151};
152
153class PostLocationChecksSucceed : public PostStmt {
154public:
155  PostLocationChecksSucceed(const Stmt* S)
156    : PostStmt(S, PostLocationChecksSucceedKind) {}
157
158  static bool classof(const ProgramPoint* Location) {
159    return Location->getKind() == PostLocationChecksSucceedKind;
160  }
161};
162
163class PostOutOfBoundsCheckFailed : public PostStmt {
164public:
165  PostOutOfBoundsCheckFailed(const Stmt* S)
166  : PostStmt(S, PostOutOfBoundsCheckFailedKind) {}
167
168  static bool classof(const ProgramPoint* Location) {
169    return Location->getKind() == PostOutOfBoundsCheckFailedKind;
170  }
171};
172
173class PostUndefLocationCheckFailed : public PostStmt {
174public:
175  PostUndefLocationCheckFailed(const Stmt* S)
176  : PostStmt(S, PostUndefLocationCheckFailedKind) {}
177
178  static bool classof(const ProgramPoint* Location) {
179    return Location->getKind() == PostUndefLocationCheckFailedKind;
180  }
181};
182
183class PostNullCheckFailed : public PostStmt {
184public:
185  PostNullCheckFailed(const Stmt* S)
186  : PostStmt(S, PostNullCheckFailedKind) {}
187
188  static bool classof(const ProgramPoint* Location) {
189    return Location->getKind() == PostNullCheckFailedKind;
190  }
191};
192
193class PostLoad : public PostStmt {
194public:
195  PostLoad(const Stmt* S) : PostStmt(S, PostLoadKind) {}
196
197  static bool classof(const ProgramPoint* Location) {
198    return Location->getKind() == PostLoadKind;
199  }
200};
201
202class PostStore : public PostStmt {
203public:
204  PostStore(const Stmt* S) : PostStmt(S, PostStoreKind) {}
205
206  static bool classof(const ProgramPoint* Location) {
207    return Location->getKind() == PostStoreKind;
208  }
209};
210
211class PostPurgeDeadSymbols : public PostStmt {
212public:
213  PostPurgeDeadSymbols(const Stmt* S) : PostStmt(S, PostPurgeDeadSymbolsKind) {}
214
215  static bool classof(const ProgramPoint* Location) {
216    return Location->getKind() == PostPurgeDeadSymbolsKind;
217  }
218};
219
220class BlockEdge : public ProgramPoint {
221public:
222  BlockEdge(const CFGBlock* B1, const CFGBlock* B2)
223    : ProgramPoint(B1, B2) {}
224
225  CFGBlock* getSrc() const {
226    return static_cast<CFGBlock*>(getData1());
227  }
228
229  CFGBlock* getDst() const {
230    return static_cast<CFGBlock*>(getData2());
231  }
232
233  static bool classof(const ProgramPoint* Location) {
234    return Location->getKind() == BlockEdgeKind;
235  }
236};
237
238
239} // end namespace clang
240
241
242namespace llvm { // Traits specialization for DenseMap
243
244template <> struct DenseMapInfo<clang::ProgramPoint> {
245
246static inline clang::ProgramPoint getEmptyKey() {
247  uintptr_t x =
248   reinterpret_cast<uintptr_t>(DenseMapInfo<void*>::getEmptyKey()) & ~0x7;
249  return clang::BlockEntrance(reinterpret_cast<clang::CFGBlock*>(x));
250}
251
252static inline clang::ProgramPoint getTombstoneKey() {
253  uintptr_t x =
254   reinterpret_cast<uintptr_t>(DenseMapInfo<void*>::getTombstoneKey()) & ~0x7;
255  return clang::BlockEntrance(reinterpret_cast<clang::CFGBlock*>(x));
256}
257
258static unsigned getHashValue(const clang::ProgramPoint& Loc) {
259  return Loc.getHashValue();
260}
261
262static bool isEqual(const clang::ProgramPoint& L,
263                    const clang::ProgramPoint& R) {
264  return L == R;
265}
266
267static bool isPod() {
268  return true;
269}
270};
271} // end namespace llvm
272
273#endif
274