/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/lib/StaticAnalyzer/Core/BasicValueFactory.cpp
Line | Count | Source (jump to first uncovered line) |
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 | | |
31 | | void CompoundValData::Profile(llvm::FoldingSetNodeID& ID, QualType T, |
32 | 1.35k | llvm::ImmutableList<SVal> L) { |
33 | 1.35k | T.Profile(ID); |
34 | 1.35k | ID.AddPointer(L.getInternalPointer()); |
35 | 1.35k | } |
36 | | |
37 | | void LazyCompoundValData::Profile(llvm::FoldingSetNodeID& ID, |
38 | | const StoreRef &store, |
39 | 93.2k | const TypedValueRegion *region) { |
40 | 93.2k | ID.AddPointer(store.getStore()); |
41 | 93.2k | ID.AddPointer(region); |
42 | 93.2k | } |
43 | | |
44 | | void PointerToMemberData::Profile( |
45 | | llvm::FoldingSetNodeID &ID, const NamedDecl *D, |
46 | 28 | llvm::ImmutableList<const CXXBaseSpecifier *> L) { |
47 | 28 | ID.AddPointer(D); |
48 | 28 | ID.AddPointer(L.getInternalPointer()); |
49 | 28 | } |
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> { |
57 | 14 | static inline void Profile(const SValData& X, llvm::FoldingSetNodeID& ID) { |
58 | 14 | X.first.Profile(ID); |
59 | 14 | ID.AddPointer( (void*) X.second); |
60 | 14 | } |
61 | | }; |
62 | | |
63 | | template<> struct FoldingSetTrait<SValPair> { |
64 | 0 | static inline void Profile(const SValPair& X, llvm::FoldingSetNodeID& ID) { |
65 | 0 | X.first.Profile(ID); |
66 | 0 | X.second.Profile(ID); |
67 | 0 | } |
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 | | |
78 | 13.7k | 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 | 13.7k | for (const auto &I : APSIntSet) |
83 | 98.6k | I.getValue().~APSInt(); |
84 | | |
85 | 13.7k | delete (PersistentSValsTy*) PersistentSVals; |
86 | 13.7k | delete (PersistentSValPairsTy*) PersistentSValPairs; |
87 | 13.7k | } |
88 | | |
89 | 1.68M | const llvm::APSInt& BasicValueFactory::getValue(const llvm::APSInt& X) { |
90 | 1.68M | llvm::FoldingSetNodeID ID; |
91 | 1.68M | void *InsertPos; |
92 | | |
93 | 1.68M | using FoldNodeTy = llvm::FoldingSetNodeWrapper<llvm::APSInt>; |
94 | | |
95 | 1.68M | X.Profile(ID); |
96 | 1.68M | FoldNodeTy* P = APSIntSet.FindNodeOrInsertPos(ID, InsertPos); |
97 | | |
98 | 1.68M | if (!P) { |
99 | 98.6k | P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>(); |
100 | 98.6k | new (P) FoldNodeTy(X); |
101 | 98.6k | APSIntSet.InsertNode(P, InsertPos); |
102 | 98.6k | } |
103 | | |
104 | 1.68M | return *P; |
105 | 1.68M | } |
106 | | |
107 | | const llvm::APSInt& BasicValueFactory::getValue(const llvm::APInt& X, |
108 | 65.4k | bool isUnsigned) { |
109 | 65.4k | llvm::APSInt V(X, isUnsigned); |
110 | 65.4k | return getValue(V); |
111 | 65.4k | } |
112 | | |
113 | | const llvm::APSInt& BasicValueFactory::getValue(uint64_t X, unsigned BitWidth, |
114 | 551k | bool isUnsigned) { |
115 | 551k | llvm::APSInt V(BitWidth, isUnsigned); |
116 | 551k | V = X; |
117 | 551k | return getValue(V); |
118 | 551k | } |
119 | | |
120 | 225k | const llvm::APSInt& BasicValueFactory::getValue(uint64_t X, QualType T) { |
121 | 225k | return getValue(getAPSIntType(T).getValue(X)); |
122 | 225k | } |
123 | | |
124 | | const CompoundValData* |
125 | | BasicValueFactory::getCompoundValData(QualType T, |
126 | 1.11k | llvm::ImmutableList<SVal> Vals) { |
127 | 1.11k | llvm::FoldingSetNodeID ID; |
128 | 1.11k | CompoundValData::Profile(ID, T, Vals); |
129 | 1.11k | void *InsertPos; |
130 | | |
131 | 1.11k | CompoundValData* D = CompoundValDataSet.FindNodeOrInsertPos(ID, InsertPos); |
132 | | |
133 | 1.11k | if (!D) { |
134 | 885 | D = (CompoundValData*) BPAlloc.Allocate<CompoundValData>(); |
135 | 885 | new (D) CompoundValData(T, Vals); |
136 | 885 | CompoundValDataSet.InsertNode(D, InsertPos); |
137 | 885 | } |
138 | | |
139 | 1.11k | return D; |
140 | 1.11k | } |
141 | | |
142 | | const LazyCompoundValData* |
143 | | BasicValueFactory::getLazyCompoundValData(const StoreRef &store, |
144 | 54.0k | const TypedValueRegion *region) { |
145 | 54.0k | llvm::FoldingSetNodeID ID; |
146 | 54.0k | LazyCompoundValData::Profile(ID, store, region); |
147 | 54.0k | void *InsertPos; |
148 | | |
149 | 54.0k | LazyCompoundValData *D = |
150 | 54.0k | LazyCompoundValDataSet.FindNodeOrInsertPos(ID, InsertPos); |
151 | | |
152 | 54.0k | if (!D) { |
153 | 19.8k | D = (LazyCompoundValData*) BPAlloc.Allocate<LazyCompoundValData>(); |
154 | 19.8k | new (D) LazyCompoundValData(store, region); |
155 | 19.8k | LazyCompoundValDataSet.InsertNode(D, InsertPos); |
156 | 19.8k | } |
157 | | |
158 | 54.0k | return D; |
159 | 54.0k | } |
160 | | |
161 | | const PointerToMemberData *BasicValueFactory::getPointerToMemberData( |
162 | 24 | const NamedDecl *ND, llvm::ImmutableList<const CXXBaseSpecifier *> L) { |
163 | 24 | llvm::FoldingSetNodeID ID; |
164 | 24 | PointerToMemberData::Profile(ID, ND, L); |
165 | 24 | void *InsertPos; |
166 | | |
167 | 24 | PointerToMemberData *D = |
168 | 24 | PointerToMemberDataSet.FindNodeOrInsertPos(ID, InsertPos); |
169 | | |
170 | 24 | if (!D) { |
171 | 20 | D = (PointerToMemberData *)BPAlloc.Allocate<PointerToMemberData>(); |
172 | 20 | new (D) PointerToMemberData(ND, L); |
173 | 20 | PointerToMemberDataSet.InsertNode(D, InsertPos); |
174 | 20 | } |
175 | | |
176 | 24 | return D; |
177 | 24 | } |
178 | | |
179 | | const PointerToMemberData *BasicValueFactory::accumCXXBase( |
180 | | llvm::iterator_range<CastExpr::path_const_iterator> PathRange, |
181 | 24 | const nonloc::PointerToMember &PTM) { |
182 | 24 | nonloc::PointerToMember::PTMDataType PTMDT = PTM.getPTMData(); |
183 | 24 | const NamedDecl *ND = nullptr; |
184 | 24 | llvm::ImmutableList<const CXXBaseSpecifier *> PathList; |
185 | | |
186 | 24 | if (PTMDT.isNull() || PTMDT.is<const NamedDecl *>()) { |
187 | 12 | if (PTMDT.is<const NamedDecl *>()) |
188 | 12 | ND = PTMDT.get<const NamedDecl *>(); |
189 | | |
190 | 12 | PathList = CXXBaseListFactory.getEmptyList(); |
191 | 12 | } else { // const PointerToMemberData * |
192 | 12 | const PointerToMemberData *PTMD = PTMDT.get<const PointerToMemberData *>(); |
193 | 12 | ND = PTMD->getDeclaratorDecl(); |
194 | | |
195 | 12 | PathList = PTMD->getCXXBaseList(); |
196 | 12 | } |
197 | | |
198 | 24 | for (const auto &I : llvm::reverse(PathRange)) |
199 | 28 | PathList = prependCXXBase(I, PathList); |
200 | 24 | return getPointerToMemberData(ND, PathList); |
201 | 24 | } |
202 | | |
203 | | const llvm::APSInt* |
204 | | BasicValueFactory::evalAPSInt(BinaryOperator::Opcode Op, |
205 | 32.8k | const llvm::APSInt& V1, const llvm::APSInt& V2) { |
206 | 32.8k | switch (Op) { |
207 | 0 | default: |
208 | 0 | llvm_unreachable("Invalid Opcode."); |
209 | | |
210 | 1.07k | case BO_Mul: |
211 | 1.07k | return &getValue( V1 * V2 ); |
212 | | |
213 | 1.35k | case BO_Div: |
214 | 1.35k | if (V2 == 0) // Avoid division by zero |
215 | 1 | return nullptr; |
216 | 1.35k | return &getValue( V1 / V2 ); |
217 | | |
218 | 19 | case BO_Rem: |
219 | 19 | if (V2 == 0) // Avoid division by zero |
220 | 0 | return nullptr; |
221 | 19 | return &getValue( V1 % V2 ); |
222 | | |
223 | 14.1k | case BO_Add: |
224 | 14.1k | return &getValue( V1 + V2 ); |
225 | | |
226 | 1.68k | case BO_Sub: |
227 | 1.68k | return &getValue( V1 - V2 ); |
228 | | |
229 | 344 | case BO_Shl: { |
230 | | // FIXME: This logic should probably go higher up, where we can |
231 | | // test these conditions symbolically. |
232 | | |
233 | 344 | if (V2.isSigned() && V2.isNegative()332 ) |
234 | 3 | return nullptr; |
235 | | |
236 | 341 | uint64_t Amt = V2.getZExtValue(); |
237 | | |
238 | 341 | if (Amt >= V1.getBitWidth()) |
239 | 6 | return nullptr; |
240 | | |
241 | 335 | if (!Ctx.getLangOpts().CPlusPlus20) { |
242 | 333 | if (V1.isSigned() && V1.isNegative()177 ) |
243 | 2 | return nullptr; |
244 | | |
245 | 331 | if (V1.isSigned() && Amt > V1.countLeadingZeros()175 ) |
246 | 2 | return nullptr; |
247 | 331 | } |
248 | | |
249 | 331 | return &getValue( V1.operator<<( (unsigned) Amt )); |
250 | 331 | } |
251 | | |
252 | 422 | case BO_Shr: { |
253 | | // FIXME: This logic should probably go higher up, where we can |
254 | | // test these conditions symbolically. |
255 | | |
256 | 422 | if (V2.isSigned() && V2.isNegative()) |
257 | 0 | return nullptr; |
258 | | |
259 | 422 | uint64_t Amt = V2.getZExtValue(); |
260 | | |
261 | 422 | if (Amt >= V1.getBitWidth()) |
262 | 0 | return nullptr; |
263 | | |
264 | 422 | return &getValue( V1.operator>>( (unsigned) Amt )); |
265 | 422 | } |
266 | | |
267 | 5.12k | case BO_LT: |
268 | 5.12k | return &getTruthValue( V1 < V2 ); |
269 | | |
270 | 458 | case BO_GT: |
271 | 458 | return &getTruthValue( V1 > V2 ); |
272 | | |
273 | 100 | case BO_LE: |
274 | 100 | return &getTruthValue( V1 <= V2 ); |
275 | | |
276 | 1.16k | case BO_GE: |
277 | 1.16k | return &getTruthValue( V1 >= V2 ); |
278 | | |
279 | 5.92k | case BO_EQ: |
280 | 5.92k | return &getTruthValue( V1 == V2 ); |
281 | | |
282 | 320 | case BO_NE: |
283 | 320 | return &getTruthValue( V1 != V2 ); |
284 | | |
285 | | // Note: LAnd, LOr, Comma are handled specially by higher-level logic. |
286 | | |
287 | 435 | case BO_And: |
288 | 435 | return &getValue( V1 & V2 ); |
289 | | |
290 | 304 | case BO_Or: |
291 | 304 | return &getValue( V1 | V2 ); |
292 | | |
293 | 7 | case BO_Xor: |
294 | 7 | return &getValue( V1 ^ V2 ); |
295 | 32.8k | } |
296 | 32.8k | } |
297 | | |
298 | | const std::pair<SVal, uintptr_t>& |
299 | 132 | BasicValueFactory::getPersistentSValWithData(const SVal& V, uintptr_t Data) { |
300 | | // Lazily create the folding set. |
301 | 132 | if (!PersistentSVals) PersistentSVals = new PersistentSValsTy()102 ; |
302 | | |
303 | 132 | llvm::FoldingSetNodeID ID; |
304 | 132 | void *InsertPos; |
305 | 132 | V.Profile(ID); |
306 | 132 | ID.AddPointer((void*) Data); |
307 | | |
308 | 132 | PersistentSValsTy& Map = *((PersistentSValsTy*) PersistentSVals); |
309 | | |
310 | 132 | using FoldNodeTy = llvm::FoldingSetNodeWrapper<SValData>; |
311 | | |
312 | 132 | FoldNodeTy* P = Map.FindNodeOrInsertPos(ID, InsertPos); |
313 | | |
314 | 132 | if (!P) { |
315 | 118 | P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>(); |
316 | 118 | new (P) FoldNodeTy(std::make_pair(V, Data)); |
317 | 118 | Map.InsertNode(P, InsertPos); |
318 | 118 | } |
319 | | |
320 | 132 | return P->getValue(); |
321 | 132 | } |
322 | | |
323 | | const std::pair<SVal, SVal>& |
324 | 0 | BasicValueFactory::getPersistentSValPair(const SVal& V1, const SVal& V2) { |
325 | | // Lazily create the folding set. |
326 | 0 | if (!PersistentSValPairs) PersistentSValPairs = new PersistentSValPairsTy(); |
327 | |
|
328 | 0 | llvm::FoldingSetNodeID ID; |
329 | 0 | void *InsertPos; |
330 | 0 | V1.Profile(ID); |
331 | 0 | V2.Profile(ID); |
332 | |
|
333 | 0 | PersistentSValPairsTy& Map = *((PersistentSValPairsTy*) PersistentSValPairs); |
334 | |
|
335 | 0 | using FoldNodeTy = llvm::FoldingSetNodeWrapper<SValPair>; |
336 | |
|
337 | 0 | FoldNodeTy* P = Map.FindNodeOrInsertPos(ID, InsertPos); |
338 | |
|
339 | 0 | if (!P) { |
340 | 0 | P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>(); |
341 | 0 | new (P) FoldNodeTy(std::make_pair(V1, V2)); |
342 | 0 | Map.InsertNode(P, InsertPos); |
343 | 0 | } |
344 | |
|
345 | 0 | return P->getValue(); |
346 | 0 | } |
347 | | |
348 | 0 | const SVal* BasicValueFactory::getPersistentSVal(SVal X) { |
349 | 0 | return &getPersistentSValWithData(X, 0).first; |
350 | 0 | } |