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