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
29using namespace clang;
30using namespace ento;
31
32void CompoundValData::Profile(llvm::FoldingSetNodeID& ID, QualType T,
33 llvm::ImmutableList<SVal> L) {
34 T.Profile(ID);
35 ID.AddPointer(Ptr: L.getInternalPointer());
36}
37
38void LazyCompoundValData::Profile(llvm::FoldingSetNodeID& ID,
39 const StoreRef &store,
40 const TypedValueRegion *region) {
41 ID.AddPointer(Ptr: store.getStore());
42 ID.AddPointer(Ptr: region);
43}
44
45void PointerToMemberData::Profile(
46 llvm::FoldingSetNodeID &ID, const NamedDecl *D,
47 llvm::ImmutableList<const CXXBaseSpecifier *> L) {
48 ID.AddPointer(Ptr: D);
49 ID.AddPointer(Ptr: L.getInternalPointer());
50}
51
52using SValData = std::pair<SVal, uintptr_t>;
53using SValPair = std::pair<SVal, SVal>;
54
55namespace llvm {
56
57template<> struct FoldingSetTrait<SValData> {
58 static inline void Profile(const SValData& X, llvm::FoldingSetNodeID& ID) {
59 X.first.Profile(ID);
60 ID.AddPointer( Ptr: (void*) X.second);
61 }
62};
63
64template<> struct FoldingSetTrait<SValPair> {
65 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
73using PersistentSValsTy =
74 llvm::FoldingSet<llvm::FoldingSetNodeWrapper<SValData>>;
75
76using PersistentSValPairsTy =
77 llvm::FoldingSet<llvm::FoldingSetNodeWrapper<SValPair>>;
78
79BasicValueFactory::~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
90APSIntPtr 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 = new (BPAlloc) FoldNodeTy(X);
101 APSIntSet.InsertNode(N: P, InsertPos);
102 }
103
104 // We own the APSInt object. It's safe here.
105 return APSIntPtr::unsafeConstructor(Ptr: &P->getValue());
106}
107
108APSIntPtr BasicValueFactory::getValue(const llvm::APInt &X, bool isUnsigned) {
109 llvm::APSInt V(X, isUnsigned);
110 return getValue(X: V);
111}
112
113APSIntPtr BasicValueFactory::getValue(uint64_t X, unsigned BitWidth,
114 bool isUnsigned) {
115 llvm::APSInt V(BitWidth, isUnsigned);
116 V = X;
117 return getValue(X: V);
118}
119
120APSIntPtr BasicValueFactory::getValue(uint64_t X, QualType T) {
121 return getValue(X: getAPSIntType(T).getValue(RawValue: X));
122}
123
124const CompoundValData*
125BasicValueFactory::getCompoundValData(QualType T,
126 llvm::ImmutableList<SVal> Vals) {
127 llvm::FoldingSetNodeID ID;
128 CompoundValData::Profile(ID, T, L: Vals);
129 void *InsertPos;
130
131 CompoundValData* D = CompoundValDataSet.FindNodeOrInsertPos(ID, InsertPos);
132
133 if (!D) {
134 D = new (BPAlloc) CompoundValData(T, Vals);
135 CompoundValDataSet.InsertNode(N: D, InsertPos);
136 }
137
138 return D;
139}
140
141const LazyCompoundValData*
142BasicValueFactory::getLazyCompoundValData(const StoreRef &store,
143 const TypedValueRegion *region) {
144 llvm::FoldingSetNodeID ID;
145 LazyCompoundValData::Profile(ID, store, region);
146 void *InsertPos;
147
148 LazyCompoundValData *D =
149 LazyCompoundValDataSet.FindNodeOrInsertPos(ID, InsertPos);
150
151 if (!D) {
152 D = new (BPAlloc) LazyCompoundValData(store, region);
153 LazyCompoundValDataSet.InsertNode(N: D, InsertPos);
154 }
155
156 return D;
157}
158
159const PointerToMemberData *BasicValueFactory::getPointerToMemberData(
160 const NamedDecl *ND, llvm::ImmutableList<const CXXBaseSpecifier *> L) {
161 llvm::FoldingSetNodeID ID;
162 PointerToMemberData::Profile(ID, D: ND, L);
163 void *InsertPos;
164
165 PointerToMemberData *D =
166 PointerToMemberDataSet.FindNodeOrInsertPos(ID, InsertPos);
167
168 if (!D) {
169 D = new (BPAlloc) PointerToMemberData(ND, L);
170 PointerToMemberDataSet.InsertNode(N: D, InsertPos);
171 }
172
173 return D;
174}
175
176LLVM_ATTRIBUTE_UNUSED static bool hasNoRepeatedElements(
177 llvm::ImmutableList<const CXXBaseSpecifier *> BaseSpecList) {
178 llvm::SmallPtrSet<QualType, 16> BaseSpecSeen;
179 for (const CXXBaseSpecifier *BaseSpec : BaseSpecList) {
180 QualType BaseType = BaseSpec->getType();
181 // Check whether inserted
182 if (!BaseSpecSeen.insert(Ptr: BaseType).second)
183 return false;
184 }
185 return true;
186}
187
188const PointerToMemberData *BasicValueFactory::accumCXXBase(
189 llvm::iterator_range<CastExpr::path_const_iterator> PathRange,
190 const nonloc::PointerToMember &PTM, const CastKind &kind) {
191 assert((kind == CK_DerivedToBaseMemberPointer ||
192 kind == CK_BaseToDerivedMemberPointer ||
193 kind == CK_ReinterpretMemberPointer) &&
194 "accumCXXBase called with wrong CastKind");
195 nonloc::PointerToMember::PTMDataType PTMDT = PTM.getPTMData();
196 const NamedDecl *ND = nullptr;
197 llvm::ImmutableList<const CXXBaseSpecifier *> BaseSpecList;
198
199 if (PTMDT.isNull() || isa<const NamedDecl *>(Val: PTMDT)) {
200 if (const auto *NDP = dyn_cast_if_present<const NamedDecl *>(Val&: PTMDT))
201 ND = NDP;
202
203 BaseSpecList = CXXBaseListFactory.getEmptyList();
204 } else {
205 const auto *PTMD = cast<const PointerToMemberData *>(Val&: PTMDT);
206 ND = PTMD->getDeclaratorDecl();
207
208 BaseSpecList = PTMD->getCXXBaseList();
209 }
210
211 assert(hasNoRepeatedElements(BaseSpecList) &&
212 "CXXBaseSpecifier list of PointerToMemberData must not have repeated "
213 "elements");
214
215 if (kind == CK_DerivedToBaseMemberPointer) {
216 // Here we pop off matching CXXBaseSpecifiers from BaseSpecList.
217 // Because, CK_DerivedToBaseMemberPointer comes from a static_cast and
218 // serves to remove a matching implicit cast. Note that static_cast's that
219 // are no-ops do not count since they produce an empty PathRange, a nice
220 // thing about Clang AST.
221
222 // Now we know that there are no repetitions in BaseSpecList.
223 // So, popping the first element from it corresponding to each element in
224 // PathRange is equivalent to only including elements that are in
225 // BaseSpecList but not it PathRange
226 auto ReducedBaseSpecList = CXXBaseListFactory.getEmptyList();
227 for (const CXXBaseSpecifier *BaseSpec : BaseSpecList) {
228 auto IsSameAsBaseSpec = [&BaseSpec](const CXXBaseSpecifier *I) -> bool {
229 return BaseSpec->getType() == I->getType();
230 };
231 if (llvm::none_of(Range&: PathRange, P: IsSameAsBaseSpec))
232 ReducedBaseSpecList =
233 CXXBaseListFactory.add(Data&: BaseSpec, L: ReducedBaseSpecList);
234 }
235
236 return getPointerToMemberData(ND, L: ReducedBaseSpecList);
237 }
238 // FIXME: Reinterpret casts on member-pointers are not handled properly by
239 // this code
240 for (const CXXBaseSpecifier *I : llvm::reverse(C&: PathRange))
241 BaseSpecList = prependCXXBase(CBS: I, L: BaseSpecList);
242 return getPointerToMemberData(ND, L: BaseSpecList);
243}
244
245std::optional<APSIntPtr>
246BasicValueFactory::evalAPSInt(BinaryOperator::Opcode Op, const llvm::APSInt &V1,
247 const llvm::APSInt &V2) {
248 switch (Op) {
249 default:
250 llvm_unreachable("Invalid Opcode.");
251
252 case BO_Mul:
253 return getValue(X: V1 * V2);
254
255 case BO_Div:
256 if (V2 == 0) // Avoid division by zero
257 return std::nullopt;
258 return getValue(X: V1 / V2);
259
260 case BO_Rem:
261 if (V2 == 0) // Avoid division by zero
262 return std::nullopt;
263 return getValue(X: V1 % V2);
264
265 case BO_Add:
266 return getValue(X: V1 + V2);
267
268 case BO_Sub:
269 return getValue(X: V1 - V2);
270
271 case BO_Shl: {
272 // FIXME: This logic should probably go higher up, where we can
273 // test these conditions symbolically.
274
275 if (V2.isNegative() || V2.getBitWidth() > 64)
276 return std::nullopt;
277
278 uint64_t Amt = V2.getZExtValue();
279
280 if (Amt >= V1.getBitWidth())
281 return std::nullopt;
282
283 return getValue(X: V1.operator<<(Bits: (unsigned)Amt));
284 }
285
286 case BO_Shr: {
287 // FIXME: This logic should probably go higher up, where we can
288 // test these conditions symbolically.
289
290 if (V2.isNegative() || V2.getBitWidth() > 64)
291 return std::nullopt;
292
293 uint64_t Amt = V2.getZExtValue();
294
295 if (Amt >= V1.getBitWidth())
296 return std::nullopt;
297
298 return getValue(X: V1.operator>>(Amt: (unsigned)Amt));
299 }
300
301 case BO_LT:
302 return getTruthValue(b: V1 < V2);
303
304 case BO_GT:
305 return getTruthValue(b: V1 > V2);
306
307 case BO_LE:
308 return getTruthValue(b: V1 <= V2);
309
310 case BO_GE:
311 return getTruthValue(b: V1 >= V2);
312
313 case BO_EQ:
314 return getTruthValue(b: V1 == V2);
315
316 case BO_NE:
317 return getTruthValue(b: V1 != V2);
318
319 // Note: LAnd, LOr, Comma are handled specially by higher-level logic.
320
321 case BO_And:
322 return getValue(X: V1 & V2);
323
324 case BO_Or:
325 return getValue(X: V1 | V2);
326
327 case BO_Xor:
328 return getValue(X: V1 ^ V2);
329 }
330}
331
332const std::pair<SVal, uintptr_t>&
333BasicValueFactory::getPersistentSValWithData(const SVal& V, uintptr_t Data) {
334 // Lazily create the folding set.
335 if (!PersistentSVals) PersistentSVals = new PersistentSValsTy();
336
337 llvm::FoldingSetNodeID ID;
338 void *InsertPos;
339 V.Profile(ID);
340 ID.AddPointer(Ptr: (void*) Data);
341
342 PersistentSValsTy& Map = *((PersistentSValsTy*) PersistentSVals);
343
344 using FoldNodeTy = llvm::FoldingSetNodeWrapper<SValData>;
345
346 FoldNodeTy* P = Map.FindNodeOrInsertPos(ID, InsertPos);
347
348 if (!P) {
349 P = new (BPAlloc) FoldNodeTy(std::make_pair(x: V, y&: Data));
350 Map.InsertNode(N: P, InsertPos);
351 }
352
353 return P->getValue();
354}
355
356const std::pair<SVal, SVal>&
357BasicValueFactory::getPersistentSValPair(const SVal& V1, const SVal& V2) {
358 // Lazily create the folding set.
359 if (!PersistentSValPairs) PersistentSValPairs = new PersistentSValPairsTy();
360
361 llvm::FoldingSetNodeID ID;
362 void *InsertPos;
363 V1.Profile(ID);
364 V2.Profile(ID);
365
366 PersistentSValPairsTy& Map = *((PersistentSValPairsTy*) PersistentSValPairs);
367
368 using FoldNodeTy = llvm::FoldingSetNodeWrapper<SValPair>;
369
370 FoldNodeTy* P = Map.FindNodeOrInsertPos(ID, InsertPos);
371
372 if (!P) {
373 P = new (BPAlloc) FoldNodeTy(std::make_pair(x: V1, y: V2));
374 Map.InsertNode(N: P, InsertPos);
375 }
376
377 return P->getValue();
378}
379
380const SVal* BasicValueFactory::getPersistentSVal(SVal X) {
381 return &getPersistentSValWithData(V: X, Data: 0).first;
382}
383