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