Coverage Report

Created: 2020-02-25 14:32

/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/lib/StaticAnalyzer/Core/ProgramState.cpp
Line
Count
Source (jump to first uncovered line)
1
//= ProgramState.cpp - Path-Sensitive "State" for tracking values --*- 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 implements ProgramState and ProgramStateManager.
10
//
11
//===----------------------------------------------------------------------===//
12
13
#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
14
#include "clang/Analysis/CFG.h"
15
#include "clang/Basic/JsonSupport.h"
16
#include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
17
#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
18
#include "clang/StaticAnalyzer/Core/PathSensitive/DynamicType.h"
19
#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
20
#include "clang/StaticAnalyzer/Core/PathSensitive/SubEngine.h"
21
#include "llvm/Support/raw_ostream.h"
22
23
using namespace clang;
24
using namespace ento;
25
26
namespace clang { namespace  ento {
27
/// Increments the number of times this state is referenced.
28
29
55.2M
void ProgramStateRetain(const ProgramState *state) {
30
55.2M
  ++const_cast<ProgramState*>(state)->refCount;
31
55.2M
}
32
33
/// Decrement the number of times this state is referenced.
34
49.9M
void ProgramStateRelease(const ProgramState *state) {
35
49.9M
  assert(state->refCount > 0);
36
49.9M
  ProgramState *s = const_cast<ProgramState*>(state);
37
49.9M
  if (--s->refCount == 0) {
38
520k
    ProgramStateManager &Mgr = s->getStateManager();
39
520k
    Mgr.StateSet.RemoveNode(s);
40
520k
    s->~ProgramState();
41
520k
    Mgr.freeStates.push_back(s);
42
520k
  }
43
49.9M
}
44
}}
45
46
ProgramState::ProgramState(ProgramStateManager *mgr, const Environment& env,
47
                 StoreRef st, GenericDataMap gdm)
48
  : stateMgr(mgr),
49
    Env(env),
50
    store(st.getStore()),
51
    GDM(gdm),
52
12.6k
    refCount(0) {
53
12.6k
  stateMgr->getStoreManager().incrementReferenceCount(store);
54
12.6k
}
55
56
ProgramState::ProgramState(const ProgramState &RHS)
57
    : llvm::FoldingSetNode(),
58
      stateMgr(RHS.stateMgr),
59
      Env(RHS.Env),
60
      store(RHS.store),
61
      GDM(RHS.GDM),
62
4.32M
      refCount(0) {
63
4.32M
  stateMgr->getStoreManager().incrementReferenceCount(store);
64
4.32M
}
65
66
2.98M
ProgramState::~ProgramState() {
67
2.98M
  if (store)
68
2.80M
    stateMgr->getStoreManager().decrementReferenceCount(store);
69
2.98M
}
70
71
2.95k
int64_t ProgramState::getID() const {
72
2.95k
  return getStateManager().Alloc.identifyKnownAlignedObject<ProgramState>(this);
73
2.95k
}
74
75
ProgramStateManager::ProgramStateManager(ASTContext &Ctx,
76
                                         StoreManagerCreator CreateSMgr,
77
                                         ConstraintManagerCreator CreateCMgr,
78
                                         llvm::BumpPtrAllocator &alloc,
79
                                         SubEngine *SubEng)
80
  : Eng(SubEng), EnvMgr(alloc), GDMFactory(alloc),
81
    svalBuilder(createSimpleSValBuilder(alloc, Ctx, *this)),
