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