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