clang 20.0.0git
BasicValueFactory.cpp
Go to the documentation of this file.
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
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(L.getInternalPointer());
36}
37
38void LazyCompoundValData::Profile(llvm::FoldingSetNodeID& ID,
39 const StoreRef &store,
40 const TypedValueRegion *region) {
41 ID.AddPointer(store.getStore());
42 ID.AddPointer(region);
43}
44
46 llvm::FoldingSetNodeID &ID, const NamedDecl *D,
47 llvm::ImmutableList<const CXXBaseSpecifier *> L) {
48 ID.AddPointer(D);
49 ID.AddPointer(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( (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
74 llvm::FoldingSet<llvm::FoldingSetNodeWrapper<SValData>>;
75
77 llvm::FoldingSet<llvm::FoldingSetNodeWrapper<SValPair>>;
78
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
90const 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 = new (BPAlloc) FoldNodeTy(X);
101 APSIntSet.InsertNode(P, InsertPos);
102 }
103
104 return *P;
105}
106
107const llvm::APSInt& BasicValueFactory::getValue(const llvm::APInt& X,
108 bool isUnsigned) {
109 llvm::APSInt V(X, isUnsigned);
110 return getValue(V);
111}
112
113const llvm::APSInt& BasicValueFactory::getValue(uint64_t X, unsigned BitWidth,
114 bool isUnsigned) {
115 llvm::APSInt V(BitWidth, isUnsigned);
116 V = X;
117 return getValue(V);
118}
119
120const llvm::APSInt& BasicValueFactory::getValue(uint64_t X, QualType T) {
121 return getValue(getAPSIntType(T).getValue(X));
122}
123
124const CompoundValData*
126 llvm::ImmutableList<SVal> Vals) {
127 llvm::FoldingSetNodeID ID;
128 CompoundValData::Profile(ID, T, 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(D, InsertPos);
136 }
137
138 return D;
139}
140
143 const TypedValueRegion *region) {
144 llvm::FoldingSetNodeID ID;
145 LazyCompoundValData::Profile(ID, store, region);
146 void *InsertPos;
147
149 LazyCompoundValDataSet.FindNodeOrInsertPos(ID, InsertPos);
150
151 if (!D) {
152 D = new (BPAlloc) LazyCompoundValData(store, region);
153 LazyCompoundValDataSet.InsertNode(D, InsertPos);
154 }
155
156 return D;
157}
158
160 const NamedDecl *ND, llvm::ImmutableList<const CXXBaseSpecifier *> L) {
161 llvm::FoldingSetNodeID ID;
163 void *InsertPos;
164
166 PointerToMemberDataSet.FindNodeOrInsertPos(ID, InsertPos);
167
168 if (!D) {
169 D = new (BPAlloc) PointerToMemberData(ND, L);
170 PointerToMemberDataSet.InsertNode(D, InsertPos);
171 }
172
173 return D;
174}
175
176LLVM_ATTRIBUTE_UNUSED bool hasNoRepeatedElements(
177 llvm::ImmutableList<const CXXBaseSpecifier *> BaseSpecList) {
179 for (const CXXBaseSpecifier *BaseSpec : BaseSpecList) {
180 QualType BaseType = BaseSpec->getType();
181 // Check whether inserted
182 if (!BaseSpecSeen.insert(BaseType).second)
183 return false;
184 }
185 return true;
186}
187
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");
196 const NamedDecl *ND = nullptr;
197 llvm::ImmutableList<const CXXBaseSpecifier *> BaseSpecList;
198
199 if (PTMDT.isNull() || PTMDT.is<const NamedDecl *>()) {
200 if (PTMDT.is<const NamedDecl *>())
201 ND = PTMDT.get<const NamedDecl *>();
202
203 BaseSpecList = CXXBaseListFactory.getEmptyList();
204 } else {
205 const PointerToMemberData *PTMD = PTMDT.get<const PointerToMemberData *>();
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(PathRange, IsSameAsBaseSpec))
232 ReducedBaseSpecList =
233 CXXBaseListFactory.add(BaseSpec, ReducedBaseSpecList);
234 }
235
236 return getPointerToMemberData(ND, ReducedBaseSpecList);
237 }
238 // FIXME: Reinterpret casts on member-pointers are not handled properly by
239 // this code
240 for (const CXXBaseSpecifier *I : llvm::reverse(PathRange))
241 BaseSpecList = prependCXXBase(I, BaseSpecList);
242 return getPointerToMemberData(ND, BaseSpecList);
243}
244
245const llvm::APSInt*
247 const llvm::APSInt& V1, const llvm::APSInt& V2) {
248 switch (Op) {
249 default:
250 llvm_unreachable("Invalid Opcode.");
251
252 case BO_Mul:
253 return &getValue( V1 * V2 );
254
255 case BO_Div:
256 if (V2 == 0) // Avoid division by zero
257 return nullptr;
258 return &getValue( V1 / V2 );
259
260 case BO_Rem:
261 if (V2 == 0) // Avoid division by zero
262 return nullptr;
263 return &getValue( V1 % V2 );
264
265 case BO_Add:
266 return &getValue( V1 + V2 );
267
268 case BO_Sub:
269 return &getValue( 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 nullptr;
277
278 uint64_t Amt = V2.getZExtValue();
279
280 if (Amt >= V1.getBitWidth())
281 return nullptr;
282
283 return &getValue( V1.operator<<( (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 nullptr;
292
293 uint64_t Amt = V2.getZExtValue();
294
295 if (Amt >= V1.getBitWidth())
296 return nullptr;
297
298 return &getValue( V1.operator>>( (unsigned) Amt ));
299 }
300
301 case BO_LT:
302 return &getTruthValue( V1 < V2 );
303
304 case BO_GT:
305 return &getTruthValue( V1 > V2 );
306
307 case BO_LE:
308 return &getTruthValue( V1 <= V2 );
309
310 case BO_GE:
311 return &getTruthValue( V1 >= V2 );
312
313 case BO_EQ:
314 return &getTruthValue( V1 == V2 );
315
316 case BO_NE:
317 return &getTruthValue( V1 != V2 );
318
319 // Note: LAnd, LOr, Comma are handled specially by higher-level logic.
320
321 case BO_And:
322 return &getValue( V1 & V2 );
323
324 case BO_Or:
325 return &getValue( V1 | V2 );
326
327 case BO_Xor:
328 return &getValue( V1 ^ V2 );
329 }
330}
331
332const std::pair<SVal, uintptr_t>&
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((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(V, Data));
350 Map.InsertNode(P, InsertPos);
351 }
352
353 return P->getValue();
354}
355
356const std::pair<SVal, SVal>&
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(V1, V2));
374 Map.InsertNode(P, InsertPos);
375 }
376
377 return P->getValue();
378}
379
381 return &getPersistentSValWithData(X, 0).first;
382}
#define V(N, I)
Definition: ASTContext.h:3341
StringRef P
static char ID
Definition: Arena.cpp:183
static bool isUnsigned(SValBuilder &SVB, NonLoc Value)
std::pair< SVal, SVal > SValPair
llvm::FoldingSet< llvm::FoldingSetNodeWrapper< SValData > > PersistentSValsTy
llvm::FoldingSet< llvm::FoldingSetNodeWrapper< SValPair > > PersistentSValPairsTy
std::pair< SVal, uintptr_t > SValData
LLVM_ATTRIBUTE_UNUSED bool hasNoRepeatedElements(llvm::ImmutableList< const CXXBaseSpecifier * > BaseSpecList)
const Decl * D
#define X(type, name)
Definition: Value.h:143
Represents a base class of a C++ class.
Definition: DeclCXX.h:146
void Profile(llvm::FoldingSetNodeID &ID, const ASTContext &Ctx)
Definition: Type.cpp:3822
This represents a decl that may have a name.
Definition: Decl.h:249
A (possibly-)qualified type.
Definition: Type.h:941
const CompoundValData * getCompoundValData(QualType T, llvm::ImmutableList< SVal > Vals)
const std::pair< SVal, SVal > & getPersistentSValPair(const SVal &V1, const SVal &V2)
const SVal * getPersistentSVal(SVal X)
const llvm::APSInt & getTruthValue(bool b, QualType T)
const std::pair< SVal, uintptr_t > & getPersistentSValWithData(const SVal &V, uintptr_t Data)
const llvm::APSInt * evalAPSInt(BinaryOperator::Opcode Op, const llvm::APSInt &V1, const llvm::APSInt &V2)
APSIntType getAPSIntType(QualType T) const
Returns the type of the APSInt used to store values of the given QualType.
const PointerToMemberData * getPointerToMemberData(const NamedDecl *ND, llvm::ImmutableList< const CXXBaseSpecifier * > L)
llvm::ImmutableList< const CXXBaseSpecifier * > prependCXXBase(const CXXBaseSpecifier *CBS, llvm::ImmutableList< const CXXBaseSpecifier * > L)
const LazyCompoundValData * getLazyCompoundValData(const StoreRef &store, const TypedValueRegion *region)
const PointerToMemberData * accumCXXBase(llvm::iterator_range< CastExpr::path_const_iterator > PathRange, const nonloc::PointerToMember &PTM, const clang::CastKind &kind)
static void Profile(llvm::FoldingSetNodeID &ID, QualType T, llvm::ImmutableList< SVal > L)
static void Profile(llvm::FoldingSetNodeID &ID, const StoreRef &store, const TypedValueRegion *region)
llvm::ImmutableList< const CXXBaseSpecifier * > getCXXBaseList() const
const NamedDecl * getDeclaratorDecl() const
It might return null.
static void Profile(llvm::FoldingSetNodeID &ID, const NamedDecl *D, llvm::ImmutableList< const CXXBaseSpecifier * > L)
SVal - This represents a symbolic expression, which can be either an L-value or an R-value.
Definition: SVals.h:55
void Profile(llvm::FoldingSetNodeID &ID) const
Definition: SVals.h:94
Store getStore() const
Definition: StoreRef.h:46
TypedValueRegion - An abstract class representing regions having a typed value.
Definition: MemRegion.h:535
Value representing pointer-to-member.
Definition: SVals.h:428
llvm::PointerUnion< const NamedDecl *, const PointerToMemberData * > PTMDataType
Definition: SVals.h:433
const PTMDataType getPTMData() const
Definition: SVals.h:435
The JSON file list parser is used to communicate input to InstallAPI.
BinaryOperatorKind
CastKind
CastKind - The kind of operation required for a conversion.
const FunctionProtoType * T
Diagnostic wrappers for TextAPI types for error reporting.
Definition: Dominators.h:30
__UINTPTR_TYPE__ uintptr_t
An unsigned integer type with the property that any valid pointer to void can be converted to this ty...
static void Profile(const SValData &X, llvm::FoldingSetNodeID &ID)
static void Profile(const SValPair &X, llvm::FoldingSetNodeID &ID)