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 <cassert>
25 #include <cstdint>
26 #include <utility>
27
28 using namespace clang;
29 using namespace ento;
30
Profile(llvm::FoldingSetNodeID & ID,QualType T,llvm::ImmutableList<SVal> L)31 void CompoundValData::Profile(llvm::FoldingSetNodeID& ID, QualType T,
32 llvm::ImmutableList<SVal> L) {
33 T.Profile(ID);
34 ID.AddPointer(L.getInternalPointer());
35 }
36
Profile(llvm::FoldingSetNodeID & ID,const StoreRef & store,const TypedValueRegion * region)37 void LazyCompoundValData::Profile(llvm::FoldingSetNodeID& ID,
38 const StoreRef &store,
39 const TypedValueRegion *region) {
40 ID.AddPointer(store.getStore());
41 ID.AddPointer(region);
42 }
43
Profile(llvm::FoldingSetNodeID & ID,const NamedDecl * D,llvm::ImmutableList<const CXXBaseSpecifier * > L)44 void PointerToMemberData::Profile(
45 llvm::FoldingSetNodeID &ID, const NamedDecl *D,
46 llvm::ImmutableList<const CXXBaseSpecifier *> L) {
47 ID.AddPointer(D);
48 ID.AddPointer(L.getInternalPointer());
49 }
50
51 using SValData = std::pair<SVal, uintptr_t>;
52 using SValPair = std::pair<SVal, SVal>;
53
54 namespace llvm {
55
56 template<> struct FoldingSetTrait<SValData> {
Profilellvm::FoldingSetTrait57 static inline void Profile(const SValData& X, llvm::FoldingSetNodeID& ID) {
58 X.first.Profile(ID);
59 ID.AddPointer( (void*) X.second);
60 }
61 };
62
63 template<> struct FoldingSetTrait<SValPair> {
Profilellvm::FoldingSetTrait64 static inline void Profile(const SValPair& X, llvm::FoldingSetNodeID& ID) {
65 X.first.Profile(ID);
66 X.second.Profile(ID);
67 }
68 };
69
70 } // namespace llvm
71
72 using PersistentSValsTy =
73 llvm::FoldingSet<llvm::FoldingSetNodeWrapper<SValData>>;
74
75 using PersistentSValPairsTy =
76 llvm::FoldingSet<llvm::FoldingSetNodeWrapper<SValPair>>;
77
~BasicValueFactory()78 BasicValueFactory::~BasicValueFactory() {
79 // Note that the dstor for the contents of APSIntSet will never be called,
80 // so we iterate over the set and invoke the dstor for each APSInt. This
81 // frees an aux. memory allocated to represent very large constants.
82 for (const auto &I : APSIntSet)
83 I.getValue().~APSInt();
84
85 delete (PersistentSValsTy*) PersistentSVals;
86 delete (PersistentSValPairsTy*) PersistentSValPairs;
87 }
88
getValue(const llvm::APSInt & X)89 const llvm::APSInt& BasicValueFactory::getValue(const llvm::APSInt& X) {
90 llvm::FoldingSetNodeID ID;
91 void *InsertPos;
92
93 using FoldNodeTy = llvm::FoldingSetNodeWrapper<llvm::APSInt>;
94
95 X.Profile(ID);
96 FoldNodeTy* P = APSIntSet.FindNodeOrInsertPos(ID, InsertPos);
97
98 if (!P) {
99 P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>();
100 new (P) FoldNodeTy(X);
101 APSIntSet.InsertNode(P, InsertPos);
102 }
103
104 return *P;
105 }
106
getValue(const llvm::APInt & X,bool isUnsigned)107 const llvm::APSInt& BasicValueFactory::getValue(const llvm::APInt& X,
108 bool isUnsigned) {
109 llvm::APSInt V(X, isUnsigned);
110 return getValue(V);
111 }
112
getValue(uint64_t X,unsigned BitWidth,bool isUnsigned)113 const 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
getValue(uint64_t X,QualType T)120 const llvm::APSInt& BasicValueFactory::getValue(uint64_t X, QualType T) {
121 return getValue(getAPSIntType(T).getValue(X));
122 }
123
124 const CompoundValData*
getCompoundValData(QualType T,llvm::ImmutableList<SVal> Vals)125 BasicValueFactory::getCompoundValData(QualType T,
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 = (CompoundValData*) BPAlloc.Allocate<CompoundValData>();
135 new (D) CompoundValData(T, Vals);
136 CompoundValDataSet.InsertNode(D, InsertPos);
137 }
138
139 return D;
140 }
141
142 const LazyCompoundValData*
getLazyCompoundValData(const StoreRef & store,const TypedValueRegion * region)143 BasicValueFactory::getLazyCompoundValData(const StoreRef &store,
144 const TypedValueRegion *region) {
145 llvm::FoldingSetNodeID ID;
146 LazyCompoundValData::Profile(ID, store, region);
147 void *InsertPos;
148
149 LazyCompoundValData *D =
150 LazyCompoundValDataSet.FindNodeOrInsertPos(ID, InsertPos);
151
152 if (!D) {
153 D = (LazyCompoundValData*) BPAlloc.Allocate<LazyCompoundValData>();
154 new (D) LazyCompoundValData(store, region);
155 LazyCompoundValDataSet.InsertNode(D, InsertPos);
156 }
157
158 return D;
159 }
160
getPointerToMemberData(const NamedDecl * ND,llvm::ImmutableList<const CXXBaseSpecifier * > L)161 const PointerToMemberData *BasicValueFactory::getPointerToMemberData(
162 const NamedDecl *ND, llvm::ImmutableList<const CXXBaseSpecifier *> L) {
163 llvm::FoldingSetNodeID ID;
164 PointerToMemberData::Profile(ID, ND, L);
165 void *InsertPos;
166
167 PointerToMemberData *D =
168 PointerToMemberDataSet.FindNodeOrInsertPos(ID, InsertPos);
169
170 if (!D) {
171 D = (PointerToMemberData *)BPAlloc.Allocate<PointerToMemberData>();
172 new (D) PointerToMemberData(ND, L);
173 PointerToMemberDataSet.InsertNode(D, InsertPos);
174 }
175
176 return D;
177 }
178
accumCXXBase(llvm::iterator_range<CastExpr::path_const_iterator> PathRange,const nonloc::PointerToMember & PTM)179 const PointerToMemberData *BasicValueFactory::accumCXXBase(
180 llvm::iterator_range<CastExpr::path_const_iterator> PathRange,
181 const nonloc::PointerToMember &PTM) {
182 nonloc::PointerToMember::PTMDataType PTMDT = PTM.getPTMData();
183 const NamedDecl *ND = nullptr;
184 llvm::ImmutableList<const CXXBaseSpecifier *> PathList;
185
186 if (PTMDT.isNull() || PTMDT.is<const NamedDecl *>()) {
187 if (PTMDT.is<const NamedDecl *>())
188 ND = PTMDT.get<const NamedDecl *>();
189
190 PathList = CXXBaseListFactory.getEmptyList();
191 } else { // const PointerToMemberData *
192 const PointerToMemberData *PTMD = PTMDT.get<const PointerToMemberData *>();
193 ND = PTMD->getDeclaratorDecl();
194
195 PathList = PTMD->getCXXBaseList();
196 }
197
198 for (const auto &I : llvm::reverse(PathRange))
199 PathList = prependCXXBase(I, PathList);
200 return getPointerToMemberData(ND, PathList);
201 }
202
203 const llvm::APSInt*
evalAPSInt(BinaryOperator::Opcode Op,const llvm::APSInt & V1,const llvm::APSInt & V2)204 BasicValueFactory::evalAPSInt(BinaryOperator::Opcode Op,
205 const llvm::APSInt& V1, const llvm::APSInt& V2) {
206 switch (Op) {
207 default:
208 llvm_unreachable("Invalid Opcode.");
209
210 case BO_Mul:
211 return &getValue( V1 * V2 );
212
213 case BO_Div:
214 if (V2 == 0) // Avoid division by zero
215 return nullptr;
216 return &getValue( V1 / V2 );
217
218 case BO_Rem:
219 if (V2 == 0) // Avoid division by zero
220 return nullptr;
221 return &getValue( V1 % V2 );
222
223 case BO_Add:
224 return &getValue( V1 + V2 );
225
226 case BO_Sub:
227 return &getValue( V1 - V2 );
228
229 case BO_Shl: {
230 // FIXME: This logic should probably go higher up, where we can
231 // test these conditions symbolically.
232
233 if (V2.isSigned() && V2.isNegative())
234 return nullptr;
235
236 uint64_t Amt = V2.getZExtValue();
237
238 if (Amt >= V1.getBitWidth())
239 return nullptr;
240
241 if (!Ctx.getLangOpts().CPlusPlus20) {
242 if (V1.isSigned() && V1.isNegative())
243 return nullptr;
244
245 if (V1.isSigned() && Amt > V1.countLeadingZeros())
246 return nullptr;
247 }
248
249 return &getValue( V1.operator<<( (unsigned) Amt ));
250 }
251
252 case BO_Shr: {
253 // FIXME: This logic should probably go higher up, where we can
254 // test these conditions symbolically.
255
256 if (V2.isSigned() && V2.isNegative())
257 return nullptr;
258
259 uint64_t Amt = V2.getZExtValue();
260
261 if (Amt >= V1.getBitWidth())
262 return nullptr;
263
264 return &getValue( V1.operator>>( (unsigned) Amt ));
265 }
266
267 case BO_LT:
268 return &getTruthValue( V1 < V2 );
269
270 case BO_GT:
271 return &getTruthValue( V1 > V2 );
272
273 case BO_LE:
274 return &getTruthValue( V1 <= V2 );
275
276 case BO_GE:
277 return &getTruthValue( V1 >= V2 );
278
279 case BO_EQ:
280 return &getTruthValue( V1 == V2 );
281
282 case BO_NE:
283 return &getTruthValue( V1 != V2 );
284
285 // Note: LAnd, LOr, Comma are handled specially by higher-level logic.
286
287 case BO_And:
288 return &getValue( V1 & V2 );
289
290 case BO_Or:
291 return &getValue( V1 | V2 );
292
293 case BO_Xor:
294 return &getValue( V1 ^ V2 );
295 }
296 }
297
298 const std::pair<SVal, uintptr_t>&
getPersistentSValWithData(const SVal & V,uintptr_t Data)299 BasicValueFactory::getPersistentSValWithData(const SVal& V, uintptr_t Data) {
300 // Lazily create the folding set.
301 if (!PersistentSVals) PersistentSVals = new PersistentSValsTy();
302
303 llvm::FoldingSetNodeID ID;
304 void *InsertPos;
305 V.Profile(ID);
306 ID.AddPointer((void*) Data);
307
308 PersistentSValsTy& Map = *((PersistentSValsTy*) PersistentSVals);
309
310 using FoldNodeTy = llvm::FoldingSetNodeWrapper<SValData>;
311
312 FoldNodeTy* P = Map.FindNodeOrInsertPos(ID, InsertPos);
313
314 if (!P) {
315 P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>();
316 new (P) FoldNodeTy(std::make_pair(V, Data));
317 Map.InsertNode(P, InsertPos);
318 }
319
320 return P->getValue();
321 }
322
323 const std::pair<SVal, SVal>&
getPersistentSValPair(const SVal & V1,const SVal & V2)324 BasicValueFactory::getPersistentSValPair(const SVal& V1, const SVal& V2) {
325 // Lazily create the folding set.
326 if (!PersistentSValPairs) PersistentSValPairs = new PersistentSValPairsTy();
327
328 llvm::FoldingSetNodeID ID;
329 void *InsertPos;
330 V1.Profile(ID);
331 V2.Profile(ID);
332
333 PersistentSValPairsTy& Map = *((PersistentSValPairsTy*) PersistentSValPairs);
334
335 using FoldNodeTy = llvm::FoldingSetNodeWrapper<SValPair>;
336
337 FoldNodeTy* P = Map.FindNodeOrInsertPos(ID, InsertPos);
338
339 if (!P) {
340 P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>();
341 new (P) FoldNodeTy(std::make_pair(V1, V2));
342 Map.InsertNode(P, InsertPos);
343 }
344
345 return P->getValue();
346 }
347
getPersistentSVal(SVal X)348 const SVal* BasicValueFactory::getPersistentSVal(SVal X) {
349 return &getPersistentSValWithData(X, 0).first;
350 }
351