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