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
176[[maybe_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> BasicValueFactory::evalAPSInt(UnaryOperator::Opcode Op,
246 const llvm::APSInt &V1) {
247 switch (Op) {
248 default:
249 assert(false && "Invalid Opcode.");
250 return std::nullopt;
251
252 case UO_Minus:
253 return getValue(X: -V1);
254
255 case UO_Not:
256 return getValue(X: ~V1);
257 }
258}
259
260std::optional<APSIntPtr>
261BasicValueFactory::evalAPSInt(BinaryOperator::Opcode Op, const llvm::APSInt &V1,
262 const llvm::APSInt &V2) {
263 switch (Op) {
264 default:
265 assert(false && "Invalid Opcode.");
266 return std::nullopt;
267
268 case BO_Mul:
269 return getValue(X: V1 * V2);
270
271 case BO_Div:
272 if (V2 == 0) // Avoid division by zero
273 return std::nullopt;
274 return getValue(X: V1 / V2);
275
276 case BO_Rem:
277 if (V2 == 0) // Avoid division by zero
278 return std::nullopt;
279 return getValue(X: V1 % V2);
280
281 case BO_Add:
282 return getValue(X: V1 + V2);
283
284 case BO_Sub:
285 return getValue(X: V1 - V2);
286
287 case BO_Shl: {
288 // FIXME: This logic should probably go higher up, where we can
289 // test these conditions symbolically.
290
291 if (V2.isNegative() || V2.getBitWidth() > 64)
292 return std::nullopt;
293
294 uint64_t Amt = V2.getZExtValue();
295
296 if (Amt >= V1.getBitWidth())
297 return std::nullopt;
298
299 return getValue(X: V1.operator<<(Bits: (unsigned)Amt));
300 }
301
302 case BO_Shr: {
303 // FIXME: This logic should probably go higher up, where we can
304 // test these conditions symbolically.
305
306 if (V2.isNegative() || V2.getBitWidth() > 64)
307 return std::nullopt;
308
309 uint64_t Amt = V2.getZExtValue();
310
311 if (Amt >= V1.getBitWidth())
312 return std::nullopt;
313
314 return getValue(X: V1.operator>>(Amt: (unsigned)Amt));
315 }
316
317 case BO_LT:
318 return getTruthValue(b: V1 < V2);
319
320 case BO_GT:
321 return getTruthValue(b: V1 > V2);
322
323 case BO_LE:
324 return getTruthValue(b: V1 <= V2);
325
326 case BO_GE:
327 return getTruthValue(b: V1 >= V2);
328
329 case BO_EQ:
330 return getTruthValue(b: V1 == V2);
331
332 case BO_NE:
333 return getTruthValue(b: V1 != V2);
334
335 // Note: LAnd, LOr, Comma are handled specially by higher-level logic.
336
337 case BO_And:
338 return getValue(X: V1 & V2);
339
340 case BO_Or:
341 return getValue(X: V1 | V2);
342
343 case BO_Xor:
344 return getValue(X: V1 ^ V2);
345 }
346}
347
348const std::pair<SVal, uintptr_t>&
349BasicValueFactory::getPersistentSValWithData(const SVal& V, uintptr_t Data) {
350 // Lazily create the folding set.
351 if (!PersistentSVals) PersistentSVals = new PersistentSValsTy();
352
353 llvm::FoldingSetNodeID ID;
354 void *InsertPos;
355 V.Profile(ID);
356 ID.AddPointer(Ptr: (void*) Data);
357
358 PersistentSValsTy& Map = *((PersistentSValsTy*) PersistentSVals);
359
360 using FoldNodeTy = llvm::FoldingSetNodeWrapper<SValData>;
361
362 FoldNodeTy* P = Map.FindNodeOrInsertPos(ID, InsertPos);
363
364 if (!P) {
365 P = new (BPAlloc) FoldNodeTy(std::make_pair(x: V, y&: Data));
366 Map.InsertNode(N: P, InsertPos);
367 }
368
369 return P->getValue();
370}
371
372const std::pair<SVal, SVal>&
373BasicValueFactory::getPersistentSValPair(const SVal& V1, const SVal& V2) {
374 // Lazily create the folding set.
375 if (!PersistentSValPairs) PersistentSValPairs = new PersistentSValPairsTy();
376
377 llvm::FoldingSetNodeID ID;
378 void *InsertPos;
379 V1.Profile(ID);
380 V2.Profile(ID);
381
382 PersistentSValPairsTy& Map = *((PersistentSValPairsTy*) PersistentSValPairs);
383
384 using FoldNodeTy = llvm::FoldingSetNodeWrapper<SValPair>;
385
386 FoldNodeTy* P = Map.FindNodeOrInsertPos(ID, InsertPos);
387
388 if (!P) {
389 P = new (BPAlloc) FoldNodeTy(std::make_pair(x: V1, y: V2));
390 Map.InsertNode(N: P, InsertPos);
391 }
392
393 return P->getValue();
394}
395
396const SVal* BasicValueFactory::getPersistentSVal(SVal X) {
397 return &getPersistentSValWithData(V: X, Data: 0).first;
398}
399