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