/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/lib/StaticAnalyzer/Core/RegionStore.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | //== RegionStore.cpp - Field-sensitive store model --------------*- 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 a basic region store model. In this model, we do have field |
10 | | // sensitivity. But we assume nothing about the heap shape. So recursive data |
11 | | // structures are largely ignored. Basically we do 1-limiting analysis. |
12 | | // Parameter pointers are assumed with no aliasing. Pointee objects of |
13 | | // parameters are created lazily. |
14 | | // |
15 | | //===----------------------------------------------------------------------===// |
16 | | |
17 | | #include "clang/AST/Attr.h" |
18 | | #include "clang/AST/CharUnits.h" |
19 | | #include "clang/ASTMatchers/ASTMatchFinder.h" |
20 | | #include "clang/Analysis/Analyses/LiveVariables.h" |
21 | | #include "clang/Analysis/AnalysisDeclContext.h" |
22 | | #include "clang/Basic/JsonSupport.h" |
23 | | #include "clang/Basic/TargetInfo.h" |
24 | | #include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h" |
25 | | #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" |
26 | | #include "clang/StaticAnalyzer/Core/PathSensitive/DynamicSize.h" |
27 | | #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" |
28 | | #include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h" |
29 | | #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" |
30 | | #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h" |
31 | | #include "llvm/ADT/ImmutableMap.h" |
32 | | #include "llvm/ADT/Optional.h" |
33 | | #include "llvm/Support/raw_ostream.h" |
34 | | #include <utility> |
35 | | |
36 | | using namespace clang; |
37 | | using namespace ento; |
38 | | |
39 | | //===----------------------------------------------------------------------===// |
40 | | // Representation of binding keys. |
41 | | //===----------------------------------------------------------------------===// |
42 | | |
43 | | namespace { |
44 | | class BindingKey { |
45 | | public: |
46 | | enum Kind { Default = 0x0, Direct = 0x1 }; |
47 | | private: |
48 | | enum { Symbolic = 0x2 }; |
49 | | |
50 | | llvm::PointerIntPair<const MemRegion *, 2> P; |
51 | | uint64_t Data; |
52 | | |
53 | | /// Create a key for a binding to region \p r, which has a symbolic offset |
54 | | /// from region \p Base. |
55 | | explicit BindingKey(const SubRegion *r, const SubRegion *Base, Kind k) |
56 | 90.8k | : P(r, k | Symbolic), Data(reinterpret_cast<uintptr_t>(Base)) { |
57 | 90.8k | assert(r && Base && "Must have known regions."); |
58 | 90.8k | assert(getConcreteOffsetRegion() == Base && "Failed to store base region"); |
59 | 90.8k | } |
60 | | |
61 | | /// Create a key for a binding at \p offset from base region \p r. |
62 | | explicit BindingKey(const MemRegion *r, uint64_t offset, Kind k) |
63 | 1.42M | : P(r, k), Data(offset) { |
64 | 1.42M | assert(r && "Must have known regions."); |
65 | 1.42M | assert(getOffset() == offset && "Failed to store offset"); |
66 | 1.42M | assert((r == r->getBaseRegion() || isa<ObjCIvarRegion>(r) || |
67 | 1.42M | isa <CXXDerivedObjectRegion>(r)) && |
68 | 1.42M | "Not a base"); |
69 | 1.42M | } |
70 | | public: |
71 | | |
72 | 377k | bool isDirect() const { return P.getInt() & Direct; } |
73 | 3.46M | bool hasSymbolicOffset() const { return P.getInt() & Symbolic; } |
74 | | |
75 | 3.26M | const MemRegion *getRegion() const { return P.getPointer(); } |
76 | 1.68M | uint64_t getOffset() const { |
77 | 1.68M | assert(!hasSymbolicOffset()); |
78 | 1.68M | return Data; |
79 | 1.68M | } |
80 | | |
81 | 182k | const SubRegion *getConcreteOffsetRegion() const { |
82 | 182k | assert(hasSymbolicOffset()); |
83 | 182k | return reinterpret_cast<const SubRegion *>(static_cast<uintptr_t>(Data)); |
84 | 182k | } |
85 | | |
86 | 1.51M | const MemRegion *getBaseRegion() const { |
87 | 1.51M | if (hasSymbolicOffset()) |
88 | 90.8k | return getConcreteOffsetRegion()->getBaseRegion(); |
89 | 1.42M | return getRegion()->getBaseRegion(); |
90 | 1.42M | } |
91 | | |
92 | 315k | void Profile(llvm::FoldingSetNodeID& ID) const { |
93 | 315k | ID.AddPointer(P.getOpaqueValue()); |
94 | 315k | ID.AddInteger(Data); |
95 | 315k | } |
96 | | |
97 | | static BindingKey Make(const MemRegion *R, Kind k); |
98 | | |
99 | 126k | bool operator<(const BindingKey &X) const { |
100 | 126k | if (P.getOpaqueValue() < X.P.getOpaqueValue()) |
101 | 48.5k | return true; |
102 | 77.4k | if (P.getOpaqueValue() > X.P.getOpaqueValue()) |
103 | 23.8k | return false; |
104 | 53.6k | return Data < X.Data; |
105 | 53.6k | } |
106 | | |
107 | 652k | bool operator==(const BindingKey &X) const { |
108 | 652k | return P.getOpaqueValue() == X.P.getOpaqueValue() && |
109 | 580k | Data == X.Data; |
110 | 652k | } |
111 | | |
112 | | LLVM_DUMP_METHOD void dump() const; |
113 | | }; |
114 | | } // end anonymous namespace |
115 | | |
116 | 1.51M | BindingKey BindingKey::Make(const MemRegion *R, Kind k) { |
117 | 1.51M | const RegionOffset &RO = R->getAsOffset(); |
118 | 1.51M | if (RO.hasSymbolicOffset()) |
119 | 90.8k | return BindingKey(cast<SubRegion>(R), cast<SubRegion>(RO.getRegion()), k); |
120 | | |
121 | 1.42M | return BindingKey(RO.getRegion(), RO.getOffset(), k); |
122 | 1.42M | } |
123 | | |
124 | | namespace llvm { |
125 | 154 | static inline raw_ostream &operator<<(raw_ostream &Out, BindingKey K) { |
126 | 94 | Out << "\"kind\": \"" << (K.isDirect() ? "Direct" : "Default"60 ) |
127 | 154 | << "\", \"offset\": "; |
128 | | |
129 | 154 | if (!K.hasSymbolicOffset()) |
130 | 154 | Out << K.getOffset(); |
131 | 0 | else |
132 | 0 | Out << "null"; |
133 | | |
134 | 154 | return Out; |
135 | 154 | } |
136 | | |
137 | | } // namespace llvm |
138 | | |
139 | | #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
140 | 0 | void BindingKey::dump() const { llvm::errs() << *this; } |
141 | | #endif |
142 | | |
143 | | //===----------------------------------------------------------------------===// |
144 | | // Actual Store type. |
145 | | //===----------------------------------------------------------------------===// |
146 | | |
147 | | typedef llvm::ImmutableMap<BindingKey, SVal> ClusterBindings; |
148 | | typedef llvm::ImmutableMapRef<BindingKey, SVal> ClusterBindingsRef; |
149 | | typedef std::pair<BindingKey, SVal> BindingPair; |
150 | | |
151 | | typedef llvm::ImmutableMap<const MemRegion *, ClusterBindings> |
152 | | RegionBindings; |
153 | | |
154 | | namespace { |
155 | | class RegionBindingsRef : public llvm::ImmutableMapRef<const MemRegion *, |
156 | | ClusterBindings> { |
157 | | ClusterBindings::Factory *CBFactory; |
158 | | |
159 | | // This flag indicates whether the current bindings are within the analysis |
160 | | // that has started from main(). It affects how we perform loads from |
161 | | // global variables that have initializers: if we have observed the |
162 | | // program execution from the start and we know that these variables |
163 | | // have not been overwritten yet, we can be sure that their initializers |
164 | | // are still relevant. This flag never gets changed when the bindings are |
165 | | // updated, so it could potentially be moved into RegionStoreManager |
166 | | // (as if it's the same bindings but a different loading procedure) |
167 | | // however that would have made the manager needlessly stateful. |
168 | | bool IsMainAnalysis; |
169 | | |
170 | | public: |
171 | | typedef llvm::ImmutableMapRef<const MemRegion *, ClusterBindings> |
172 | | ParentTy; |
173 | | |
174 | | RegionBindingsRef(ClusterBindings::Factory &CBFactory, |
175 | | const RegionBindings::TreeTy *T, |
176 | | RegionBindings::TreeTy::Factory *F, |
177 | | bool IsMainAnalysis) |
178 | | : llvm::ImmutableMapRef<const MemRegion *, ClusterBindings>(T, F), |
179 | 11.7M | CBFactory(&CBFactory), IsMainAnalysis(IsMainAnalysis) {} |
180 | | |
181 | | RegionBindingsRef(const ParentTy &P, |
182 | | ClusterBindings::Factory &CBFactory, |
183 | | bool IsMainAnalysis) |
184 | | : llvm::ImmutableMapRef<const MemRegion *, ClusterBindings>(P), |
185 | 596k | CBFactory(&CBFactory), IsMainAnalysis(IsMainAnalysis) {} |
186 | | |
187 | 286k | RegionBindingsRef add(key_type_ref K, data_type_ref D) const { |
188 | 286k | return RegionBindingsRef(static_cast<const ParentTy *>(this)->add(K, D), |
189 | 286k | *CBFactory, IsMainAnalysis); |
190 | 286k | } |
191 | | |
192 | 296k | RegionBindingsRef remove(key_type_ref K) const { |
193 | 296k | return RegionBindingsRef(static_cast<const ParentTy *>(this)->remove(K), |
194 | 296k | *CBFactory, IsMainAnalysis); |
195 | 296k | } |
196 | | |
197 | | RegionBindingsRef addBinding(BindingKey K, SVal V) const; |
198 | | |
199 | | RegionBindingsRef addBinding(const MemRegion *R, |
200 | | BindingKey::Kind k, SVal V) const; |
201 | | |
202 | | const SVal *lookup(BindingKey K) const; |
203 | | const SVal *lookup(const MemRegion *R, BindingKey::Kind k) const; |
204 | | using llvm::ImmutableMapRef<const MemRegion *, ClusterBindings>::lookup; |
205 | | |
206 | | RegionBindingsRef removeBinding(BindingKey K); |
207 | | |
208 | | RegionBindingsRef removeBinding(const MemRegion *R, |
209 | | BindingKey::Kind k); |
210 | | |
211 | 60.5k | RegionBindingsRef removeBinding(const MemRegion *R) { |
212 | 60.5k | return removeBinding(R, BindingKey::Direct). |
213 | 60.5k | removeBinding(R, BindingKey::Default); |
214 | 60.5k | } |
215 | | |
216 | | Optional<SVal> getDirectBinding(const MemRegion *R) const; |
217 | | |
218 | | /// getDefaultBinding - Returns an SVal* representing an optional default |
219 | | /// binding associated with a region and its subregions. |
220 | | Optional<SVal> getDefaultBinding(const MemRegion *R) const; |
221 | | |
222 | | /// Return the internal tree as a Store. |
223 | 636k | Store asStore() const { |
224 | 636k | llvm::PointerIntPair<Store, 1, bool> Ptr = { |
225 | 636k | asImmutableMap().getRootWithoutRetain(), IsMainAnalysis}; |
226 | 636k | return reinterpret_cast<Store>(Ptr.getOpaqueValue()); |
227 | 636k | } |
228 | | |
229 | 24.7k | bool isMainAnalysis() const { |
230 | 24.7k | return IsMainAnalysis; |
231 | 24.7k | } |
232 | | |
233 | | void printJson(raw_ostream &Out, const char *NL = "\n", |
234 | 86 | unsigned int Space = 0, bool IsDot = false) const { |
235 | 236 | for (iterator I = begin(); I != end(); ++I150 ) { |
236 | | // TODO: We might need a .printJson for I.getKey() as well. |
237 | 150 | Indent(Out, Space, IsDot) |
238 | 150 | << "{ \"cluster\": \"" << I.getKey() << "\", \"pointer\": \"" |
239 | 150 | << (const void *)I.getKey() << "\", \"items\": [" << NL; |
240 | | |
241 | 150 | ++Space; |
242 | 150 | const ClusterBindings &CB = I.getData(); |
243 | 304 | for (ClusterBindings::iterator CI = CB.begin(); CI != CB.end(); ++CI154 ) { |
244 | 154 | Indent(Out, Space, IsDot) << "{ " << CI.getKey() << ", \"value\": "; |
245 | 154 | CI.getData().printJson(Out, /*AddQuotes=*/true); |
246 | 154 | Out << " }"; |
247 | 154 | if (std::next(CI) != CB.end()) |
248 | 4 | Out << ','; |
249 | 154 | Out << NL; |
250 | 154 | } |
251 | | |
252 | 150 | --Space; |
253 | 150 | Indent(Out, Space, IsDot) << "]}"; |
254 | 150 | if (std::next(I) != end()) |
255 | 64 | Out << ','; |
256 | 150 | Out << NL; |
257 | 150 | } |
258 | 86 | } |
259 | | |
260 | 0 | LLVM_DUMP_METHOD void dump() const { printJson(llvm::errs()); } |
261 | | }; |
262 | | } // end anonymous namespace |
263 | | |
264 | | typedef const RegionBindingsRef& RegionBindingsConstRef; |
265 | | |
266 | 416k | Optional<SVal> RegionBindingsRef::getDirectBinding(const MemRegion *R) const { |
267 | 416k | return Optional<SVal>::create(lookup(R, BindingKey::Direct)); |
268 | 416k | } |
269 | | |
270 | 478k | Optional<SVal> RegionBindingsRef::getDefaultBinding(const MemRegion *R) const { |
271 | 478k | return Optional<SVal>::create(lookup(R, BindingKey::Default)); |
272 | 478k | } |
273 | | |
274 | 265k | RegionBindingsRef RegionBindingsRef::addBinding(BindingKey K, SVal V) const { |
275 | 265k | const MemRegion *Base = K.getBaseRegion(); |
276 | | |
277 | 265k | const ClusterBindings *ExistingCluster = lookup(Base); |
278 | 265k | ClusterBindings Cluster = |
279 | 243k | (ExistingCluster ? *ExistingCluster21.7k : CBFactory->getEmptyMap()); |
280 | | |
281 | 265k | ClusterBindings NewCluster = CBFactory->add(Cluster, K, V); |
282 | 265k | return add(Base, NewCluster); |
283 | 265k | } |
284 | | |
285 | | |
286 | | RegionBindingsRef RegionBindingsRef::addBinding(const MemRegion *R, |
287 | | BindingKey::Kind k, |
288 | 28.7k | SVal V) const { |
289 | 28.7k | return addBinding(BindingKey::Make(R, k), V); |
290 | 28.7k | } |
291 | | |
292 | 955k | const SVal *RegionBindingsRef::lookup(BindingKey K) const { |
293 | 955k | const ClusterBindings *Cluster = lookup(K.getBaseRegion()); |
294 | 955k | if (!Cluster) |
295 | 587k | return nullptr; |
296 | 367k | return Cluster->lookup(K); |
297 | 367k | } |
298 | | |
299 | | const SVal *RegionBindingsRef::lookup(const MemRegion *R, |
300 | 955k | BindingKey::Kind k) const { |
301 | 955k | return lookup(BindingKey::Make(R, k)); |
302 | 955k | } |
303 | | |
304 | 121k | RegionBindingsRef RegionBindingsRef::removeBinding(BindingKey K) { |
305 | 121k | const MemRegion *Base = K.getBaseRegion(); |
306 | 121k | const ClusterBindings *Cluster = lookup(Base); |
307 | 121k | if (!Cluster) |
308 | 121k | return *this; |
309 | | |
310 | 89 | ClusterBindings NewCluster = CBFactory->remove(*Cluster, K); |
311 | 89 | if (NewCluster.isEmpty()) |
312 | 4 | return remove(Base); |
313 | 85 | return add(Base, NewCluster); |
314 | 85 | } |
315 | | |
316 | | RegionBindingsRef RegionBindingsRef::removeBinding(const MemRegion *R, |
317 | 121k | BindingKey::Kind k){ |
318 | 121k | return removeBinding(BindingKey::Make(R, k)); |
319 | 121k | } |
320 | | |
321 | | //===----------------------------------------------------------------------===// |
322 | | // Fine-grained control of RegionStoreManager. |
323 | | //===----------------------------------------------------------------------===// |
324 | | |
325 | | namespace { |
326 | | struct minimal_features_tag {}; |
327 | | struct maximal_features_tag {}; |
328 | | |
329 | | class RegionStoreFeatures { |
330 | | bool SupportsFields; |
331 | | public: |
332 | | RegionStoreFeatures(minimal_features_tag) : |
333 | 0 | SupportsFields(false) {} |
334 | | |
335 | | RegionStoreFeatures(maximal_features_tag) : |
336 | 13.7k | SupportsFields(true) {} |
337 | | |
338 | 0 | void enableFields(bool t) { SupportsFields = t; } |
339 | | |
340 | 23.7k | bool supportsFields() const { return SupportsFields; } |
341 | | }; |
342 | | } |
343 | | |
344 | | //===----------------------------------------------------------------------===// |
345 | | // Main RegionStore logic. |
346 | | //===----------------------------------------------------------------------===// |
347 | | |
348 | | namespace { |
349 | | class InvalidateRegionsWorker; |
350 | | |
351 | | class RegionStoreManager : public StoreManager { |
352 | | public: |
353 | | const RegionStoreFeatures Features; |
354 | | |
355 | | RegionBindings::Factory RBFactory; |
356 | | mutable ClusterBindings::Factory CBFactory; |
357 | | |
358 | | typedef std::vector<SVal> SValListTy; |
359 | | private: |
360 | | typedef llvm::DenseMap<const LazyCompoundValData *, |
361 | | SValListTy> LazyBindingsMapTy; |
362 | | LazyBindingsMapTy LazyBindingsMap; |
363 | | |
364 | | /// The largest number of fields a struct can have and still be |
365 | | /// considered "small". |
366 | | /// |
367 | | /// This is currently used to decide whether or not it is worth "forcing" a |
368 | | /// LazyCompoundVal on bind. |
369 | | /// |
370 | | /// This is controlled by 'region-store-small-struct-limit' option. |
371 | | /// To disable all small-struct-dependent behavior, set the option to "0". |
372 | | unsigned SmallStructLimit; |
373 | | |
374 | | /// A helper used to populate the work list with the given set of |
375 | | /// regions. |
376 | | void populateWorkList(InvalidateRegionsWorker &W, |
377 | | ArrayRef<SVal> Values, |
378 | | InvalidatedRegions *TopLevelRegions); |
379 | | |
380 | | public: |
381 | | RegionStoreManager(ProgramStateManager& mgr, const RegionStoreFeatures &f) |
382 | | : StoreManager(mgr), Features(f), |
383 | | RBFactory(mgr.getAllocator()), CBFactory(mgr.getAllocator()), |
384 | 13.7k | SmallStructLimit(0) { |
385 | 13.7k | ExprEngine &Eng = StateMgr.getOwningEngine(); |
386 | 13.7k | AnalyzerOptions &Options = Eng.getAnalysisManager().options; |
387 | 13.7k | SmallStructLimit = Options.RegionStoreSmallStructLimit; |
388 | 13.7k | } |
389 | | |
390 | | |
391 | | /// setImplicitDefaultValue - Set the default binding for the provided |
392 | | /// MemRegion to the value implicitly defined for compound literals when |
393 | | /// the value is not specified. |
394 | | RegionBindingsRef setImplicitDefaultValue(RegionBindingsConstRef B, |
395 | | const MemRegion *R, QualType T); |
396 | | |
397 | | /// ArrayToPointer - Emulates the "decay" of an array to a pointer |
398 | | /// type. 'Array' represents the lvalue of the array being decayed |
399 | | /// to a pointer, and the returned SVal represents the decayed |
400 | | /// version of that lvalue (i.e., a pointer to the first element of |
401 | | /// the array). This is called by ExprEngine when evaluating |
402 | | /// casts from arrays to pointers. |
403 | | SVal ArrayToPointer(Loc Array, QualType ElementTy) override; |
404 | | |
405 | | /// Creates the Store that correctly represents memory contents before |
406 | | /// the beginning of the analysis of the given top-level stack frame. |
407 | 13.7k | StoreRef getInitialStore(const LocationContext *InitLoc) override { |
408 | 13.7k | bool IsMainAnalysis = false; |
409 | 13.7k | if (const auto *FD = dyn_cast<FunctionDecl>(InitLoc->getDecl())) |
410 | 12.4k | IsMainAnalysis = FD->isMain() && !Ctx.getLangOpts().CPlusPlus59 ; |
411 | 13.7k | return StoreRef(RegionBindingsRef( |
412 | 13.7k | RegionBindingsRef::ParentTy(RBFactory.getEmptyMap(), RBFactory), |
413 | 13.7k | CBFactory, IsMainAnalysis).asStore(), *this); |
414 | 13.7k | } |
415 | | |
416 | | //===-------------------------------------------------------------------===// |
417 | | // Binding values to regions. |
418 | | //===-------------------------------------------------------------------===// |
419 | | RegionBindingsRef invalidateGlobalRegion(MemRegion::Kind K, |
420 | | const Expr *Ex, |
421 | | unsigned Count, |
422 | | const LocationContext *LCtx, |
423 | | RegionBindingsRef B, |
424 | | InvalidatedRegions *Invalidated); |
425 | | |
426 | | StoreRef invalidateRegions(Store store, |
427 | | ArrayRef<SVal> Values, |
428 | | const Expr *E, unsigned Count, |
429 | | const LocationContext *LCtx, |
430 | | const CallEvent *Call, |
431 | | InvalidatedSymbols &IS, |
432 | | RegionAndSymbolInvalidationTraits &ITraits, |
433 | | InvalidatedRegions *Invalidated, |
434 | | InvalidatedRegions *InvalidatedTopLevel) override; |
435 | | |
436 | | bool scanReachableSymbols(Store S, const MemRegion *R, |
437 | | ScanReachableSymbols &Callbacks) override; |
438 | | |
439 | | RegionBindingsRef removeSubRegionBindings(RegionBindingsConstRef B, |
440 | | const SubRegion *R); |
441 | | |
442 | | public: // Part of public interface to class. |
443 | | |
444 | 172k | StoreRef Bind(Store store, Loc LV, SVal V) override { |
445 | 172k | return StoreRef(bind(getRegionBindings(store), LV, V).asStore(), *this); |
446 | 172k | } |
447 | | |
448 | | RegionBindingsRef bind(RegionBindingsConstRef B, Loc LV, SVal V); |
449 | | |
450 | | // BindDefaultInitial is only used to initialize a region with |
451 | | // a default value. |
452 | | StoreRef BindDefaultInitial(Store store, const MemRegion *R, |
453 | 750 | SVal V) override { |
454 | 750 | RegionBindingsRef B = getRegionBindings(store); |
455 | | // Use other APIs when you have to wipe the region that was initialized |
456 | | // earlier. |
457 | 750 | assert(!(B.getDefaultBinding(R) || B.getDirectBinding(R)) && |
458 | 750 | "Double initialization!"); |
459 | 750 | B = B.addBinding(BindingKey::Make(R, BindingKey::Default), V); |
460 | 750 | return StoreRef(B.asImmutableMap().getRootWithoutRetain(), *this); |
461 | 750 | } |
462 | | |
463 | | // BindDefaultZero is used for zeroing constructors that may accidentally |
464 | | // overwrite existing bindings. |
465 | 2.04k | StoreRef BindDefaultZero(Store store, const MemRegion *R) override { |
466 | | // FIXME: The offsets of empty bases can be tricky because of |
467 | | // of the so called "empty base class optimization". |
468 | | // If a base class has been optimized out |
469 | | // we should not try to create a binding, otherwise we should. |
470 | | // Unfortunately, at the moment ASTRecordLayout doesn't expose |
471 | | // the actual sizes of the empty bases |
472 | | // and trying to infer them from offsets/alignments |
473 | | // seems to be error-prone and non-trivial because of the trailing padding. |
474 | | // As a temporary mitigation we don't create bindings for empty bases. |
475 | 2.04k | if (const auto *BR = dyn_cast<CXXBaseObjectRegion>(R)) |
476 | 16 | if (BR->getDecl()->isEmpty()) |
477 | 4 | return StoreRef(store, *this); |
478 | | |
479 | 2.03k | RegionBindingsRef B = getRegionBindings(store); |
480 | 2.03k | SVal V = svalBuilder.makeZeroVal(Ctx.CharTy); |
481 | 2.03k | B = removeSubRegionBindings(B, cast<SubRegion>(R)); |
482 | 2.03k | B = B.addBinding(BindingKey::Make(R, BindingKey::Default), V); |
483 | 2.03k | return StoreRef(B.asImmutableMap().getRootWithoutRetain(), *this); |
484 | 2.03k | } |
485 | | |
486 | | /// Attempt to extract the fields of \p LCV and bind them to the struct region |
487 | | /// \p R. |
488 | | /// |
489 | | /// This path is used when it seems advantageous to "force" loading the values |
490 | | /// within a LazyCompoundVal to bind memberwise to the struct region, rather |
491 | | /// than using a Default binding at the base of the entire region. This is a |
492 | | /// heuristic attempting to avoid building long chains of LazyCompoundVals. |
493 | | /// |
494 | | /// \returns The updated store bindings, or \c None if binding non-lazily |
495 | | /// would be too expensive. |
496 | | Optional<RegionBindingsRef> tryBindSmallStruct(RegionBindingsConstRef B, |
497 | | const TypedValueRegion *R, |
498 | | const RecordDecl *RD, |
499 | | nonloc::LazyCompoundVal LCV); |
500 | | |
501 | | /// BindStruct - Bind a compound value to a structure. |
502 | | RegionBindingsRef bindStruct(RegionBindingsConstRef B, |
503 | | const TypedValueRegion* R, SVal V); |
504 | | |
505 | | /// BindVector - Bind a compound value to a vector. |
506 | | RegionBindingsRef bindVector(RegionBindingsConstRef B, |
507 | | const TypedValueRegion* R, SVal V); |
508 | | |
509 | | RegionBindingsRef bindArray(RegionBindingsConstRef B, |
510 | | const TypedValueRegion* R, |
511 | | SVal V); |
512 | | |
513 | | /// Clears out all bindings in the given region and assigns a new value |
514 | | /// as a Default binding. |
515 | | RegionBindingsRef bindAggregate(RegionBindingsConstRef B, |
516 | | const TypedRegion *R, |
517 | | SVal DefaultVal); |
518 | | |
519 | | /// Create a new store with the specified binding removed. |
520 | | /// \param ST the original store, that is the basis for the new store. |
521 | | /// \param L the location whose binding should be removed. |
522 | | StoreRef killBinding(Store ST, Loc L) override; |
523 | | |
524 | 5.41M | void incrementReferenceCount(Store store) override { |
525 | 5.41M | getRegionBindings(store).manualRetain(); |
526 | 5.41M | } |
527 | | |
528 | | /// If the StoreManager supports it, decrement the reference count of |
529 | | /// the specified Store object. If the reference count hits 0, the memory |
530 | | /// associated with the object is recycled. |
531 | 4.33M | void decrementReferenceCount(Store store) override { |
532 | 4.33M | getRegionBindings(store).manualRelease(); |
533 | 4.33M | } |
534 | | |
535 | | bool includedInBindings(Store store, const MemRegion *region) const override; |
536 | | |
537 | | /// Return the value bound to specified location in a given state. |
538 | | /// |
539 | | /// The high level logic for this method is this: |
540 | | /// getBinding (L) |
541 | | /// if L has binding |
542 | | /// return L's binding |
543 | | /// else if L is in killset |
544 | | /// return unknown |
545 | | /// else |
546 | | /// if L is on stack or heap |
547 | | /// return undefined |
548 | | /// else |
549 | | /// return symbolic |
550 | 514k | SVal getBinding(Store S, Loc L, QualType T) override { |
551 | 514k | return getBinding(getRegionBindings(S), L, T); |
552 | 514k | } |
553 | | |
554 | 15 | Optional<SVal> getDefaultBinding(Store S, const MemRegion *R) override { |
555 | 15 | RegionBindingsRef B = getRegionBindings(S); |
556 | | // Default bindings are always applied over a base region so look up the |
557 | | // base region's default binding, otherwise the lookup will fail when R |
558 | | // is at an offset from R->getBaseRegion(). |
559 | 15 | return B.getDefaultBinding(R->getBaseRegion()); |
560 | 15 | } |
561 | | |
562 | | SVal getBinding(RegionBindingsConstRef B, Loc L, QualType T = QualType()); |
563 | | |
564 | | SVal getBindingForElement(RegionBindingsConstRef B, const ElementRegion *R); |
565 | | |
566 | | SVal getBindingForField(RegionBindingsConstRef B, const FieldRegion *R); |
567 | | |
568 | | SVal getBindingForObjCIvar(RegionBindingsConstRef B, const ObjCIvarRegion *R); |
569 | | |
570 | | SVal getBindingForVar(RegionBindingsConstRef B, const VarRegion *R); |
571 | | |
572 | | SVal getBindingForLazySymbol(const TypedValueRegion *R); |
573 | | |
574 | | SVal getBindingForFieldOrElementCommon(RegionBindingsConstRef B, |
575 | | const TypedValueRegion *R, |
576 | | QualType Ty); |
577 | | |
578 | | SVal getLazyBinding(const SubRegion *LazyBindingRegion, |
579 | | RegionBindingsRef LazyBinding); |
580 | | |
581 | | /// Get bindings for the values in a struct and return a CompoundVal, used |
582 | | /// when doing struct copy: |
583 | | /// struct s x, y; |
584 | | /// x = y; |
585 | | /// y's value is retrieved by this method. |
586 | | SVal getBindingForStruct(RegionBindingsConstRef B, const TypedValueRegion *R); |
587 | | SVal getBindingForArray(RegionBindingsConstRef B, const TypedValueRegion *R); |
588 | | NonLoc createLazyBinding(RegionBindingsConstRef B, const TypedValueRegion *R); |
589 | | |
590 | | /// Used to lazily generate derived symbols for bindings that are defined |
591 | | /// implicitly by default bindings in a super region. |
592 | | /// |
593 | | /// Note that callers may need to specially handle LazyCompoundVals, which |
594 | | /// are returned as is in case the caller needs to treat them differently. |
595 | | Optional<SVal> getBindingForDerivedDefaultValue(RegionBindingsConstRef B, |
596 | | const MemRegion *superR, |
597 | | const TypedValueRegion *R, |
598 | | QualType Ty); |
599 | | |
600 | | /// Get the state and region whose binding this region \p R corresponds to. |
601 | | /// |
602 | | /// If there is no lazy binding for \p R, the returned value will have a null |
603 | | /// \c second. Note that a null pointer can represents a valid Store. |
604 | | std::pair<Store, const SubRegion *> |
605 | | findLazyBinding(RegionBindingsConstRef B, const SubRegion *R, |
606 | | const SubRegion *originalRegion); |
607 | | |
608 | | /// Returns the cached set of interesting SVals contained within a lazy |
609 | | /// binding. |
610 | | /// |
611 | | /// The precise value of "interesting" is determined for the purposes of |
612 | | /// RegionStore's internal analysis. It must always contain all regions and |
613 | | /// symbols, but may omit constants and other kinds of SVal. |
614 | | const SValListTy &getInterestingValues(nonloc::LazyCompoundVal LCV); |
615 | | |
616 | | //===------------------------------------------------------------------===// |
617 | | // State pruning. |
618 | | //===------------------------------------------------------------------===// |
619 | | |
620 | | /// removeDeadBindings - Scans the RegionStore of 'state' for dead values. |
621 | | /// It returns a new Store with these values removed. |
622 | | StoreRef removeDeadBindings(Store store, const StackFrameContext *LCtx, |
623 | | SymbolReaper& SymReaper) override; |
624 | | |
625 | | //===------------------------------------------------------------------===// |
626 | | // Utility methods. |
627 | | //===------------------------------------------------------------------===// |
628 | | |
629 | 11.7M | RegionBindingsRef getRegionBindings(Store store) const { |
630 | 11.7M | llvm::PointerIntPair<Store, 1, bool> Ptr; |
631 | 11.7M | Ptr.setFromOpaqueValue(const_cast<void *>(store)); |
632 | 11.7M | return RegionBindingsRef( |
633 | 11.7M | CBFactory, |
634 | 11.7M | static_cast<const RegionBindings::TreeTy *>(Ptr.getPointer()), |
635 | 11.7M | RBFactory.getTreeFactory(), |
636 | 11.7M | Ptr.getInt()); |
637 | 11.7M | } |
638 | | |
639 | | void printJson(raw_ostream &Out, Store S, const char *NL = "\n", |
640 | | unsigned int Space = 0, bool IsDot = false) const override; |
641 | | |
642 | 77.1k | void iterBindings(Store store, BindingsHandler& f) override { |
643 | 77.1k | RegionBindingsRef B = getRegionBindings(store); |
644 | 367k | for (RegionBindingsRef::iterator I = B.begin(), E = B.end(); I != E; ++I290k ) { |
645 | 290k | const ClusterBindings &Cluster = I.getData(); |
646 | 290k | for (ClusterBindings::iterator CI = Cluster.begin(), CE = Cluster.end(); |
647 | 655k | CI != CE; ++CI365k ) { |
648 | 365k | const BindingKey &K = CI.getKey(); |
649 | 365k | if (!K.isDirect()) |
650 | 157k | continue; |
651 | 207k | if (const SubRegion *R = dyn_cast<SubRegion>(K.getRegion())) { |
652 | | // FIXME: Possibly incorporate the offset? |
653 | 207k | if (!f.HandleBinding(*this, store, R, CI.getData())) |
654 | 544 | return; |
655 | 207k | } |
656 | 207k | } |
657 | 290k | } |
658 | 77.1k | } |
659 | | }; |
660 | | |
661 | | } // end anonymous namespace |
662 | | |
663 | | //===----------------------------------------------------------------------===// |
664 | | // RegionStore creation. |
665 | | //===----------------------------------------------------------------------===// |
666 | | |
667 | | std::unique_ptr<StoreManager> |
668 | 13.7k | ento::CreateRegionStoreManager(ProgramStateManager &StMgr) { |
669 | 13.7k | RegionStoreFeatures F = maximal_features_tag(); |
670 | 13.7k | return std::make_unique<RegionStoreManager>(StMgr, F); |
671 | 13.7k | } |
672 | | |
673 | | std::unique_ptr<StoreManager> |
674 | 0 | ento::CreateFieldsOnlyRegionStoreManager(ProgramStateManager &StMgr) { |
675 | 0 | RegionStoreFeatures F = minimal_features_tag(); |
676 | 0 | F.enableFields(true); |
677 | 0 | return std::make_unique<RegionStoreManager>(StMgr, F); |
678 | 0 | } |
679 | | |
680 | | |
681 | | //===----------------------------------------------------------------------===// |
682 | | // Region Cluster analysis. |
683 | | //===----------------------------------------------------------------------===// |
684 | | |
685 | | namespace { |
686 | | /// Used to determine which global regions are automatically included in the |
687 | | /// initial worklist of a ClusterAnalysis. |
688 | | enum GlobalsFilterKind { |
689 | | /// Don't include any global regions. |
690 | | GFK_None, |
691 | | /// Only include system globals. |
692 | | GFK_SystemOnly, |
693 | | /// Include all global regions. |
694 | | GFK_All |
695 | | }; |
696 | | |
697 | | template <typename DERIVED> |
698 | | class ClusterAnalysis { |
699 | | protected: |
700 | | typedef llvm::DenseMap<const MemRegion *, const ClusterBindings *> ClusterMap; |
701 | | typedef const MemRegion * WorkListElement; |
702 | | typedef SmallVector<WorkListElement, 10> WorkList; |
703 | | |
704 | | llvm::SmallPtrSet<const ClusterBindings *, 16> Visited; |
705 | | |
706 | | WorkList WL; |
707 | | |
708 | | RegionStoreManager &RM; |
709 | | ASTContext &Ctx; |
710 | | SValBuilder &svalBuilder; |
711 | | |
712 | | RegionBindingsRef B; |
713 | | |
714 | | |
715 | | protected: |
716 | 4.54M | const ClusterBindings *getCluster(const MemRegion *R) { |
717 | 4.54M | return B.lookup(R); |
718 | 4.54M | } RegionStore.cpp:(anonymous namespace)::ClusterAnalysis<(anonymous namespace)::RemoveDeadBindingsWorker>::getCluster(clang::ento::MemRegion const*) Line | Count | Source | 716 | 4.43M | const ClusterBindings *getCluster(const MemRegion *R) { | 717 | 4.43M | return B.lookup(R); | 718 | 4.43M | } |
RegionStore.cpp:(anonymous namespace)::ClusterAnalysis<(anonymous namespace)::InvalidateRegionsWorker>::getCluster(clang::ento::MemRegion const*) Line | Count | Source | 716 | 118k | const ClusterBindings *getCluster(const MemRegion *R) { | 717 | 118k | return B.lookup(R); | 718 | 118k | } |
|
719 | | |
720 | | /// Returns true if all clusters in the given memspace should be initially |
721 | | /// included in the cluster analysis. Subclasses may provide their |
722 | | /// own implementation. |
723 | 1.33M | bool includeEntireMemorySpace(const MemRegion *Base) { |
724 | 1.33M | return false; |
725 | 1.33M | } |
726 | | |
727 | | public: |
728 | | ClusterAnalysis(RegionStoreManager &rm, ProgramStateManager &StateMgr, |
729 | | RegionBindingsRef b) |
730 | | : RM(rm), Ctx(StateMgr.getContext()), |
731 | 395k | svalBuilder(StateMgr.getSValBuilder()), B(std::move(b)) {} RegionStore.cpp:(anonymous namespace)::ClusterAnalysis<(anonymous namespace)::RemoveDeadBindingsWorker>::ClusterAnalysis((anonymous namespace)::RegionStoreManager&, clang::ento::ProgramStateManager&, (anonymous namespace)::RegionBindingsRef) Line | Count | Source | 731 | 360k | svalBuilder(StateMgr.getSValBuilder()), B(std::move(b)) {} |
RegionStore.cpp:(anonymous namespace)::ClusterAnalysis<(anonymous namespace)::InvalidateRegionsWorker>::ClusterAnalysis((anonymous namespace)::RegionStoreManager&, clang::ento::ProgramStateManager&, (anonymous namespace)::RegionBindingsRef) Line | Count | Source | 731 | 34.4k | svalBuilder(StateMgr.getSValBuilder()), B(std::move(b)) {} |
|
732 | | |
733 | 34.4k | RegionBindingsRef getRegionBindings() const { return B; } |
734 | | |
735 | 1.33M | bool isVisited(const MemRegion *R) { |
736 | 1.33M | return Visited.count(getCluster(R)); |
737 | 1.33M | } |
738 | | |
739 | 395k | void GenerateClusters() { |
740 | | // Scan the entire set of bindings and record the region clusters. |
741 | 395k | for (RegionBindingsRef::iterator RI = B.begin(), RE = B.end(); |
742 | 1.84M | RI != RE; ++RI1.44M ){ |
743 | 1.44M | const MemRegion *Base = RI.getKey(); |
744 | | |
745 | 1.44M | const ClusterBindings &Cluster = RI.getData(); |
746 | 1.44M | assert(!Cluster.isEmpty() && "Empty clusters should be removed"); |
747 | 1.44M | static_cast<DERIVED*>(this)->VisitAddedToCluster(Base, Cluster); |
748 | | |
749 | | // If the base's memspace should be entirely invalidated, add the cluster |
750 | | // to the workspace up front. |
751 | 1.44M | if (static_cast<DERIVED*>(this)->includeEntireMemorySpace(Base)) |
752 | 48.0k | AddToWorkList(WorkListElement(Base), &Cluster); |
753 | 1.44M | } |
754 | 395k | } RegionStore.cpp:(anonymous namespace)::ClusterAnalysis<(anonymous namespace)::RemoveDeadBindingsWorker>::GenerateClusters() Line | Count | Source | 739 | 360k | void GenerateClusters() { | 740 | | // Scan the entire set of bindings and record the region clusters. | 741 | 360k | for (RegionBindingsRef::iterator RI = B.begin(), RE = B.end(); | 742 | 1.69M | RI != RE; ++RI1.33M ){ | 743 | 1.33M | const MemRegion *Base = RI.getKey(); | 744 | | | 745 | 1.33M | const ClusterBindings &Cluster = RI.getData(); | 746 | 1.33M | assert(!Cluster.isEmpty() && "Empty clusters should be removed"); | 747 | 1.33M | static_cast<DERIVED*>(this)->VisitAddedToCluster(Base, Cluster); | 748 | | | 749 | | // If the base's memspace should be entirely invalidated, add the cluster | 750 | | // to the workspace up front. | 751 | 1.33M | if (static_cast<DERIVED*>(this)->includeEntireMemorySpace(Base)) | 752 | 0 | AddToWorkList(WorkListElement(Base), &Cluster); | 753 | 1.33M | } | 754 | 360k | } |
RegionStore.cpp:(anonymous namespace)::ClusterAnalysis<(anonymous namespace)::InvalidateRegionsWorker>::GenerateClusters() Line | Count | Source | 739 | 34.4k | void GenerateClusters() { | 740 | | // Scan the entire set of bindings and record the region clusters. | 741 | 34.4k | for (RegionBindingsRef::iterator RI = B.begin(), RE = B.end(); | 742 | 147k | RI != RE; ++RI113k ){ | 743 | 113k | const MemRegion *Base = RI.getKey(); | 744 | | | 745 | 113k | const ClusterBindings &Cluster = RI.getData(); | 746 | 113k | assert(!Cluster.isEmpty() && "Empty clusters should be removed"); | 747 | 113k | static_cast<DERIVED*>(this)->VisitAddedToCluster(Base, Cluster); | 748 | | | 749 | | // If the base's memspace should be entirely invalidated, add the cluster | 750 | | // to the workspace up front. | 751 | 113k | if (static_cast<DERIVED*>(this)->includeEntireMemorySpace(Base)) | 752 | 48.0k | AddToWorkList(WorkListElement(Base), &Cluster); | 753 | 113k | } | 754 | 34.4k | } |
|
755 | | |
756 | 2.41M | bool AddToWorkList(WorkListElement E, const ClusterBindings *C) { |
757 | 2.41M | if (C && !Visited.insert(C).second1.69M ) |
758 | 412k | return false; |
759 | 2.00M | WL.push_back(E); |
760 | 2.00M | return true; |
761 | 2.00M | } RegionStore.cpp:(anonymous namespace)::ClusterAnalysis<(anonymous namespace)::RemoveDeadBindingsWorker>::AddToWorkList(clang::ento::MemRegion const*, llvm::ImmutableMap<(anonymous namespace)::BindingKey, clang::ento::SVal, llvm::ImutKeyValueInfo<(anonymous namespace)::BindingKey, clang::ento::SVal> > const*) Line | Count | Source | 756 | 2.33M | bool AddToWorkList(WorkListElement E, const ClusterBindings *C) { | 757 | 2.33M | if (C && !Visited.insert(C).second1.63M ) | 758 | 412k | return false; | 759 | 1.92M | WL.push_back(E); | 760 | 1.92M | return true; | 761 | 1.92M | } |
RegionStore.cpp:(anonymous namespace)::ClusterAnalysis<(anonymous namespace)::InvalidateRegionsWorker>::AddToWorkList(clang::ento::MemRegion const*, llvm::ImmutableMap<(anonymous namespace)::BindingKey, clang::ento::SVal, llvm::ImutKeyValueInfo<(anonymous namespace)::BindingKey, clang::ento::SVal> > const*) Line | Count | Source | 756 | 83.2k | bool AddToWorkList(WorkListElement E, const ClusterBindings *C) { | 757 | 83.2k | if (C && !Visited.insert(C).second67.7k ) | 758 | 74 | return false; | 759 | 83.1k | WL.push_back(E); | 760 | 83.1k | return true; | 761 | 83.1k | } |
|
762 | | |
763 | | bool AddToWorkList(const MemRegion *R) { |
764 | | return static_cast<DERIVED*>(this)->AddToWorkList(R); |
765 | | } |
766 | | |
767 | 396k | void RunWorkList() { |
768 | 2.39M | while (!WL.empty()) { |
769 | 2.00M | WorkListElement E = WL.pop_back_val(); |
770 | 2.00M | const MemRegion *BaseR = E; |
771 | | |
772 | 2.00M | static_cast<DERIVED*>(this)->VisitCluster(BaseR, getCluster(BaseR)); |
773 | 2.00M | } |
774 | 396k | } RegionStore.cpp:(anonymous namespace)::ClusterAnalysis<(anonymous namespace)::RemoveDeadBindingsWorker>::RunWorkList() Line | Count | Source | 767 | 362k | void RunWorkList() { | 768 | 2.28M | while (!WL.empty()) { | 769 | 1.92M | WorkListElement E = WL.pop_back_val(); | 770 | 1.92M | const MemRegion *BaseR = E; | 771 | | | 772 | 1.92M | static_cast<DERIVED*>(this)->VisitCluster(BaseR, getCluster(BaseR)); | 773 | 1.92M | } | 774 | 362k | } |
RegionStore.cpp:(anonymous namespace)::ClusterAnalysis<(anonymous namespace)::InvalidateRegionsWorker>::RunWorkList() Line | Count | Source | 767 | 34.4k | void RunWorkList() { | 768 | 117k | while (!WL.empty()) { | 769 | 83.1k | WorkListElement E = WL.pop_back_val(); | 770 | 83.1k | const MemRegion *BaseR = E; | 771 | | | 772 | 83.1k | static_cast<DERIVED*>(this)->VisitCluster(BaseR, getCluster(BaseR)); | 773 | 83.1k | } | 774 | 34.4k | } |
|
775 | | |
776 | 113k | void VisitAddedToCluster(const MemRegion *baseR, const ClusterBindings &C) {} |
777 | | void VisitCluster(const MemRegion *baseR, const ClusterBindings *C) {} |
778 | | |
779 | | void VisitCluster(const MemRegion *BaseR, const ClusterBindings *C, |
780 | | bool Flag) { |
781 | | static_cast<DERIVED*>(this)->VisitCluster(BaseR, C); |
782 | | } |
783 | | }; |
784 | | } |
785 | | |
786 | | //===----------------------------------------------------------------------===// |
787 | | // Binding invalidation. |
788 | | //===----------------------------------------------------------------------===// |
789 | | |
790 | | bool RegionStoreManager::scanReachableSymbols(Store S, const MemRegion *R, |
791 | 770k | ScanReachableSymbols &Callbacks) { |
792 | 770k | assert(R == R->getBaseRegion() && "Should only be called for base regions"); |
793 | 770k | RegionBindingsRef B = getRegionBindings(S); |
794 | 770k | const ClusterBindings *Cluster = B.lookup(R); |
795 | | |
796 | 770k | if (!Cluster) |
797 | 525k | return true; |
798 | | |
799 | 244k | for (ClusterBindings::iterator RI = Cluster->begin(), RE = Cluster->end(); |
800 | 729k | RI != RE; ++RI484k ) { |
801 | 484k | if (!Callbacks.scan(RI.getData())) |
802 | 0 | return false; |
803 | 484k | } |
804 | | |
805 | 244k | return true; |
806 | 244k | } |
807 | | |
808 | 149 | static inline bool isUnionField(const FieldRegion *FR) { |
809 | 149 | return FR->getDecl()->getParent()->isUnion(); |
810 | 149 | } |
811 | | |
812 | | typedef SmallVector<const FieldDecl *, 8> FieldVector; |
813 | | |
814 | 154 | static void getSymbolicOffsetFields(BindingKey K, FieldVector &Fields) { |
815 | 154 | assert(K.hasSymbolicOffset() && "Not implemented for concrete offset keys"); |
816 | | |
817 | 154 | const MemRegion *Base = K.getConcreteOffsetRegion(); |
818 | 154 | const MemRegion *R = K.getRegion(); |
819 | | |
820 | 490 | while (R != Base) { |
821 | 336 | if (const FieldRegion *FR = dyn_cast<FieldRegion>(R)) |
822 | 149 | if (!isUnionField(FR)) |
823 | 133 | Fields.push_back(FR->getDecl()); |
824 | | |
825 | 336 | R = cast<SubRegion>(R)->getSuperRegion(); |
826 | 336 | } |
827 | 154 | } |
828 | | |
829 | 111 | static bool isCompatibleWithFields(BindingKey K, const FieldVector &Fields) { |
830 | 111 | assert(K.hasSymbolicOffset() && "Not implemented for concrete offset keys"); |
831 | | |
832 | 111 | if (Fields.empty()) |
833 | 56 | return true; |
834 | | |
835 | 55 | FieldVector FieldsInBindingKey; |
836 | 55 | getSymbolicOffsetFields(K, FieldsInBindingKey); |
837 | | |
838 | 55 | ptrdiff_t Delta = FieldsInBindingKey.size() - Fields.size(); |
839 | 55 | if (Delta >= 0) |
840 | 51 | return std::equal(FieldsInBindingKey.begin() + Delta, |
841 | 51 | FieldsInBindingKey.end(), |
842 | 51 | Fields.begin()); |
843 | 4 | else |
844 | 4 | return std::equal(FieldsInBindingKey.begin(), FieldsInBindingKey.end(), |
845 | 4 | Fields.begin() - Delta); |
846 | 55 | } |
847 | | |
848 | | /// Collects all bindings in \p Cluster that may refer to bindings within |
849 | | /// \p Top. |
850 | | /// |
851 | | /// Each binding is a pair whose \c first is the key (a BindingKey) and whose |
852 | | /// \c second is the value (an SVal). |
853 | | /// |
854 | | /// The \p IncludeAllDefaultBindings parameter specifies whether to include |
855 | | /// default bindings that may extend beyond \p Top itself, e.g. if \p Top is |
856 | | /// an aggregate within a larger aggregate with a default binding. |
857 | | static void |
858 | | collectSubRegionBindings(SmallVectorImpl<BindingPair> &Bindings, |
859 | | SValBuilder &SVB, const ClusterBindings &Cluster, |
860 | | const SubRegion *Top, BindingKey TopKey, |
861 | 23.5k | bool IncludeAllDefaultBindings) { |
862 | 23.5k | FieldVector FieldsInSymbolicSubregions; |
863 | 23.5k | if (TopKey.hasSymbolicOffset()) { |
864 | 99 | getSymbolicOffsetFields(TopKey, FieldsInSymbolicSubregions); |
865 | 99 | Top = TopKey.getConcreteOffsetRegion(); |
866 | 99 | TopKey = BindingKey::Make(Top, BindingKey::Default); |
867 | 99 | } |
868 | | |
869 | | // Find the length (in bits) of the region being invalidated. |
870 | 23.5k | uint64_t Length = UINT64_MAX; |
871 | 23.5k | SVal Extent = Top->getMemRegionManager().getStaticSize(Top, SVB); |
872 | 23.5k | if (Optional<nonloc::ConcreteInt> ExtentCI = |
873 | 23.4k | Extent.getAs<nonloc::ConcreteInt>()) { |
874 | 23.4k | const llvm::APSInt &ExtentInt = ExtentCI->getValue(); |
875 | 23.4k | assert(ExtentInt.isNonNegative() || ExtentInt.isUnsigned()); |
876 | | // Extents are in bytes but region offsets are in bits. Be careful! |
877 | 23.4k | Length = ExtentInt.getLimitedValue() * SVB.getContext().getCharWidth(); |
878 | 58 | } else if (const FieldRegion *FR = dyn_cast<FieldRegion>(Top)) { |
879 | 37 | if (FR->getDecl()->isBitField()) |
880 | 37 | Length = FR->getDecl()->getBitWidthValue(SVB.getContext()); |
881 | 37 | } |
882 | | |
883 | 23.5k | for (ClusterBindings::iterator I = Cluster.begin(), E = Cluster.end(); |
884 | 82.1k | I != E; ++I58.6k ) { |
885 | 58.6k | BindingKey NextKey = I.getKey(); |
886 | 58.6k | if (NextKey.getRegion() == TopKey.getRegion()) { |
887 | | // FIXME: This doesn't catch the case where we're really invalidating a |
888 | | // region with a symbolic offset. Example: |
889 | | // R: points[i].y |
890 | | // Next: points[0].x |
891 | | |
892 | 58.3k | if (NextKey.getOffset() > TopKey.getOffset() && |
893 | 10.7k | NextKey.getOffset() - TopKey.getOffset() < Length) { |
894 | | // Case 1: The next binding is inside the region we're invalidating. |
895 | | // Include it. |
896 | 285 | Bindings.push_back(*I); |
897 | | |
898 | 58.1k | } else if (NextKey.getOffset() == TopKey.getOffset()) { |
899 | | // Case 2: The next binding is at the same offset as the region we're |
900 | | // invalidating. In this case, we need to leave default bindings alone, |
901 | | // since they may be providing a default value for a regions beyond what |
902 | | // we're invalidating. |
903 | | // FIXME: This is probably incorrect; consider invalidating an outer |
904 | | // struct whose first field is bound to a LazyCompoundVal. |
905 | 12.4k | if (IncludeAllDefaultBindings || NextKey.isDirect()11.4k ) |
906 | 12.0k | Bindings.push_back(*I); |
907 | 12.4k | } |
908 | | |
909 | 249 | } else if (NextKey.hasSymbolicOffset()) { |
910 | 147 | const MemRegion *Base = NextKey.getConcreteOffsetRegion(); |
911 | 147 | if (Top->isSubRegionOf(Base) && Top != Base111 ) { |
912 | | // Case 3: The next key is symbolic and we just changed something within |
913 | | // its concrete region. We don't know if the binding is still valid, so |
914 | | // we'll be conservative and include it. |
915 | 28 | if (IncludeAllDefaultBindings || NextKey.isDirect()) |
916 | 28 | if (isCompatibleWithFields(NextKey, FieldsInSymbolicSubregions)) |
917 | 28 | Bindings.push_back(*I); |
918 | 119 | } else if (const SubRegion *BaseSR = dyn_cast<SubRegion>(Base)) { |
919 | | // Case 4: The next key is symbolic, but we changed a known |
920 | | // super-region. In this case the binding is certainly included. |
921 | 119 | if (BaseSR->isSubRegionOf(Top)) |
922 | 83 | if (isCompatibleWithFields(NextKey, FieldsInSymbolicSubregions)) |
923 | 41 | Bindings.push_back(*I); |
924 | 119 | } |
925 | 147 | } |
926 | 58.6k | } |
927 | 23.5k | } |
928 | | |
929 | | static void |
930 | | collectSubRegionBindings(SmallVectorImpl<BindingPair> &Bindings, |
931 | | SValBuilder &SVB, const ClusterBindings &Cluster, |
932 | 975 | const SubRegion *Top, bool IncludeAllDefaultBindings) { |
933 | 975 | collectSubRegionBindings(Bindings, SVB, Cluster, Top, |
934 | 975 | BindingKey::Make(Top, BindingKey::Default), |
935 | 975 | IncludeAllDefaultBindings); |
936 | 975 | } |
937 | | |
938 | | RegionBindingsRef |
939 | | RegionStoreManager::removeSubRegionBindings(RegionBindingsConstRef B, |
940 | 176k | const SubRegion *Top) { |
941 | 176k | BindingKey TopKey = BindingKey::Make(Top, BindingKey::Default); |
942 | 176k | const MemRegion *ClusterHead = TopKey.getBaseRegion(); |
943 | | |
944 | 176k | if (Top == ClusterHead) { |
945 | | // We can remove an entire cluster's bindings all in one go. |
946 | 117k | return B.remove(Top); |
947 | 117k | } |
948 | | |
949 | 58.8k | const ClusterBindings *Cluster = B.lookup(ClusterHead); |
950 | 58.8k | if (!Cluster) { |
951 | | // If we're invalidating a region with a symbolic offset, we need to make |
952 | | // sure we don't treat the base region as uninitialized anymore. |
953 | 36.2k | if (TopKey.hasSymbolicOffset()) { |
954 | 148 | const SubRegion *Concrete = TopKey.getConcreteOffsetRegion(); |
955 | 148 | return B.addBinding(Concrete, BindingKey::Default, UnknownVal()); |
956 | 148 | } |
957 | 36.1k | return B; |
958 | 36.1k | } |
959 | | |
960 | 22.5k | SmallVector<BindingPair, 32> Bindings; |
961 | 22.5k | collectSubRegionBindings(Bindings, svalBuilder, *Cluster, Top, TopKey, |
962 | 22.5k | /*IncludeAllDefaultBindings=*/false); |
963 | | |
964 | 22.5k | ClusterBindingsRef Result(*Cluster, CBFactory); |
965 | 22.5k | for (SmallVectorImpl<BindingPair>::const_iterator I = Bindings.begin(), |
966 | 22.5k | E = Bindings.end(); |
967 | 33.7k | I != E; ++I11.1k ) |
968 | 11.1k | Result = Result.remove(I->first); |
969 | | |
970 | | // If we're invalidating a region with a symbolic offset, we need to make sure |
971 | | // we don't treat the base region as uninitialized anymore. |
972 | | // FIXME: This isn't very precise; see the example in |
973 | | // collectSubRegionBindings. |
974 | 22.5k | if (TopKey.hasSymbolicOffset()) { |
975 | 99 | const SubRegion *Concrete = TopKey.getConcreteOffsetRegion(); |
976 | 99 | Result = Result.add(BindingKey::Make(Concrete, BindingKey::Default), |
977 | 99 | UnknownVal()); |
978 | 99 | } |
979 | | |
980 | 22.5k | if (Result.isEmpty()) |
981 | 1.34k | return B.remove(ClusterHead); |
982 | 21.2k | return B.add(ClusterHead, Result.asImmutableMap()); |
983 | 21.2k | } |
984 | | |
985 | | namespace { |
986 | | class InvalidateRegionsWorker : public ClusterAnalysis<InvalidateRegionsWorker> |
987 | | { |
988 | | const Expr *Ex; |
989 | | unsigned Count; |
990 | | const LocationContext *LCtx; |
991 | | InvalidatedSymbols &IS; |
992 | | RegionAndSymbolInvalidationTraits &ITraits; |
993 | | StoreManager::InvalidatedRegions *Regions; |
994 | | GlobalsFilterKind GlobalsFilter; |
995 | | public: |
996 | | InvalidateRegionsWorker(RegionStoreManager &rm, |
997 | | ProgramStateManager &stateMgr, |
998 | | RegionBindingsRef b, |
999 | | const Expr *ex, unsigned count, |
1000 | | const LocationContext *lctx, |
1001 | | InvalidatedSymbols &is, |
1002 | | RegionAndSymbolInvalidationTraits &ITraitsIn, |
1003 | | StoreManager::InvalidatedRegions *r, |
1004 | | GlobalsFilterKind GFK) |
1005 | | : ClusterAnalysis<InvalidateRegionsWorker>(rm, stateMgr, b), |
1006 | | Ex(ex), Count(count), LCtx(lctx), IS(is), ITraits(ITraitsIn), Regions(r), |
1007 | 34.4k | GlobalsFilter(GFK) {} |
1008 | | |
1009 | | void VisitCluster(const MemRegion *baseR, const ClusterBindings *C); |
1010 | | void VisitBinding(SVal V); |
1011 | | |
1012 | | using ClusterAnalysis::AddToWorkList; |
1013 | | |
1014 | | bool AddToWorkList(const MemRegion *R); |
1015 | | |
1016 | | /// Returns true if all clusters in the memory space for \p Base should be |
1017 | | /// be invalidated. |
1018 | | bool includeEntireMemorySpace(const MemRegion *Base); |
1019 | | |
1020 | | /// Returns true if the memory space of the given region is one of the global |
1021 | | /// regions specially included at the start of invalidation. |
1022 | | bool isInitiallyIncludedGlobalRegion(const MemRegion *R); |
1023 | | }; |
1024 | | } |
1025 | | |
1026 | 35.1k | bool InvalidateRegionsWorker::AddToWorkList(const MemRegion *R) { |
1027 | 35.1k | bool doNotInvalidateSuperRegion = ITraits.hasTrait( |
1028 | 35.1k | R, RegionAndSymbolInvalidationTraits::TK_DoNotInvalidateSuperRegion); |
1029 | 32.9k | const MemRegion *BaseR = doNotInvalidateSuperRegion ? R2.14k : R->getBaseRegion(); |
1030 | 35.1k | return AddToWorkList(WorkListElement(BaseR), getCluster(BaseR)); |
1031 | 35.1k | } |
1032 | | |
1033 | 71.9k | void InvalidateRegionsWorker::VisitBinding(SVal V) { |
1034 | | // A symbol? Mark it touched by the invalidation. |
1035 | 71.9k | if (SymbolRef Sym = V.getAsSymbol()) |
1036 | 66.1k | IS.insert(Sym); |
1037 | | |
1038 | 71.9k | if (const MemRegion *R = V.getAsRegion()) { |
1039 | 1.16k | AddToWorkList(R); |
1040 | 1.16k | return; |
1041 | 1.16k | } |
1042 | | |
1043 | | // Is it a LazyCompoundVal? All references get invalidated as well. |
1044 | 70.7k | if (Optional<nonloc::LazyCompoundVal> LCS = |
1045 | 143 | V.getAs<nonloc::LazyCompoundVal>()) { |
1046 | | |
1047 | 143 | const RegionStoreManager::SValListTy &Vals = RM.getInterestingValues(*LCS); |
1048 | | |
1049 | 143 | for (RegionStoreManager::SValListTy::const_iterator I = Vals.begin(), |
1050 | 143 | E = Vals.end(); |
1051 | 155 | I != E; ++I12 ) |
1052 | 12 | VisitBinding(*I); |
1053 | | |
1054 | 143 | return; |
1055 | 143 | } |
1056 | 70.7k | } |
1057 | | |
1058 | | void InvalidateRegionsWorker::VisitCluster(const MemRegion *baseR, |
1059 | 83.1k | const ClusterBindings *C) { |
1060 | | |
1061 | 83.1k | bool PreserveRegionsContents = |
1062 | 83.1k | ITraits.hasTrait(baseR, |
1063 | 83.1k | RegionAndSymbolInvalidationTraits::TK_PreserveContents); |
1064 | | |
1065 | 83.1k | if (C) { |
1066 | 140k | for (ClusterBindings::iterator I = C->begin(), E = C->end(); I != E; ++I71.9k ) |
1067 | 71.9k | VisitBinding(I.getData()); |
1068 | | |
1069 | | // Invalidate regions contents. |
1070 | 68.1k | if (!PreserveRegionsContents) |
1071 | 64.6k | B = B.remove(baseR); |
1072 | 68.1k | } |
1073 | | |
1074 | 83.1k | if (const auto *TO = dyn_cast<TypedValueRegion>(baseR)) { |
1075 | 25.2k | if (const auto *RD = TO->getValueType()->getAsCXXRecordDecl()) { |
1076 | | |
1077 | | // Lambdas can affect all static local variables without explicitly |
1078 | | // capturing those. |
1079 | | // We invalidate all static locals referenced inside the lambda body. |
1080 | 18.8k | if (RD->isLambda() && RD->getLambdaCallOperator()->getBody()4 ) { |
1081 | 4 | using namespace ast_matchers; |
1082 | | |
1083 | 4 | const char *DeclBind = "DeclBind"; |
1084 | 4 | StatementMatcher RefToStatic = stmt(hasDescendant(declRefExpr( |
1085 | 4 | to(varDecl(hasStaticStorageDuration()).bind(DeclBind))))); |
1086 | 4 | auto Matches = |
1087 | 4 | match(RefToStatic, *RD->getLambdaCallOperator()->getBody(), |
1088 | 4 | RD->getASTContext()); |
1089 | | |
1090 | 2 | for (BoundNodes &Match : Matches) { |
1091 | 2 | auto *VD = Match.getNodeAs<VarDecl>(DeclBind); |
1092 | 2 | const VarRegion *ToInvalidate = |
1093 | 2 | RM.getRegionManager().getVarRegion(VD, LCtx); |
1094 | 2 | AddToWorkList(ToInvalidate); |
1095 | 2 | } |
1096 | 4 | } |
1097 | 18.8k | } |
1098 | 25.2k | } |
1099 | | |
1100 | | // BlockDataRegion? If so, invalidate captured variables that are passed |
1101 | | // by reference. |
1102 | 83.1k | if (const BlockDataRegion *BR = dyn_cast<BlockDataRegion>(baseR)) { |
1103 | 138 | for (BlockDataRegion::referenced_vars_iterator |
1104 | 138 | BI = BR->referenced_vars_begin(), BE = BR->referenced_vars_end() ; |
1105 | 268 | BI != BE; ++BI130 ) { |
1106 | 130 | const VarRegion *VR = BI.getCapturedRegion(); |
1107 | 130 | const VarDecl *VD = VR->getDecl(); |
1108 | 130 | if (VD->hasAttr<BlocksAttr>() || !VD->hasLocalStorage()114 ) { |
1109 | 32 | AddToWorkList(VR); |
1110 | 32 | } |
1111 | 98 | else if (Loc::isLocType(VR->getValueType())) { |
1112 | | // Map the current bindings to a Store to retrieve the value |
1113 | | // of the binding. If that binding itself is a region, we should |
1114 | | // invalidate that region. This is because a block may capture |
1115 | | // a pointer value, but the thing pointed by that pointer may |
1116 | | // get invalidated. |
1117 | 59 | SVal V = RM.getBinding(B, loc::MemRegionVal(VR)); |
1118 | 59 | if (Optional<Loc> L = V.getAs<Loc>()) { |
1119 | 59 | if (const MemRegion *LR = L->getAsRegion()) |
1120 | 59 | AddToWorkList(LR); |
1121 | 59 | } |
1122 | 59 | } |
1123 | 130 | } |
1124 | 138 | return; |
1125 | 138 | } |
1126 | | |
1127 | | // Symbolic region? |
1128 | 83.0k | if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(baseR)) |
1129 | 9.85k | IS.insert(SR->getSymbol()); |
1130 | | |
1131 | | // Nothing else should be done in the case when we preserve regions context. |
1132 | 83.0k | if (PreserveRegionsContents) |
1133 | 7.47k | return; |
1134 | | |
1135 | | // Otherwise, we have a normal data region. Record that we touched the region. |
1136 | 75.5k | if (Regions) |
1137 | 75.5k | Regions->push_back(baseR); |
1138 | | |
1139 | 75.5k | if (isa<AllocaRegion>(baseR) || isa<SymbolicRegion>(baseR)75.5k ) { |
1140 | | // Invalidate the region by setting its default value to |
1141 | | // conjured symbol. The type of the symbol is irrelevant. |
1142 | 7.81k | DefinedOrUnknownSVal V = |
1143 | 7.81k | svalBuilder.conjureSymbolVal(baseR, Ex, LCtx, Ctx.IntTy, Count); |
1144 | 7.81k | B = B.addBinding(baseR, BindingKey::Default, V); |
1145 | 7.81k | return; |
1146 | 7.81k | } |
1147 | | |
1148 | 67.7k | if (!baseR->isBoundable()) |
1149 | 48.3k | return; |
1150 | | |
1151 | 19.4k | const TypedValueRegion *TR = cast<TypedValueRegion>(baseR); |
1152 | 19.4k | QualType T = TR->getValueType(); |
1153 | | |
1154 | 19.4k | if (isInitiallyIncludedGlobalRegion(baseR)) { |
1155 | | // If the region is a global and we are invalidating all globals, |
1156 | | // erasing the entry is good enough. This causes all globals to be lazily |
1157 | | // symbolicated from the same base symbol. |
1158 | 403 | return; |
1159 | 403 | } |
1160 | | |
1161 | 19.0k | if (T->isRecordType()) { |
1162 | | // Invalidate the region by setting its default value to |
1163 | | // conjured symbol. The type of the symbol is irrelevant. |
1164 | 16.8k | DefinedOrUnknownSVal V = svalBuilder.conjureSymbolVal(baseR, Ex, LCtx, |
1165 | 16.8k | Ctx.IntTy, Count); |
1166 | 16.8k | B = B.addBinding(baseR, BindingKey::Default, V); |
1167 | 16.8k | return; |
1168 | 16.8k | } |
1169 | | |
1170 | 2.14k | if (const ArrayType *AT = Ctx.getAsArrayType(T)) { |
1171 | 786 | bool doNotInvalidateSuperRegion = ITraits.hasTrait( |
1172 | 786 | baseR, |
1173 | 786 | RegionAndSymbolInvalidationTraits::TK_DoNotInvalidateSuperRegion); |
1174 | | |
1175 | 786 | if (doNotInvalidateSuperRegion) { |
1176 | | // We are not doing blank invalidation of the whole array region so we |
1177 | | // have to manually invalidate each elements. |
1178 | 35 | Optional<uint64_t> NumElements; |
1179 | | |
1180 | | // Compute lower and upper offsets for region within array. |
1181 | 35 | if (const ConstantArrayType *CAT = dyn_cast<ConstantArrayType>(AT)) |
1182 | 35 | NumElements = CAT->getSize().getZExtValue(); |
1183 | 35 | if (!NumElements) // We are not dealing with a constant size array |
1184 | 0 | goto conjure_default; |
1185 | 35 | QualType ElementTy = AT->getElementType(); |
1186 | 35 | uint64_t ElemSize = Ctx.getTypeSize(ElementTy); |
1187 | 35 | const RegionOffset &RO = baseR->getAsOffset(); |
1188 | 35 | const MemRegion *SuperR = baseR->getBaseRegion(); |
1189 | 35 | if (RO.hasSymbolicOffset()) { |
1190 | | // If base region has a symbolic offset, |
1191 | | // we revert to invalidating the super region. |
1192 | 4 | if (SuperR) |
1193 | 4 | AddToWorkList(SuperR); |
1194 | 4 | goto conjure_default; |
1195 | 4 | } |
1196 | | |
1197 | 31 | uint64_t LowerOffset = RO.getOffset(); |
1198 | 31 | uint64_t UpperOffset = LowerOffset + *NumElements * ElemSize; |
1199 | 31 | bool UpperOverflow = UpperOffset < LowerOffset; |
1200 | | |
1201 | | // Invalidate regions which are within array boundaries, |
1202 | | // or have a symbolic offset. |
1203 | 31 | if (!SuperR) |
1204 | 0 | goto conjure_default; |
1205 | | |
1206 | 31 | const ClusterBindings *C = B.lookup(SuperR); |
1207 | 31 | if (!C) |
1208 | 0 | goto conjure_default; |
1209 | | |
1210 | 159 | for (ClusterBindings::iterator I = C->begin(), E = C->end(); 31 I != E; |
1211 | 128 | ++I) { |
1212 | 128 | const BindingKey &BK = I.getKey(); |
1213 | 128 | Optional<uint64_t> ROffset = |
1214 | 123 | BK.hasSymbolicOffset() ? Optional<uint64_t>()5 : BK.getOffset(); |
1215 | | |
1216 | | // Check offset is not symbolic and within array's boundaries. |
1217 | | // Handles arrays of 0 elements and of 0-sized elements as well. |
1218 | 128 | if (!ROffset || |
1219 | 123 | ((*ROffset >= LowerOffset && *ROffset < UpperOffset110 ) || |
1220 | 50 | (UpperOverflow && |
1221 | 11 | (*ROffset >= LowerOffset || *ROffset < UpperOffset5 )) || |
1222 | 89 | (42 LowerOffset == UpperOffset42 && *ROffset == LowerOffset3 ))) { |
1223 | 89 | B = B.removeBinding(I.getKey()); |
1224 | | // Bound symbolic regions need to be invalidated for dead symbol |
1225 | | // detection. |
1226 | 89 | SVal V = I.getData(); |
1227 | 89 | const MemRegion *R = V.getAsRegion(); |
1228 | 89 | if (R && isa<SymbolicRegion>(R)3 ) |
1229 | 3 | VisitBinding(V); |
1230 | 89 | } |
1231 | 128 | } |
1232 | 31 | } |
1233 | 786 | conjure_default: |
1234 | | // Set the default value of the array to conjured symbol. |
1235 | 786 | DefinedOrUnknownSVal V = |
1236 | 786 | svalBuilder.conjureSymbolVal(baseR, Ex, LCtx, |
1237 | 786 | AT->getElementType(), Count); |
1238 | 786 | B = B.addBinding(baseR, BindingKey::Default, V); |
1239 | 786 | return; |
1240 | 1.36k | } |
1241 | | |
1242 | 1.36k | DefinedOrUnknownSVal V = svalBuilder.conjureSymbolVal(baseR, Ex, LCtx, |
1243 | 1.36k | T,Count); |
1244 | 1.36k | assert(SymbolManager::canSymbolicate(T) || V.isUnknown()); |
1245 | 1.36k | B = B.addBinding(baseR, BindingKey::Direct, V); |
1246 | 1.36k | } |
1247 | | |
1248 | | bool InvalidateRegionsWorker::isInitiallyIncludedGlobalRegion( |
1249 | 132k | const MemRegion *R) { |
1250 | 132k | switch (GlobalsFilter) { |
1251 | 2.78k | case GFK_None: |
1252 | 2.78k | return false; |
1253 | 21.4k | case GFK_SystemOnly: |
1254 | 21.4k | return isa<GlobalSystemSpaceRegion>(R->getMemorySpace()); |
1255 | 108k | case GFK_All: |
1256 | 108k | return isa<NonStaticGlobalSpaceRegion>(R->getMemorySpace()); |
1257 | 0 | } |
1258 | | |
1259 | 0 | llvm_unreachable("unknown globals filter"); |
1260 | 0 | } |
1261 | | |
1262 | 113k | bool InvalidateRegionsWorker::includeEntireMemorySpace(const MemRegion *Base) { |
1263 | 113k | if (isInitiallyIncludedGlobalRegion(Base)) |
1264 | 48.0k | return true; |
1265 | | |
1266 | 65.3k | const MemSpaceRegion *MemSpace = Base->getMemorySpace(); |
1267 | 65.3k | return ITraits.hasTrait(MemSpace, |
1268 | 65.3k | RegionAndSymbolInvalidationTraits::TK_EntireMemSpace); |
1269 | 65.3k | } |
1270 | | |
1271 | | RegionBindingsRef |
1272 | | RegionStoreManager::invalidateGlobalRegion(MemRegion::Kind K, |
1273 | | const Expr *Ex, |
1274 | | unsigned Count, |
1275 | | const LocationContext *LCtx, |
1276 | | RegionBindingsRef B, |
1277 | 60.5k | InvalidatedRegions *Invalidated) { |
1278 | | // Bind the globals memory space to a new symbol that we will use to derive |
1279 | | // the bindings for all globals. |
1280 | 60.5k | const GlobalsSpaceRegion *GS = MRMgr.getGlobalsRegion(K); |
1281 | 60.5k | SVal V = svalBuilder.conjureSymbolVal(/* symbolTag = */ (const void*) GS, Ex, LCtx, |
1282 | 60.5k | /* type does not matter */ Ctx.IntTy, |
1283 | 60.5k | Count); |
1284 | | |
1285 | 60.5k | B = B.removeBinding(GS) |
1286 | 60.5k | .addBinding(BindingKey::Make(GS, BindingKey::Default), V); |
1287 | | |
1288 | | // Even if there are no bindings in the global scope, we still need to |
1289 | | // record that we touched it. |
1290 | 60.5k | if (Invalidated) |
1291 | 60.5k | Invalidated->push_back(GS); |
1292 | | |
1293 | 60.5k | return B; |
1294 | 60.5k | } |
1295 | | |
1296 | | void RegionStoreManager::populateWorkList(InvalidateRegionsWorker &W, |
1297 | | ArrayRef<SVal> Values, |
1298 | 34.4k | InvalidatedRegions *TopLevelRegions) { |
1299 | 34.4k | for (ArrayRef<SVal>::iterator I = Values.begin(), |
1300 | 84.5k | E = Values.end(); I != E; ++I50.1k ) { |
1301 | 50.1k | SVal V = *I; |
1302 | 50.1k | if (Optional<nonloc::LazyCompoundVal> LCS = |
1303 | 9.65k | V.getAs<nonloc::LazyCompoundVal>()) { |
1304 | | |
1305 | 9.65k | const SValListTy &Vals = getInterestingValues(*LCS); |
1306 | | |
1307 | 9.65k | for (SValListTy::const_iterator I = Vals.begin(), |
1308 | 19.2k | E = Vals.end(); I != E; ++I9.59k ) { |
1309 | | // Note: the last argument is false here because these are |
1310 | | // non-top-level regions. |
1311 | 9.59k | if (const MemRegion *R = (*I).getAsRegion()) |
1312 | 441 | W.AddToWorkList(R); |
1313 | 9.59k | } |
1314 | 9.65k | continue; |
1315 | 9.65k | } |
1316 | | |
1317 | 40.4k | if (const MemRegion *R = V.getAsRegion()) { |
1318 | 33.4k | if (TopLevelRegions) |
1319 | 33.4k | TopLevelRegions->push_back(R); |
1320 | 33.4k | W.AddToWorkList(R); |
1321 | 33.4k | continue; |
1322 | 33.4k | } |
1323 | 40.4k | } |
1324 | 34.4k | } |
1325 | | |
1326 | | StoreRef |
1327 | | RegionStoreManager::invalidateRegions(Store store, |
1328 | | ArrayRef<SVal> Values, |
1329 | | const Expr *Ex, unsigned Count, |
1330 | | const LocationContext *LCtx, |
1331 | | const CallEvent *Call, |
1332 | | InvalidatedSymbols &IS, |
1333 | | RegionAndSymbolInvalidationTraits &ITraits, |
1334 | | InvalidatedRegions *TopLevelRegions, |
1335 | 34.4k | InvalidatedRegions *Invalidated) { |
1336 | 34.4k | GlobalsFilterKind GlobalsFilter; |
1337 | 34.4k | if (Call) { |
1338 | 33.4k | if (Call->isInSystemHeader()) |
1339 | 6.36k | GlobalsFilter = GFK_SystemOnly; |
1340 | 27.0k | else |
1341 | 27.0k | GlobalsFilter = GFK_All; |
1342 | 958 | } else { |
1343 | 958 | GlobalsFilter = GFK_None; |
1344 | 958 | } |
1345 | | |
1346 | 34.4k | RegionBindingsRef B = getRegionBindings(store); |
1347 | 34.4k | InvalidateRegionsWorker W(*this, StateMgr, B, Ex, Count, LCtx, IS, ITraits, |
1348 | 34.4k | Invalidated, GlobalsFilter); |
1349 | | |
1350 | | // Scan the bindings and generate the clusters. |
1351 | 34.4k | W.GenerateClusters(); |
1352 | | |
1353 | | // Add the regions to the worklist. |
1354 | 34.4k | populateWorkList(W, Values, TopLevelRegions); |
1355 | | |
1356 | 34.4k | W.RunWorkList(); |
1357 | | |
1358 | | // Return the new bindings. |
1359 | 34.4k | B = W.getRegionBindings(); |
1360 | | |
1361 | | // For calls, determine which global regions should be invalidated and |
1362 | | // invalidate them. (Note that function-static and immutable globals are never |
1363 | | // invalidated by this.) |
1364 | | // TODO: This could possibly be more precise with modules. |
1365 | 34.4k | switch (GlobalsFilter) { |
1366 | 27.0k | case GFK_All: |
1367 | 27.0k | B = invalidateGlobalRegion(MemRegion::GlobalInternalSpaceRegionKind, |
1368 | 27.0k | Ex, Count, LCtx, B, Invalidated); |
1369 | 27.0k | LLVM_FALLTHROUGH; |
1370 | 33.4k | case GFK_SystemOnly: |
1371 | 33.4k | B = invalidateGlobalRegion(MemRegion::GlobalSystemSpaceRegionKind, |
1372 | 33.4k | Ex, Count, LCtx, B, Invalidated); |
1373 | 33.4k | LLVM_FALLTHROUGH; |
1374 | 34.4k | case GFK_None: |
1375 | 34.4k | break; |
1376 | 34.4k | } |
1377 | | |
1378 | 34.4k | return StoreRef(B.asStore(), *this); |
1379 | 34.4k | } |
1380 | | |
1381 | | //===----------------------------------------------------------------------===// |
1382 | | // Location and region casting. |
1383 | | //===----------------------------------------------------------------------===// |
1384 | | |
1385 | | /// ArrayToPointer - Emulates the "decay" of an array to a pointer |
1386 | | /// type. 'Array' represents the lvalue of the array being decayed |
1387 | | /// to a pointer, and the returned SVal represents the decayed |
1388 | | /// version of that lvalue (i.e., a pointer to the first element of |
1389 | | /// the array). This is called by ExprEngine when evaluating casts |
1390 | | /// from arrays to pointers. |
1391 | 9.31k | SVal RegionStoreManager::ArrayToPointer(Loc Array, QualType T) { |
1392 | 9.31k | if (Array.getAs<loc::ConcreteInt>()) |
1393 | 7 | return Array; |
1394 | | |
1395 | 9.30k | if (!Array.getAs<loc::MemRegionVal>()) |
1396 | 0 | return UnknownVal(); |
1397 | | |
1398 | 9.30k | const SubRegion *R = |
1399 | 9.30k | cast<SubRegion>(Array.castAs<loc::MemRegionVal>().getRegion()); |
1400 | 9.30k | NonLoc ZeroIdx = svalBuilder.makeZeroArrayIndex(); |
1401 | 9.30k | return loc::MemRegionVal(MRMgr.getElementRegion(T, ZeroIdx, R, Ctx)); |
1402 | 9.30k | } |
1403 | | |
1404 | | //===----------------------------------------------------------------------===// |
1405 | | // Loading values from regions. |
1406 | | //===----------------------------------------------------------------------===// |
1407 | | |
1408 | 514k | SVal RegionStoreManager::getBinding(RegionBindingsConstRef B, Loc L, QualType T) { |
1409 | 514k | assert(!L.getAs<UnknownVal>() && "location unknown"); |
1410 | 514k | assert(!L.getAs<UndefinedVal>() && "location undefined"); |
1411 | | |
1412 | | // For access to concrete addresses, return UnknownVal. Checks |
1413 | | // for null dereferences (and similar errors) are done by checkers, not |
1414 | | // the Store. |
1415 | | // FIXME: We can consider lazily symbolicating such memory, but we really |
1416 | | // should defer this when we can reason easily about symbolicating arrays |
1417 | | // of bytes. |
1418 | 514k | if (L.getAs<loc::ConcreteInt>()) { |
1419 | 12 | return UnknownVal(); |
1420 | 12 | } |
1421 | 514k | if (!L.getAs<loc::MemRegionVal>()) { |
1422 | 0 | return UnknownVal(); |
1423 | 0 | } |
1424 | | |
1425 | 514k | const MemRegion *MR = L.castAs<loc::MemRegionVal>().getRegion(); |
1426 | | |
1427 | 514k | if (isa<BlockDataRegion>(MR)) { |
1428 | 1 | return UnknownVal(); |
1429 | 1 | } |
1430 | | |
1431 | 514k | if (!isa<TypedValueRegion>(MR)) { |
1432 | 7.20k | if (T.isNull()) { |
1433 | 5.23k | if (const TypedRegion *TR = dyn_cast<TypedRegion>(MR)) |
1434 | 0 | T = TR->getLocationType()->getPointeeType(); |
1435 | 5.23k | else if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(MR)) |
1436 | 5.23k | T = SR->getSymbol()->getType()->getPointeeType(); |
1437 | 5.23k | } |
1438 | 7.20k | assert(!T.isNull() && "Unable to auto-detect binding type!"); |
1439 | 7.20k | assert(!T->isVoidType() && "Attempting to dereference a void pointer!"); |
1440 | 7.20k | MR = GetElementZeroRegion(cast<SubRegion>(MR), T); |
1441 | 507k | } else { |
1442 | 507k | T = cast<TypedValueRegion>(MR)->getValueType(); |
1443 | 507k | } |
1444 | | |
1445 | | // FIXME: Perhaps this method should just take a 'const MemRegion*' argument |
1446 | | // instead of 'Loc', and have the other Loc cases handled at a higher level. |
1447 | 514k | const TypedValueRegion *R = cast<TypedValueRegion>(MR); |
1448 | 514k | QualType RTy = R->getValueType(); |
1449 | | |
1450 | | // FIXME: we do not yet model the parts of a complex type, so treat the |
1451 | | // whole thing as "unknown". |
1452 | 514k | if (RTy->isAnyComplexType()) |
1453 | 87 | return UnknownVal(); |
1454 | | |
1455 | | // FIXME: We should eventually handle funny addressing. e.g.: |
1456 | | // |
1457 | | // int x = ...; |
1458 | | // int *p = &x; |
1459 | | // char *q = (char*) p; |
1460 | | // char c = *q; // returns the first byte of 'x'. |
1461 | | // |
1462 | | // Such funny addressing will occur due to layering of regions. |
1463 | 514k | if (RTy->isStructureOrClassType()) |
1464 | 58.2k | return getBindingForStruct(B, R); |
1465 | | |
1466 | | // FIXME: Handle unions. |
1467 | 456k | if (RTy->isUnionType()) |
1468 | 85 | return createLazyBinding(B, R); |
1469 | | |
1470 | 456k | if (RTy->isArrayType()) { |
1471 | 2.03k | if (RTy->isConstantArrayType()) |
1472 | 2.03k | return getBindingForArray(B, R); |
1473 | 2 | else |
1474 | 2 | return UnknownVal(); |
1475 | 454k | } |
1476 | | |
1477 | | // FIXME: handle Vector types. |
1478 | 454k | if (RTy->isVectorType()) |
1479 | 21 | return UnknownVal(); |
1480 | | |
1481 | 453k | if (const FieldRegion* FR = dyn_cast<FieldRegion>(R)) |
1482 | 68.9k | return CastRetrievedVal(getBindingForField(B, FR), FR, T); |
1483 | | |
1484 | 384k | if (const ElementRegion* ER = dyn_cast<ElementRegion>(R)) { |
1485 | | // FIXME: Here we actually perform an implicit conversion from the loaded |
1486 | | // value to the element type. Eventually we want to compose these values |
1487 | | // more intelligently. For example, an 'element' can encompass multiple |
1488 | | // bound regions (e.g., several bound bytes), or could be a subset of |
1489 | | // a larger value. |
1490 | 16.5k | return CastRetrievedVal(getBindingForElement(B, ER), ER, T); |
1491 | 16.5k | } |
1492 | | |
1493 | 368k | if (const ObjCIvarRegion *IVR = dyn_cast<ObjCIvarRegion>(R)) { |
1494 | | // FIXME: Here we actually perform an implicit conversion from the loaded |
1495 | | // value to the ivar type. What we should model is stores to ivars |
1496 | | // that blow past the extent of the ivar. If the address of the ivar is |
1497 | | // reinterpretted, it is possible we stored a different value that could |
1498 | | // fit within the ivar. Either we need to cast these when storing them |
1499 | | // or reinterpret them lazily (as we do here). |
1500 | 2.51k | return CastRetrievedVal(getBindingForObjCIvar(B, IVR), IVR, T); |
1501 | 2.51k | } |
1502 | | |
1503 | 365k | if (const VarRegion *VR = dyn_cast<VarRegion>(R)) { |
1504 | | // FIXME: Here we actually perform an implicit conversion from the loaded |
1505 | | // value to the variable type. What we should model is stores to variables |
1506 | | // that blow past the extent of the variable. If the address of the |
1507 | | // variable is reinterpretted, it is possible we stored a different value |
1508 | | // that could fit within the variable. Either we need to cast these when |
1509 | | // storing them or reinterpret them lazily (as we do here). |
1510 | 304k | return CastRetrievedVal(getBindingForVar(B, VR), VR, T); |
1511 | 304k | } |
1512 | | |
1513 | 61.0k | const SVal *V = B.lookup(R, BindingKey::Direct); |
1514 | | |
1515 | | // Check if the region has a binding. |
1516 | 61.0k | if (V) |
1517 | 57.4k | return *V; |
1518 | | |
1519 | | // The location does not have a bound value. This means that it has |
1520 | | // the value it had upon its creation and/or entry to the analyzed |
1521 | | // function/method. These are either symbolic values or 'undefined'. |
1522 | 3.69k | if (R->hasStackNonParametersStorage()) { |
1523 | | // All stack variables are considered to have undefined values |
1524 | | // upon creation. All heap allocated blocks are considered to |
1525 | | // have undefined values as well unless they are explicitly bound |
1526 | | // to specific values. |
1527 | 42 | return UndefinedVal(); |
1528 | 42 | } |
1529 | | |
1530 | | // All other values are symbolic. |
1531 | 3.64k | return svalBuilder.getRegionValueSymbolVal(R); |
1532 | 3.64k | } |
1533 | | |
1534 | 814 | static QualType getUnderlyingType(const SubRegion *R) { |
1535 | 814 | QualType RegionTy; |
1536 | 814 | if (const TypedValueRegion *TVR = dyn_cast<TypedValueRegion>(R)) |
1537 | 807 | RegionTy = TVR->getValueType(); |
1538 | | |
1539 | 814 | if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) |
1540 | 7 | RegionTy = SR->getSymbol()->getType(); |
1541 | | |
1542 | 814 | return RegionTy; |
1543 | 814 | } |
1544 | | |
1545 | | /// Checks to see if store \p B has a lazy binding for region \p R. |
1546 | | /// |
1547 | | /// If \p AllowSubregionBindings is \c false, a lazy binding will be rejected |
1548 | | /// if there are additional bindings within \p R. |
1549 | | /// |
1550 | | /// Note that unlike RegionStoreManager::findLazyBinding, this will not search |
1551 | | /// for lazy bindings for super-regions of \p R. |
1552 | | static Optional<nonloc::LazyCompoundVal> |
1553 | | getExistingLazyBinding(SValBuilder &SVB, RegionBindingsConstRef B, |
1554 | 169k | const SubRegion *R, bool AllowSubregionBindings) { |
1555 | 169k | Optional<SVal> V = B.getDefaultBinding(R); |
1556 | 169k | if (!V) |
1557 | 150k | return None; |
1558 | | |
1559 | 18.7k | Optional<nonloc::LazyCompoundVal> LCV = V->getAs<nonloc::LazyCompoundVal>(); |
1560 | 18.7k | if (!LCV) |
1561 | 17.9k | return None; |
1562 | | |
1563 | | // If the LCV is for a subregion, the types might not match, and we shouldn't |
1564 | | // reuse the binding. |
1565 | 814 | QualType RegionTy = getUnderlyingType(R); |
1566 | 814 | if (!RegionTy.isNull() && |
1567 | 814 | !RegionTy->isVoidPointerType()) { |
1568 | 810 | QualType SourceRegionTy = LCV->getRegion()->getValueType(); |
1569 | 810 | if (!SVB.getContext().hasSameUnqualifiedType(RegionTy, SourceRegionTy)) |
1570 | 222 | return None; |
1571 | 592 | } |
1572 | | |
1573 | 592 | if (!AllowSubregionBindings) { |
1574 | | // If there are any other bindings within this region, we shouldn't reuse |
1575 | | // the top-level binding. |
1576 | 148 | SmallVector<BindingPair, 16> Bindings; |
1577 | 148 | collectSubRegionBindings(Bindings, SVB, *B.lookup(R->getBaseRegion()), R, |
1578 | 148 | /*IncludeAllDefaultBindings=*/true); |
1579 | 148 | if (Bindings.size() > 1) |
1580 | 2 | return None; |
1581 | 590 | } |
1582 | | |
1583 | 590 | return *LCV; |
1584 | 590 | } |
1585 | | |
1586 | | |
1587 | | std::pair<Store, const SubRegion *> |
1588 | | RegionStoreManager::findLazyBinding(RegionBindingsConstRef B, |
1589 | | const SubRegion *R, |
1590 | 186k | const SubRegion *originalRegion) { |
1591 | 186k | if (originalRegion != R) { |
1592 | 114k | if (Optional<nonloc::LazyCompoundVal> V = |
1593 | 444 | getExistingLazyBinding(svalBuilder, B, R, true)) |
1594 | 444 | return std::make_pair(V->getStore(), V->getRegion()); |
1595 | 186k | } |
1596 | | |
1597 | 186k | typedef std::pair<Store, const SubRegion *> StoreRegionPair; |
1598 | 186k | StoreRegionPair Result = StoreRegionPair(); |
1599 | | |
1600 | 186k | if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) { |
1601 | 48.6k | Result = findLazyBinding(B, cast<SubRegion>(ER->getSuperRegion()), |
1602 | 48.6k | originalRegion); |
1603 | | |
1604 | 48.6k | if (Result.second) |
1605 | 254 | Result.second = MRMgr.getElementRegionWithSuper(ER, Result.second); |
1606 | | |
1607 | 137k | } else if (const FieldRegion *FR = dyn_cast<FieldRegion>(R)) { |
1608 | 65.1k | Result = findLazyBinding(B, cast<SubRegion>(FR->getSuperRegion()), |
1609 | 65.1k | originalRegion); |
1610 | | |
1611 | 65.1k | if (Result.second) |
1612 | 449 | Result.second = MRMgr.getFieldRegionWithSuper(FR, Result.second); |
1613 | | |
1614 | 72.5k | } else if (const CXXBaseObjectRegion *BaseReg = |
1615 | 1.09k | dyn_cast<CXXBaseObjectRegion>(R)) { |
1616 | | // C++ base object region is another kind of region that we should blast |
1617 | | // through to look for lazy compound value. It is like a field region. |
1618 | 1.09k | Result = findLazyBinding(B, cast<SubRegion>(BaseReg->getSuperRegion()), |
1619 | 1.09k | originalRegion); |
1620 | | |
1621 | 1.09k | if (Result.second) |
1622 | 40 | Result.second = MRMgr.getCXXBaseObjectRegionWithSuper(BaseReg, |
1623 | 40 | Result.second); |
1624 | 1.09k | } |
1625 | | |
1626 | 186k | return Result; |
1627 | 186k | } |
1628 | | |
1629 | | SVal RegionStoreManager::getBindingForElement(RegionBindingsConstRef B, |
1630 | 16.6k | const ElementRegion* R) { |
1631 | | // Check if the region has a binding. |
1632 | 16.6k | if (const Optional<SVal> &V = B.getDirectBinding(R)) |
1633 | 3.67k | return *V; |
1634 | | |
1635 | 12.9k | const MemRegion* superR = R->getSuperRegion(); |
1636 | | |
1637 | | // Check if the region is an element region of a string literal. |
1638 | 12.9k | if (const StringRegion *StrR = dyn_cast<StringRegion>(superR)) { |
1639 | | // FIXME: Handle loads from strings where the literal is treated as |
1640 | | // an integer, e.g., *((unsigned int*)"hello") |
1641 | 192 | QualType T = Ctx.getAsArrayType(StrR->getValueType())->getElementType(); |
1642 | 192 | if (!Ctx.hasSameUnqualifiedType(T, R->getElementType())) |
1643 | 2 | return UnknownVal(); |
1644 | | |
1645 | 190 | const StringLiteral *Str = StrR->getStringLiteral(); |
1646 | 190 | SVal Idx = R->getIndex(); |
1647 | 190 | if (Optional<nonloc::ConcreteInt> CI = Idx.getAs<nonloc::ConcreteInt>()) { |
1648 | 190 | int64_t i = CI->getValue().getSExtValue(); |
1649 | | // Abort on string underrun. This can be possible by arbitrary |
1650 | | // clients of getBindingForElement(). |
1651 | 190 | if (i < 0) |
1652 | 0 | return UndefinedVal(); |
1653 | 190 | int64_t length = Str->getLength(); |
1654 | | // Technically, only i == length is guaranteed to be null. |
1655 | | // However, such overflows should be caught before reaching this point; |
1656 | | // the only time such an access would be made is if a string literal was |
1657 | | // used to initialize a larger array. |
1658 | 182 | char c = (i >= length) ? '\0'8 : Str->getCodeUnit(i); |
1659 | 190 | return svalBuilder.makeIntVal(c, T); |
1660 | 190 | } |
1661 | 12.8k | } else if (const VarRegion *VR = dyn_cast<VarRegion>(superR)) { |
1662 | | // Check if the containing array has an initialized value that we can trust. |
1663 | | // We can trust a const value or a value of a global initializer in main(). |
1664 | 3.42k | const VarDecl *VD = VR->getDecl(); |
1665 | 3.42k | if (VD->getType().isConstQualified() || |
1666 | 3.37k | R->getElementType().isConstQualified() || |
1667 | 3.37k | (B.isMainAnalysis() && VD->hasGlobalStorage()7 )) { |
1668 | 57 | if (const Expr *Init = VD->getAnyInitializer()) { |
1669 | 57 | if (const auto *InitList = dyn_cast<InitListExpr>(Init)) { |
1670 | | // The array index has to be known. |
1671 | 57 | if (auto CI = R->getIndex().getAs<nonloc::ConcreteInt>()) { |
1672 | 57 | int64_t i = CI->getValue().getSExtValue(); |
1673 | | // If it is known that the index is out of bounds, we can return |
1674 | | // an undefined value. |
1675 | 57 | if (i < 0) |
1676 | 1 | return UndefinedVal(); |
1677 | | |
1678 | 56 | if (auto CAT = Ctx.getAsConstantArrayType(VD->getType())) |
1679 | 56 | if (CAT->getSize().sle(i)) |
1680 | 1 | return UndefinedVal(); |
1681 | | |
1682 | | // If there is a list, but no init, it must be zero. |
1683 | 55 | if (i >= InitList->getNumInits()) |
1684 | 1 | return svalBuilder.makeZeroVal(R->getElementType()); |
1685 | | |
1686 | 54 | if (const Expr *ElemInit = InitList->getInit(i)) |
1687 | 54 | if (Optional<SVal> V = svalBuilder.getConstantVal(ElemInit)) |
1688 | 54 | return *V; |
1689 | 12.7k | } |
1690 | 57 | } |
1691 | 57 | } |
1692 | 57 | } |
1693 | 3.42k | } |
1694 | | |
1695 | | // Check for loads from a code text region. For such loads, just give up. |
1696 | 12.7k | if (isa<CodeTextRegion>(superR)) |
1697 | 89 | return UnknownVal(); |
1698 | | |
1699 | | // Handle the case where we are indexing into a larger scalar object. |
1700 | | // For example, this handles: |
1701 | | // int x = ... |
1702 | | // char *y = &x; |
1703 | | // return *y; |
1704 | | // FIXME: This is a hack, and doesn't do anything really intelligent yet. |
1705 | 12.6k | const RegionRawOffset &O = R->getAsArrayOffset(); |
1706 | | |
1707 | | // If we cannot reason about the offset, return an unknown value. |
1708 | 12.6k | if (!O.getRegion()) |
1709 | 1.93k | return UnknownVal(); |
1710 | | |
1711 | 10.7k | if (const TypedValueRegion *baseR = |
1712 | 4.35k | dyn_cast_or_null<TypedValueRegion>(O.getRegion())) { |
1713 | 4.35k | QualType baseT = baseR->getValueType(); |
1714 | 4.35k | if (baseT->isScalarType()) { |
1715 | 80 | QualType elemT = R->getElementType(); |
1716 | 80 | if (elemT->isScalarType()) { |
1717 | 80 | if (Ctx.getTypeSizeInChars(baseT) >= Ctx.getTypeSizeInChars(elemT)) { |
1718 | 79 | if (const Optional<SVal> &V = B.getDirectBinding(superR)) { |
1719 | 4 | if (SymbolRef parentSym = V->getAsSymbol()) |
1720 | 0 | return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R); |
1721 | | |
1722 | 4 | if (V->isUnknownOrUndef()) |
1723 | 0 | return *V; |
1724 | | // Other cases: give up. We are indexing into a larger object |
1725 | | // that has some value, but we don't know how to handle that yet. |
1726 | 4 | return UnknownVal(); |
1727 | 4 | } |
1728 | 79 | } |
1729 | 80 | } |
1730 | 80 | } |
1731 | 4.35k | } |
1732 | 10.7k | return getBindingForFieldOrElementCommon(B, R, R->getElementType()); |
1733 | 10.7k | } |
1734 | | |
1735 | | SVal RegionStoreManager::getBindingForField(RegionBindingsConstRef B, |
1736 | 91.4k | const FieldRegion* R) { |
1737 | | |
1738 | | // Check if the region has a binding. |
1739 | 91.4k | if (const Optional<SVal> &V = B.getDirectBinding(R)) |
1740 | 30.0k | return *V; |
1741 | | |
1742 | | // Is the field declared constant and has an in-class initializer? |
1743 | 61.3k | const FieldDecl *FD = R->getDecl(); |
1744 | 61.3k | QualType Ty = FD->getType(); |
1745 | 61.3k | if (Ty.isConstQualified()) |
1746 | 49 | if (const Expr *Init = FD->getInClassInitializer()) |
1747 | 0 | if (Optional<SVal> V = svalBuilder.getConstantVal(Init)) |
1748 | 0 | return *V; |
1749 | | |
1750 | | // If the containing record was initialized, try to get its constant value. |
1751 | 61.3k | const MemRegion* superR = R->getSuperRegion(); |
1752 | 61.3k | if (const auto *VR = dyn_cast<VarRegion>(superR)) { |
1753 | 14.8k | const VarDecl *VD = VR->getDecl(); |
1754 | 14.8k | QualType RecordVarTy = VD->getType(); |
1755 | 14.8k | unsigned Index = FD->getFieldIndex(); |
1756 | | // Either the record variable or the field has an initializer that we can |
1757 | | // trust. We trust initializers of constants and, additionally, respect |
1758 | | // initializers of globals when analyzing main(). |
1759 | 14.8k | if (RecordVarTy.isConstQualified() || Ty.isConstQualified()14.5k || |
1760 | 14.4k | (B.isMainAnalysis() && VD->hasGlobalStorage()3 )) |
1761 | 349 | if (const Expr *Init = VD->getAnyInitializer()) |
1762 | 136 | if (const auto *InitList = dyn_cast<InitListExpr>(Init)) { |
1763 | 97 | if (Index < InitList->getNumInits()) { |
1764 | 96 | if (const Expr *FieldInit = InitList->getInit(Index)) |
1765 | 96 | if (Optional<SVal> V = svalBuilder.getConstantVal(FieldInit)) |
1766 | 96 | return *V; |
1767 | 1 | } else { |
1768 | 1 | return svalBuilder.makeZeroVal(Ty); |
1769 | 1 | } |
1770 | 61.2k | } |
1771 | 14.8k | } |
1772 | | |
1773 | 61.2k | return getBindingForFieldOrElementCommon(B, R, Ty); |
1774 | 61.2k | } |
1775 | | |
1776 | | Optional<SVal> |
1777 | | RegionStoreManager::getBindingForDerivedDefaultValue(RegionBindingsConstRef B, |
1778 | | const MemRegion *superR, |
1779 | | const TypedValueRegion *R, |
1780 | 182k | QualType Ty) { |
1781 | | |
1782 | 182k | if (const Optional<SVal> &D = B.getDefaultBinding(superR)) { |
1783 | 13.8k | const SVal &val = D.getValue(); |
1784 | 13.8k | if (SymbolRef parentSym = val.getAsSymbol()) |
1785 | 12.5k | return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R); |
1786 | | |
1787 | 1.32k | if (val.isZeroConstant()) |
1788 | 357 | return svalBuilder.makeZeroVal(Ty); |
1789 | | |
1790 | 969 | if (val.isUnknownOrUndef()) |
1791 | 947 | return val; |
1792 | | |
1793 | | // Lazy bindings are usually handled through getExistingLazyBinding(). |
1794 | | // We should unify these two code paths at some point. |
1795 | 22 | if (val.getAs<nonloc::LazyCompoundVal>() || |
1796 | 10 | val.getAs<nonloc::CompoundVal>()) |
1797 | 22 | return val; |
1798 | | |
1799 | 0 | llvm_unreachable("Unknown default value"); |
1800 | 0 | } |
1801 | | |
1802 | 169k | return None; |
1803 | 169k | } |
1804 | | |
1805 | | SVal RegionStoreManager::getLazyBinding(const SubRegion *LazyBindingRegion, |
1806 | 444 | RegionBindingsRef LazyBinding) { |
1807 | 444 | SVal Result; |
1808 | 444 | if (const ElementRegion *ER = dyn_cast<ElementRegion>(LazyBindingRegion)) |
1809 | 154 | Result = getBindingForElement(LazyBinding, ER); |
1810 | 290 | else |
1811 | 290 | Result = getBindingForField(LazyBinding, |
1812 | 290 | cast<FieldRegion>(LazyBindingRegion)); |
1813 | | |
1814 | | // FIXME: This is a hack to deal with RegionStore's inability to distinguish a |
1815 | | // default value for /part/ of an aggregate from a default value for the |
1816 | | // /entire/ aggregate. The most common case of this is when struct Outer |
1817 | | // has as its first member a struct Inner, which is copied in from a stack |
1818 | | // variable. In this case, even if the Outer's default value is symbolic, 0, |
1819 | | // or unknown, it gets overridden by the Inner's default value of undefined. |
1820 | | // |
1821 | | // This is a general problem -- if the Inner is zero-initialized, the Outer |
1822 | | // will now look zero-initialized. The proper way to solve this is with a |
1823 | | // new version of RegionStore that tracks the extent of a binding as well |
1824 | | // as the offset. |
1825 | | // |
1826 | | // This hack only takes care of the undefined case because that can very |
1827 | | // quickly result in a warning. |
1828 | 444 | if (Result.isUndef()) |
1829 | 7 | Result = UnknownVal(); |
1830 | | |
1831 | 444 | return Result; |
1832 | 444 | } |
1833 | | |
1834 | | SVal |
1835 | | RegionStoreManager::getBindingForFieldOrElementCommon(RegionBindingsConstRef B, |
1836 | | const TypedValueRegion *R, |
1837 | 71.9k | QualType Ty) { |
1838 | | |
1839 | | // At this point we have already checked in either getBindingForElement or |
1840 | | // getBindingForField if 'R' has a direct binding. |
1841 | | |
1842 | | // Lazy binding? |
1843 | 71.9k | Store lazyBindingStore = nullptr; |
1844 | 71.9k | const SubRegion *lazyBindingRegion = nullptr; |
1845 | 71.9k | std::tie(lazyBindingStore, lazyBindingRegion) = findLazyBinding(B, R, R); |
1846 | 71.9k | if (lazyBindingRegion) |
1847 | 444 | return getLazyBinding(lazyBindingRegion, |
1848 | 444 | getRegionBindings(lazyBindingStore)); |
1849 | | |
1850 | | // Record whether or not we see a symbolic index. That can completely |
1851 | | // be out of scope of our lookup. |
1852 | 71.4k | bool hasSymbolicIndex = false; |
1853 | | |
1854 | | // FIXME: This is a hack to deal with RegionStore's inability to distinguish a |
1855 | | // default value for /part/ of an aggregate from a default value for the |
1856 | | // /entire/ aggregate. The most common case of this is when struct Outer |
1857 | | // has as its first member a struct Inner, which is copied in from a stack |
1858 | | // variable. In this case, even if the Outer's default value is symbolic, 0, |
1859 | | // or unknown, it gets overridden by the Inner's default value of undefined. |
1860 | | // |
1861 | | // This is a general problem -- if the Inner is zero-initialized, the Outer |
1862 | | // will now look zero-initialized. The proper way to solve this is with a |
1863 | | // new version of RegionStore that tracks the extent of a binding as well |
1864 | | // as the offset. |
1865 | | // |
1866 | | // This hack only takes care of the undefined case because that can very |
1867 | | // quickly result in a warning. |
1868 | 71.4k | bool hasPartialLazyBinding = false; |
1869 | | |
1870 | 71.4k | const SubRegion *SR = R; |
1871 | 239k | while (SR) { |
1872 | 176k | const MemRegion *Base = SR->getSuperRegion(); |
1873 | 176k | if (Optional<SVal> D = getBindingForDerivedDefaultValue(B, Base, R, Ty)) { |
1874 | 8.55k | if (D->getAs<nonloc::LazyCompoundVal>()) { |
1875 | 12 | hasPartialLazyBinding = true; |
1876 | 12 | break; |
1877 | 12 | } |
1878 | | |
1879 | 8.53k | return *D; |
1880 | 8.53k | } |
1881 | | |
1882 | 167k | if (const ElementRegion *ER = dyn_cast<ElementRegion>(Base)) { |
1883 | 37.4k | NonLoc index = ER->getIndex(); |
1884 | 37.4k | if (!index.isConstant()) |
1885 | 27.0k | hasSymbolicIndex = true; |
1886 | 37.4k | } |
1887 | | |
1888 | | // If our super region is a field or element itself, walk up the region |
1889 | | // hierarchy to see if there is a default value installed in an ancestor. |
1890 | 167k | SR = dyn_cast<SubRegion>(Base); |
1891 | 167k | } |
1892 | | |
1893 | 62.9k | if (R->hasStackNonParametersStorage()) { |
1894 | 16.7k | if (isa<ElementRegion>(R)) { |
1895 | | // Currently we don't reason specially about Clang-style vectors. Check |
1896 | | // if superR is a vector and if so return Unknown. |
1897 | 2.64k | if (const TypedValueRegion *typedSuperR = |
1898 | 2.63k | dyn_cast<TypedValueRegion>(R->getSuperRegion())) { |
1899 | 2.63k | if (typedSuperR->getValueType()->isVectorType()) |
1900 | 6 | return UnknownVal(); |
1901 | 16.7k | } |
1902 | 2.64k | } |
1903 | | |
1904 | | // FIXME: We also need to take ElementRegions with symbolic indexes into |
1905 | | // account. This case handles both directly accessing an ElementRegion |
1906 | | // with a symbolic offset, but also fields within an element with |
1907 | | // a symbolic offset. |
1908 | 16.7k | if (hasSymbolicIndex) |
1909 | 11 | return UnknownVal(); |
1910 | | |
1911 | | // Additionally allow introspection of a block's internal layout. |
1912 | 16.6k | if (!hasPartialLazyBinding && !isa<BlockDataRegion>(R->getBaseRegion())16.6k ) |
1913 | 16.6k | return UndefinedVal(); |
1914 | 46.2k | } |
1915 | | |
1916 | | // All other values are symbolic. |
1917 | 46.2k | return svalBuilder.getRegionValueSymbolVal(R); |
1918 | 46.2k | } |
1919 | | |
1920 | | SVal RegionStoreManager::getBindingForObjCIvar(RegionBindingsConstRef B, |
1921 | 2.51k | const ObjCIvarRegion* R) { |
1922 | | // Check if the region has a binding. |
1923 | 2.51k | if (const Optional<SVal> &V = B.getDirectBinding(R)) |
1924 | 1.11k | return *V; |
1925 | | |
1926 | 1.40k | const MemRegion *superR = R->getSuperRegion(); |
1927 | | |
1928 | | // Check if the super region has a default binding. |
1929 | 1.40k | if (const Optional<SVal> &V = B.getDefaultBinding(superR)) { |
1930 | 66 | if (SymbolRef parentSym = V->getAsSymbol()) |
1931 | 66 | return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R); |
1932 | | |
1933 | | // Other cases: give up. |
1934 | 0 | return UnknownVal(); |
1935 | 0 | } |
1936 | | |
1937 | 1.33k | return getBindingForLazySymbol(R); |
1938 | 1.33k | } |
1939 | | |
1940 | | SVal RegionStoreManager::getBindingForVar(RegionBindingsConstRef B, |
1941 | 304k | const VarRegion *R) { |
1942 | | |
1943 | | // Check if the region has a binding. |
1944 | 304k | if (Optional<SVal> V = B.getDirectBinding(R)) |
1945 | 180k | return *V; |
1946 | | |
1947 | 123k | if (Optional<SVal> V = B.getDefaultBinding(R)) |
1948 | 13 | return *V; |
1949 | | |
1950 | | // Lazily derive a value for the VarRegion. |
1951 | 123k | const VarDecl *VD = R->getDecl(); |
1952 | 123k | const MemSpaceRegion *MS = R->getMemorySpace(); |
1953 | | |
1954 | | // Arguments are always symbolic. |
1955 | 123k | if (isa<StackArgumentsSpaceRegion>(MS)) |
1956 | 58.3k | return svalBuilder.getRegionValueSymbolVal(R); |
1957 | | |
1958 | | // Is 'VD' declared constant? If so, retrieve the constant value. |
1959 | 65.5k | if (VD->getType().isConstQualified()) { |
1960 | 788 | if (const Expr *Init = VD->getAnyInitializer()) { |
1961 | 552 | if (Optional<SVal> V = svalBuilder.getConstantVal(Init)) |
1962 | 515 | return *V; |
1963 | | |
1964 | | // If the variable is const qualified and has an initializer but |
1965 | | // we couldn't evaluate initializer to a value, treat the value as |
1966 | | // unknown. |
1967 | 37 | return UnknownVal(); |
1968 | 37 | } |
1969 | 788 | } |
1970 | | |
1971 | | // This must come after the check for constants because closure-captured |
1972 | | // constant variables may appear in UnknownSpaceRegion. |
1973 | 64.9k | if (isa<UnknownSpaceRegion>(MS)) |
1974 | 138 | return svalBuilder.getRegionValueSymbolVal(R); |
1975 | | |
1976 | 64.8k | if (isa<GlobalsSpaceRegion>(MS)) { |
1977 | 6.87k | QualType T = VD->getType(); |
1978 | | |
1979 | | // If we're in main(), then global initializers have not become stale yet. |
1980 | 6.87k | if (B.isMainAnalysis()) |
1981 | 3 | if (const Expr *Init = VD->getAnyInitializer()) |
1982 | 1 | if (Optional<SVal> V = svalBuilder.getConstantVal(Init)) |
1983 | 1 | return *V; |
1984 | | |
1985 | | // Function-scoped static variables are default-initialized to 0; if they |
1986 | | // have an initializer, it would have been processed by now. |
1987 | | // FIXME: This is only true when we're starting analysis from main(). |
1988 | | // We're losing a lot of coverage here. |
1989 | 6.87k | if (isa<StaticGlobalSpaceRegion>(MS)) |
1990 | 203 | return svalBuilder.makeZeroVal(T); |
1991 | | |
1992 | 6.66k | if (Optional<SVal> V = getBindingForDerivedDefaultValue(B, MS, R, T)) { |
1993 | 5.31k | assert(!V->getAs<nonloc::LazyCompoundVal>()); |
1994 | 5.31k | return V.getValue(); |
1995 | 5.31k | } |
1996 | | |
1997 | 1.35k | return svalBuilder.getRegionValueSymbolVal(R); |
1998 | 1.35k | } |
1999 | | |
2000 | 57.9k | return UndefinedVal(); |
2001 | 57.9k | } |
2002 | | |
2003 | 1.33k | SVal RegionStoreManager::getBindingForLazySymbol(const TypedValueRegion *R) { |
2004 | | // All other values are symbolic. |
2005 | 1.33k | return svalBuilder.getRegionValueSymbolVal(R); |
2006 | 1.33k | } |
2007 | | |
2008 | | const RegionStoreManager::SValListTy & |
2009 | 14.2k | RegionStoreManager::getInterestingValues(nonloc::LazyCompoundVal LCV) { |
2010 | | // First, check the cache. |
2011 | 14.2k | LazyBindingsMapTy::iterator I = LazyBindingsMap.find(LCV.getCVData()); |
2012 | 14.2k | if (I != LazyBindingsMap.end()) |
2013 | 13.1k | return I->second; |
2014 | | |
2015 | | // If we don't have a list of values cached, start constructing it. |
2016 | 1.08k | SValListTy List; |
2017 | | |
2018 | 1.08k | const SubRegion *LazyR = LCV.getRegion(); |
2019 | 1.08k | RegionBindingsRef B = getRegionBindings(LCV.getStore()); |
2020 | | |
2021 | | // If this region had /no/ bindings at the time, there are no interesting |
2022 | | // values to return. |
2023 | 1.08k | const ClusterBindings *Cluster = B.lookup(LazyR->getBaseRegion()); |
2024 | 1.08k | if (!Cluster) |
2025 | 261 | return (LazyBindingsMap[LCV.getCVData()] = std::move(List)); |
2026 | | |
2027 | 827 | SmallVector<BindingPair, 32> Bindings; |
2028 | 827 | collectSubRegionBindings(Bindings, svalBuilder, *Cluster, LazyR, |
2029 | 827 | /*IncludeAllDefaultBindings=*/true); |
2030 | 827 | for (SmallVectorImpl<BindingPair>::const_iterator I = Bindings.begin(), |
2031 | 827 | E = Bindings.end(); |
2032 | 1.86k | I != E; ++I1.03k ) { |
2033 | 1.03k | SVal V = I->second; |
2034 | 1.03k | if (V.isUnknownOrUndef() || V.isConstant()951 ) |
2035 | 340 | continue; |
2036 | | |
2037 | 699 | if (Optional<nonloc::LazyCompoundVal> InnerLCV = |
2038 | 6 | V.getAs<nonloc::LazyCompoundVal>()) { |
2039 | 6 | const SValListTy &InnerList = getInterestingValues(*InnerLCV); |
2040 | 6 | List.insert(List.end(), InnerList.begin(), InnerList.end()); |
2041 | 6 | continue; |
2042 | 6 | } |
2043 | | |
2044 | 693 | List.push_back(V); |
2045 | 693 | } |
2046 | | |
2047 | 827 | return (LazyBindingsMap[LCV.getCVData()] = std::move(List)); |
2048 | 827 | } |
2049 | | |
2050 | | NonLoc RegionStoreManager::createLazyBinding(RegionBindingsConstRef B, |
2051 | 54.1k | const TypedValueRegion *R) { |
2052 | 54.1k | if (Optional<nonloc::LazyCompoundVal> V = |
2053 | 146 | getExistingLazyBinding(svalBuilder, B, R, false)) |
2054 | 146 | return *V; |
2055 | | |
2056 | 54.0k | return svalBuilder.makeLazyCompoundVal(StoreRef(B.asStore(), *this), R); |
2057 | 54.0k | } |
2058 | | |
2059 | 57.6k | static bool isRecordEmpty(const RecordDecl *RD) { |
2060 | 57.6k | if (!RD->field_empty()) |
2061 | 50.8k | return false; |
2062 | 6.82k | if (const CXXRecordDecl *CRD = dyn_cast<CXXRecordDecl>(RD)) |
2063 | 6.69k | return CRD->getNumBases() == 0; |
2064 | 133 | return true; |
2065 | 133 | } |
2066 | | |
2067 | | SVal RegionStoreManager::getBindingForStruct(RegionBindingsConstRef B, |
2068 | 58.2k | const TypedValueRegion *R) { |
2069 | 58.2k | const RecordDecl *RD = R->getValueType()->castAs<RecordType>()->getDecl(); |
2070 | 58.2k | if (!RD->getDefinition() || isRecordEmpty(RD)57.6k ) |
2071 | 6.15k | return UnknownVal(); |
2072 | | |
2073 | 52.0k | return createLazyBinding(B, R); |
2074 | 52.0k | } |
2075 | | |
2076 | | SVal RegionStoreManager::getBindingForArray(RegionBindingsConstRef B, |
2077 | 2.03k | const TypedValueRegion *R) { |
2078 | 2.03k | assert(Ctx.getAsConstantArrayType(R->getValueType()) && |
2079 | 2.03k | "Only constant array types can have compound bindings."); |
2080 | | |
2081 | 2.03k | return createLazyBinding(B, R); |
2082 | 2.03k | } |
2083 | | |
2084 | | bool RegionStoreManager::includedInBindings(Store store, |
2085 | 14.5k | const MemRegion *region) const { |
2086 | 14.5k | RegionBindingsRef B = getRegionBindings(store); |
2087 | 14.5k | region = region->getBaseRegion(); |
2088 | | |
2089 | | // Quick path: if the base is the head of a cluster, the region is live. |
2090 | 14.5k | if (B.lookup(region)) |
2091 | 0 | return true; |
2092 | | |
2093 | | // Slow path: if the region is the VALUE of any binding, it is live. |
2094 | 60.6k | for (RegionBindingsRef::iterator RI = B.begin(), RE = B.end(); 14.5k RI != RE; ++RI46.1k ) { |
2095 | 46.1k | const ClusterBindings &Cluster = RI.getData(); |
2096 | 46.1k | for (ClusterBindings::iterator CI = Cluster.begin(), CE = Cluster.end(); |
2097 | 92.6k | CI != CE; ++CI46.5k ) { |
2098 | 46.5k | const SVal &D = CI.getData(); |
2099 | 46.5k | if (const MemRegion *R = D.getAsRegion()) |
2100 | 9.36k | if (R->getBaseRegion() == region) |
2101 | 0 | return true; |
2102 | 46.5k | } |
2103 | 46.1k | } |
2104 | | |
2105 | 14.5k | return false; |
2106 | 14.5k | } |
2107 | | |
2108 | | //===----------------------------------------------------------------------===// |
2109 | | // Binding values to regions. |
2110 | | //===----------------------------------------------------------------------===// |
2111 | | |
2112 | 6 | StoreRef RegionStoreManager::killBinding(Store ST, Loc L) { |
2113 | 6 | if (Optional<loc::MemRegionVal> LV = L.getAs<loc::MemRegionVal>()) |
2114 | 0 | if (const MemRegion* R = LV->getRegion()) |
2115 | 0 | return StoreRef(getRegionBindings(ST).removeBinding(R) |
2116 | 0 | .asImmutableMap() |
2117 | 0 | .getRootWithoutRetain(), |
2118 | 0 | *this); |
2119 | | |
2120 | 6 | return StoreRef(ST, *this); |
2121 | 6 | } |
2122 | | |
2123 | | RegionBindingsRef |
2124 | 197k | RegionStoreManager::bind(RegionBindingsConstRef B, Loc L, SVal V) { |
2125 | 197k | if (L.getAs<loc::ConcreteInt>()) |
2126 | 5 | return B; |
2127 | | |
2128 | | // If we get here, the location should be a region. |
2129 | 197k | const MemRegion *R = L.castAs<loc::MemRegionVal>().getRegion(); |
2130 | | |
2131 | | // Check if the region is a struct region. |
2132 | 197k | if (const TypedValueRegion* TR = dyn_cast<TypedValueRegion>(R)) { |
2133 | 197k | QualType Ty = TR->getValueType(); |
2134 | 197k | if (Ty->isArrayType()) |
2135 | 1.30k | return bindArray(B, TR, V); |
2136 | 195k | if (Ty->isStructureOrClassType()) |
2137 | 23.4k | return bindStruct(B, TR, V); |
2138 | 172k | if (Ty->isVectorType()) |
2139 | 11 | return bindVector(B, TR, V); |
2140 | 172k | if (Ty->isUnionType()) |
2141 | 71 | return bindAggregate(B, TR, V); |
2142 | 173k | } |
2143 | | |
2144 | 173k | if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) { |
2145 | | // Binding directly to a symbolic region should be treated as binding |
2146 | | // to element 0. |
2147 | 558 | QualType T = SR->getSymbol()->getType(); |
2148 | 558 | if (T->isAnyPointerType() || T->isReferenceType()130 ) |
2149 | 558 | T = T->getPointeeType(); |
2150 | | |
2151 | 558 | R = GetElementZeroRegion(SR, T); |
2152 | 558 | } |
2153 | | |
2154 | 173k | assert((!isa<CXXThisRegion>(R) || !B.lookup(R)) && |
2155 | 173k | "'this' pointer is not an l-value and is not assignable"); |
2156 | | |
2157 | | // Clear out bindings that may overlap with this binding. |
2158 | 173k | RegionBindingsRef NewB = removeSubRegionBindings(B, cast<SubRegion>(R)); |
2159 | 173k | return NewB.addBinding(BindingKey::Make(R, BindingKey::Direct), V); |
2160 | 173k | } |
2161 | | |
2162 | | RegionBindingsRef |
2163 | | RegionStoreManager::setImplicitDefaultValue(RegionBindingsConstRef B, |
2164 | | const MemRegion *R, |
2165 | 320 | QualType T) { |
2166 | 320 | SVal V; |
2167 | | |
2168 | 320 | if (Loc::isLocType(T)) |
2169 | 10 | V = svalBuilder.makeNull(); |
2170 | 310 | else if (T->isIntegralOrEnumerationType()) |
2171 | 262 | V = svalBuilder.makeZeroVal(T); |
2172 | 48 | else if (T->isStructureOrClassType() || T->isArrayType()14 ) { |
2173 | | // Set the default value to a zero constant when it is a structure |
2174 | | // or array. The type doesn't really matter. |
2175 | 34 | V = svalBuilder.makeZeroVal(Ctx.IntTy); |
2176 | 34 | } |
2177 | 14 | else { |
2178 | | // We can't represent values of this type, but we still need to set a value |
2179 | | // to record that the region has been initialized. |
2180 | | // If this assertion ever fires, a new case should be added above -- we |
2181 | | // should know how to default-initialize any value we can symbolicate. |
2182 | 14 | assert(!SymbolManager::canSymbolicate(T) && "This type is representable"); |
2183 | 14 | V = UnknownVal(); |
2184 | 14 | } |
2185 | | |
2186 | 320 | return B.addBinding(R, BindingKey::Default, V); |
2187 | 320 | } |
2188 | | |
2189 | | RegionBindingsRef |
2190 | | RegionStoreManager::bindArray(RegionBindingsConstRef B, |
2191 | | const TypedValueRegion* R, |
2192 | 1.52k | SVal Init) { |
2193 | | |
2194 | 1.52k | const ArrayType *AT =cast<ArrayType>(Ctx.getCanonicalType(R->getValueType())); |
2195 | 1.52k | QualType ElementTy = AT->getElementType(); |
2196 | 1.52k | Optional<uint64_t> Size; |
2197 | | |
2198 | 1.52k | if (const ConstantArrayType* CAT = dyn_cast<ConstantArrayType>(AT)) |
2199 | 1.51k | Size = CAT->getSize().getZExtValue(); |
2200 | | |
2201 | | // Check if the init expr is a literal. If so, bind the rvalue instead. |
2202 | | // FIXME: It's not responsibility of the Store to transform this lvalue |
2203 | | // to rvalue. ExprEngine or maybe even CFG should do this before binding. |
2204 | 1.52k | if (Optional<loc::MemRegionVal> MRV = Init.getAs<loc::MemRegionVal>()) { |
2205 | 456 | SVal V = getBinding(B.asStore(), *MRV, R->getValueType()); |
2206 | 456 | return bindAggregate(B, R, V); |
2207 | 456 | } |
2208 | | |
2209 | | // Handle lazy compound values. |
2210 | 1.06k | if (Init.getAs<nonloc::LazyCompoundVal>()) |
2211 | 8 | return bindAggregate(B, R, Init); |
2212 | | |
2213 | 1.05k | if (Init.isUnknown()) |
2214 | 46 | return bindAggregate(B, R, UnknownVal()); |
2215 | | |
2216 | | // Remaining case: explicit compound values. |
2217 | 1.01k | const nonloc::CompoundVal& CV = Init.castAs<nonloc::CompoundVal>(); |
2218 | 1.01k | nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end(); |
2219 | 1.01k | uint64_t i = 0; |
2220 | | |
2221 | 1.01k | RegionBindingsRef NewB(B); |
2222 | | |
2223 | 3.88k | for (; Size.hasValue() ? i < Size.getValue()3.86k : true14 ; ++i, ++VI2.86k ) { |
2224 | | // The init list might be shorter than the array length. |
2225 | 3.18k | if (VI == VE) |
2226 | 320 | break; |
2227 | | |
2228 | 2.86k | const NonLoc &Idx = svalBuilder.makeArrayIndex(i); |
2229 | 2.86k | const ElementRegion *ER = MRMgr.getElementRegion(ElementTy, Idx, R, Ctx); |
2230 | | |
2231 | 2.86k | if (ElementTy->isStructureOrClassType()) |
2232 | 190 | NewB = bindStruct(NewB, ER, *VI); |
2233 | 2.67k | else if (ElementTy->isArrayType()) |
2234 | 81 | NewB = bindArray(NewB, ER, *VI); |
2235 | 2.59k | else |
2236 | 2.59k | NewB = bind(NewB, loc::MemRegionVal(ER), *VI); |
2237 | 2.86k | } |
2238 | | |
2239 | | // If the init list is shorter than the array length (or the array has |
2240 | | // variable length), set the array default value. Values that are already set |
2241 | | // are not overwritten. |
2242 | 1.01k | if (!Size.hasValue() || i < Size.getValue()1.00k ) |
2243 | 320 | NewB = setImplicitDefaultValue(NewB, R, ElementTy); |
2244 | | |
2245 | 1.01k | return NewB; |
2246 | 1.01k | } |
2247 | | |
2248 | | RegionBindingsRef RegionStoreManager::bindVector(RegionBindingsConstRef B, |
2249 | | const TypedValueRegion* R, |
2250 | 11 | SVal V) { |
2251 | 11 | QualType T = R->getValueType(); |
2252 | 11 | const VectorType *VT = T->castAs<VectorType>(); // Use castAs for typedefs. |
2253 | | |
2254 | | // Handle lazy compound values and symbolic values. |
2255 | 11 | if (V.getAs<nonloc::LazyCompoundVal>() || V.getAs<nonloc::SymbolVal>()) |
2256 | 0 | return bindAggregate(B, R, V); |
2257 | | |
2258 | | // We may get non-CompoundVal accidentally due to imprecise cast logic or |
2259 | | // that we are binding symbolic struct value. Kill the field values, and if |
2260 | | // the value is symbolic go and bind it as a "default" binding. |
2261 | 11 | if (!V.getAs<nonloc::CompoundVal>()) { |
2262 | 3 | return bindAggregate(B, R, UnknownVal()); |
2263 | 3 | } |
2264 | | |
2265 | 8 | QualType ElemType = VT->getElementType(); |
2266 | 8 | nonloc::CompoundVal CV = V.castAs<nonloc::CompoundVal>(); |
2267 | 8 | nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end(); |
2268 | 8 | unsigned index = 0, numElements = VT->getNumElements(); |
2269 | 8 | RegionBindingsRef NewB(B); |
2270 | | |
2271 | 28 | for ( ; index != numElements ; ++index20 ) { |
2272 | 20 | if (VI == VE) |
2273 | 0 | break; |
2274 | | |
2275 | 20 | NonLoc Idx = svalBuilder.makeArrayIndex(index); |
2276 | 20 | const ElementRegion *ER = MRMgr.getElementRegion(ElemType, Idx, R, Ctx); |
2277 | | |
2278 | 20 | if (ElemType->isArrayType()) |
2279 | 0 | NewB = bindArray(NewB, ER, *VI); |
2280 | 20 | else if (ElemType->isStructureOrClassType()) |
2281 | 0 | NewB = bindStruct(NewB, ER, *VI); |
2282 | 20 | else |
2283 | 20 | NewB = bind(NewB, loc::MemRegionVal(ER), *VI); |
2284 | 20 | } |
2285 | 8 | return NewB; |
2286 | 8 | } |
2287 | | |
2288 | | Optional<RegionBindingsRef> |
2289 | | RegionStoreManager::tryBindSmallStruct(RegionBindingsConstRef B, |
2290 | | const TypedValueRegion *R, |
2291 | | const RecordDecl *RD, |
2292 | 22.2k | nonloc::LazyCompoundVal LCV) { |
2293 | 22.2k | FieldVector Fields; |
2294 | | |
2295 | 22.2k | if (const CXXRecordDecl *Class = dyn_cast<CXXRecordDecl>(RD)) |
2296 | 22.0k | if (Class->getNumBases() != 0 || Class->getNumVBases() != 021.9k ) |
2297 | 75 | return None; |
2298 | | |
2299 | 22.6k | for (const auto *FD : RD->fields())22.1k { |
2300 | 22.6k | if (FD->isUnnamedBitfield()) |
2301 | 8 | continue; |
2302 | | |
2303 | | // If there are too many fields, or if any of the fields are aggregates, |
2304 | | // just use the LCV as a default binding. |
2305 | 22.6k | if (Fields.size() == SmallStructLimit) |
2306 | 106 | return None; |
2307 | | |
2308 | 22.5k | QualType Ty = FD->getType(); |
2309 | 22.5k | if (!(Ty->isScalarType() || Ty->isReferenceType()495 )) |
2310 | 187 | return None; |
2311 | | |
2312 | 22.3k | Fields.push_back(FD); |
2313 | 22.3k | } |
2314 | | |
2315 | 21.8k | RegionBindingsRef NewB = B; |
2316 | | |
2317 | 43.9k | for (FieldVector::iterator I = Fields.begin(), E = Fields.end(); I != E; ++I22.1k ){ |
2318 | 22.1k | const FieldRegion *SourceFR = MRMgr.getFieldRegion(*I, LCV.getRegion()); |
2319 | 22.1k | SVal V = getBindingForField(getRegionBindings(LCV.getStore()), SourceFR); |
2320 | | |
2321 | 22.1k | const FieldRegion *DestFR = MRMgr.getFieldRegion(*I, R); |
2322 | 22.1k | NewB = bind(NewB, loc::MemRegionVal(DestFR), V); |
2323 | 22.1k | } |
2324 | | |
2325 | 21.8k | return NewB; |
2326 | 22.1k | } |
2327 | | |
2328 | | RegionBindingsRef RegionStoreManager::bindStruct(RegionBindingsConstRef B, |
2329 | | const TypedValueRegion* R, |
2330 | 23.7k | SVal V) { |
2331 | 23.7k | if (!Features.supportsFields()) |
2332 | 0 | return B; |
2333 | | |
2334 | 23.7k | QualType T = R->getValueType(); |
2335 | 23.7k | assert(T->isStructureOrClassType()); |
2336 | | |
2337 | 23.7k | const RecordType* RT = T->castAs<RecordType>(); |
2338 | 23.7k | const RecordDecl *RD = RT->getDecl(); |
2339 | | |
2340 | 23.7k | if (!RD->isCompleteDefinition()) |
2341 | 0 | return B; |
2342 | | |
2343 | | // Handle lazy compound values and symbolic values. |
2344 | 23.7k | if (Optional<nonloc::LazyCompoundVal> LCV = |
2345 | 22.2k | V.getAs<nonloc::LazyCompoundVal>()) { |
2346 | 22.2k | if (Optional<RegionBindingsRef> NewB = tryBindSmallStruct(B, R, RD, *LCV)) |
2347 | 21.8k | return *NewB; |
2348 | 368 | return bindAggregate(B, R, V); |
2349 | 368 | } |
2350 | 1.52k | if (V.getAs<nonloc::SymbolVal>()) |
2351 | 448 | return bindAggregate(B, R, V); |
2352 | | |
2353 | | // We may get non-CompoundVal accidentally due to imprecise cast logic or |
2354 | | // that we are binding symbolic struct value. Kill the field values, and if |
2355 | | // the value is symbolic go and bind it as a "default" binding. |
2356 | 1.07k | if (V.isUnknown() || !V.getAs<nonloc::CompoundVal>()1.00k ) |
2357 | 78 | return bindAggregate(B, R, UnknownVal()); |
2358 | | |
2359 | | // The raw CompoundVal is essentially a symbolic InitListExpr: an (immutable) |
2360 | | // list of other values. It appears pretty much only when there's an actual |
2361 | | // initializer list expression in the program, and the analyzer tries to |
2362 | | // unwrap it as soon as possible. |
2363 | | // This code is where such unwrap happens: when the compound value is put into |
2364 | | // the object that it was supposed to initialize (it's an *initializer* list, |
2365 | | // after all), instead of binding the whole value to the whole object, we bind |
2366 | | // sub-values to sub-objects. Sub-values may themselves be compound values, |
2367 | | // and in this case the procedure becomes recursive. |
2368 | | // FIXME: The annoying part about compound values is that they don't carry |
2369 | | // any sort of information about which value corresponds to which sub-object. |
2370 | | // It's simply a list of values in the middle of nowhere; we expect to match |
2371 | | // them to sub-objects, essentially, "by index": first value binds to |
2372 | | // the first field, second value binds to the second field, etc. |
2373 | | // It would have been much safer to organize non-lazy compound values as |
2374 | | // a mapping from fields/bases to values. |
2375 | 998 | const nonloc::CompoundVal& CV = V.castAs<nonloc::CompoundVal>(); |
2376 | 998 | nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end(); |
2377 | | |
2378 | 998 | RegionBindingsRef NewB(B); |
2379 | | |
2380 | | // In C++17 aggregates may have base classes, handle those as well. |
2381 | | // They appear before fields in the initializer list / compound value. |
2382 | 998 | if (const auto *CRD = dyn_cast<CXXRecordDecl>(RD)) { |
2383 | | // If the object was constructed with a constructor, its value is a |
2384 | | // LazyCompoundVal. If it's a raw CompoundVal, it means that we're |
2385 | | // performing aggregate initialization. The only exception from this |
2386 | | // rule is sending an Objective-C++ message that returns a C++ object |
2387 | | // to a nil receiver; in this case the semantics is to return a |
2388 | | // zero-initialized object even if it's a C++ object that doesn't have |
2389 | | // this sort of constructor; the CompoundVal is empty in this case. |
2390 | 768 | assert((CRD->isAggregate() || (Ctx.getLangOpts().ObjC && VI == VE)) && |
2391 | 768 | "Non-aggregates are constructed with a constructor!"); |
2392 | | |
2393 | 66 | for (const auto &B : CRD->bases()) { |
2394 | | // (Multiple inheritance is fine though.) |
2395 | 66 | assert(!B.isVirtual() && "Aggregates cannot have virtual base classes!"); |
2396 | | |
2397 | 66 | if (VI == VE) |
2398 | 0 | break; |
2399 | | |
2400 | 66 | QualType BTy = B.getType(); |
2401 | 66 | assert(BTy->isStructureOrClassType() && "Base classes must be classes!"); |
2402 | | |
2403 | 66 | const CXXRecordDecl *BRD = BTy->getAsCXXRecordDecl(); |
2404 | 66 | assert(BRD && "Base classes must be C++ classes!"); |
2405 | | |
2406 | 66 | const CXXBaseObjectRegion *BR = |
2407 | 66 | MRMgr.getCXXBaseObjectRegion(BRD, R, /*IsVirtual=*/false); |
2408 | | |
2409 | 66 | NewB = bindStruct(NewB, BR, *VI); |
2410 | | |
2411 | 66 | ++VI; |
2412 | 66 | } |
2413 | 768 | } |
2414 | | |
2415 | 998 | RecordDecl::field_iterator FI, FE; |
2416 | | |
2417 | 1.94k | for (FI = RD->field_begin(), FE = RD->field_end(); FI != FE; ++FI946 ) { |
2418 | | |
2419 | 953 | if (VI == VE) |
2420 | 7 | break; |
2421 | | |
2422 | | // Skip any unnamed bitfields to stay in sync with the initializers. |
2423 | 946 | if (FI->isUnnamedBitfield()) |
2424 | 4 | continue; |
2425 | | |
2426 | 942 | QualType FTy = FI->getType(); |
2427 | 942 | const FieldRegion* FR = MRMgr.getFieldRegion(*FI, R); |
2428 | | |
2429 | 942 | if (FTy->isArrayType()) |
2430 | 140 | NewB = bindArray(NewB, FR, *VI); |
2431 | 802 | else if (FTy->isStructureOrClassType()) |
2432 | 45 | NewB = bindStruct(NewB, FR, *VI); |
2433 | 757 | else |
2434 | 757 | NewB = bind(NewB, loc::MemRegionVal(FR), *VI); |
2435 | 942 | ++VI; |
2436 | 942 | } |
2437 | | |
2438 | | // There may be fewer values in the initialize list than the fields of struct. |
2439 | 998 | if (FI != FE) { |
2440 | 7 | NewB = NewB.addBinding(R, BindingKey::Default, |
2441 | 7 | svalBuilder.makeIntVal(0, false)); |
2442 | 7 | } |
2443 | | |
2444 | 998 | return NewB; |
2445 | 998 | } |
2446 | | |
2447 | | RegionBindingsRef |
2448 | | RegionStoreManager::bindAggregate(RegionBindingsConstRef B, |
2449 | | const TypedRegion *R, |
2450 | 1.47k | SVal Val) { |
2451 | | // Remove the old bindings, using 'R' as the root of all regions |
2452 | | // we will invalidate. Then add the new binding. |
2453 | 1.47k | return removeSubRegionBindings(B, R).addBinding(R, BindingKey::Default, Val); |
2454 | 1.47k | } |
2455 | | |
2456 | | //===----------------------------------------------------------------------===// |
2457 | | // State pruning. |
2458 | | //===----------------------------------------------------------------------===// |
2459 | | |
2460 | | namespace { |
2461 | | class RemoveDeadBindingsWorker |
2462 | | : public ClusterAnalysis<RemoveDeadBindingsWorker> { |
2463 | | SmallVector<const SymbolicRegion *, 12> Postponed; |
2464 | | SymbolReaper &SymReaper; |
2465 | | const StackFrameContext *CurrentLCtx; |
2466 | | |
2467 | | public: |
2468 | | RemoveDeadBindingsWorker(RegionStoreManager &rm, |
2469 | | ProgramStateManager &stateMgr, |
2470 | | RegionBindingsRef b, SymbolReaper &symReaper, |
2471 | | const StackFrameContext *LCtx) |
2472 | | : ClusterAnalysis<RemoveDeadBindingsWorker>(rm, stateMgr, b), |
2473 | 360k | SymReaper(symReaper), CurrentLCtx(LCtx) {} |
2474 | | |
2475 | | // Called by ClusterAnalysis. |
2476 | | void VisitAddedToCluster(const MemRegion *baseR, const ClusterBindings &C); |
2477 | | void VisitCluster(const MemRegion *baseR, const ClusterBindings *C); |
2478 | | using ClusterAnalysis<RemoveDeadBindingsWorker>::VisitCluster; |
2479 | | |
2480 | | using ClusterAnalysis::AddToWorkList; |
2481 | | |
2482 | | bool AddToWorkList(const MemRegion *R); |
2483 | | |
2484 | | bool UpdatePostponed(); |
2485 | | void VisitBinding(SVal V); |
2486 | | }; |
2487 | | } |
2488 | | |
2489 | 1.17M | bool RemoveDeadBindingsWorker::AddToWorkList(const MemRegion *R) { |
2490 | 1.17M | const MemRegion *BaseR = R->getBaseRegion(); |
2491 | 1.17M | return AddToWorkList(WorkListElement(BaseR), getCluster(BaseR)); |
2492 | 1.17M | } |
2493 | | |
2494 | | void RemoveDeadBindingsWorker::VisitAddedToCluster(const MemRegion *baseR, |
2495 | 1.33M | const ClusterBindings &C) { |
2496 | | |
2497 | 1.33M | if (const VarRegion *VR = dyn_cast<VarRegion>(baseR)) { |
2498 | 652k | if (SymReaper.isLive(VR)) |
2499 | 527k | AddToWorkList(baseR, &C); |
2500 | | |
2501 | 652k | return; |
2502 | 652k | } |
2503 | | |
2504 | 679k | if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(baseR)) { |
2505 | 53.6k | if (SymReaper.isLive(SR->getSymbol())) |
2506 | 41.2k | AddToWorkList(SR, &C); |
2507 | 12.4k | else |
2508 | 12.4k | Postponed.push_back(SR); |
2509 | | |
2510 | 53.6k | return; |
2511 | 53.6k | } |
2512 | | |
2513 | 625k | if (isa<NonStaticGlobalSpaceRegion>(baseR)) { |
2514 | 464k | AddToWorkList(baseR, &C); |
2515 | 464k | return; |
2516 | 464k | } |
2517 | | |
2518 | | // CXXThisRegion in the current or parent location context is live. |
2519 | 161k | if (const CXXThisRegion *TR = dyn_cast<CXXThisRegion>(baseR)) { |
2520 | 136k | const auto *StackReg = |
2521 | 136k | cast<StackArgumentsSpaceRegion>(TR->getSuperRegion()); |
2522 | 136k | const StackFrameContext *RegCtx = StackReg->getStackFrame(); |
2523 | 136k | if (CurrentLCtx && |
2524 | 136k | (RegCtx == CurrentLCtx || RegCtx->isParentOf(CurrentLCtx)84.8k )) |
2525 | 119k | AddToWorkList(TR, &C); |
2526 | 136k | } |
2527 | 161k | } |
2528 | | |
2529 | | void RemoveDeadBindingsWorker::VisitCluster(const MemRegion *baseR, |
2530 | 1.92M | const ClusterBindings *C) { |
2531 | 1.92M | if (!C) |
2532 | 701k | return; |
2533 | | |
2534 | | // Mark the symbol for any SymbolicRegion with live bindings as live itself. |
2535 | | // This means we should continue to track that symbol. |
2536 | 1.21M | if (const SymbolicRegion *SymR = dyn_cast<SymbolicRegion>(baseR)) |
2537 | 46.6k | SymReaper.markLive(SymR->getSymbol()); |
2538 | | |
2539 | 2.73M | for (ClusterBindings::iterator I = C->begin(), E = C->end(); I != E; ++I1.51M ) { |
2540 | | // Element index of a binding key is live. |
2541 | 1.51M | SymReaper.markElementIndicesLive(I.getKey().getRegion()); |
2542 | | |
2543 | 1.51M | VisitBinding(I.getData()); |
2544 | 1.51M | } |
2545 | 1.21M | } |
2546 | | |
2547 | 1.51M | void RemoveDeadBindingsWorker::VisitBinding(SVal V) { |
2548 | | // Is it a LazyCompoundVal? All referenced regions are live as well. |
2549 | 1.51M | if (Optional<nonloc::LazyCompoundVal> LCS = |
2550 | 4.44k | V.getAs<nonloc::LazyCompoundVal>()) { |
2551 | | |
2552 | 4.44k | const RegionStoreManager::SValListTy &Vals = RM.getInterestingValues(*LCS); |
2553 | | |
2554 | 4.44k | for (RegionStoreManager::SValListTy::const_iterator I = Vals.begin(), |
2555 | 4.44k | E = Vals.end(); |
2556 | 4.83k | I != E; ++I390 ) |
2557 | 390 | VisitBinding(*I); |
2558 | | |
2559 | 4.44k | return; |
2560 | 4.44k | } |
2561 | | |
2562 | | // If V is a region, then add it to the worklist. |
2563 | 1.50M | if (const MemRegion *R = V.getAsRegion()) { |
2564 | 387k | AddToWorkList(R); |
2565 | 387k | SymReaper.markLive(R); |
2566 | | |
2567 | | // All regions captured by a block are also live. |
2568 | 387k | if (const BlockDataRegion *BR = dyn_cast<BlockDataRegion>(R)) { |
2569 | 624 | BlockDataRegion::referenced_vars_iterator I = BR->referenced_vars_begin(), |
2570 | 624 | E = BR->referenced_vars_end(); |
2571 | 1.18k | for ( ; I != E; ++I563 ) |
2572 | 563 | AddToWorkList(I.getCapturedRegion()); |
2573 | 624 | } |
2574 | 387k | } |
2575 | | |
2576 | | |
2577 | | // Update the set of live symbols. |
2578 | 2.37M | for (auto SI = V.symbol_begin(), SE = V.symbol_end(); SI!=SE; ++SI869k ) |
2579 | 869k | SymReaper.markLive(*SI); |
2580 | 1.50M | } |
2581 | | |
2582 | 362k | bool RemoveDeadBindingsWorker::UpdatePostponed() { |
2583 | | // See if any postponed SymbolicRegions are actually live now, after |
2584 | | // having done a scan. |
2585 | 362k | bool Changed = false; |
2586 | | |
2587 | 376k | for (auto I = Postponed.begin(), E = Postponed.end(); I != E; ++I14.6k ) { |
2588 | 14.6k | if (const SymbolicRegion *SR = *I) { |
2589 | 12.6k | if (SymReaper.isLive(SR->getSymbol())) { |
2590 | 5.45k | Changed |= AddToWorkList(SR); |
2591 | 5.45k | *I = nullptr; |
2592 | 5.45k | } |
2593 | 12.6k | } |
2594 | 14.6k | } |
2595 | | |
2596 | 362k | return Changed; |
2597 | 362k | } |
2598 | | |
2599 | | StoreRef RegionStoreManager::removeDeadBindings(Store store, |
2600 | | const StackFrameContext *LCtx, |
2601 | 360k | SymbolReaper& SymReaper) { |
2602 | 360k | RegionBindingsRef B = getRegionBindings(store); |
2603 | 360k | RemoveDeadBindingsWorker W(*this, StateMgr, B, SymReaper, LCtx); |
2604 | 360k | W.GenerateClusters(); |
2605 | | |
2606 | | // Enqueue the region roots onto the worklist. |
2607 | 360k | for (SymbolReaper::region_iterator I = SymReaper.region_begin(), |
2608 | 1.14M | E = SymReaper.region_end(); I != E; ++I785k ) { |
2609 | 785k | W.AddToWorkList(*I); |
2610 | 785k | } |
2611 | | |
2612 | 362k | do W.RunWorkList(); while (W.UpdatePostponed()); |
2613 | | |
2614 | | // We have now scanned the store, marking reachable regions and symbols |
2615 | | // as live. We now remove all the regions that are dead from the store |
2616 | | // as well as update DSymbols with the set symbols that are now dead. |
2617 | 1.69M | for (RegionBindingsRef::iterator I = B.begin(), E = B.end(); I != E; ++I1.33M ) { |
2618 | 1.33M | const MemRegion *Base = I.getKey(); |
2619 | | |
2620 | | // If the cluster has been visited, we know the region has been marked. |
2621 | | // Otherwise, remove the dead entry. |
2622 | 1.33M | if (!W.isVisited(Base)) |
2623 | 112k | B = B.remove(Base); |
2624 | 1.33M | } |
2625 | | |
2626 | 360k | return StoreRef(B.asStore(), *this); |
2627 | 360k | } |
2628 | | |
2629 | | //===----------------------------------------------------------------------===// |
2630 | | // Utility methods. |
2631 | | //===----------------------------------------------------------------------===// |
2632 | | |
2633 | | void RegionStoreManager::printJson(raw_ostream &Out, Store S, const char *NL, |
2634 | 126 | unsigned int Space, bool IsDot) const { |
2635 | 126 | RegionBindingsRef Bindings = getRegionBindings(S); |
2636 | | |
2637 | 126 | Indent(Out, Space, IsDot) << "\"store\": "; |
2638 | | |
2639 | 126 | if (Bindings.isEmpty()) { |
2640 | 40 | Out << "null," << NL; |
2641 | 40 | return; |
2642 | 40 | } |
2643 | | |
2644 | 86 | Out << "{ \"pointer\": \"" << Bindings.asStore() << "\", \"items\": [" << NL; |
2645 | 86 | Bindings.printJson(Out, NL, Space + 1, IsDot); |
2646 | 86 | Indent(Out, Space, IsDot) << "]}," << NL; |
2647 | 86 | } |