1 //=== BasicValueFactory.cpp - Basic values for Path Sens 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 BasicValueFactory, a class that manages the lifetime
11 // of APSInt objects and symbolic constraints used by ExprEngine
12 // and related classes.
13 //
14 //===----------------------------------------------------------------------===//
15
16 #include "clang/StaticAnalyzer/Core/PathSensitive/BasicValueFactory.h"
17 #include "clang/StaticAnalyzer/Core/PathSensitive/Store.h"
18
19 using namespace clang;
20 using namespace ento;
21
Profile(llvm::FoldingSetNodeID & ID,QualType T,llvm::ImmutableList<SVal> L)22 void CompoundValData::Profile(llvm::FoldingSetNodeID& ID, QualType T,
23 llvm::ImmutableList<SVal> L) {
24 T.Profile(ID);
25 ID.AddPointer(L.getInternalPointer());
26 }
27
Profile(llvm::FoldingSetNodeID & ID,const StoreRef & store,const TypedValueRegion * region)28 void LazyCompoundValData::Profile(llvm::FoldingSetNodeID& ID,
29 const StoreRef &store,
30 const TypedValueRegion *region) {
31 ID.AddPointer(store.getStore());
32 ID.AddPointer(region);
33 }
34
35 typedef std::pair<SVal, uintptr_t> SValData;
36 typedef std::pair<SVal, SVal> SValPair;
37
38 namespace llvm {
39 template<> struct FoldingSetTrait<SValData> {
Profilellvm::FoldingSetTrait40 static inline void Profile(const SValData& X, llvm::FoldingSetNodeID& ID) {
41 X.first.Profile(ID);
42 ID.AddPointer( (void*) X.second);
43 }
44 };
45
46 template<> struct FoldingSetTrait<SValPair> {
Profilellvm::FoldingSetTrait47 static inline void Profile(const SValPair& X, llvm::FoldingSetNodeID& ID) {
48 X.first.Profile(ID);
49 X.second.Profile(ID);
50 }
51 };
52 }
53
54 typedef llvm::FoldingSet<llvm::FoldingSetNodeWrapper<SValData> >
55 PersistentSValsTy;
56
57 typedef llvm::FoldingSet<llvm::FoldingSetNodeWrapper<SValPair> >
58 PersistentSValPairsTy;
59
~BasicValueFactory()60 BasicValueFactory::~BasicValueFactory() {
61 // Note that the dstor for the contents of APSIntSet will never be called,
62 // so we iterate over the set and invoke the dstor for each APSInt. This
63 // frees an aux. memory allocated to represent very large constants.
64 for (APSIntSetTy::iterator I=APSIntSet.begin(), E=APSIntSet.end(); I!=E; ++I)
65 I->getValue().~APSInt();
66
67 delete (PersistentSValsTy*) PersistentSVals;
68 delete (PersistentSValPairsTy*) PersistentSValPairs;
69 }
70
getValue(const llvm::APSInt & X)71 const llvm::APSInt& BasicValueFactory::getValue(const llvm::APSInt& X) {
72 llvm::FoldingSetNodeID ID;
73 void *InsertPos;
74 typedef llvm::FoldingSetNodeWrapper<llvm::APSInt> FoldNodeTy;
75
76 X.Profile(ID);
77 FoldNodeTy* P = APSIntSet.FindNodeOrInsertPos(ID, InsertPos);
78
79 if (!P) {
80 P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>();
81 new (P) FoldNodeTy(X);
82 APSIntSet.InsertNode(P, InsertPos);
83 }
84
85 return *P;
86 }
87
getValue(const llvm::APInt & X,bool isUnsigned)88 const llvm::APSInt& BasicValueFactory::getValue(const llvm::APInt& X,
89 bool isUnsigned) {
90 llvm::APSInt V(X, isUnsigned);
91 return getValue(V);
92 }
93
getValue(uint64_t X,unsigned BitWidth,bool isUnsigned)94 const llvm::APSInt& BasicValueFactory::getValue(uint64_t X, unsigned BitWidth,
95 bool isUnsigned) {
96 llvm::APSInt V(BitWidth, isUnsigned);
97 V = X;
98 return getValue(V);
99 }
100
getValue(uint64_t X,QualType T)101 const llvm::APSInt& BasicValueFactory::getValue(uint64_t X, QualType T) {
102
103 unsigned bits = Ctx.getTypeSize(T);
104 llvm::APSInt V(bits,
105 T->isUnsignedIntegerOrEnumerationType() || Loc::isLocType(T));
106 V = X;
107 return getValue(V);
108 }
109
110 const CompoundValData*
getCompoundValData(QualType T,llvm::ImmutableList<SVal> Vals)111 BasicValueFactory::getCompoundValData(QualType T,
112 llvm::ImmutableList<SVal> Vals) {
113
114 llvm::FoldingSetNodeID ID;
115 CompoundValData::Profile(ID, T, Vals);
116 void *InsertPos;
117
118 CompoundValData* D = CompoundValDataSet.FindNodeOrInsertPos(ID, InsertPos);
119
120 if (!D) {
121 D = (CompoundValData*) BPAlloc.Allocate<CompoundValData>();
122 new (D) CompoundValData(T, Vals);
123 CompoundValDataSet.InsertNode(D, InsertPos);
124 }
125
126 return D;
127 }
128
129 const LazyCompoundValData*
getLazyCompoundValData(const StoreRef & store,const TypedValueRegion * region)130 BasicValueFactory::getLazyCompoundValData(const StoreRef &store,
131 const TypedValueRegion *region) {
132 llvm::FoldingSetNodeID ID;
133 LazyCompoundValData::Profile(ID, store, region);
134 void *InsertPos;
135
136 LazyCompoundValData *D =
137 LazyCompoundValDataSet.FindNodeOrInsertPos(ID, InsertPos);
138
139 if (!D) {
140 D = (LazyCompoundValData*) BPAlloc.Allocate<LazyCompoundValData>();
141 new (D) LazyCompoundValData(store, region);
142 LazyCompoundValDataSet.InsertNode(D, InsertPos);
143 }
144
145 return D;
146 }
147
148 const llvm::APSInt*
evalAPSInt(BinaryOperator::Opcode Op,const llvm::APSInt & V1,const llvm::APSInt & V2)149 BasicValueFactory::evalAPSInt(BinaryOperator::Opcode Op,
150 const llvm::APSInt& V1, const llvm::APSInt& V2) {
151
152 switch (Op) {
153 default:
154 assert (false && "Invalid Opcode.");
155
156 case BO_Mul:
157 return &getValue( V1 * V2 );
158
159 case BO_Div:
160 return &getValue( V1 / V2 );
161
162 case BO_Rem:
163 return &getValue( V1 % V2 );
164
165 case BO_Add:
166 return &getValue( V1 + V2 );
167
168 case BO_Sub:
169 return &getValue( V1 - V2 );
170
171 case BO_Shl: {
172
173 // FIXME: This logic should probably go higher up, where we can
174 // test these conditions symbolically.
175
176 // FIXME: Expand these checks to include all undefined behavior.
177
178 if (V2.isSigned() && V2.isNegative())
179 return NULL;
180
181 uint64_t Amt = V2.getZExtValue();
182
183 if (Amt > V1.getBitWidth())
184 return NULL;
185
186 return &getValue( V1.operator<<( (unsigned) Amt ));
187 }
188
189 case BO_Shr: {
190
191 // FIXME: This logic should probably go higher up, where we can
192 // test these conditions symbolically.
193
194 // FIXME: Expand these checks to include all undefined behavior.
195
196 if (V2.isSigned() && V2.isNegative())
197 return NULL;
198
199 uint64_t Amt = V2.getZExtValue();
200
201 if (Amt > V1.getBitWidth())
202 return NULL;
203
204 return &getValue( V1.operator>>( (unsigned) Amt ));
205 }
206
207 case BO_LT:
208 return &getTruthValue( V1 < V2 );
209
210 case BO_GT:
211 return &getTruthValue( V1 > V2 );
212
213 case BO_LE:
214 return &getTruthValue( V1 <= V2 );
215
216 case BO_GE:
217 return &getTruthValue( V1 >= V2 );
218
219 case BO_EQ:
220 return &getTruthValue( V1 == V2 );
221
222 case BO_NE:
223 return &getTruthValue( V1 != V2 );
224
225 // Note: LAnd, LOr, Comma are handled specially by higher-level logic.
226
227 case BO_And:
228 return &getValue( V1 & V2 );
229
230 case BO_Or:
231 return &getValue( V1 | V2 );
232
233 case BO_Xor:
234 return &getValue( V1 ^ V2 );
235 }
236 }
237
238
239 const std::pair<SVal, uintptr_t>&
getPersistentSValWithData(const SVal & V,uintptr_t Data)240 BasicValueFactory::getPersistentSValWithData(const SVal& V, uintptr_t Data) {
241
242 // Lazily create the folding set.
243 if (!PersistentSVals) PersistentSVals = new PersistentSValsTy();
244
245 llvm::FoldingSetNodeID ID;
246 void *InsertPos;
247 V.Profile(ID);
248 ID.AddPointer((void*) Data);
249
250 PersistentSValsTy& Map = *((PersistentSValsTy*) PersistentSVals);
251
252 typedef llvm::FoldingSetNodeWrapper<SValData> FoldNodeTy;
253 FoldNodeTy* P = Map.FindNodeOrInsertPos(ID, InsertPos);
254
255 if (!P) {
256 P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>();
257 new (P) FoldNodeTy(std::make_pair(V, Data));
258 Map.InsertNode(P, InsertPos);
259 }
260
261 return P->getValue();
262 }
263
264 const std::pair<SVal, SVal>&
getPersistentSValPair(const SVal & V1,const SVal & V2)265 BasicValueFactory::getPersistentSValPair(const SVal& V1, const SVal& V2) {
266
267 // Lazily create the folding set.
268 if (!PersistentSValPairs) PersistentSValPairs = new PersistentSValPairsTy();
269
270 llvm::FoldingSetNodeID ID;
271 void *InsertPos;
272 V1.Profile(ID);
273 V2.Profile(ID);
274
275 PersistentSValPairsTy& Map = *((PersistentSValPairsTy*) PersistentSValPairs);
276
277 typedef llvm::FoldingSetNodeWrapper<SValPair> FoldNodeTy;
278 FoldNodeTy* P = Map.FindNodeOrInsertPos(ID, InsertPos);
279
280 if (!P) {
281 P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>();
282 new (P) FoldNodeTy(std::make_pair(V1, V2));
283 Map.InsertNode(P, InsertPos);
284 }
285
286 return P->getValue();
287 }
288
getPersistentSVal(SVal X)289 const SVal* BasicValueFactory::getPersistentSVal(SVal X) {
290 return &getPersistentSValWithData(X, 0).first;
291 }
292