ProgramPoint.h revision 424f67155475296804f9b9159dba606859441924 
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
24namespace clang {
25
26class ProgramPoint {
27public:
28  enum Kind { LayeredNodeKind  =  0x0,
29              BlockEntranceKind = 0x1,
30              PostStmtKind      = 0x2,
31              BlockExitKind     = 0x3,
32              BlockEdgeSrcKind  = 0x5, // Skip 0x4.
33              BlockEdgeDstKind  = 0x6,
34              BlockEdgeAuxKind  = 0x7 };
35protected:
36  uintptr_t Data;
37
38  ProgramPoint(const void* Ptr, Kind k) {
39    assert ((reinterpret_cast<uintptr_t>(const_cast<void*>(Ptr)) & 0x7) == 0
40            && "Address must have at least an 8-byte alignment.");
41
42    Data = reinterpret_cast<uintptr_t>(const_cast<void*>(Ptr)) | k;
43  }
44
45  ProgramPoint() : Data(0) {}
46
47public:
48
49  unsigned getKind() const {
50    unsigned x = Data & 0x7;
51    return x & 0x3 ? x : 0;  // Use only lower 2 bits for 0x0.
52  }
53
54  void* getRawPtr() const {
55    return (void*) (getKind() ? Data & ~0x7 : Data & ~0x3);
56  }
57
58  void* getRawData() const { return reinterpret_cast<void*>(Data); }
59
60  static bool classof(const ProgramPoint*) { return true; }
61  bool operator==(const ProgramPoint & RHS) const { return Data == RHS.Data; }
62  bool operator!=(const ProgramPoint& RHS) const { return Data != RHS.Data; }
63
64  void Profile(llvm::FoldingSetNodeID& ID) const {
65    ID.AddInteger(getKind());
66    ID.AddPointer(getRawPtr());
67  }
68};
69
70class ExplodedNodeImpl;
71template <typename StateTy> class ExplodedNode;
72
73class LayeredNode : public ProgramPoint {
74public:
75  LayeredNode(ExplodedNodeImpl* N) : ProgramPoint(N, LayeredNodeKind) {
76    assert (reinterpret_cast<uintptr_t>(N) & 0x3 == 0 &&
77            "Address of ExplodedNode must have 4-byte alignment.");
78  }
79
80  ExplodedNodeImpl* getNodeImpl() const {
81    return (ExplodedNodeImpl*) getRawPtr();
82  }
83
84  template <typename StateTy>
85  ExplodedNode<StateTy>* getNode() const {
86    return (ExplodedNode<StateTy>*) getRawPtr();
87  }
88
89};
90
91class BlockEntrance : public ProgramPoint {
92public:
93  BlockEntrance(const CFGBlock* B) : ProgramPoint(B, BlockEntranceKind) {}
94
95  CFGBlock* getBlock() const {
96    return reinterpret_cast<CFGBlock*>(getRawPtr());
97  }
98
99  Stmt* getFirstStmt() const {
100    CFGBlock* B = getBlock();
101    return B->empty() ? NULL : B->front();
102  }
103
104  static bool classof(const ProgramPoint* Location) {
105    return Location->getKind() == BlockEntranceKind;
106  }
107};
108
109class BlockExit : public ProgramPoint {
110public:
111  BlockExit(const CFGBlock* B) : ProgramPoint(B, BlockExitKind) {}
112
113  CFGBlock* getBlock() const {
114    return reinterpret_cast<CFGBlock*>(getRawPtr());
115  }
116
117  Stmt* getLastStmt() const {
118    CFGBlock* B = getBlock();
119    return B->empty() ? NULL : B->back();
120  }
121
122  Stmt* getTerminator() const {
123    return getBlock()->getTerminator();
124  }
125
126  static bool classof(const ProgramPoint* Location) {
127    return Location->getKind() == BlockExitKind;
128  }
129};
130
131
132class PostStmt : public ProgramPoint {
133public:
134  PostStmt(const Stmt* S) : ProgramPoint(S, PostStmtKind) {}
135
136  Stmt* getStmt() const { return (Stmt*) getRawPtr(); }
137
138  static bool classof(const ProgramPoint* Location) {
139    return Location->getKind() == PostStmtKind;
140  }
141};
142
143class BlockEdge : public ProgramPoint {
144  typedef std::pair<CFGBlock*,CFGBlock*> BPair;
145public:
146  BlockEdge(CFG& cfg, const CFGBlock* B1, const CFGBlock* B2);
147
148  /// This ctor forces the BlockEdge to be constructed using an explicitly
149  ///  allocated pair object that is stored in the CFG.  This is usually
150  ///  used to construct edges representing jumps using computed gotos.
151  BlockEdge(CFG& cfg, const CFGBlock* B1, const CFGBlock* B2, bool) {
152    Data = reinterpret_cast<uintptr_t>(cfg.getBlockEdgeImpl(B1, B2))
153           | BlockEdgeAuxKind;
154  }
155
156
157  CFGBlock* getSrc() const;
158  CFGBlock* getDst() const;
159
160  static bool classof(const ProgramPoint* Location) {
161    unsigned k = Location->getKind();
162    return k >= BlockEdgeSrcKind && k <= BlockEdgeAuxKind;
163  }
164};
165
166
167
168} // end namespace clang
169
170
171namespace llvm { // Traits specialization for DenseMap
172
173template <> struct DenseMapInfo<clang::ProgramPoint> {
174
175  static inline clang::ProgramPoint getEmptyKey() {
176    uintptr_t x =
177     reinterpret_cast<uintptr_t>(DenseMapInfo<void*>::getEmptyKey()) & ~0x7;
178
179    return clang::BlockEntrance(reinterpret_cast<clang::CFGBlock*>(x));
180  }
181
182  static inline clang::ProgramPoint getTombstoneKey() {
183    uintptr_t x =
184     reinterpret_cast<uintptr_t>(DenseMapInfo<void*>::getTombstoneKey()) & ~0x7;
185
186    return clang::BlockEntrance(reinterpret_cast<clang::CFGBlock*>(x));
187  }
188
189  static unsigned getHashValue(const clang::ProgramPoint& Loc) {
190    return DenseMapInfo<void*>::getHashValue(Loc.getRawData());
191  }
192
193  static bool isEqual(const clang::ProgramPoint& L,
194                      const clang::ProgramPoint& R) {
195    return L == R;
196  }
197
198  static bool isPod() {
199    return true;
200  }
201};
202} // end namespace llvm
203
204#endif
205