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