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