82
12.6k
    CallEventMgr(new CallEventManager(alloc)), Alloc(alloc) {
83
12.6k
  StoreMgr = (*CreateSMgr)(*this);
84
12.6k
  ConstraintMgr = (*CreateCMgr)(*this, SubEng);
85
12.6k
}
86
87
88
12.6k
ProgramStateManager::~ProgramStateManager() {
89
12.6k
  for (GDMContextsTy::iterator I=GDMContexts.begin(), E=GDMContexts.end();
90
44.6k
       I!=E; 
++I31.9k
)
91
31.9k
    I->second.second(I->second.first);
92
12.6k
}
93
94
ProgramStateRef ProgramStateManager::removeDeadBindingsFromEnvironmentAndStore(
95
    ProgramStateRef state, const StackFrameContext *LCtx,
96
470k
    SymbolReaper &SymReaper) {
97
470k
98
470k
  // This code essentially performs a "mark-and-sweep" of the VariableBindings.
99
470k
  // The roots are any Block-level exprs and Decls that our liveness algorithm
100
470k
  // tells us are live.  We then see what Decls they may reference, and keep
101
470k
  // those around.  This code more than likely can be made faster, and the
102
470k
  // frequency of which this method is called should be experimented with
103
470k
  // for optimum performance.
104
470k
  ProgramState NewState = *state;
105
470k
106
470k
  NewState.Env = EnvMgr.removeDeadBindings(NewState.Env, SymReaper, state);
107
470k
108
470k
  // Clean up the store.
109
470k
  StoreRef newStore = StoreMgr->removeDeadBindings(NewState.getStore(), LCtx,
110
470k
                                                   SymReaper);
111
470k
  NewState.setStore(newStore);
112
470k
  SymReaper.setReapedStore(newStore);
113
470k
114
470k
  return getPersistentState(NewState);
115
470k
}
116
117
ProgramStateRef ProgramState::bindLoc(Loc LV,
118
                                      SVal V,
119
                                      const LocationContext *LCtx,
120
166k
                                      bool notifyChanges) const {
121
166k
  ProgramStateManager &Mgr = getStateManager();
122
166k
  ProgramStateRef newState = makeWithStore(Mgr.StoreMgr->Bind(getStore(),
123
166k
                                                             LV, V));
124
166k
  const MemRegion *MR = LV.getAsRegion();
125
166k
  if (MR && 
notifyChanges166k
)
126
111k
    return Mgr.getOwningEngine().processRegionChange(newState, MR, LCtx);
127
55.1k
128
55.1k
  return newState;
129
55.1k
}
130
131
ProgramStateRef
132
ProgramState::bindDefaultInitial(SVal loc, SVal V,
133
790
                                 const LocationContext *LCtx) const {
134
790
  ProgramStateManager &Mgr = getStateManager();
135
790
  const MemRegion *R = loc.castAs<loc::MemRegionVal>().getRegion();
136
790
  const StoreRef &newStore = Mgr.StoreMgr->BindDefaultInitial(getStore(), R, V);
137
790
  ProgramStateRef new_state = makeWithStore(newStore);
138
790
  return Mgr.getOwningEngine().processRegionChange(new_state, R, LCtx);
139
790
}
140
141
ProgramStateRef
142
1.90k
ProgramState::bindDefaultZero(SVal loc, const LocationContext *LCtx) const {
143
1.90k
  ProgramStateManager &Mgr = getStateManager();
144
1.90k
  const MemRegion *R = loc.castAs<loc::MemRegionVal>().getRegion();
145
1.90k
  const StoreRef &newStore = Mgr.StoreMgr->BindDefaultZero(getStore(), R);
146
1.90k
  ProgramStateRef new_state = makeWithStore(newStore);
147
1.90k
  return Mgr.getOwningEngine().processRegionChange(new_state, R, LCtx);
148
1.90k
}
149
150
typedef ArrayRef<const MemRegion *> RegionList;
151
typedef ArrayRef<SVal> ValueList;
152
153
ProgramStateRef
154
ProgramState::invalidateRegions(RegionList Regions,
155
                             const Expr *E, unsigned Count,
156
                             const LocationContext *LCtx,
157
                             bool CausedByPointerEscape,
158
                             InvalidatedSymbols *IS,
159
                             const CallEvent *Call,
160
2.60k
                             RegionAndSymbolInvalidationTraits *ITraits) const {
161
2.60k
  SmallVector<SVal, 8> Values;
162
2.60k
  for (RegionList::const_iterator I = Regions.begin(),
163
5.31k
                                  End = Regions.end(); I != End; 
++I2.70k
)
164
2.70k
    Values.push_back(loc::MemRegionVal(*I));
165
2.60k
166
2.60k
  return invalidateRegionsImpl(Values, E, Count, LCtx, CausedByPointerEscape,
167
2.60k
                               IS, ITraits, Call);
168
2.60k
}
169
170
ProgramStateRef
171
ProgramState::invalidateRegions(ValueList Values,
172
                             const Expr *E, unsigned Count,
173
                             const LocationContext *LCtx,
174
                             bool CausedByPointerEscape,
175
                             InvalidatedSymbols *IS,
176
                             const CallEvent *Call,
177
33.6k
                             RegionAndSymbolInvalidationTraits *ITraits) const {
178
33.6k
179
33.6k
  return invalidateRegionsImpl(Values, E, Count, LCtx, CausedByPointerEscape,
180
33.6k
                               IS, ITraits, Call);
181
33.6k
}
182
183
ProgramStateRef
184
ProgramState::invalidateRegionsImpl(ValueList Values,
185
                                    const Expr *E, unsigned Count,
186
                                    const LocationContext *LCtx,
187
                                    bool CausedByPointerEscape,
188
                                    InvalidatedSymbols *IS,
189
                                    RegionAndSymbolInvalidationTraits *ITraits,
190
36.2k
                                    const CallEvent *Call) const {
191
36.2k
  ProgramStateManager &Mgr = getStateManager();
192
36.2k
  SubEngine &Eng = Mgr.getOwningEngine();
193
36.2k
194
36.2k
  InvalidatedSymbols InvalidatedSyms;
195
36.2k
  if (!IS)
196
36.2k
    IS = &InvalidatedSyms;
197
36.2k
198
36.2k
  RegionAndSymbolInvalidationTraits ITraitsLocal;
199
36.2k
  if (!ITraits)
200
54
    ITraits = &ITraitsLocal;
201
36.2k
202
36.2k
  StoreManager::InvalidatedRegions TopLevelInvalidated;
203
36.2k
  StoreManager::InvalidatedRegions Invalidated;
204
36.2k
  const StoreRef &newStore
205
36.2k
  = Mgr.StoreMgr->invalidateRegions(getStore(), Values, E, Count, LCtx, Call,
206
36.2k
                                    *IS, *ITraits, &TopLevelInvalidated,
207
36.2k
                                    &Invalidated);
208
36.2k
209
36.2k
  ProgramStateRef newState = makeWithStore(newStore);
210
36.2k
211
36.2k
  if (CausedByPointerEscape) {
212
34.0k
    newState = Eng.notifyCheckersOfPointerEscape(newState, IS,
213
34.0k
                                                 TopLevelInvalidated,
214
34.0k
                                                 Call,
215
34.0k
                                                 *ITraits);
216
34.0k
  }
217
36.2k
218
36.2k
  return Eng.processRegionChanges(newState, IS, TopLevelInvalidated,
219
36.2k
                                  Invalidated, LCtx, Call);
220
36.2k
}
221
222
6
ProgramStateRef ProgramState::killBinding(Loc LV) const {
223
6
  assert(!LV.getAs<loc::MemRegionVal>() && "Use invalidateRegion instead.");
224
6
225
6
  Store OldStore = getStore();
226
6
  const StoreRef &newStore =
227
6
    getStateManager().StoreMgr->killBinding(OldStore, LV);
228
6
229
6
  if (newStore.getStore() == OldStore)
230
6
    return this;
231
0
232
0
  return makeWithStore(newStore);
233
0
}
234
235
ProgramStateRef
236
ProgramState::enterStackFrame(const CallEvent &Call,
237
63.7k
                              const StackFrameContext *CalleeCtx) const {
238
63.7k
  const StoreRef &NewStore =
239
63.7k
    getStateManager().StoreMgr->enterStackFrame(getStore(), Call, CalleeCtx);
240
63.7k
  return makeWithStore(NewStore);
241
63.7k
}
242
243
0
SVal ProgramState::getSValAsScalarOrLoc(const MemRegion *R) const {
244
0
  // We only want to do fetches from regions that we can actually bind
245
0
  // values.  For example, SymbolicRegions of type 'id<...>' cannot
246
0
  // have direct bindings (but their can be bindings on their subregions).
247
0
  if (!R->isBoundable())
248
0
    return UnknownVal();
249
0
250
0
  if (const TypedValueRegion *TR = dyn_cast<TypedValueRegion>(R)) {
251
0
    QualType T = TR->getValueType();
252
0
    if (Loc::isLocType(T) || T->isIntegralOrEnumerationType())
253
0
      return getSVal(R);
254
0
  }
255
0
256
0
  return UnknownVal();
257
0
}
258
259
349k
SVal ProgramState::getSVal(Loc location, QualType T) const {
260
349k
  SVal V = getRawSVal(location, T);
261
349k
262
349k
  // If 'V' is a symbolic value that is *perfectly* constrained to
263
349k
  // be a constant value, use that value instead to lessen the burden
264
349k
  // on later analysis stages (so we have less symbolic values to reason
265
349k
  // about).
266
349k
  // We only go into this branch if we can convert the APSInt value we have
267
349k
  // to the type of T, which is not always the case (e.g. for void).
268
349k
  if (!T.isNull() && 
(187k
T->isIntegralOrEnumerationType()187k
||
Loc::isLocType(T)120k
)) {
269
174k
    if (SymbolRef sym = V.getAsSymbol()) {
270
77.5k
      if (const llvm::APSInt *Int = getStateManager()
271
1.42k
                                    .getConstraintManager()
272
1.42k
                                    .getSymVal(this, sym)) {
273
1.42k
        // FIXME: Because we don't correctly model (yet) sign-extension
274
1.42k
        // and truncation of symbolic values, we need to convert
275
1.42k
        // the integer value to the correct signedness and bitwidth.
276
1.42k
        //
277
1.42k
        // This shows up in the following:
278
1.42k
        //
279
1.42k
        //   char foo();
280
1.42k
        //   unsigned x = foo();
281
1.42k
        //   if (x == 54)
282
1.42k
        //     ...
283
1.42k
        //
284
1.42k
        //  The symbolic value stored to 'x' is actually the conjured
285
1.42k
        //  symbol for the call to foo(); the type of that symbol is 'char',
286
1.42k
        //  not unsigned.
287
1.42k
        const llvm::APSInt &NewV = getBasicVals().Convert(T, *Int);
288
1.42k
289
1.42k
        if (V.getAs<Loc>())
290
558
          return loc::ConcreteInt(NewV);
291
864
        else
292
864
          return nonloc::ConcreteInt(NewV);
293
347k
      }
294
77.5k
    }
295
174k
  }
296
347k
297
347k
  return V;
298
347k
}
299
300
ProgramStateRef ProgramState::BindExpr(const Stmt *S,
301
                                           const LocationContext *LCtx,
302
1.01M
                                           SVal V, bool Invalidate) const{
303
1.01M
  Environment NewEnv =
304
1.01M
    getStateManager().EnvMgr.bindExpr(Env, EnvironmentEntry(S, LCtx), V,
305
1.01M
                                      Invalidate);
306
1.01M
  if (NewEnv == Env)
307
49.3k
    return this;
308
966k
309
966k
  ProgramState NewSt = *this;
310
966k
  NewSt.Env = NewEnv;
311
966k
  return getStateManager().getPersistentState(NewSt);
312
966k
}
313
314
ProgramStateRef ProgramState::assumeInBound(DefinedOrUnknownSVal Idx,
315
                                      DefinedOrUnknownSVal UpperBound,
316
                                      bool Assumption,
317
2.47k
                                      QualType indexTy) const {
318
2.47k
  if (Idx.isUnknown() || UpperBound.isUnknown())
319
4
    return this;
320
2.46k
321
2.46k
  // Build an expression for 0 <= Idx < UpperBound.
322
2.46k
  // This is the same as Idx + MIN < UpperBound + MIN, if overflow is allowed.
323
2.46k
  // FIXME: This should probably be part of SValBuilder.
324
2.46k
  ProgramStateManager &SM = getStateManager();
325
2.46k
  SValBuilder &svalBuilder = SM.getSValBuilder();
326
2.46k
  ASTContext &Ctx = svalBuilder.getContext();
327
2.46k
328
2.46k
  // Get the offset: the minimum value of the array index type.
329
2.46k
  BasicValueFactory &BVF = svalBuilder.getBasicValueFactory();
330
2.46k
  if (indexTy.isNull())
331
2.44k
    indexTy = svalBuilder.getArrayIndexType();
332
2.46k
  nonloc::ConcreteInt Min(BVF.getMinValue(indexTy));
333
2.46k
334
2.46k
  // Adjust the index.
335
2.46k
  SVal newIdx = svalBuilder.evalBinOpNN(this, BO_Add,
336
2.46k
                                        Idx.castAs<NonLoc>(), Min, indexTy);
337
2.46k
  if (newIdx.isUnknownOrUndef())
338
0
    return this;
339
2.46k
340
2.46k
  // Adjust the upper bound.
341
2.46k
  SVal newBound =
342
2.46k
    svalBuilder.evalBinOpNN(this, BO_Add, UpperBound.castAs<NonLoc>(),
343
2.46k
                            Min, indexTy);
344
2.46k
345
2.46k
  if (newBound.isUnknownOrUndef())
346
0
    return this;
347
2.46k
348
2.46k
  // Build the actual comparison.
349
2.46k
  SVal inBound = svalBuilder.evalBinOpNN(this, BO_LT, newIdx.castAs<NonLoc>(),
350
2.46k
                                         newBound.castAs<NonLoc>(), Ctx.IntTy);
351
2.46k
  if (inBound.isUnknownOrUndef())
352
0
    return this;
353
2.46k
354
2.46k
  // Finally, let the constraint manager take care of it.
355
2.46k
  ConstraintManager &CM = SM.getConstraintManager();
356
2.46k
  return CM.assume(this, inBound.castAs<DefinedSVal>(), Assumption);
357
2.46k
}
358
359
21.0k
ConditionTruthVal ProgramState::isNonNull(SVal V) const {
360
21.0k
  ConditionTruthVal IsNull = isNull(V);
361
21.0k
  if (IsNull.isUnderconstrained())
362
6.38k
    return IsNull;
363
14.6k
  return ConditionTruthVal(!IsNull.getValue());
364
14.6k
}
365
366
0
ConditionTruthVal ProgramState::areEqual(SVal Lhs, SVal Rhs) const {
367
0
  return stateMgr->getSValBuilder().areEqual(this, Lhs, Rhs);
368
0
}
369
370
58.9k
ConditionTruthVal ProgramState::isNull(SVal V) const {
371
58.9k
  if (V.isZeroConstant())
372
1.28k
    return true;
373
57.7k
374
57.7k
  if (V.isConstant())
375
14.9k
    return false;
376
42.7k
377
42.7k
  SymbolRef Sym = V.getAsSymbol(/* IncludeBaseRegion */ true);
378
42.7k
  if (!Sym)
379
9.43k
    return ConditionTruthVal();
380
33.2k
381
33.2k
  return getStateManager().ConstraintMgr->isNull(this, Sym);
382
33.2k
}
383
384
12.6k
ProgramStateRef ProgramStateManager::getInitialState(const LocationContext *InitLoc) {
385
12.6k
  ProgramState State(this,
386
12.6k
                EnvMgr.getInitialEnvironment(),
387
12.6k
                StoreMgr->getInitialStore(InitLoc),
388
12.6k
                GDMFactory.getEmptyMap());
389
12.6k
390
12.6k
  return getPersistentState(State);
391
12.6k
}
392
393
ProgramStateRef ProgramStateManager::getPersistentStateWithGDM(
394
                                                     ProgramStateRef FromState,
395
470k
                                                     ProgramStateRef GDMState) {
396
470k
  ProgramState NewState(*FromState);
397
470k
  NewState.GDM = GDMState->GDM;
398
470k
  return getPersistentState(NewState);
399
470k
}
400
401
2.46M
ProgramStateRef ProgramStateManager::getPersistentState(ProgramState &State) {
402
2.46M
403
2.46M
  llvm::FoldingSetNodeID ID;
404
2.46M
  State.Profile(ID);
405
2.46M
  void *InsertPos;
406
2.46M
407
2.46M
  if (ProgramState *I = StateSet.FindNodeOrInsertPos(ID, InsertPos))
408
599k
    return I;
409
1.86M
410
1.86M
  ProgramState *newState = nullptr;
411
1.86M
  if (!freeStates.empty()) {
412
510k
    newState = freeStates.back();
413
510k
    freeStates.pop_back();
414
510k
  }
415
1.35M
  else {
416
1.35M
    newState = (ProgramState*) Alloc.Allocate<ProgramState>();
417
1.35M
  }
418
1.86M
  new (newState) ProgramState(State);
419
1.86M
  StateSet.InsertNode(newState, InsertPos);
420
1.86M
  return newState;
421
1.86M
}
422
423
269k
ProgramStateRef ProgramState::makeWithStore(const StoreRef &store) const {
424
269k
  ProgramState NewSt(*this);
425
269k
  NewSt.setStore(store);
426
269k
  return getStateManager().getPersistentState(NewSt);
427
269k
}
428
429
739k
void ProgramState::setStore(const StoreRef &newStore) {
430
739k
  Store newStoreStore = newStore.getStore();
431
739k
  if (newStoreStore)
432
696k
    stateMgr->getStoreManager().incrementReferenceCount(newStoreStore);
433
739k
  if (store)
434
685k
    stateMgr->getStoreManager().decrementReferenceCount(store);
435
739k
  store = newStoreStore;
436
739k
}
437
438
//===----------------------------------------------------------------------===//
439
//  State pretty-printing.
440
//===----------------------------------------------------------------------===//
441
442
void ProgramState::printJson(raw_ostream &Out, const LocationContext *LCtx,
443
                             const char *NL, unsigned int Space,
444
107
                             bool IsDot) const {
445
107
  Indent(Out, Space, IsDot) << "\"program_state\": {" << NL;
446
107
  ++Space;
447
107
448
107
  ProgramStateManager &Mgr = getStateManager();
449
107
450
107
  // Print the store.
451
107
  Mgr.getStoreManager().printJson(Out, getStore(), NL, Space, IsDot);
452
107
453
107
  // Print out the environment.
454
107
  Env.printJson(Out, Mgr.getContext(), LCtx, NL, Space, IsDot);
455
107
456
107
  // Print out the constraints.
457
107
  Mgr.getConstraintManager().printJson(Out, this, NL, Space, IsDot);
458
107
459
107
  // Print out the tracked dynamic types.
460
107
  printDynamicTypeInfoJson(Out, this, NL, Space, IsDot);
461
107
462
107
  // Print checker-specific data.
463
107
  Mgr.getOwningEngine().printJson(Out, this, LCtx, NL, Space, IsDot);
464
107
465
107
  --Space;
466
107
  Indent(Out, Space, IsDot) << '}';
467
107
}
468
469
void ProgramState::printDOT(raw_ostream &Out, const LocationContext *LCtx,
470
88
                            unsigned int Space) const {
471
88
  printJson(Out, LCtx, /*NL=*/"\\l", Space, /*IsDot=*/true);
472
88
}
473
474
19
LLVM_DUMP_METHOD void ProgramState::dump() const {
475
19
  printJson(llvm::errs());
476
19
}
477
478
7.51k
AnalysisManager& ProgramState::getAnalysisManager() const {
479
7.51k
  return stateMgr->getOwningEngine().getAnalysisManager();
480
7.51k
}
481
482
//===----------------------------------------------------------------------===//
483
// Generic Data Map.
484
//===----------------------------------------------------------------------===//
485
486
6.52M
void *const* ProgramState::FindGDM(void *K) const {
487
6.52M
  return GDM.lookup(K);
488
6.52M
}
489
490
void*
491
ProgramStateManager::FindGDMContext(void *K,
492
                               void *(*CreateContext)(llvm::BumpPtrAllocator&),
493
1.83M
                               void (*DeleteContext)(void*)) {
494
1.83M
495
1.83M
  std::pair<void*, void (*)(void*)>& p = GDMContexts[K];
496
1.83M
  if (!p.first) {
497
31.9k
    p.first = CreateContext(Alloc);
498
31.9k
    p.second = DeleteContext;
499
31.9k
  }
500
1.83M
501
1.83M
  return p.first;
502
1.83M
}
503
504
1.19M
ProgramStateRef ProgramStateManager::addGDM(ProgramStateRef St, void *Key, void *Data){
505
1.19M
  ProgramState::GenericDataMap M1 = St->getGDM();
506
1.19M
  ProgramState::GenericDataMap M2 = GDMFactory.add(M1, Key, Data);
507
1.19M
508
1.19M
  if (M1 == M2)
509
919k
    return St;
510
279k
511
279k
  ProgramState NewSt = *St;
512
279k
  NewSt.GDM = M2;
513
279k
  return getPersistentState(NewSt);
514
279k
}
515
516
218
ProgramStateRef ProgramStateManager::removeGDM(ProgramStateRef state, void *Key) {
517
218
  ProgramState::GenericDataMap OldM = state->getGDM();
518
218
  ProgramState::GenericDataMap NewM = GDMFactory.remove(OldM, Key);
519
218
520
218
  if (NewM == OldM)
521
0
    return state;
522
218
523
218
  ProgramState NewState = *state;
524
218
  NewState.GDM = NewM;
525
218
  return getPersistentState(NewState);
526
218
}
527
528
111k
bool ScanReachableSymbols::scan(nonloc::LazyCompoundVal val) {
529
111k
  bool wasVisited = !visited.insert(val.getCVData()).second;
530
111k
  if (wasVisited)
531
12
    return true;
532
111k
533
111k
  StoreManager &StoreMgr = state->getStateManager().getStoreManager();
534
111k
  // FIXME: We don't really want to use getBaseRegion() here because pointer
535
111k
  // arithmetic doesn't apply, but scanReachableSymbols only accepts base
536
111k
  // regions right now.
537
111k
  const MemRegion *R = val.getRegion()->getBaseRegion();
538
111k
  return StoreMgr.scanReachableSymbols(val.getStore(), R, *this);
539
111k
}
540
541
1.22k
bool ScanReachableSymbols::scan(nonloc::CompoundVal val) {
542
3.24k
  for (nonloc::CompoundVal::iterator I=val.begin(), E=val.end(); I!=E; 
++I2.02k
)
543
2.02k
    if (!scan(*I))
544
0
      return false;
545
1.22k
546
1.22k
  return true;
547
1.22k
}
548
549
349k
bool ScanReachableSymbols::scan(const SymExpr *sym) {
550
349k
  for (SymExpr::symbol_iterator SI = sym->symbol_begin(),
551
349k
                                SE = sym->symbol_end();
552
832k
       SI != SE; 
++SI482k
) {
553
482k
    bool wasVisited = !visited.insert(*SI).second;
554
482k
    if (wasVisited)
555
29.4k
      continue;
556
453k
557
453k
    if (!visitor.VisitSymbol(*SI))
558
0
      return false;
559
453k
  }
560
349k
561
349k
  return true;
562
349k
}
563
564
2.57M
bool ScanReachableSymbols::scan(SVal val) {
565
2.57M
  if (Optional<loc::MemRegionVal> X = val.getAs<loc::MemRegionVal>())
566
1.73M
    return scan(X->getRegion());
567
833k
568
833k
  if (Optional<nonloc::LazyCompoundVal> X =
569
111k
          val.getAs<nonloc::LazyCompoundVal>())
570
111k
    return scan(*X);
571
722k
572
722k
  if (Optional<nonloc::LocAsInteger> X = val.getAs<nonloc::LocAsInteger>())
573
341
    return scan(X->getLoc());
574
722k
575
722k
  if (SymbolRef Sym = val.getAsSymbol())
576
349k
    return scan(Sym);
577
372k
578
372k
  if (const SymExpr *Sym = val.getAsSymbolicExpression())
579
0
    return scan(Sym);
580
372k
581
372k
  if (Optional<nonloc::CompoundVal> X = val.getAs<nonloc::CompoundVal>())
582
1.22k
    return scan(*X);
583
371k
584
371k
  return true;
585
371k
}
586
587
3.17M
bool ScanReachableSymbols::scan(const MemRegion *R) {
588
3.17M
  if (isa<MemSpaceRegion>(R))
589
1.19M
    return true;
590
1.97M
591
1.97M
  bool wasVisited = !visited.insert(R).second;
592
1.97M
  if (wasVisited)
593
542k
    return true;
594
1.43M
595
1.43M
  if (!visitor.VisitMemRegion(R))
596
0
    return false;
597
1.43M
598
1.43M
  // If this is a symbolic region, visit the symbol for the region.
599
1.43M
  if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R))
