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