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