ProgramPoint.h revision a5fdd9ce694b1c2dbfd225cb6f55ef743d1ab562 
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/CFG.h"
19#include "llvm/System/DataTypes.h"
20#include "llvm/ADT/DenseMap.h"
21#include "llvm/ADT/FoldingSet.h"
22#include "llvm/Support/Casting.h"
23#include <cassert>
24#include <utility>
25
26namespace clang {
27
28class LocationContext;
29class FunctionDecl;
30
31class ProgramPoint {
32public:
33  enum Kind { BlockEdgeKind,
34              BlockEntranceKind,
35              BlockExitKind,
36              PreStmtKind,
37              PostStmtKind,
38              PreLoadKind,
39              PostLoadKind,
40              PreStoreKind,
41              PostStoreKind,
42              PostPurgeDeadSymbolsKind,
43              PostStmtCustomKind,
44              PostLValueKind,
45              CallEnterKind,
46              CallExitKind,
47              MinPostStmtKind = PostStmtKind,
48              MaxPostStmtKind = PostLValueKind };
49
50private:
51  std::pair<const void *, const void *> Data;
52  Kind K;
53
54  // The LocationContext could be NULL to allow ProgramPoint to be used in
55  // context insensitive analysis.
56  const LocationContext *L;
57  const void *Tag;
58
59protected:
60  ProgramPoint(const void* P, Kind k, const LocationContext *l,
61               const void *tag = 0)
62    : Data(P, static_cast<const void*>(NULL)), K(k), L(l), Tag(tag) {}
63
64  ProgramPoint(const void* P1, const void* P2, Kind k, const LocationContext *l,
65               const void *tag = 0)
66    : Data(P1, P2), K(k), L(l), Tag(tag) {}
67
68protected:
69  const void* getData1() const { return Data.first; }
70  const void* getData2() const { return Data.second; }
71  const void *getTag() const { return Tag; }
72
73public:
74  Kind getKind() const { return K; }
75
76  const LocationContext *getLocationContext() const { return L; }
77
78  // For use with DenseMap.  This hash is probably slow.
79  unsigned getHashValue() const {
80    llvm::FoldingSetNodeID ID;
81    Profile(ID);
82    return ID.ComputeHash();
83  }
84
85  static bool classof(const ProgramPoint*) { return true; }
86
87  bool operator==(const ProgramPoint & RHS) const {
88    return K == RHS.K && Data == RHS.Data && L == RHS.L && Tag == RHS.Tag;
89  }
90
91  bool operator!=(const ProgramPoint& RHS) const {
92    return K != RHS.K || Data != RHS.Data || L != RHS.L || Tag != RHS.Tag;
93  }
94
95  void Profile(llvm::FoldingSetNodeID& ID) const {
96    ID.AddInteger((unsigned) K);
97    ID.AddPointer(Data.first);
98    ID.AddPointer(Data.second);
99    ID.AddPointer(L);
100    ID.AddPointer(Tag);
101  }
102};
103
104class BlockEntrance : public ProgramPoint {
105public:
106  BlockEntrance(const CFGBlock* B, const LocationContext *L,
107                const void *tag = 0)
108    : ProgramPoint(B, BlockEntranceKind, L, tag) {}
109
110  CFGBlock* getBlock() const {
111    return const_cast<CFGBlock*>(reinterpret_cast<const CFGBlock*>(getData1()));
112  }
113
114  CFGElement getFirstElement() const {
115    const CFGBlock* B = getBlock();
116    return B->empty() ? CFGElement() : B->front();
117  }
118
119  Stmt *getFirstStmt() const {
120    return getFirstElement().getStmt();
121  }
122
123  static bool classof(const ProgramPoint* Location) {
124    return Location->getKind() == BlockEntranceKind;
125  }
126};
127
128class BlockExit : public ProgramPoint {
129public:
130  BlockExit(const CFGBlock* B, const LocationContext *L)
131    : ProgramPoint(B, BlockExitKind, L) {}
132
133  CFGBlock* getBlock() const {
134    return const_cast<CFGBlock*>(reinterpret_cast<const CFGBlock*>(getData1()));
135  }
136
137  Stmt* getLastStmt() const {
138    const CFGBlock* B = getBlock();
139    return B->empty() ? CFGElement() : B->back();
140  }
141
142  Stmt* getTerminator() const {
143    return getBlock()->getTerminator();
144  }
145
146  static bool classof(const ProgramPoint* Location) {
147    return Location->getKind() == BlockExitKind;
148  }
149};
150
151class StmtPoint : public ProgramPoint {
152public:
153  StmtPoint(const Stmt *S, const void *p2, Kind k, const LocationContext *L,
154            const void *tag)
155    : ProgramPoint(S, p2, k, L, tag) {}
156
157  const Stmt *getStmt() const { return (const Stmt*) getData1(); }
158
159  template <typename T>
160  const T* getStmtAs() const { return llvm::dyn_cast<T>(getStmt()); }
161
162  static bool classof(const ProgramPoint* Location) {
163    unsigned k = Location->getKind();
164    return k >= PreStmtKind && k <= MaxPostStmtKind;
165  }
166};
167
168
169class PreStmt : public StmtPoint {
170public:
171  PreStmt(const Stmt *S, const LocationContext *L, const void *tag,
172          const Stmt *SubStmt = 0)
173    : StmtPoint(S, SubStmt, PreStmtKind, L, tag) {}
174
175  const Stmt *getSubStmt() const { return (const Stmt*) getData2(); }
176
177  static bool classof(const ProgramPoint* Location) {
178    return Location->getKind() == PreStmtKind;
179  }
180};
181
182class PostStmt : public StmtPoint {
183protected:
184  PostStmt(const Stmt* S, Kind k, const LocationContext *L, const void *tag = 0)
185    : StmtPoint(S, NULL, k, L, tag) {}
186
187  PostStmt(const Stmt* S, const void* data, Kind k, const LocationContext *L,
188           const void *tag =0)
189    : StmtPoint(S, data, k, L, tag) {}
190
191public:
192  explicit PostStmt(const Stmt* S, const LocationContext *L,const void *tag = 0)
193    : StmtPoint(S, NULL, PostStmtKind, L, tag) {}
194
195  static bool classof(const ProgramPoint* Location) {
196    unsigned k = Location->getKind();
197    return k >= MinPostStmtKind && k <= MaxPostStmtKind;
198  }
199};
200
201class PostStmtCustom : public PostStmt {
202public:
203  PostStmtCustom(const Stmt* S,
204                 const std::pair<const void*, const void*>* TaggedData,\
205                 const LocationContext *L)
206    : PostStmt(S, TaggedData, PostStmtCustomKind, L) {}
207
208  const std::pair<const void*, const void*>& getTaggedPair() const {
209    return
210      *reinterpret_cast<const std::pair<const void*, const void*>*>(getData2());
211  }
212
213  const void* getTag() const { return getTaggedPair().first; }
214
215  const void* getTaggedData() const { return getTaggedPair().second; }
216
217  static bool classof(const ProgramPoint* Location) {
218    return Location->getKind() == PostStmtCustomKind;
219  }
220};
221
222
223class LocationCheck : public StmtPoint {
224protected:
225  LocationCheck(const Stmt *S, const LocationContext *L,
226                ProgramPoint::Kind K, const void *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, const void *tag = 0)
238    : LocationCheck(S, L, PreLoadKind, tag) {}
239
240  static bool classof(const ProgramPoint *location) {
241    return location->getKind() == PreLoadKind;
242  }
243};
244
245class PreStore : public LocationCheck {
246public:
247  PreStore(const Stmt *S, const LocationContext *L, const void *tag = 0)
248  : LocationCheck(S, L, PreStoreKind, tag) {}
249
250  static bool classof(const ProgramPoint *location) {
251    return location->getKind() == PreStoreKind;
252  }
253};
254
255class PostLoad : public PostStmt {
256public:
257  PostLoad(const Stmt* S, const LocationContext *L, const void *tag = 0)
258    : PostStmt(S, PostLoadKind, L, tag) {}
259
260  static bool classof(const ProgramPoint* Location) {
261    return Location->getKind() == PostLoadKind;
262  }
263};
264
265class PostStore : public PostStmt {
266public:
267  PostStore(const Stmt* S, const LocationContext *L, const void *tag = 0)
268    : PostStmt(S, PostStoreKind, L, tag) {}
269
270  static bool classof(const ProgramPoint* Location) {
271    return Location->getKind() == PostStoreKind;
272  }
273};
274
275class PostLValue : public PostStmt {
276public:
277  PostLValue(const Stmt* S, const LocationContext *L, const void *tag = 0)
278    : PostStmt(S, PostLValueKind, L, tag) {}
279
280  static bool classof(const ProgramPoint* Location) {
281    return Location->getKind() == PostLValueKind;
282  }
283};
284
285class PostPurgeDeadSymbols : public PostStmt {
286public:
287  PostPurgeDeadSymbols(const Stmt* S, const LocationContext *L,
288                       const void *tag = 0)
289    : PostStmt(S, PostPurgeDeadSymbolsKind, L, tag) {}
290
291  static bool classof(const ProgramPoint* Location) {
292    return Location->getKind() == PostPurgeDeadSymbolsKind;
293  }
294};
295
296class BlockEdge : public ProgramPoint {
297public:
298  BlockEdge(const CFGBlock* B1, const CFGBlock* B2, const LocationContext *L)
299    : ProgramPoint(B1, B2, BlockEdgeKind, L) {}
300
301  CFGBlock* getSrc() const {
302    return const_cast<CFGBlock*>(static_cast<const CFGBlock*>(getData1()));
303  }
304
305  CFGBlock* getDst() const {
306    return const_cast<CFGBlock*>(static_cast<const CFGBlock*>(getData2()));
307  }
308
309  static bool classof(const ProgramPoint* Location) {
310    return Location->getKind() == BlockEdgeKind;
311  }
312};
313
314class CallEnter : public StmtPoint {
315public:
316  // CallEnter uses the caller's location context.
317  CallEnter(const Stmt *S, const FunctionDecl *fd, const LocationContext *L)
318    : StmtPoint(S, fd, CallEnterKind, L, 0) {}
319
320  const Stmt *getCallExpr() const {
321    return static_cast<const Stmt *>(getData1());
322  }
323
324  const FunctionDecl *getCallee() const {
325    return static_cast<const FunctionDecl *>(getData2());
326  }
327
328  static bool classof(const ProgramPoint *Location) {
329    return Location->getKind() == CallEnterKind;
330  }
331};
332
333class CallExit : public StmtPoint {
334public:
335  // CallExit uses the callee's location context.
336  CallExit(const Stmt *S, const LocationContext *L)
337    : StmtPoint(S, 0, CallExitKind, L, 0) {}
338
339  static bool classof(const ProgramPoint *Location) {
340    return Location->getKind() == CallExitKind;
341  }
342};
343
344
345} // end namespace clang
346
347
348namespace llvm { // Traits specialization for DenseMap
349
350template <> struct DenseMapInfo<clang::ProgramPoint> {
351
352static inline clang::ProgramPoint getEmptyKey() {
353  uintptr_t x =
354   reinterpret_cast<uintptr_t>(DenseMapInfo<void*>::getEmptyKey()) & ~0x7;
355  return clang::BlockEntrance(reinterpret_cast<clang::CFGBlock*>(x), 0);
356}
357
358static inline clang::ProgramPoint getTombstoneKey() {
359  uintptr_t x =
360   reinterpret_cast<uintptr_t>(DenseMapInfo<void*>::getTombstoneKey()) & ~0x7;
361  return clang::BlockEntrance(reinterpret_cast<clang::CFGBlock*>(x), 0);
362}
363
364static unsigned getHashValue(const clang::ProgramPoint& Loc) {
365  return Loc.getHashValue();
366}
367
368static bool isEqual(const clang::ProgramPoint& L,
369                    const clang::ProgramPoint& R) {
370  return L == R;
371}
372
373};
374
375template <>
376struct isPodLike<clang::ProgramPoint> { static const bool value = true; };
377
378} // end namespace llvm
379
380#endif
381