/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h
Line | Count | Source (jump to first uncovered line) |
1 | | //===- SymbolManager.h - Management of Symbolic Values ----------*- C++ -*-===// |
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 SymbolManager, a class that manages symbolic values |
10 | | // created for use by ExprEngine and related classes. |
11 | | // |
12 | | //===----------------------------------------------------------------------===// |
13 | | |
14 | | #ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SYMBOLMANAGER_H |
15 | | #define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SYMBOLMANAGER_H |
16 | | |
17 | | #include "clang/AST/Expr.h" |
18 | | #include "clang/AST/Type.h" |
19 | | #include "clang/Analysis/AnalysisDeclContext.h" |
20 | | #include "clang/Basic/LLVM.h" |
21 | | #include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h" |
22 | | #include "clang/StaticAnalyzer/Core/PathSensitive/StoreRef.h" |
23 | | #include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h" |
24 | | #include "llvm/ADT/DenseMap.h" |
25 | | #include "llvm/ADT/DenseSet.h" |
26 | | #include "llvm/ADT/FoldingSet.h" |
27 | | #include "llvm/Support/Allocator.h" |
28 | | #include <cassert> |
29 | | |
30 | | namespace clang { |
31 | | |
32 | | class ASTContext; |
33 | | class Stmt; |
34 | | |
35 | | namespace ento { |
36 | | |
37 | | class BasicValueFactory; |
38 | | class StoreManager; |
39 | | |
40 | | ///A symbol representing the value stored at a MemRegion. |
41 | | class SymbolRegionValue : public SymbolData { |
42 | | const TypedValueRegion *R; |
43 | | |
44 | | public: |
45 | | SymbolRegionValue(SymbolID sym, const TypedValueRegion *r) |
46 | 15.0k | : SymbolData(SymbolRegionValueKind, sym), R(r) { |
47 | 15.0k | assert(r); |
48 | 0 | assert(isValidTypeForSymbol(r->getValueType())); |
49 | 15.0k | } |
50 | | |
51 | 1.08M | const TypedValueRegion* getRegion() const { return R; } |
52 | | |
53 | 245k | static void Profile(llvm::FoldingSetNodeID& profile, const TypedValueRegion* R) { |
54 | 245k | profile.AddInteger((unsigned) SymbolRegionValueKind); |
55 | 245k | profile.AddPointer(R); |
56 | 245k | } |
57 | | |
58 | 122k | void Profile(llvm::FoldingSetNodeID& profile) override { |
59 | 122k | Profile(profile, R); |
60 | 122k | } |
61 | | |
62 | | StringRef getKindStr() const override; |
63 | | |
64 | | void dumpToStream(raw_ostream &os) const override; |
65 | 1.17k | const MemRegion *getOriginRegion() const override { return getRegion(); } |
66 | | |
67 | | QualType getType() const override; |
68 | | |
69 | | // Implement isa<T> support. |
70 | 38.8k | static bool classof(const SymExpr *SE) { |
71 | 38.8k | return SE->getKind() == SymbolRegionValueKind; |
72 | 38.8k | } |
73 | | }; |
74 | | |
75 | | /// A symbol representing the result of an expression in the case when we do |
76 | | /// not know anything about what the expression is. |
77 | | class SymbolConjured : public SymbolData { |
78 | | const Stmt *S; |
79 | | QualType T; |
80 | | unsigned Count; |
81 | | const LocationContext *LCtx; |
82 | | const void *SymbolTag; |
83 | | |
84 | | public: |
85 | | SymbolConjured(SymbolID sym, const Stmt *s, const LocationContext *lctx, |
86 | | QualType t, unsigned count, const void *symbolTag) |
87 | | : SymbolData(SymbolConjuredKind, sym), S(s), T(t), Count(count), |
88 | 68.7k | LCtx(lctx), SymbolTag(symbolTag) { |
89 | | // FIXME: 's' might be a nullptr if we're conducting invalidation |
90 | | // that was caused by a destructor call on a temporary object, |
91 | | // which has no statement associated with it. |
92 | | // Due to this, we might be creating the same invalidation symbol for |
93 | | // two different invalidation passes (for two different temporaries). |
94 | 68.7k | assert(lctx); |
95 | 0 | assert(isValidTypeForSymbol(t)); |
96 | 68.7k | } |
97 | | |
98 | 7 | const Stmt *getStmt() const { return S; } |
99 | 0 | unsigned getCount() const { return Count; } |
100 | 0 | const void *getTag() const { return SymbolTag; } |
101 | | |
102 | | QualType getType() const override; |
103 | | |
104 | | StringRef getKindStr() const override; |
105 | | |
106 | | void dumpToStream(raw_ostream &os) const override; |
107 | | |
108 | | static void Profile(llvm::FoldingSetNodeID& profile, const Stmt *S, |
109 | | QualType T, unsigned Count, const LocationContext *LCtx, |
110 | 239k | const void *SymbolTag) { |
111 | 239k | profile.AddInteger((unsigned) SymbolConjuredKind); |
112 | 239k | profile.AddPointer(S); |
113 | 239k | profile.AddPointer(LCtx); |
114 | 239k | profile.Add(T); |
115 | 239k | profile.AddInteger(Count); |
116 | 239k | profile.AddPointer(SymbolTag); |
117 | 239k | } |
118 | | |
119 | 109k | void Profile(llvm::FoldingSetNodeID& profile) override { |
120 | 109k | Profile(profile, S, T, Count, LCtx, SymbolTag); |
121 | 109k | } |
122 | | |
123 | | // Implement isa<T> support. |
124 | 196 | static bool classof(const SymExpr *SE) { |
125 | 196 | return SE->getKind() == SymbolConjuredKind; |
126 | 196 | } |
127 | | }; |
128 | | |
129 | | /// A symbol representing the value of a MemRegion whose parent region has |
130 | | /// symbolic value. |
131 | | class SymbolDerived : public SymbolData { |
132 | | SymbolRef parentSymbol; |
133 | | const TypedValueRegion *R; |
134 | | |
135 | | public: |
136 | | SymbolDerived(SymbolID sym, SymbolRef parent, const TypedValueRegion *r) |
137 | 3.02k | : SymbolData(SymbolDerivedKind, sym), parentSymbol(parent), R(r) { |
138 | 3.02k | assert(parent); |
139 | 0 | assert(r); |
140 | 0 | assert(isValidTypeForSymbol(r->getValueType())); |
141 | 3.02k | } |
142 | | |
143 | 77.7k | SymbolRef getParentSymbol() const { return parentSymbol; } |
144 | 452 | const TypedValueRegion *getRegion() const { return R; } |
145 | | |
146 | | QualType getType() const override; |
147 | | |
148 | | StringRef getKindStr() const override; |
149 | | |
150 | | void dumpToStream(raw_ostream &os) const override; |
151 | 109 | const MemRegion *getOriginRegion() const override { return getRegion(); } |
152 | | |
153 | | static void Profile(llvm::FoldingSetNodeID& profile, SymbolRef parent, |
154 | 32.7k | const TypedValueRegion *r) { |
155 | 32.7k | profile.AddInteger((unsigned) SymbolDerivedKind); |
156 | 32.7k | profile.AddPointer(r); |
157 | 32.7k | profile.AddPointer(parent); |
158 | 32.7k | } |
159 | | |
160 | 17.8k | void Profile(llvm::FoldingSetNodeID& profile) override { |
161 | 17.8k | Profile(profile, parentSymbol, R); |
162 | 17.8k | } |
163 | | |
164 | | // Implement isa<T> support. |
165 | 39.5k | static bool classof(const SymExpr *SE) { |
166 | 39.5k | return SE->getKind() == SymbolDerivedKind; |
167 | 39.5k | } |
168 | | }; |
169 | | |
170 | | /// SymbolExtent - Represents the extent (size in bytes) of a bounded region. |
171 | | /// Clients should not ask the SymbolManager for a region's extent. Always use |
172 | | /// SubRegion::getExtent instead -- the value returned may not be a symbol. |
173 | | class SymbolExtent : public SymbolData { |
174 | | const SubRegion *R; |
175 | | |
176 | | public: |
177 | | SymbolExtent(SymbolID sym, const SubRegion *r) |
178 | 236 | : SymbolData(SymbolExtentKind, sym), R(r) { |
179 | 236 | assert(r); |
180 | 236 | } |
181 | | |
182 | 680 | const SubRegion *getRegion() const { return R; } |
183 | | |
184 | | QualType getType() const override; |
185 | | |
186 | | StringRef getKindStr() const override; |
187 | | |
188 | | void dumpToStream(raw_ostream &os) const override; |
189 | | |
190 | 636 | static void Profile(llvm::FoldingSetNodeID& profile, const SubRegion *R) { |
191 | 636 | profile.AddInteger((unsigned) SymbolExtentKind); |
192 | 636 | profile.AddPointer(R); |
193 | 636 | } |
194 | | |
195 | 237 | void Profile(llvm::FoldingSetNodeID& profile) override { |
196 | 237 | Profile(profile, R); |
197 | 237 | } |
198 | | |
199 | | // Implement isa<T> support. |
200 | 0 | static bool classof(const SymExpr *SE) { |
201 | 0 | return SE->getKind() == SymbolExtentKind; |
202 | 0 | } |
203 | | }; |
204 | | |
205 | | /// SymbolMetadata - Represents path-dependent metadata about a specific region. |
206 | | /// Metadata symbols remain live as long as they are marked as in use before |
207 | | /// dead-symbol sweeping AND their associated regions are still alive. |
208 | | /// Intended for use by checkers. |
209 | | class SymbolMetadata : public SymbolData { |
210 | | const MemRegion* R; |
211 | | const Stmt *S; |
212 | | QualType T; |
213 | | const LocationContext *LCtx; |
214 | | unsigned Count; |
215 | | const void *Tag; |
216 | | |
217 | | public: |
218 | | SymbolMetadata(SymbolID sym, const MemRegion* r, const Stmt *s, QualType t, |
219 | | const LocationContext *LCtx, unsigned count, const void *tag) |
220 | | : SymbolData(SymbolMetadataKind, sym), R(r), S(s), T(t), LCtx(LCtx), |
221 | 583 | Count(count), Tag(tag) { |
222 | 583 | assert(r); |
223 | 0 | assert(s); |
224 | 0 | assert(isValidTypeForSymbol(t)); |
225 | 0 | assert(LCtx); |
226 | 0 | assert(tag); |
227 | 583 | } |
228 | | |
229 | 1.47k | const MemRegion *getRegion() const { return R; } |
230 | 0 | const Stmt *getStmt() const { return S; } |
231 | 0 | const LocationContext *getLocationContext() const { return LCtx; } |
232 | 0 | unsigned getCount() const { return Count; } |
233 | 0 | const void *getTag() const { return Tag; } |
234 | | |
235 | | QualType getType() const override; |
236 | | |
237 | | StringRef getKindStr() const override; |
238 | | |
239 | | void dumpToStream(raw_ostream &os) const override; |
240 | | |
241 | | static void Profile(llvm::FoldingSetNodeID& profile, const MemRegion *R, |
242 | | const Stmt *S, QualType T, const LocationContext *LCtx, |
243 | 775 | unsigned Count, const void *Tag) { |
244 | 775 | profile.AddInteger((unsigned) SymbolMetadataKind); |
245 | 775 | profile.AddPointer(R); |
246 | 775 | profile.AddPointer(S); |
247 | 775 | profile.Add(T); |
248 | 775 | profile.AddPointer(LCtx); |
249 | 775 | profile.AddInteger(Count); |
250 | 775 | profile.AddPointer(Tag); |
251 | 775 | } |
252 | | |
253 | 168 | void Profile(llvm::FoldingSetNodeID& profile) override { |
254 | 168 | Profile(profile, R, S, T, LCtx, Count, Tag); |
255 | 168 | } |
256 | | |
257 | | // Implement isa<T> support. |
258 | 6.45k | static bool classof(const SymExpr *SE) { |
259 | 6.45k | return SE->getKind() == SymbolMetadataKind; |
260 | 6.45k | } |
261 | | }; |
262 | | |
263 | | /// Represents a cast expression. |
264 | | class SymbolCast : public SymExpr { |
265 | | const SymExpr *Operand; |
266 | | |
267 | | /// Type of the operand. |
268 | | QualType FromTy; |
269 | | |
270 | | /// The type of the result. |
271 | | QualType ToTy; |
272 | | |
273 | | public: |
274 | | SymbolCast(const SymExpr *In, QualType From, QualType To) |
275 | 1.01k | : SymExpr(SymbolCastKind), Operand(In), FromTy(From), ToTy(To) { |
276 | 1.01k | assert(In); |
277 | 0 | assert(isValidTypeForSymbol(From)); |
278 | | // FIXME: GenericTaintChecker creates symbols of void type. |
279 | | // Otherwise, 'To' should also be a valid type. |
280 | 1.01k | } |
281 | | |
282 | 38 | unsigned computeComplexity() const override { |
283 | 38 | if (Complexity == 0) |
284 | 12 | Complexity = 1 + Operand->computeComplexity(); |
285 | 38 | return Complexity; |
286 | 38 | } |
287 | | |
288 | 9.91k | QualType getType() const override { return ToTy; } |
289 | | |
290 | 6.05k | const SymExpr *getOperand() const { return Operand; } |
291 | | |
292 | | void dumpToStream(raw_ostream &os) const override; |
293 | | |
294 | | static void Profile(llvm::FoldingSetNodeID& ID, |
295 | 11.1k | const SymExpr *In, QualType From, QualType To) { |
296 | 11.1k | ID.AddInteger((unsigned) SymbolCastKind); |
297 | 11.1k | ID.AddPointer(In); |
298 | 11.1k | ID.Add(From); |
299 | 11.1k | ID.Add(To); |
300 | 11.1k | } |
301 | | |
302 | 6.07k | void Profile(llvm::FoldingSetNodeID& ID) override { |
303 | 6.07k | Profile(ID, Operand, FromTy, ToTy); |
304 | 6.07k | } |
305 | | |
306 | | // Implement isa<T> support. |
307 | 43.6k | static bool classof(const SymExpr *SE) { |
308 | 43.6k | return SE->getKind() == SymbolCastKind; |
309 | 43.6k | } |
310 | | }; |
311 | | |
312 | | /// Represents a symbolic expression involving a binary operator |
313 | | class BinarySymExpr : public SymExpr { |
314 | | BinaryOperator::Opcode Op; |
315 | | QualType T; |
316 | | |
317 | | protected: |
318 | | BinarySymExpr(Kind k, BinaryOperator::Opcode op, QualType t) |
319 | 36.8k | : SymExpr(k), Op(op), T(t) { |
320 | 36.8k | assert(classof(this)); |
321 | | // Binary expressions are results of arithmetic. Pointer arithmetic is not |
322 | | // handled by binary expressions, but it is instead handled by applying |
323 | | // sub-regions to regions. |
324 | 0 | assert(isValidTypeForSymbol(t) && !Loc::isLocType(t)); |
325 | 36.8k | } |
326 | | |
327 | | public: |
328 | | // FIXME: We probably need to make this out-of-line to avoid redundant |
329 | | // generation of virtual functions. |
330 | 3.22M | QualType getType() const override { return T; } |
331 | | |
332 | 890k | BinaryOperator::Opcode getOpcode() const { return Op; } |
333 | | |
334 | | // Implement isa<T> support. |
335 | 184k | static bool classof(const SymExpr *SE) { |
336 | 184k | Kind k = SE->getKind(); |
337 | 184k | return k >= BEGIN_BINARYSYMEXPRS && k <= END_BINARYSYMEXPRS; |
338 | 184k | } |
339 | | |
340 | | protected: |
341 | 2.11k | static unsigned computeOperandComplexity(const SymExpr *Value) { |
342 | 2.11k | return Value->computeComplexity(); |
343 | 2.11k | } |
344 | 584 | static unsigned computeOperandComplexity(const llvm::APSInt &Value) { |
345 | 584 | return 1; |
346 | 584 | } |
347 | | |
348 | 394k | static const llvm::APSInt *getPointer(const llvm::APSInt &Value) { |
349 | 394k | return &Value; |
350 | 394k | } |
351 | 670k | static const SymExpr *getPointer(const SymExpr *Value) { return Value; } |
352 | | |
353 | | static void dumpToStreamImpl(raw_ostream &os, const SymExpr *Value); |
354 | | static void dumpToStreamImpl(raw_ostream &os, const llvm::APSInt &Value); |
355 | | static void dumpToStreamImpl(raw_ostream &os, BinaryOperator::Opcode op); |
356 | | }; |
357 | | |
358 | | /// Template implementation for all binary symbolic expressions |
359 | | template <class LHSTYPE, class RHSTYPE, SymExpr::Kind ClassKind> |
360 | | class BinarySymExprImpl : public BinarySymExpr { |
361 | | LHSTYPE LHS; |
362 | | RHSTYPE RHS; |
363 | | |
364 | | public: |
365 | | BinarySymExprImpl(LHSTYPE lhs, BinaryOperator::Opcode op, RHSTYPE rhs, |
366 | | QualType t) |
367 | 36.8k | : BinarySymExpr(ClassKind, op, t), LHS(lhs), RHS(rhs) { |
368 | 36.8k | assert(getPointer(lhs)); |
369 | 0 | assert(getPointer(rhs)); |
370 | 36.8k | } clang::ento::BinarySymExprImpl<clang::ento::SymExpr const*, llvm::APSInt const&, (clang::ento::SymExpr::Kind)1>::BinarySymExprImpl(clang::ento::SymExpr const*, clang::BinaryOperatorKind, llvm::APSInt const&, clang::QualType) Line | Count | Source | 367 | 28.9k | : BinarySymExpr(ClassKind, op, t), LHS(lhs), RHS(rhs) { | 368 | 28.9k | assert(getPointer(lhs)); | 369 | 0 | assert(getPointer(rhs)); | 370 | 28.9k | } |
clang::ento::BinarySymExprImpl<llvm::APSInt const&, clang::ento::SymExpr const*, (clang::ento::SymExpr::Kind)0>::BinarySymExprImpl(llvm::APSInt const&, clang::BinaryOperatorKind, clang::ento::SymExpr const*, clang::QualType) Line | Count | Source | 367 | 259 | : BinarySymExpr(ClassKind, op, t), LHS(lhs), RHS(rhs) { | 368 | 259 | assert(getPointer(lhs)); | 369 | 0 | assert(getPointer(rhs)); | 370 | 259 | } |
clang::ento::BinarySymExprImpl<clang::ento::SymExpr const*, clang::ento::SymExpr const*, (clang::ento::SymExpr::Kind)2>::BinarySymExprImpl(clang::ento::SymExpr const*, clang::BinaryOperatorKind, clang::ento::SymExpr const*, clang::QualType) Line | Count | Source | 367 | 7.58k | : BinarySymExpr(ClassKind, op, t), LHS(lhs), RHS(rhs) { | 368 | 7.58k | assert(getPointer(lhs)); | 369 | 0 | assert(getPointer(rhs)); | 370 | 7.58k | } |
|
371 | | |
372 | 81 | void dumpToStream(raw_ostream &os) const override { |
373 | 81 | dumpToStreamImpl(os, LHS); |
374 | 81 | dumpToStreamImpl(os, getOpcode()); |
375 | 81 | dumpToStreamImpl(os, RHS); |
376 | 81 | } clang::ento::BinarySymExprImpl<clang::ento::SymExpr const*, llvm::APSInt const&, (clang::ento::SymExpr::Kind)1>::dumpToStream(llvm::raw_ostream&) const Line | Count | Source | 372 | 44 | void dumpToStream(raw_ostream &os) const override { | 373 | 44 | dumpToStreamImpl(os, LHS); | 374 | 44 | dumpToStreamImpl(os, getOpcode()); | 375 | 44 | dumpToStreamImpl(os, RHS); | 376 | 44 | } |
clang::ento::BinarySymExprImpl<llvm::APSInt const&, clang::ento::SymExpr const*, (clang::ento::SymExpr::Kind)0>::dumpToStream(llvm::raw_ostream&) const Line | Count | Source | 372 | 2 | void dumpToStream(raw_ostream &os) const override { | 373 | 2 | dumpToStreamImpl(os, LHS); | 374 | 2 | dumpToStreamImpl(os, getOpcode()); | 375 | 2 | dumpToStreamImpl(os, RHS); | 376 | 2 | } |
clang::ento::BinarySymExprImpl<clang::ento::SymExpr const*, clang::ento::SymExpr const*, (clang::ento::SymExpr::Kind)2>::dumpToStream(llvm::raw_ostream&) const Line | Count | Source | 372 | 35 | void dumpToStream(raw_ostream &os) const override { | 373 | 35 | dumpToStreamImpl(os, LHS); | 374 | 35 | dumpToStreamImpl(os, getOpcode()); | 375 | 35 | dumpToStreamImpl(os, RHS); | 376 | 35 | } |
|
377 | | |
378 | 3.83M | LHSTYPE getLHS() const { return LHS; } clang::ento::BinarySymExprImpl<clang::ento::SymExpr const*, llvm::APSInt const&, (clang::ento::SymExpr::Kind)1>::getLHS() const Line | Count | Source | 378 | 3.05M | LHSTYPE getLHS() const { return LHS; } |
clang::ento::BinarySymExprImpl<llvm::APSInt const&, clang::ento::SymExpr const*, (clang::ento::SymExpr::Kind)0>::getLHS() const Line | Count | Source | 378 | 320 | LHSTYPE getLHS() const { return LHS; } |
clang::ento::BinarySymExprImpl<clang::ento::SymExpr const*, clang::ento::SymExpr const*, (clang::ento::SymExpr::Kind)2>::getLHS() const Line | Count | Source | 378 | 772k | LHSTYPE getLHS() const { return LHS; } |
|
379 | 1.01M | RHSTYPE getRHS() const { return RHS; } clang::ento::BinarySymExprImpl<clang::ento::SymExpr const*, llvm::APSInt const&, (clang::ento::SymExpr::Kind)1>::getRHS() const Line | Count | Source | 379 | 243k | RHSTYPE getRHS() const { return RHS; } |
clang::ento::BinarySymExprImpl<llvm::APSInt const&, clang::ento::SymExpr const*, (clang::ento::SymExpr::Kind)0>::getRHS() const Line | Count | Source | 379 | 16.0k | RHSTYPE getRHS() const { return RHS; } |
clang::ento::BinarySymExprImpl<clang::ento::SymExpr const*, clang::ento::SymExpr const*, (clang::ento::SymExpr::Kind)2>::getRHS() const Line | Count | Source | 379 | 760k | RHSTYPE getRHS() const { return RHS; } |
|
380 | | |
381 | 11.6k | unsigned computeComplexity() const override { |
382 | 11.6k | if (Complexity == 0) |
383 | 1.35k | Complexity = |
384 | 1.35k | computeOperandComplexity(RHS) + computeOperandComplexity(LHS); |
385 | 11.6k | return Complexity; |
386 | 11.6k | } clang::ento::BinarySymExprImpl<clang::ento::SymExpr const*, llvm::APSInt const&, (clang::ento::SymExpr::Kind)1>::computeComplexity() const Line | Count | Source | 381 | 3.57k | unsigned computeComplexity() const override { | 382 | 3.57k | if (Complexity == 0) | 383 | 548 | Complexity = | 384 | 548 | computeOperandComplexity(RHS) + computeOperandComplexity(LHS); | 385 | 3.57k | return Complexity; | 386 | 3.57k | } |
clang::ento::BinarySymExprImpl<llvm::APSInt const&, clang::ento::SymExpr const*, (clang::ento::SymExpr::Kind)0>::computeComplexity() const Line | Count | Source | 381 | 57 | unsigned computeComplexity() const override { | 382 | 57 | if (Complexity == 0) | 383 | 36 | Complexity = | 384 | 36 | computeOperandComplexity(RHS) + computeOperandComplexity(LHS); | 385 | 57 | return Complexity; | 386 | 57 | } |
clang::ento::BinarySymExprImpl<clang::ento::SymExpr const*, clang::ento::SymExpr const*, (clang::ento::SymExpr::Kind)2>::computeComplexity() const Line | Count | Source | 381 | 7.99k | unsigned computeComplexity() const override { | 382 | 7.99k | if (Complexity == 0) | 383 | 766 | Complexity = | 384 | 766 | computeOperandComplexity(RHS) + computeOperandComplexity(LHS); | 385 | 7.99k | return Complexity; | 386 | 7.99k | } |
|
387 | | |
388 | | static void Profile(llvm::FoldingSetNodeID &ID, LHSTYPE lhs, |
389 | 495k | BinaryOperator::Opcode op, RHSTYPE rhs, QualType t) { |
390 | 495k | ID.AddInteger((unsigned)ClassKind); |
391 | 495k | ID.AddPointer(getPointer(lhs)); |
392 | 495k | ID.AddInteger(op); |
393 | 495k | ID.AddPointer(getPointer(rhs)); |
394 | 495k | ID.Add(t); |
395 | 495k | } clang::ento::BinarySymExprImpl<clang::ento::SymExpr const*, llvm::APSInt const&, (clang::ento::SymExpr::Kind)1>::Profile(llvm::FoldingSetNodeID&, clang::ento::SymExpr const*, clang::BinaryOperatorKind, llvm::APSInt const&, clang::QualType) Line | Count | Source | 389 | 364k | BinaryOperator::Opcode op, RHSTYPE rhs, QualType t) { | 390 | 364k | ID.AddInteger((unsigned)ClassKind); | 391 | 364k | ID.AddPointer(getPointer(lhs)); | 392 | 364k | ID.AddInteger(op); | 393 | 364k | ID.AddPointer(getPointer(rhs)); | 394 | 364k | ID.Add(t); | 395 | 364k | } |
clang::ento::BinarySymExprImpl<llvm::APSInt const&, clang::ento::SymExpr const*, (clang::ento::SymExpr::Kind)0>::Profile(llvm::FoldingSetNodeID&, llvm::APSInt const&, clang::BinaryOperatorKind, clang::ento::SymExpr const*, clang::QualType) Line | Count | Source | 389 | 726 | BinaryOperator::Opcode op, RHSTYPE rhs, QualType t) { | 390 | 726 | ID.AddInteger((unsigned)ClassKind); | 391 | 726 | ID.AddPointer(getPointer(lhs)); | 392 | 726 | ID.AddInteger(op); | 393 | 726 | ID.AddPointer(getPointer(rhs)); | 394 | 726 | ID.Add(t); | 395 | 726 | } |
clang::ento::BinarySymExprImpl<clang::ento::SymExpr const*, clang::ento::SymExpr const*, (clang::ento::SymExpr::Kind)2>::Profile(llvm::FoldingSetNodeID&, clang::ento::SymExpr const*, clang::BinaryOperatorKind, clang::ento::SymExpr const*, clang::QualType) Line | Count | Source | 389 | 130k | BinaryOperator::Opcode op, RHSTYPE rhs, QualType t) { | 390 | 130k | ID.AddInteger((unsigned)ClassKind); | 391 | 130k | ID.AddPointer(getPointer(lhs)); | 392 | 130k | ID.AddInteger(op); | 393 | 130k | ID.AddPointer(getPointer(rhs)); | 394 | 130k | ID.Add(t); | 395 | 130k | } |
|
396 | | |
397 | 272k | void Profile(llvm::FoldingSetNodeID &ID) override { |
398 | 272k | Profile(ID, LHS, getOpcode(), RHS, getType()); |
399 | 272k | } clang::ento::BinarySymExprImpl<clang::ento::SymExpr const*, llvm::APSInt const&, (clang::ento::SymExpr::Kind)1>::Profile(llvm::FoldingSetNodeID&) Line | Count | Source | 397 | 195k | void Profile(llvm::FoldingSetNodeID &ID) override { | 398 | 195k | Profile(ID, LHS, getOpcode(), RHS, getType()); | 399 | 195k | } |
clang::ento::BinarySymExprImpl<llvm::APSInt const&, clang::ento::SymExpr const*, (clang::ento::SymExpr::Kind)0>::Profile(llvm::FoldingSetNodeID&) Line | Count | Source | 397 | 386 | void Profile(llvm::FoldingSetNodeID &ID) override { | 398 | 386 | Profile(ID, LHS, getOpcode(), RHS, getType()); | 399 | 386 | } |
clang::ento::BinarySymExprImpl<clang::ento::SymExpr const*, clang::ento::SymExpr const*, (clang::ento::SymExpr::Kind)2>::Profile(llvm::FoldingSetNodeID&) Line | Count | Source | 397 | 76.7k | void Profile(llvm::FoldingSetNodeID &ID) override { | 398 | 76.7k | Profile(ID, LHS, getOpcode(), RHS, getType()); | 399 | 76.7k | } |
|
400 | | |
401 | | // Implement isa<T> support. |
402 | 1.25M | static bool classof(const SymExpr *SE) { return SE->getKind() == ClassKind; } clang::ento::BinarySymExprImpl<clang::ento::SymExpr const*, llvm::APSInt const&, (clang::ento::SymExpr::Kind)1>::classof(clang::ento::SymExpr const*) Line | Count | Source | 402 | 714k | static bool classof(const SymExpr *SE) { return SE->getKind() == ClassKind; } |
Unexecuted instantiation: clang::ento::BinarySymExprImpl<llvm::APSInt const&, clang::ento::SymExpr const*, (clang::ento::SymExpr::Kind)0>::classof(clang::ento::SymExpr const*) clang::ento::BinarySymExprImpl<clang::ento::SymExpr const*, clang::ento::SymExpr const*, (clang::ento::SymExpr::Kind)2>::classof(clang::ento::SymExpr const*) Line | Count | Source | 402 | 542k | static bool classof(const SymExpr *SE) { return SE->getKind() == ClassKind; } |
|
403 | | }; |
404 | | |
405 | | /// Represents a symbolic expression like 'x' + 3. |
406 | | using SymIntExpr = BinarySymExprImpl<const SymExpr *, const llvm::APSInt &, |
407 | | SymExpr::Kind::SymIntExprKind>; |
408 | | |
409 | | /// Represents a symbolic expression like 3 - 'x'. |
410 | | using IntSymExpr = BinarySymExprImpl<const llvm::APSInt &, const SymExpr *, |
411 | | SymExpr::Kind::IntSymExprKind>; |
412 | | |
413 | | /// Represents a symbolic expression like 'x' + 'y'. |
414 | | using SymSymExpr = BinarySymExprImpl<const SymExpr *, const SymExpr *, |
415 | | SymExpr::Kind::SymSymExprKind>; |
416 | | |
417 | | class SymbolManager { |
418 | | using DataSetTy = llvm::FoldingSet<SymExpr>; |
419 | | using SymbolDependTy = |
420 | | llvm::DenseMap<SymbolRef, std::unique_ptr<SymbolRefSmallVectorTy>>; |
421 | | |
422 | | DataSetTy DataSet; |
423 | | |
424 | | /// Stores the extra dependencies between symbols: the data should be kept |
425 | | /// alive as long as the key is live. |
426 | | SymbolDependTy SymbolDependencies; |
427 | | |
428 | | unsigned SymbolCounter = 0; |
429 | | llvm::BumpPtrAllocator& BPAlloc; |
430 | | BasicValueFactory &BV; |
431 | | ASTContext &Ctx; |
432 | | |
433 | | public: |
434 | | SymbolManager(ASTContext &ctx, BasicValueFactory &bv, |
435 | | llvm::BumpPtrAllocator& bpalloc) |
436 | 15.3k | : SymbolDependencies(16), BPAlloc(bpalloc), BV(bv), Ctx(ctx) {} |
437 | | |
438 | | static bool canSymbolicate(QualType T); |
439 | | |
440 | | /// Make a unique symbol for MemRegion R according to its kind. |
441 | | const SymbolRegionValue* getRegionValueSymbol(const TypedValueRegion* R); |
442 | | |
443 | | const SymbolConjured* conjureSymbol(const Stmt *E, |
444 | | const LocationContext *LCtx, |
445 | | QualType T, |
446 | | unsigned VisitCount, |
447 | | const void *SymbolTag = nullptr); |
448 | | |
449 | | const SymbolConjured* conjureSymbol(const Expr *E, |
450 | | const LocationContext *LCtx, |
451 | | unsigned VisitCount, |
452 | 0 | const void *SymbolTag = nullptr) { |
453 | 0 | return conjureSymbol(E, LCtx, E->getType(), VisitCount, SymbolTag); |
454 | 0 | } |
455 | | |
456 | | const SymbolDerived *getDerivedSymbol(SymbolRef parentSymbol, |
457 | | const TypedValueRegion *R); |
458 | | |
459 | | const SymbolExtent *getExtentSymbol(const SubRegion *R); |
460 | | |
461 | | /// Creates a metadata symbol associated with a specific region. |
462 | | /// |
463 | | /// VisitCount can be used to differentiate regions corresponding to |
464 | | /// different loop iterations, thus, making the symbol path-dependent. |
465 | | const SymbolMetadata *getMetadataSymbol(const MemRegion *R, const Stmt *S, |
466 | | QualType T, |
467 | | const LocationContext *LCtx, |
468 | | unsigned VisitCount, |
469 | | const void *SymbolTag = nullptr); |
470 | | |
471 | | const SymbolCast* getCastSymbol(const SymExpr *Operand, |
472 | | QualType From, QualType To); |
473 | | |
474 | | const SymIntExpr *getSymIntExpr(const SymExpr *lhs, BinaryOperator::Opcode op, |
475 | | const llvm::APSInt& rhs, QualType t); |
476 | | |
477 | | const SymIntExpr *getSymIntExpr(const SymExpr &lhs, BinaryOperator::Opcode op, |
478 | 0 | const llvm::APSInt& rhs, QualType t) { |
479 | 0 | return getSymIntExpr(&lhs, op, rhs, t); |
480 | 0 | } |
481 | | |
482 | | const IntSymExpr *getIntSymExpr(const llvm::APSInt& lhs, |
483 | | BinaryOperator::Opcode op, |
484 | | const SymExpr *rhs, QualType t); |
485 | | |
486 | | const SymSymExpr *getSymSymExpr(const SymExpr *lhs, BinaryOperator::Opcode op, |
487 | | const SymExpr *rhs, QualType t); |
488 | | |
489 | 1.56k | QualType getType(const SymExpr *SE) const { |
490 | 1.56k | return SE->getType(); |
491 | 1.56k | } |
492 | | |
493 | | /// Add artificial symbol dependency. |
494 | | /// |
495 | | /// The dependent symbol should stay alive as long as the primary is alive. |
496 | | void addSymbolDependency(const SymbolRef Primary, const SymbolRef Dependent); |
497 | | |
498 | | const SymbolRefSmallVectorTy *getDependentSymbols(const SymbolRef Primary); |
499 | | |
500 | 972 | ASTContext &getContext() { return Ctx; } |
501 | 695 | BasicValueFactory &getBasicVals() { return BV; } |
502 | | }; |
503 | | |
504 | | /// A class responsible for cleaning up unused symbols. |
505 | | class SymbolReaper { |
506 | | enum SymbolStatus { |
507 | | NotProcessed, |
508 | | HaveMarkedDependents |
509 | | }; |
510 | | |
511 | | using SymbolSetTy = llvm::DenseSet<SymbolRef>; |
512 | | using SymbolMapTy = llvm::DenseMap<SymbolRef, SymbolStatus>; |
513 | | using RegionSetTy = llvm::DenseSet<const MemRegion *>; |
514 | | |
515 | | SymbolMapTy TheLiving; |
516 | | SymbolSetTy MetadataInUse; |
517 | | |
518 | | RegionSetTy RegionRoots; |
519 | | |
520 | | const StackFrameContext *LCtx; |
521 | | const Stmt *Loc; |
522 | | SymbolManager& SymMgr; |
523 | | StoreRef reapedStore; |
524 | | llvm::DenseMap<const MemRegion *, unsigned> includedRegionCache; |
525 | | |
526 | | public: |
527 | | /// Construct a reaper object, which removes everything which is not |
528 | | /// live before we execute statement s in the given location context. |
529 | | /// |
530 | | /// If the statement is NULL, everything is this and parent contexts is |
531 | | /// considered live. |
532 | | /// If the stack frame context is NULL, everything on stack is considered |
533 | | /// dead. |
534 | | SymbolReaper(const StackFrameContext *Ctx, const Stmt *s, |
535 | | SymbolManager &symmgr, StoreManager &storeMgr) |
536 | 383k | : LCtx(Ctx), Loc(s), SymMgr(symmgr), reapedStore(nullptr, storeMgr) {} |
537 | | |
538 | 0 | const LocationContext *getLocationContext() const { return LCtx; } |
539 | | |
540 | | bool isLive(SymbolRef sym); |
541 | | bool isLiveRegion(const MemRegion *region); |
542 | | bool isLive(const Expr *ExprVal, const LocationContext *LCtx) const; |
543 | | bool isLive(const VarRegion *VR, bool includeStoreBindings = false) const; |
544 | | |
545 | | /// Unconditionally marks a symbol as live. |
546 | | /// |
547 | | /// This should never be |
548 | | /// used by checkers, only by the state infrastructure such as the store and |
549 | | /// environment. Checkers should instead use metadata symbols and markInUse. |
550 | | void markLive(SymbolRef sym); |
551 | | |
552 | | /// Marks a symbol as important to a checker. |
553 | | /// |
554 | | /// For metadata symbols, |
555 | | /// this will keep the symbol alive as long as its associated region is also |
556 | | /// live. For other symbols, this has no effect; checkers are not permitted |
557 | | /// to influence the life of other symbols. This should be used before any |
558 | | /// symbol marking has occurred, i.e. in the MarkLiveSymbols callback. |
559 | | void markInUse(SymbolRef sym); |
560 | | |
561 | | using region_iterator = RegionSetTy::const_iterator; |
562 | | |
563 | 383k | region_iterator region_begin() const { return RegionRoots.begin(); } |
564 | 383k | region_iterator region_end() const { return RegionRoots.end(); } |
565 | | |
566 | | /// Returns whether or not a symbol has been confirmed dead. |
567 | | /// |
568 | | /// This should only be called once all marking of dead symbols has completed. |
569 | | /// (For checkers, this means only in the checkDeadSymbols callback.) |
570 | 1.92M | bool isDead(SymbolRef sym) { |
571 | 1.92M | return !isLive(sym); |
572 | 1.92M | } |
573 | | |
574 | | void markLive(const MemRegion *region); |
575 | | void markElementIndicesLive(const MemRegion *region); |
576 | | |
577 | | /// Set to the value of the symbolic store after |
578 | | /// StoreManager::removeDeadBindings has been called. |
579 | 383k | void setReapedStore(StoreRef st) { reapedStore = st; } |
580 | | |
581 | | private: |
582 | | /// Mark the symbols dependent on the input symbol as live. |
583 | | void markDependentsLive(SymbolRef sym); |
584 | | }; |
585 | | |
586 | | class SymbolVisitor { |
587 | | protected: |
588 | | ~SymbolVisitor() = default; |
589 | | |
590 | | public: |
591 | 392k | SymbolVisitor() = default; |
592 | | SymbolVisitor(const SymbolVisitor &) = default; |
593 | 0 | SymbolVisitor(SymbolVisitor &&) {} |
594 | | |
595 | | /// A visitor method invoked by ProgramStateManager::scanReachableSymbols. |
596 | | /// |
597 | | /// The method returns \c true if symbols should continue be scanned and \c |
598 | | /// false otherwise. |
599 | | virtual bool VisitSymbol(SymbolRef sym) = 0; |
600 | 1.77k | virtual bool VisitMemRegion(const MemRegion *) { return true; } |
601 | | }; |
602 | | |
603 | | } // namespace ento |
604 | | |
605 | | } // namespace clang |
606 | | |
607 | | #endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SYMBOLMANAGER_H |