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