ProgramPoint.h revision ab422d17dce198f2af9851340ea7384771a2a8c5 
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/AST/CFG.h"
19#include "llvm/Support/DataTypes.h"
20#include "llvm/ADT/DenseMap.h"
21#include "llvm/ADT/FoldingSet.h"
22#include <cassert>
23#include <utility>
24
25namespace clang {
26
27class ProgramPoint {
28public:
29  enum Kind { BlockEdgeKind = 0x0,
30              BlockEntranceKind = 0x1,
31              BlockExitKind = 0x2,
32              // Keep the following four together and in this order.
33              PostStmtKind = 0x3,
34              PostLocationChecksSucceedKind = 0x4,
35              PostOutOfBoundsCheckFailedKind = 0x5,
36              PostNullCheckFailedKind = 0x6,
37              PostUndefLocationCheckFailedKind = 0x7,
38              PostLoadKind = 0x8,
39              PostStoreKind = 0x9,
40              PostPurgeDeadSymbolsKind = 0x10,
41              PostStmtCustomKind = 0x11,
42              PostLValueKind = 0x12,
43              MinPostStmtKind = PostStmtKind,
44              MaxPostStmtKind = PostLValueKind };
45
46private:
47  enum { TwoPointers = 0x1, Custom = 0x2, Mask = 0x3 };
48
49  std::pair<uintptr_t,uintptr_t> Data;
50  const void *Tag;
51
52protected:
53  ProgramPoint(const void* P, Kind k, const void *tag = 0)
54    : Data(reinterpret_cast<uintptr_t>(P),
55           (uintptr_t) k), Tag(tag) {}
56
57  ProgramPoint(const void* P1, const void* P2, const void *tag = 0)
58    : Data(reinterpret_cast<uintptr_t>(P1) | TwoPointers,
59           reinterpret_cast<uintptr_t>(P2)), Tag(tag) {}
60
61  ProgramPoint(const void* P1, const void* P2, bool, const void *tag = 0)
62    : Data(reinterpret_cast<uintptr_t>(P1) | Custom,
63           reinterpret_cast<uintptr_t>(P2)), Tag(tag) {}
64
65protected:
66  void* getData1NoMask() const {
67    Kind k = getKind(); k = k;
68    assert(k == BlockEntranceKind || k == BlockExitKind);
69    return reinterpret_cast<void*>(Data.first);
70  }
71
72  void* getData1() const {
73    Kind k = getKind(); k = k;
74    assert(k == BlockEdgeKind ||(k >= MinPostStmtKind && k <= MaxPostStmtKind));
75    return reinterpret_cast<void*>(Data.first & ~Mask);
76  }
77
78  void* getData2() const {
79    Kind k = getKind(); k = k;
80    assert(k == BlockEdgeKind || k == PostStmtCustomKind);
81    return reinterpret_cast<void*>(Data.second);
82  }
83
84  const void *getTag() const { return Tag; }
85
86public:
87  Kind getKind() const {
88    switch (Data.first & Mask) {
89      case TwoPointers: return BlockEdgeKind;
90      case Custom: return PostStmtCustomKind;
91      default: return (Kind) Data.second;
92    }
93  }
94
95  // For use with DenseMap.  This hash is probably slow.
96  unsigned getHashValue() const {
97    llvm::FoldingSetNodeID ID;
98    ID.AddPointer(reinterpret_cast<void*>(Data.first));
99    ID.AddPointer(reinterpret_cast<void*>(Data.second));
100    ID.AddPointer(Tag);
101    return ID.ComputeHash();
102  }
103
104  static bool classof(const ProgramPoint*) { return true; }
105
106  bool operator==(const ProgramPoint & RHS) const {
107    return Data == RHS.Data && Tag == RHS.Tag;
108  }
109
110  bool operator!=(const ProgramPoint& RHS) const {
111    return Data != RHS.Data || Tag != RHS.Tag;
112  }
113
114  bool operator<(const ProgramPoint& RHS) const {
115    return Data < RHS.Data && Tag < RHS.Tag;
116  }
117
118  void Profile(llvm::FoldingSetNodeID& ID) const {
119    ID.AddPointer(reinterpret_cast<void*>(Data.first));
120    if (getKind() != PostStmtCustomKind)
121      ID.AddPointer(reinterpret_cast<void*>(Data.second));
122    else {
123      const std::pair<const void*, const void*> *P =
124        reinterpret_cast<std::pair<const void*, const void*>*>(Data.second);
125      ID.AddPointer(P->first);
126      ID.AddPointer(P->second);
127    }
128    ID.AddPointer(Tag);
129  }
130};
131
132class BlockEntrance : public ProgramPoint {
133public:
134  BlockEntrance(const CFGBlock* B, const void *tag = 0)
135    : ProgramPoint(B, BlockEntranceKind, tag) {}
136
137  CFGBlock* getBlock() const {
138    return reinterpret_cast<CFGBlock*>(getData1NoMask());
139  }
140
141  Stmt* getFirstStmt() const {
142    CFGBlock* B = getBlock();
143    return B->empty() ? NULL : B->front();
144  }
145
146  static bool classof(const ProgramPoint* Location) {
147    return Location->getKind() == BlockEntranceKind;
148  }
149};
150
151class BlockExit : public ProgramPoint {
152public:
153  BlockExit(const CFGBlock* B) : ProgramPoint(B, BlockExitKind) {}
154
155  CFGBlock* getBlock() const {
156    return reinterpret_cast<CFGBlock*>(getData1NoMask());
157  }
158
159  Stmt* getLastStmt() const {
160    CFGBlock* B = getBlock();
161    return B->empty() ? NULL : B->back();
162  }
163
164  Stmt* getTerminator() const {
165    return getBlock()->getTerminator();
166  }
167
168  static bool classof(const ProgramPoint* Location) {
169    return Location->getKind() == BlockExitKind;
170  }
171};
172
173class PostStmt : public ProgramPoint {
174protected:
175  PostStmt(const Stmt* S, Kind k,const void *tag = 0)
176    : ProgramPoint(S, k, tag) {}
177
178  PostStmt(const Stmt* S, const void* data, bool, const void *tag =0)
179    : ProgramPoint(S, data, true, tag) {}
180
181public:
182  PostStmt(const Stmt* S, const void *tag = 0)
183    : ProgramPoint(S, PostStmtKind, tag) {}
184
185
186  Stmt* getStmt() const { return (Stmt*) getData1(); }
187
188  static bool classof(const ProgramPoint* Location) {
189    unsigned k = Location->getKind();
190    return k >= MinPostStmtKind && k <= MaxPostStmtKind;
191  }
192};
193
194class PostLocationChecksSucceed : public PostStmt {
195public:
196  PostLocationChecksSucceed(const Stmt* S, const void *tag = 0)
197    : PostStmt(S, PostLocationChecksSucceedKind, tag) {}
198
199  static bool classof(const ProgramPoint* Location) {
200    return Location->getKind() == PostLocationChecksSucceedKind;
201  }
202};
203
204class PostStmtCustom : public PostStmt {
205public:
206  PostStmtCustom(const Stmt* S,
207                 const std::pair<const void*, const void*>* TaggedData)
208    : PostStmt(S, TaggedData, true) {
209    assert(getKind() == PostStmtCustomKind);
210  }
211
212  const std::pair<const void*, const void*>& getTaggedPair() const {
213    return *reinterpret_cast<std::pair<const void*, const void*>*>(getData2());
214  }
215
216  const void* getTag() const { return getTaggedPair().first; }
217
218  const void* getTaggedData() const { return getTaggedPair().second; }
219
220  static bool classof(const ProgramPoint* Location) {
221    return Location->getKind() == PostStmtCustomKind;
222  }
223};
224
225class PostOutOfBoundsCheckFailed : public PostStmt {
226public:
227  PostOutOfBoundsCheckFailed(const Stmt* S, const void *tag = 0)
228  : PostStmt(S, PostOutOfBoundsCheckFailedKind, tag) {}
229
230  static bool classof(const ProgramPoint* Location) {
231    return Location->getKind() == PostOutOfBoundsCheckFailedKind;
232  }
233};
234
235class PostUndefLocationCheckFailed : public PostStmt {
236public:
237  PostUndefLocationCheckFailed(const Stmt* S, const void *tag = 0)
238  : PostStmt(S, PostUndefLocationCheckFailedKind, tag) {}
239
240  static bool classof(const ProgramPoint* Location) {
241    return Location->getKind() == PostUndefLocationCheckFailedKind;
242  }
243};
244
245class PostNullCheckFailed : public PostStmt {
246public:
247  PostNullCheckFailed(const Stmt* S, const void *tag = 0)
248  : PostStmt(S, PostNullCheckFailedKind, tag) {}
249
250  static bool classof(const ProgramPoint* Location) {
251    return Location->getKind() == PostNullCheckFailedKind;
252  }
253};
254
255class PostLoad : public PostStmt {
256public:
257  PostLoad(const Stmt* S, const void *tag = 0)
258    : PostStmt(S, PostLoadKind, 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 void *tag = 0)
268    : PostStmt(S, PostStoreKind, 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 void *tag = 0)
278  : PostStmt(S, PostLValueKind, 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 void *tag = 0)
288    : PostStmt(S, PostPurgeDeadSymbolsKind, tag) {}
289
290  static bool classof(const ProgramPoint* Location) {
291    return Location->getKind() == PostPurgeDeadSymbolsKind;
292  }
293};
294
295class BlockEdge : public ProgramPoint {
296public:
297  BlockEdge(const CFGBlock* B1, const CFGBlock* B2)
298    : ProgramPoint(B1, B2) {}
299
300  CFGBlock* getSrc() const {
301    return static_cast<CFGBlock*>(getData1());
302  }
303
304  CFGBlock* getDst() const {
305    return static_cast<CFGBlock*>(getData2());
306  }
307
308  static bool classof(const ProgramPoint* Location) {
309    return Location->getKind() == BlockEdgeKind;
310  }
311};
312
313
314} // end namespace clang
315
316
317namespace llvm { // Traits specialization for DenseMap
318
319template <> struct DenseMapInfo<clang::ProgramPoint> {
320
321static inline clang::ProgramPoint getEmptyKey() {
322  uintptr_t x =
323   reinterpret_cast<uintptr_t>(DenseMapInfo<void*>::getEmptyKey()) & ~0x7;
324  return clang::BlockEntrance(reinterpret_cast<clang::CFGBlock*>(x));
325}
326
327static inline clang::ProgramPoint getTombstoneKey() {
328  uintptr_t x =
329   reinterpret_cast<uintptr_t>(DenseMapInfo<void*>::getTombstoneKey()) & ~0x7;
330  return clang::BlockEntrance(reinterpret_cast<clang::CFGBlock*>(x));
331}
332
333static unsigned getHashValue(const clang::ProgramPoint& Loc) {
334  return Loc.getHashValue();
335}
336
337static bool isEqual(const clang::ProgramPoint& L,
338                    const clang::ProgramPoint& R) {
339  return L == R;
340}
341
342static bool isPod() {
343  return true;
344}
345};
346} // end namespace llvm
347
348#endif
349