600
126k
    if (!visitor.VisitSymbol(SR->getSymbol()))
601
0
      return false;
602
1.43M
603
1.43M
  // If this is a subregion, also visit the parent regions.
604
1.43M
  if (const SubRegion *SR = dyn_cast<SubRegion>(R)) {
605
1.43M
    const MemRegion *Super = SR->getSuperRegion();
606
1.43M
    if (!scan(Super))
607
0
      return false;
608
1.43M
609
1.43M
    // When we reach the topmost region, scan all symbols in it.
610
1.43M
    if (isa<MemSpaceRegion>(Super)) {
611
1.19M
      StoreManager &StoreMgr = state->getStateManager().getStoreManager();
612
1.19M
      if (!StoreMgr.scanReachableSymbols(state->getStore(), SR, *this))
613
0
        return false;
614
1.43M
    }
615
1.43M
  }
616
1.43M
617
1.43M
  // Regions captured by a block are also implicitly reachable.
618
1.43M
  if (const BlockDataRegion *BDR = dyn_cast<BlockDataRegion>(R)) {
619
1.38k
    BlockDataRegion::referenced_vars_iterator I = BDR->referenced_vars_begin(),
620
1.38k
                                              E = BDR->referenced_vars_end();
621
2.79k
    for ( ; I != E; 
++I1.41k
) {
622
1.41k
      if (!scan(I.getCapturedRegion()))
623
0
        return false;
624
1.41k
    }
625
1.38k
  }
626
1.43M
627
1.43M
  return true;
628
1.43M
}
629
630
7.74k
bool ProgramState::scanReachableSymbols(SVal val, SymbolVisitor& visitor) const {
631
7.74k
  ScanReachableSymbols S(this, visitor);
632
7.74k
  return S.scan(val);
633
7.74k
}
634
635
bool ProgramState::scanReachableSymbols(
636
    llvm::iterator_range<region_iterator> Reachable,
637
29
    SymbolVisitor &visitor) const {
638
29
  ScanReachableSymbols S(this, visitor);
639
33
  for (const MemRegion *R : Reachable) {
640
33
    if (!S.scan(R))
641
0
      return false;
642
33
  }
643
29
  return true;
644
29
}