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