ProgramPoint.h revision 9f8eb2032030482b1d3de86e9bee725d93564302 
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/Analysis/CFG.h"
19#include "llvm/System/DataTypes.h"
20#include "llvm/ADT/DenseMap.h"
21#include "llvm/ADT/FoldingSet.h"
22#include "llvm/Support/Casting.h"
23#include <cassert>
24#include <utility>
25
26namespace clang {
27
28class LocationContext;
29
30class ProgramPoint {
31public:
32  enum Kind { BlockEdgeKind,
33              BlockEntranceKind,
34              BlockExitKind,
35              PreStmtKind,
36              // Keep the following together and in this order.
37              PostStmtKind,
38              PostLocationChecksSucceedKind,
39              PostOutOfBoundsCheckFailedKind,
40              PostNullCheckFailedKind,
41              PostUndefLocationCheckFailedKind,
42              PostLoadKind,
43              PostStoreKind,
44              PostPurgeDeadSymbolsKind,
45              PostStmtCustomKind,
46              PostLValueKind,
47              MinPostStmtKind = PostStmtKind,
48              MaxPostStmtKind = PostLValueKind };
49
50private:
51  std::pair<const void *, const void *> Data;
52  Kind K;
53
54  // The LocationContext could be NULL to allow ProgramPoint to be used in
55  // context insensitive analysis.
56  const LocationContext *L;
57  const void *Tag;
58
59protected:
60  ProgramPoint(const void* P, Kind k, const LocationContext *l,
61               const void *tag = 0)
62    : Data(P, NULL), K(k), L(l), Tag(tag) {}
63
64  ProgramPoint(const void* P1, const void* P2, Kind k, const LocationContext *l,
65               const void *tag = 0)
66    : Data(P1, P2), K(k), L(l), Tag(tag) {}
67
68protected:
69  const void* getData1() const { return Data.first; }
70  const void* getData2() const { return Data.second; }
71  const void *getTag() const { return Tag; }
72
73public:
74  Kind getKind() const { return K; }
75
76  const LocationContext *getLocationContext() const { return L; }
77
78  // For use with DenseMap.  This hash is probably slow.
79  unsigned getHashValue() const {
80    llvm::FoldingSetNodeID ID;
81    Profile(ID);
82    return ID.ComputeHash();
83  }
84
85  static bool classof(const ProgramPoint*) { return true; }
86
87  bool operator==(const ProgramPoint & RHS) const {
88    return K == RHS.K && Data == RHS.Data && L == RHS.L && Tag == RHS.Tag;
89  }
90
91  bool operator!=(const ProgramPoint& RHS) const {
92    return K != RHS.K || Data != RHS.Data || L != RHS.L || Tag != RHS.Tag;
93  }
94
95  void Profile(llvm::FoldingSetNodeID& ID) const {
96    ID.AddInteger((unsigned) K);
97    ID.AddPointer(Data.first);
98    ID.AddPointer(Data.second);
99    ID.AddPointer(L);
100    ID.AddPointer(Tag);
101  }
102};
103
104class BlockEntrance : public ProgramPoint {
105public:
106  BlockEntrance(const CFGBlock* B, const LocationContext *L,
107                const void *tag = 0)
108    : ProgramPoint(B, BlockEntranceKind, L, tag) {}
109
110  CFGBlock* getBlock() const {
111    return const_cast<CFGBlock*>(reinterpret_cast<const CFGBlock*>(getData1()));
112  }
113
114  Stmt* getFirstStmt() const {
115    const CFGBlock* B = getBlock();
116    return B->empty() ? NULL : B->front();
117  }
118
119  static bool classof(const ProgramPoint* Location) {
120    return Location->getKind() == BlockEntranceKind;
121  }
122};
123
124class BlockExit : public ProgramPoint {
125public:
126  BlockExit(const CFGBlock* B, const LocationContext *L)
127    : ProgramPoint(B, BlockExitKind, L) {}
128
129  CFGBlock* getBlock() const {
130    return const_cast<CFGBlock*>(reinterpret_cast<const CFGBlock*>(getData1()));
131  }
132
133  Stmt* getLastStmt() const {
134    const CFGBlock* B = getBlock();
135    return B->empty() ? NULL : B->back();
136  }
137
138  Stmt* getTerminator() const {
139    return getBlock()->getTerminator();
140  }
141
142  static bool classof(const ProgramPoint* Location) {
143    return Location->getKind() == BlockExitKind;
144  }
145};
146
147class StmtPoint : public ProgramPoint {
148public:
149  StmtPoint(const Stmt *S, const void *p2, Kind k, const LocationContext *L,
150            const void *tag)
151    : ProgramPoint(S, p2, k, L, tag) {}
152
153  const Stmt *getStmt() const { return (const Stmt*) getData1(); }
154
155  template <typename T>
156  const T* getStmtAs() const { return llvm::dyn_cast<T>(getStmt()); }
157
158  static bool classof(const ProgramPoint* Location) {
159    unsigned k = Location->getKind();
160    return k >= PreStmtKind && k <= MaxPostStmtKind;
161  }
162};
163
164
165class PreStmt : public StmtPoint {
166public:
167  PreStmt(const Stmt *S, const LocationContext *L, const void *tag,
168          const Stmt *SubStmt = 0)
169    : StmtPoint(S, SubStmt, PreStmtKind, L, tag) {}
170
171  const Stmt *getSubStmt() const { return (const Stmt*) getData2(); }
172
173  static bool classof(const ProgramPoint* Location) {
174    return Location->getKind() == PreStmtKind;
175  }
176};
177
178class PostStmt : public StmtPoint {
179protected:
180  PostStmt(const Stmt* S, Kind k, const LocationContext *L, const void *tag = 0)
181    : StmtPoint(S, NULL, k, L, tag) {}
182
183  PostStmt(const Stmt* S, const void* data, Kind k, const LocationContext *L,
184           const void *tag =0)
185    : StmtPoint(S, data, k, L, tag) {}
186
187public:
188  explicit PostStmt(const Stmt* S, const LocationContext *L,const void *tag = 0)
189    : StmtPoint(S, NULL, PostStmtKind, L, tag) {}
190
191  static bool classof(const ProgramPoint* Location) {
192    unsigned k = Location->getKind();
193    return k >= MinPostStmtKind && k <= MaxPostStmtKind;
194  }
195};
196
197class PostLocationChecksSucceed : public PostStmt {
198public:
199  PostLocationChecksSucceed(const Stmt* S, const LocationContext *L,
200                            const void *tag = 0)
201    : PostStmt(S, PostLocationChecksSucceedKind, L, tag) {}
202
203  static bool classof(const ProgramPoint* Location) {
204    return Location->getKind() == PostLocationChecksSucceedKind;
205  }
206};
207
208class PostStmtCustom : public PostStmt {
209public:
210  PostStmtCustom(const Stmt* S,
211                 const std::pair<const void*, const void*>* TaggedData,\
212                 const LocationContext *L)
213    : PostStmt(S, TaggedData, PostStmtCustomKind, L) {}
214
215  const std::pair<const void*, const void*>& getTaggedPair() const {
216    return
217      *reinterpret_cast<const std::pair<const void*, const void*>*>(getData2());
218  }
219
220  const void* getTag() const { return getTaggedPair().first; }
221
222  const void* getTaggedData() const { return getTaggedPair().second; }
223
224  static bool classof(const ProgramPoint* Location) {
225    return Location->getKind() == PostStmtCustomKind;
226  }
227};
228
229class PostOutOfBoundsCheckFailed : public PostStmt {
230public:
231  PostOutOfBoundsCheckFailed(const Stmt* S, const LocationContext *L,
232                             const void *tag = 0)
233    : PostStmt(S, PostOutOfBoundsCheckFailedKind, L, tag) {}
234
235  static bool classof(const ProgramPoint* Location) {
236    return Location->getKind() == PostOutOfBoundsCheckFailedKind;
237  }
238};
239
240class PostUndefLocationCheckFailed : public PostStmt {
241public:
242  PostUndefLocationCheckFailed(const Stmt* S, const LocationContext *L,
243                               const void *tag = 0)
244    : PostStmt(S, PostUndefLocationCheckFailedKind, L, tag) {}
245
246  static bool classof(const ProgramPoint* Location) {
247    return Location->getKind() == PostUndefLocationCheckFailedKind;
248  }
249};
250
251class PostNullCheckFailed : public PostStmt {
252public:
253  PostNullCheckFailed(const Stmt* S, const LocationContext *L,
254                      const void *tag = 0)
255    : PostStmt(S, PostNullCheckFailedKind, L, tag) {}
256
257  static bool classof(const ProgramPoint* Location) {
258    return Location->getKind() == PostNullCheckFailedKind;
259  }
260};
261
262class PostLoad : public PostStmt {
263public:
264  PostLoad(const Stmt* S, const LocationContext *L, const void *tag = 0)
265    : PostStmt(S, PostLoadKind, L, tag) {}
266
267  static bool classof(const ProgramPoint* Location) {
268    return Location->getKind() == PostLoadKind;
269  }
270};
271
272class PostStore : public PostStmt {
273public:
274  PostStore(const Stmt* S, const LocationContext *L, const void *tag = 0)
275    : PostStmt(S, PostStoreKind, L, tag) {}
276
277  static bool classof(const ProgramPoint* Location) {
278    return Location->getKind() == PostStoreKind;
279  }
280};
281
282class PostLValue : public PostStmt {
283public:
284  PostLValue(const Stmt* S, const LocationContext *L, const void *tag = 0)
285    : PostStmt(S, PostLValueKind, L, tag) {}
286
287  static bool classof(const ProgramPoint* Location) {
288    return Location->getKind() == PostLValueKind;
289  }
290};
291
292class PostPurgeDeadSymbols : public PostStmt {
293public:
294  PostPurgeDeadSymbols(const Stmt* S, const LocationContext *L,
295                       const void *tag = 0)
296    : PostStmt(S, PostPurgeDeadSymbolsKind, L, tag) {}
297
298  static bool classof(const ProgramPoint* Location) {
299    return Location->getKind() == PostPurgeDeadSymbolsKind;
300  }
301};
302
303class BlockEdge : public ProgramPoint {
304public:
305  BlockEdge(const CFGBlock* B1, const CFGBlock* B2, const LocationContext *L)
306    : ProgramPoint(B1, B2, BlockEdgeKind, L) {}
307
308  CFGBlock* getSrc() const {
309    return const_cast<CFGBlock*>(static_cast<const CFGBlock*>(getData1()));
310  }
311
312  CFGBlock* getDst() const {
313    return const_cast<CFGBlock*>(static_cast<const CFGBlock*>(getData2()));
314  }
315
316  static bool classof(const ProgramPoint* Location) {
317    return Location->getKind() == BlockEdgeKind;
318  }
319};
320
321
322} // end namespace clang
323
324
325namespace llvm { // Traits specialization for DenseMap
326
327template <> struct DenseMapInfo<clang::ProgramPoint> {
328
329static inline clang::ProgramPoint getEmptyKey() {
330  uintptr_t x =
331   reinterpret_cast<uintptr_t>(DenseMapInfo<void*>::getEmptyKey()) & ~0x7;
332  return clang::BlockEntrance(reinterpret_cast<clang::CFGBlock*>(x), 0);
333}
334
335static inline clang::ProgramPoint getTombstoneKey() {
336  uintptr_t x =
337   reinterpret_cast<uintptr_t>(DenseMapInfo<void*>::getTombstoneKey()) & ~0x7;
338  return clang::BlockEntrance(reinterpret_cast<clang::CFGBlock*>(x), 0);
339}
340
341static unsigned getHashValue(const clang::ProgramPoint& Loc) {
342  return Loc.getHashValue();
343}
344
345static bool isEqual(const clang::ProgramPoint& L,
346                    const clang::ProgramPoint& R) {
347  return L == R;
348}
349
350static bool isPod() {
351  return true;
352}
353};
354} // end namespace llvm
355
356#endif
357