Coverage Report

Created: 2019-07-24 05:18

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