ProgramPoint.h revision f4be8ee748831bc23e35b542e6c1bb6d1eb49baa 
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 = 0x0,
29              BlockEntranceKind = 0x1,
30              BlockExitKind = 0x2,
31              // Keep the following four together and in this order.
32              PostStmtKind = 0x3,
33              PostLocationChecksSucceedKind = 0x4,
34              PostOutOfBoundsCheckFailedKind = 0x5,
35              PostNullCheckFailedKind = 0x6,
36              PostUndefLocationCheckFailedKind = 0x7,
37              PostLoadKind = 0x8,
38              PostStoreKind = 0x9,
39              PostPurgeDeadSymbolsKind = 0x10,
40              PostStmtCustomKind = 0x11,
41              MinPostStmtKind = PostStmtKind,
42              MaxPostStmtKind = PostStmtCustomKind };
43
44private:
45  enum { TwoPointers = 0x1, Custom = 0x2, Mask = 0x3 };
46
47  std::pair<uintptr_t,uintptr_t> Data;
48
49protected:
50  ProgramPoint(const void* P, Kind k)
51    : Data(reinterpret_cast<uintptr_t>(P),
52           (uintptr_t) k) {}
53
54  ProgramPoint(const void* P1, const void* P2)
55    : Data(reinterpret_cast<uintptr_t>(P1) | TwoPointers,
56           reinterpret_cast<uintptr_t>(P2)) {}
57
58  ProgramPoint(const void* P1, const void* P2, bool)
59    : Data(reinterpret_cast<uintptr_t>(P1) | Custom,
60           reinterpret_cast<uintptr_t>(P2)) {}
61
62protected:
63  void* getData1NoMask() const {
64    Kind k = getKind(); k = k;
65    assert(k == BlockEntranceKind || k == BlockExitKind);
66    return reinterpret_cast<void*>(Data.first);
67  }
68
69  void* getData1() const {
70    Kind k = getKind(); k = k;
71    assert(k == BlockEdgeKind || (k >= MinPostStmtKind && k < MaxPostStmtKind));
72    return reinterpret_cast<void*>(Data.first & ~Mask);
73  }
74
75  void* getData2() const {
76    Kind k = getKind(); k = k;
77    assert(k == BlockEdgeKind || k == PostStmtCustomKind);
78    return reinterpret_cast<void*>(Data.second);
79  }
80
81public:
82  Kind getKind() const {
83    switch (Data.first & Mask) {
84      case TwoPointers: return BlockEdgeKind;
85      case Custom: return PostStmtCustomKind;
86      default: return (Kind) Data.second;
87    }
88  }
89
90  // For use with DenseMap.
91  unsigned getHashValue() const {
92    std::pair<void*,void*> P(reinterpret_cast<void*>(Data.first),
93                             reinterpret_cast<void*>(Data.second));
94    return llvm::DenseMapInfo<std::pair<void*,void*> >::getHashValue(P);
95  }
96
97  static bool classof(const ProgramPoint*) { return true; }
98
99  bool operator==(const ProgramPoint & RHS) const {
100    return Data == RHS.Data;
101  }
102
103  bool operator!=(const ProgramPoint& RHS) const {
104    return Data != RHS.Data;
105  }
106
107  bool operator<(const ProgramPoint& RHS) const {
108    return Data < RHS.Data;
109  }
110
111  void Profile(llvm::FoldingSetNodeID& ID) const {
112    ID.AddPointer(reinterpret_cast<void*>(Data.first));
113    ID.AddPointer(reinterpret_cast<void*>(Data.second));
114  }
115};
116
117class BlockEntrance : public ProgramPoint {
118public:
119  BlockEntrance(const CFGBlock* B) : ProgramPoint(B, BlockEntranceKind) {}
120
121  CFGBlock* getBlock() const {
122    return reinterpret_cast<CFGBlock*>(getData1NoMask());
123  }
124
125  Stmt* getFirstStmt() const {
126    CFGBlock* B = getBlock();
127    return B->empty() ? NULL : B->front();
128  }
129
130  static bool classof(const ProgramPoint* Location) {
131    return Location->getKind() == BlockEntranceKind;
132  }
133};
134
135class BlockExit : public ProgramPoint {
136public:
137  BlockExit(const CFGBlock* B) : ProgramPoint(B, BlockExitKind) {}
138
139  CFGBlock* getBlock() const {
140    return reinterpret_cast<CFGBlock*>(getData1NoMask());
141  }
142
143  Stmt* getLastStmt() const {
144    CFGBlock* B = getBlock();
145    return B->empty() ? NULL : B->back();
146  }
147
148  Stmt* getTerminator() const {
149    return getBlock()->getTerminator();
150  }
151
152  static bool classof(const ProgramPoint* Location) {
153    return Location->getKind() == BlockExitKind;
154  }
155};
156
157
158class PostStmt : public ProgramPoint {
159protected:
160  PostStmt(const Stmt* S, Kind k) : ProgramPoint(S, k) {}
161  PostStmt(const Stmt* S, const void* data) : ProgramPoint(S, data, true) {}
162
163public:
164  PostStmt(const Stmt* S) : ProgramPoint(S, PostStmtKind) {}
165
166  Stmt* getStmt() const { return (Stmt*) getData1(); }
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)
177    : PostStmt(S, PostLocationChecksSucceedKind) {}
178
179  static bool classof(const ProgramPoint* Location) {
180    return Location->getKind() == PostLocationChecksSucceedKind;
181  }
182};
183
184class PostStmtCustom : public PostStmt {
185  PostStmtCustom(const Stmt* S, const void* Data)
186    : PostStmt(S, Data) {
187    assert(getKind() == PostStmtCustomKind);
188  }
189
190  void* getCustomData() const { return getData2(); }
191
192  static bool classof(const ProgramPoint* Location) {
193    return Location->getKind() == PostStmtCustomKind;
194  }
195};
196
197class PostOutOfBoundsCheckFailed : public PostStmt {
198public:
199  PostOutOfBoundsCheckFailed(const Stmt* S)
200  : PostStmt(S, PostOutOfBoundsCheckFailedKind) {}
201
202  static bool classof(const ProgramPoint* Location) {
203    return Location->getKind() == PostOutOfBoundsCheckFailedKind;
204  }
205};
206
207class PostUndefLocationCheckFailed : public PostStmt {
208public:
209  PostUndefLocationCheckFailed(const Stmt* S)
210  : PostStmt(S, PostUndefLocationCheckFailedKind) {}
211
212  static bool classof(const ProgramPoint* Location) {
213    return Location->getKind() == PostUndefLocationCheckFailedKind;
214  }
215};
216
217class PostNullCheckFailed : public PostStmt {
218public:
219  PostNullCheckFailed(const Stmt* S)
220  : PostStmt(S, PostNullCheckFailedKind) {}
221
222  static bool classof(const ProgramPoint* Location) {
223    return Location->getKind() == PostNullCheckFailedKind;
224  }
225};
226
227class PostLoad : public PostStmt {
228public:
229  PostLoad(const Stmt* S) : PostStmt(S, PostLoadKind) {}
230
231  static bool classof(const ProgramPoint* Location) {
232    return Location->getKind() == PostLoadKind;
233  }
234};
235
236class PostStore : public PostStmt {
237public:
238  PostStore(const Stmt* S) : PostStmt(S, PostStoreKind) {}
239
240  static bool classof(const ProgramPoint* Location) {
241    return Location->getKind() == PostStoreKind;
242  }
243};
244
245class PostPurgeDeadSymbols : public PostStmt {
246public:
247  PostPurgeDeadSymbols(const Stmt* S) : PostStmt(S, PostPurgeDeadSymbolsKind) {}
248
249  static bool classof(const ProgramPoint* Location) {
250    return Location->getKind() == PostPurgeDeadSymbolsKind;
251  }
252};
253
254class BlockEdge : public ProgramPoint {
255public:
256  BlockEdge(const CFGBlock* B1, const CFGBlock* B2)
257    : ProgramPoint(B1, B2) {}
258
259  CFGBlock* getSrc() const {
260    return static_cast<CFGBlock*>(getData1());
261  }
262
263  CFGBlock* getDst() const {
264    return static_cast<CFGBlock*>(getData2());
265  }
266
267  static bool classof(const ProgramPoint* Location) {
268    return Location->getKind() == BlockEdgeKind;
269  }
270};
271
272
273} // end namespace clang
274
275
276namespace llvm { // Traits specialization for DenseMap
277
278template <> struct DenseMapInfo<clang::ProgramPoint> {
279
280static inline clang::ProgramPoint getEmptyKey() {
281  uintptr_t x =
282   reinterpret_cast<uintptr_t>(DenseMapInfo<void*>::getEmptyKey()) & ~0x7;
283  return clang::BlockEntrance(reinterpret_cast<clang::CFGBlock*>(x));
284}
285
286static inline clang::ProgramPoint getTombstoneKey() {
287  uintptr_t x =
288   reinterpret_cast<uintptr_t>(DenseMapInfo<void*>::getTombstoneKey()) & ~0x7;
289  return clang::BlockEntrance(reinterpret_cast<clang::CFGBlock*>(x));
290}
291
292static unsigned getHashValue(const clang::ProgramPoint& Loc) {
293  return Loc.getHashValue();
294}
295
296static bool isEqual(const clang::ProgramPoint& L,
297                    const clang::ProgramPoint& R) {
298  return L == R;
299}
300
301static bool isPod() {
302  return true;
303}
304};
305} // end namespace llvm
306
307#endif
308