1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
|
//=== FlatStore.cpp - Flat region-based store model -------------*- C++ -*-===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
#include "clang/GR/PathSensitive/GRState.h"
#include "llvm/ADT/ImmutableIntervalMap.h"
#include "llvm/Support/ErrorHandling.h"
using namespace clang;
using llvm::Interval;
// The actual store type.
typedef llvm::ImmutableIntervalMap<SVal> BindingVal;
typedef llvm::ImmutableMap<const MemRegion *, BindingVal> RegionBindings;
namespace {
class FlatStoreManager : public StoreManager {
RegionBindings::Factory RBFactory;
BindingVal::Factory BVFactory;
public:
FlatStoreManager(GRStateManager &mgr)
: StoreManager(mgr),
RBFactory(mgr.getAllocator()),
BVFactory(mgr.getAllocator()) {}
SVal Retrieve(Store store, Loc L, QualType T);
Store Bind(Store store, Loc L, SVal val);
Store Remove(Store St, Loc L);
Store BindCompoundLiteral(Store store, const CompoundLiteralExpr* cl,
const LocationContext *LC, SVal v);
Store getInitialStore(const LocationContext *InitLoc) {
return RBFactory.getEmptyMap().getRoot();
}
SubRegionMap *getSubRegionMap(Store store) {
return 0;
}
SVal ArrayToPointer(Loc Array);
Store RemoveDeadBindings(Store store, const StackFrameContext *LCtx,
SymbolReaper& SymReaper,
llvm::SmallVectorImpl<const MemRegion*>& RegionRoots){
return store;
}
Store BindDecl(Store store, const VarRegion *VR, SVal initVal);
Store BindDeclWithNoInit(Store store, const VarRegion *VR);
typedef llvm::DenseSet<SymbolRef> InvalidatedSymbols;
Store InvalidateRegions(Store store, const MemRegion * const *I,
const MemRegion * const *E, const Expr *Ex,
unsigned Count, InvalidatedSymbols *IS,
bool invalidateGlobals, InvalidatedRegions *Regions);
void print(Store store, llvm::raw_ostream& Out, const char* nl,
const char *sep);
void iterBindings(Store store, BindingsHandler& f);
private:
static RegionBindings getRegionBindings(Store store) {
return RegionBindings(static_cast<const RegionBindings::TreeTy*>(store));
}
class RegionInterval {
public:
const MemRegion *R;
Interval I;
RegionInterval(const MemRegion *r, int64_t s, int64_t e) : R(r), I(s, e){}
};
RegionInterval RegionToInterval(const MemRegion *R);
SVal RetrieveRegionWithNoBinding(const MemRegion *R, QualType T);
};
} // end anonymous namespace
StoreManager *clang::CreateFlatStoreManager(GRStateManager &StMgr) {
return new FlatStoreManager(StMgr);
}
SVal FlatStoreManager::Retrieve(Store store, Loc L, QualType T) {
const MemRegion *R = cast<loc::MemRegionVal>(L).getRegion();
RegionInterval RI = RegionToInterval(R);
// FIXME: FlatStore should handle regions with unknown intervals.
if (!RI.R)
return UnknownVal();
RegionBindings B = getRegionBindings(store);
const BindingVal *BV = B.lookup(RI.R);
if (BV) {
const SVal *V = BVFactory.lookup(*BV, RI.I);
if (V)
return *V;
else
return RetrieveRegionWithNoBinding(R, T);
}
return RetrieveRegionWithNoBinding(R, T);
}
SVal FlatStoreManager::RetrieveRegionWithNoBinding(const MemRegion *R,
QualType T) {
if (R->hasStackNonParametersStorage())
return UndefinedVal();
else
return svalBuilder.getRegionValueSymbolVal(cast<TypedRegion>(R));
}
Store FlatStoreManager::Bind(Store store, Loc L, SVal val) {
const MemRegion *R = cast<loc::MemRegionVal>(L).getRegion();
RegionBindings B = getRegionBindings(store);
const BindingVal *V = B.lookup(R);
BindingVal BV = BVFactory.getEmptyMap();
if (V)
BV = *V;
RegionInterval RI = RegionToInterval(R);
// FIXME: FlatStore should handle regions with unknown intervals.
if (!RI.R)
return B.getRoot();
BV = BVFactory.add(BV, RI.I, val);
B = RBFactory.add(B, RI.R, BV);
return B.getRoot();
}
Store FlatStoreManager::Remove(Store store, Loc L) {
return store;
}
Store FlatStoreManager::BindCompoundLiteral(Store store,
const CompoundLiteralExpr* cl,
const LocationContext *LC,
SVal v) {
return store;
}
SVal FlatStoreManager::ArrayToPointer(Loc Array) {
return Array;
}
Store FlatStoreManager::BindDecl(Store store, const VarRegion *VR,
SVal initVal) {
return Bind(store, svalBuilder.makeLoc(VR), initVal);
}
Store FlatStoreManager::BindDeclWithNoInit(Store store, const VarRegion *VR) {
return store;
}
Store FlatStoreManager::InvalidateRegions(Store store,
const MemRegion * const *I,
const MemRegion * const *E,
const Expr *Ex, unsigned Count,
InvalidatedSymbols *IS,
bool invalidateGlobals,
InvalidatedRegions *Regions) {
assert(false && "Not implemented");
return store;
}
void FlatStoreManager::print(Store store, llvm::raw_ostream& Out,
const char* nl, const char *sep) {
}
void FlatStoreManager::iterBindings(Store store, BindingsHandler& f) {
}
FlatStoreManager::RegionInterval
FlatStoreManager::RegionToInterval(const MemRegion *R) {
switch (R->getKind()) {
case MemRegion::VarRegionKind: {
QualType T = cast<VarRegion>(R)->getValueType();
int64_t Size = Ctx.getTypeSize(T);
return RegionInterval(R, 0, Size-1);
}
case MemRegion::ElementRegionKind:
case MemRegion::FieldRegionKind: {
RegionOffset Offset = R->getAsOffset();
// We cannot compute offset for all regions, for example, elements
// with symbolic offsets.
if (!Offset.getRegion())
return RegionInterval(0, 0, 0);
int64_t Start = Offset.getOffset();
int64_t Size = Ctx.getTypeSize(cast<TypedRegion>(R)->getValueType());
return RegionInterval(Offset.getRegion(), Start, Start+Size);
}
default:
llvm_unreachable("Region kind unhandled.");
return RegionInterval(0, 0, 0);
}
}
|
