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