1 //===- BasicValueFactory.cpp - Basic values for Path Sens analysis --------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file defines BasicValueFactory, a class that manages the lifetime
10 // of APSInt objects and symbolic constraints used by ExprEngine
11 // and related classes.
12 //
13 //===----------------------------------------------------------------------===//
14
15 #include "clang/StaticAnalyzer/Core/PathSensitive/BasicValueFactory.h"
16 #include "clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h"
17 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
18 #include "clang/StaticAnalyzer/Core/PathSensitive/Store.h"
19 #include "clang/StaticAnalyzer/Core/PathSensitive/StoreRef.h"
20 #include "llvm/ADT/APSInt.h"
21 #include "llvm/ADT/FoldingSet.h"
22 #include "llvm/ADT/ImmutableList.h"
23 #include "llvm/ADT/STLExtras.h"
24 #include "llvm/ADT/SmallPtrSet.h"
25 #include <cassert>
26 #include <cstdint>
27 #include <utility>
28
29 using namespace clang;
30 using namespace ento;
31
Profile(llvm::FoldingSetNodeID & ID,QualType T,llvm::ImmutableList<SVal> L)32 void CompoundValData::Profile(llvm::FoldingSetNodeID& ID, QualType T,
33 llvm::ImmutableList<SVal> L) {
34 T.Profile(ID);
35 ID.AddPointer(L.getInternalPointer());
36 }
37
Profile(llvm::FoldingSetNodeID & ID,const StoreRef & store,const TypedValueRegion * region)38 void LazyCompoundValData::Profile(llvm::FoldingSetNodeID& ID,
39 const StoreRef &store,
40 const TypedValueRegion *region) {
41 ID.AddPointer(store.getStore());
42 ID.AddPointer(region);
43 }
44
Profile(llvm::FoldingSetNodeID & ID,const NamedDecl * D,llvm::ImmutableList<const CXXBaseSpecifier * > L)45 void PointerToMemberData::Profile(
46 llvm::FoldingSetNodeID &ID, const NamedDecl *D,
47 llvm::ImmutableList<const CXXBaseSpecifier *> L) {
48 ID.AddPointer(D);
49 ID.AddPointer(L.getInternalPointer());
50 }
51
52 using SValData = std::pair<SVal, uintptr_t>;
53 using SValPair = std::pair<SVal, SVal>;
54
55 namespace llvm {
56
57 template<> struct FoldingSetTrait<SValData> {
Profilellvm::FoldingSetTrait58 static inline void Profile(const SValData& X, llvm::FoldingSetNodeID& ID) {
59 X.first.Profile(ID);
60 ID.AddPointer( (void*) X.second);
61 }
62 };
63
64 template<> struct FoldingSetTrait<SValPair> {
Profilellvm::FoldingSetTrait65 static inline void Profile(const SValPair& X, llvm::FoldingSetNodeID& ID) {
66 X.first.Profile(ID);
67 X.second.Profile(ID);
68 }
69 };
70
71 } // namespace llvm
72
73 using PersistentSValsTy =
74 llvm::FoldingSet<llvm::FoldingSetNodeWrapper<SValData>>;
75
76 using PersistentSValPairsTy =
77 llvm::FoldingSet<llvm::FoldingSetNodeWrapper<SValPair>>;
78
~BasicValueFactory()79 BasicValueFactory::~BasicValueFactory() {
80 // Note that the dstor for the contents of APSIntSet will never be called,
81 // so we iterate over the set and invoke the dstor for each APSInt. This
82 // frees an aux. memory allocated to represent very large constants.
83 for (const auto &I : APSIntSet)
84 I.getValue().~APSInt();
85
86 delete (PersistentSValsTy*) PersistentSVals;
87 delete (PersistentSValPairsTy*) PersistentSValPairs;
88 }
89
getValue(const llvm::APSInt & X)90 const llvm::APSInt& BasicValueFactory::getValue(const llvm::APSInt& X) {
91 llvm::FoldingSetNodeID ID;
92 void *InsertPos;
93
94 using FoldNodeTy = llvm::FoldingSetNodeWrapper<llvm::APSInt>;
95
96 X.Profile(ID);
97 FoldNodeTy* P = APSIntSet.FindNodeOrInsertPos(ID, InsertPos);
98
99 if (!P) {
100 P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>();
101 new (P) FoldNodeTy(X);
102 APSIntSet.InsertNode(P, InsertPos);
103 }
104
105 return *P;
106 }
107
getValue(const llvm::APInt & X,bool isUnsigned)108 const llvm::APSInt& BasicValueFactory::getValue(const llvm::APInt& X,
109 bool isUnsigned) {
110 llvm::APSInt V(X, isUnsigned);
111 return getValue(V);
112 }
113
getValue(uint64_t X,unsigned BitWidth,bool isUnsigned)114 const llvm::APSInt& BasicValueFactory::getValue(uint64_t X, unsigned BitWidth,
115 bool isUnsigned) {
116 llvm::APSInt V(BitWidth, isUnsigned);
117 V = X;
118 return getValue(V);
119 }
120
getValue(uint64_t X,QualType T)121 const llvm::APSInt& BasicValueFactory::getValue(uint64_t X, QualType T) {
122 return getValue(getAPSIntType(T).getValue(X));
123 }
124
125 const CompoundValData*
getCompoundValData(QualType T,llvm::ImmutableList<SVal> Vals)126 BasicValueFactory::getCompoundValData(QualType T,
127 llvm::ImmutableList<SVal> Vals) {
128 llvm::FoldingSetNodeID ID;
129 CompoundValData::Profile(ID, T, Vals);
130 void *InsertPos;
131
132 CompoundValData* D = CompoundValDataSet.FindNodeOrInsertPos(ID, InsertPos);
133
134 if (!D) {
135 D = (CompoundValData*) BPAlloc.Allocate<CompoundValData>();
136 new (D) CompoundValData(T, Vals);
137 CompoundValDataSet.InsertNode(D, InsertPos);
138 }
139
140 return D;
141 }
142
143 const LazyCompoundValData*
getLazyCompoundValData(const StoreRef & store,const TypedValueRegion * region)144 BasicValueFactory::getLazyCompoundValData(const StoreRef &store,
145 const TypedValueRegion *region) {
146 llvm::FoldingSetNodeID ID;
147 LazyCompoundValData::Profile(ID, store, region);
148 void *InsertPos;
149
150 LazyCompoundValData *D =
151 LazyCompoundValDataSet.FindNodeOrInsertPos(ID, InsertPos);
152
153 if (!D) {
154 D = (LazyCompoundValData*) BPAlloc.Allocate<LazyCompoundValData>();
155 new (D) LazyCompoundValData(store, region);
156 LazyCompoundValDataSet.InsertNode(D, InsertPos);
157 }
158
159 return D;
160 }
161
getPointerToMemberData(const NamedDecl * ND,llvm::ImmutableList<const CXXBaseSpecifier * > L)162 const PointerToMemberData *BasicValueFactory::getPointerToMemberData(
163 const NamedDecl *ND, llvm::ImmutableList<const CXXBaseSpecifier *> L) {
164 llvm::FoldingSetNodeID ID;
165 PointerToMemberData::Profile(ID, ND, L);
166 void *InsertPos;
167
168 PointerToMemberData *D =
169 PointerToMemberDataSet.FindNodeOrInsertPos(ID, InsertPos);
170
171 if (!D) {
172 D = (PointerToMemberData *)BPAlloc.Allocate<PointerToMemberData>();
173 new (D) PointerToMemberData(ND, L);
174 PointerToMemberDataSet.InsertNode(D, InsertPos);
175 }
176
177 return D;
178 }
179
hasNoRepeatedElements(llvm::ImmutableList<const CXXBaseSpecifier * > BaseSpecList)180 LLVM_ATTRIBUTE_UNUSED bool hasNoRepeatedElements(
181 llvm::ImmutableList<const CXXBaseSpecifier *> BaseSpecList) {
182 llvm::SmallPtrSet<QualType, 16> BaseSpecSeen;
183 for (const CXXBaseSpecifier *BaseSpec : BaseSpecList) {
184 QualType BaseType = BaseSpec->getType();
185 // Check whether inserted
186 if (!BaseSpecSeen.insert(BaseType).second)
187 return false;
188 }
189 return true;
190 }
191
accumCXXBase(llvm::iterator_range<CastExpr::path_const_iterator> PathRange,const nonloc::PointerToMember & PTM,const CastKind & kind)192 const PointerToMemberData *BasicValueFactory::accumCXXBase(
193 llvm::iterator_range<CastExpr::path_const_iterator> PathRange,
194 const nonloc::PointerToMember &PTM, const CastKind &kind) {
195 assert((kind == CK_DerivedToBaseMemberPointer ||
196 kind == CK_BaseToDerivedMemberPointer ||
197 kind == CK_ReinterpretMemberPointer) &&
198 "accumCXXBase called with wrong CastKind");
199 nonloc::PointerToMember::PTMDataType PTMDT = PTM.getPTMData();
200 const NamedDecl *ND = nullptr;
201 llvm::ImmutableList<const CXXBaseSpecifier *> BaseSpecList;
202
203 if (PTMDT.isNull() || PTMDT.is<const NamedDecl *>()) {
204 if (PTMDT.is<const NamedDecl *>())
205 ND = PTMDT.get<const NamedDecl *>();
206
207 BaseSpecList = CXXBaseListFactory.getEmptyList();
208 } else {
209 const PointerToMemberData *PTMD = PTMDT.get<const PointerToMemberData *>();
210 ND = PTMD->getDeclaratorDecl();
211
212 BaseSpecList = PTMD->getCXXBaseList();
213 }
214
215 assert(hasNoRepeatedElements(BaseSpecList) &&
216 "CXXBaseSpecifier list of PointerToMemberData must not have repeated "
217 "elements");
218
219 if (kind == CK_DerivedToBaseMemberPointer) {
220 // Here we pop off matching CXXBaseSpecifiers from BaseSpecList.
221 // Because, CK_DerivedToBaseMemberPointer comes from a static_cast and
222 // serves to remove a matching implicit cast. Note that static_cast's that
223 // are no-ops do not count since they produce an empty PathRange, a nice
224 // thing about Clang AST.
225
226 // Now we know that there are no repetitions in BaseSpecList.
227 // So, popping the first element from it corresponding to each element in
228 // PathRange is equivalent to only including elements that are in
229 // BaseSpecList but not it PathRange
230 auto ReducedBaseSpecList = CXXBaseListFactory.getEmptyList();
231 for (const CXXBaseSpecifier *BaseSpec : BaseSpecList) {
232 auto IsSameAsBaseSpec = [&BaseSpec](const CXXBaseSpecifier *I) -> bool {
233 return BaseSpec->getType() == I->getType();
234 };
235 if (llvm::none_of(PathRange, IsSameAsBaseSpec))
236 ReducedBaseSpecList =
237 CXXBaseListFactory.add(BaseSpec, ReducedBaseSpecList);
238 }
239
240 return getPointerToMemberData(ND, ReducedBaseSpecList);
241 }
242 // FIXME: Reinterpret casts on member-pointers are not handled properly by
243 // this code
244 for (const CXXBaseSpecifier *I : llvm::reverse(PathRange))
245 BaseSpecList = prependCXXBase(I, BaseSpecList);
246 return getPointerToMemberData(ND, BaseSpecList);
247 }
248
249 const llvm::APSInt*
evalAPSInt(BinaryOperator::Opcode Op,const llvm::APSInt & V1,const llvm::APSInt & V2)250 BasicValueFactory::evalAPSInt(BinaryOperator::Opcode Op,
251 const llvm::APSInt& V1, const llvm::APSInt& V2) {
252 switch (Op) {
253 default:
254 llvm_unreachable("Invalid Opcode.");
255
256 case BO_Mul:
257 return &getValue( V1 * V2 );
258
259 case BO_Div:
260 if (V2 == 0) // Avoid division by zero
261 return nullptr;
262 return &getValue( V1 / V2 );
263
264 case BO_Rem:
265 if (V2 == 0) // Avoid division by zero
266 return nullptr;
267 return &getValue( V1 % V2 );
268
269 case BO_Add:
270 return &getValue( V1 + V2 );
271
272 case BO_Sub:
273 return &getValue( V1 - V2 );
274
275 case BO_Shl: {
276 // FIXME: This logic should probably go higher up, where we can
277 // test these conditions symbolically.
278
279 if (V2.isSigned() && V2.isNegative())
280 return nullptr;
281
282 uint64_t Amt = V2.getZExtValue();
283
284 if (Amt >= V1.getBitWidth())
285 return nullptr;
286
287 if (!Ctx.getLangOpts().CPlusPlus20) {
288 if (V1.isSigned() && V1.isNegative())
289 return nullptr;
290
291 if (V1.isSigned() && Amt > V1.countLeadingZeros())
292 return nullptr;
293 }
294
295 return &getValue( V1.operator<<( (unsigned) Amt ));
296 }
297
298 case BO_Shr: {
299 // FIXME: This logic should probably go higher up, where we can
300 // test these conditions symbolically.
301
302 if (V2.isSigned() && V2.isNegative())
303 return nullptr;
304
305 uint64_t Amt = V2.getZExtValue();
306
307 if (Amt >= V1.getBitWidth())
308 return nullptr;
309
310 return &getValue( V1.operator>>( (unsigned) Amt ));
311 }
312
313 case BO_LT:
314 return &getTruthValue( V1 < V2 );
315
316 case BO_GT:
317 return &getTruthValue( V1 > V2 );
318
319 case BO_LE:
320 return &getTruthValue( V1 <= V2 );
321
322 case BO_GE:
323 return &getTruthValue( V1 >= V2 );
324
325 case BO_EQ:
326 return &getTruthValue( V1 == V2 );
327
328 case BO_NE:
329 return &getTruthValue( V1 != V2 );
330
331 // Note: LAnd, LOr, Comma are handled specially by higher-level logic.
332
333 case BO_And:
334 return &getValue( V1 & V2 );
335
336 case BO_Or:
337 return &getValue( V1 | V2 );
338
339 case BO_Xor:
340 return &getValue( V1 ^ V2 );
341 }
342 }
343
344 const std::pair<SVal, uintptr_t>&
getPersistentSValWithData(const SVal & V,uintptr_t Data)345 BasicValueFactory::getPersistentSValWithData(const SVal& V, uintptr_t Data) {
346 // Lazily create the folding set.
347 if (!PersistentSVals) PersistentSVals = new PersistentSValsTy();
348
349 llvm::FoldingSetNodeID ID;
350 void *InsertPos;
351 V.Profile(ID);
352 ID.AddPointer((void*) Data);
353
354 PersistentSValsTy& Map = *((PersistentSValsTy*) PersistentSVals);
355
356 using FoldNodeTy = llvm::FoldingSetNodeWrapper<SValData>;
357
358 FoldNodeTy* P = Map.FindNodeOrInsertPos(ID, InsertPos);
359
360 if (!P) {
361 P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>();
362 new (P) FoldNodeTy(std::make_pair(V, Data));
363 Map.InsertNode(P, InsertPos);
364 }
365
366 return P->getValue();
367 }
368
369 const std::pair<SVal, SVal>&
getPersistentSValPair(const SVal & V1,const SVal & V2)370 BasicValueFactory::getPersistentSValPair(const SVal& V1, const SVal& V2) {
371 // Lazily create the folding set.
372 if (!PersistentSValPairs) PersistentSValPairs = new PersistentSValPairsTy();
373
374 llvm::FoldingSetNodeID ID;
375 void *InsertPos;
376 V1.Profile(ID);
377 V2.Profile(ID);
378
379 PersistentSValPairsTy& Map = *((PersistentSValPairsTy*) PersistentSValPairs);
380
381 using FoldNodeTy = llvm::FoldingSetNodeWrapper<SValPair>;
382
383 FoldNodeTy* P = Map.FindNodeOrInsertPos(ID, InsertPos);
384
385 if (!P) {
386 P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>();
387 new (P) FoldNodeTy(std::make_pair(V1, V2));
388 Map.InsertNode(P, InsertPos);
389 }
390
391 return P->getValue();
392 }
393
getPersistentSVal(SVal X)394 const SVal* BasicValueFactory::getPersistentSVal(SVal X) {
395 return &getPersistentSValWithData(X, 0).first;
396 }
397