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