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