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