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