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