Coverage Report

Created: 2020-09-19 12:23

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