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