Coverage Report

Created: 2019-07-24 05:18

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