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