1226586Sdim//= ProgramState.cpp - Path-Sensitive "State" for tracking values --*- C++ -*--= 2226586Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6226586Sdim// 7226586Sdim//===----------------------------------------------------------------------===// 8226586Sdim// 9226586Sdim// This file implements ProgramState and ProgramStateManager. 10226586Sdim// 11226586Sdim//===----------------------------------------------------------------------===// 12226586Sdim 13249423Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" 14226586Sdim#include "clang/Analysis/CFG.h" 15353358Sdim#include "clang/Basic/JsonSupport.h" 16353358Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h" 17239462Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" 18360784Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/DynamicType.h" 19226586Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h" 20226586Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/SubEngine.h" 21226586Sdim#include "llvm/Support/raw_ostream.h" 22226586Sdim 23226586Sdimusing namespace clang; 24226586Sdimusing namespace ento; 25226586Sdim 26234353Sdimnamespace clang { namespace ento { 27234353Sdim/// Increments the number of times this state is referenced. 28234353Sdim 29234353Sdimvoid ProgramStateRetain(const ProgramState *state) { 30234353Sdim ++const_cast<ProgramState*>(state)->refCount; 31234353Sdim} 32234353Sdim 33234353Sdim/// Decrement the number of times this state is referenced. 34234353Sdimvoid ProgramStateRelease(const ProgramState *state) { 35234353Sdim assert(state->refCount > 0); 36234353Sdim ProgramState *s = const_cast<ProgramState*>(state); 37234353Sdim if (--s->refCount == 0) { 38234353Sdim ProgramStateManager &Mgr = s->getStateManager(); 39234353Sdim Mgr.StateSet.RemoveNode(s); 40296417Sdim s->~ProgramState(); 41234353Sdim Mgr.freeStates.push_back(s); 42234353Sdim } 43234353Sdim} 44234353Sdim}} 45234353Sdim 46226586SdimProgramState::ProgramState(ProgramStateManager *mgr, const Environment& env, 47226586Sdim StoreRef st, GenericDataMap gdm) 48226586Sdim : stateMgr(mgr), 49226586Sdim Env(env), 50226586Sdim store(st.getStore()), 51226586Sdim GDM(gdm), 52226586Sdim refCount(0) { 53226586Sdim stateMgr->getStoreManager().incrementReferenceCount(store); 54226586Sdim} 55226586Sdim 56226586SdimProgramState::ProgramState(const ProgramState &RHS) 57226586Sdim : llvm::FoldingSetNode(), 58226586Sdim stateMgr(RHS.stateMgr), 59226586Sdim Env(RHS.Env), 60226586Sdim store(RHS.store), 61226586Sdim GDM(RHS.GDM), 62226586Sdim refCount(0) { 63226586Sdim stateMgr->getStoreManager().incrementReferenceCount(store); 64226586Sdim} 65226586Sdim 66226586SdimProgramState::~ProgramState() { 67226586Sdim if (store) 68226586Sdim stateMgr->getStoreManager().decrementReferenceCount(store); 69226586Sdim} 70226586Sdim 71344779Sdimint64_t ProgramState::getID() const { 72344779Sdim return getStateManager().Alloc.identifyKnownAlignedObject<ProgramState>(this); 73344779Sdim} 74344779Sdim 75239462SdimProgramStateManager::ProgramStateManager(ASTContext &Ctx, 76239462Sdim StoreManagerCreator CreateSMgr, 77239462Sdim ConstraintManagerCreator CreateCMgr, 78239462Sdim llvm::BumpPtrAllocator &alloc, 79243830Sdim SubEngine *SubEng) 80243830Sdim : Eng(SubEng), EnvMgr(alloc), GDMFactory(alloc), 81239462Sdim svalBuilder(createSimpleSValBuilder(alloc, Ctx, *this)), 82239462Sdim CallEventMgr(new CallEventManager(alloc)), Alloc(alloc) { 83280031Sdim StoreMgr = (*CreateSMgr)(*this); 84280031Sdim ConstraintMgr = (*CreateCMgr)(*this, SubEng); 85239462Sdim} 86239462Sdim 87239462Sdim 88226586SdimProgramStateManager::~ProgramStateManager() { 89226586Sdim for (GDMContextsTy::iterator I=GDMContexts.begin(), E=GDMContexts.end(); 90226586Sdim I!=E; ++I) 91226586Sdim I->second.second(I->second.first); 92226586Sdim} 93226586Sdim 94360784SdimProgramStateRef ProgramStateManager::removeDeadBindingsFromEnvironmentAndStore( 95360784Sdim ProgramStateRef state, const StackFrameContext *LCtx, 96360784Sdim SymbolReaper &SymReaper) { 97226586Sdim 98226586Sdim // This code essentially performs a "mark-and-sweep" of the VariableBindings. 99226586Sdim // The roots are any Block-level exprs and Decls that our liveness algorithm 100226586Sdim // tells us are live. We then see what Decls they may reference, and keep 101226586Sdim // those around. This code more than likely can be made faster, and the 102226586Sdim // frequency of which this method is called should be experimented with 103226586Sdim // for optimum performance. 104226586Sdim ProgramState NewState = *state; 105226586Sdim 106226586Sdim NewState.Env = EnvMgr.removeDeadBindings(NewState.Env, SymReaper, state); 107226586Sdim 108226586Sdim // Clean up the store. 109226586Sdim StoreRef newStore = StoreMgr->removeDeadBindings(NewState.getStore(), LCtx, 110226586Sdim SymReaper); 111226586Sdim NewState.setStore(newStore); 112226586Sdim SymReaper.setReapedStore(newStore); 113226586Sdim 114360784Sdim return getPersistentState(NewState); 115226586Sdim} 116226586Sdim 117321369SdimProgramStateRef ProgramState::bindLoc(Loc LV, 118321369Sdim SVal V, 119321369Sdim const LocationContext *LCtx, 120321369Sdim bool notifyChanges) const { 121226586Sdim ProgramStateManager &Mgr = getStateManager(); 122296417Sdim ProgramStateRef newState = makeWithStore(Mgr.StoreMgr->Bind(getStore(), 123226586Sdim LV, V)); 124226586Sdim const MemRegion *MR = LV.getAsRegion(); 125344779Sdim if (MR && notifyChanges) 126344779Sdim return Mgr.getOwningEngine().processRegionChange(newState, MR, LCtx); 127226586Sdim 128226586Sdim return newState; 129226586Sdim} 130226586Sdim 131341825SdimProgramStateRef 132341825SdimProgramState::bindDefaultInitial(SVal loc, SVal V, 133341825Sdim const LocationContext *LCtx) const { 134226586Sdim ProgramStateManager &Mgr = getStateManager(); 135249423Sdim const MemRegion *R = loc.castAs<loc::MemRegionVal>().getRegion(); 136341825Sdim const StoreRef &newStore = Mgr.StoreMgr->BindDefaultInitial(getStore(), R, V); 137234353Sdim ProgramStateRef new_state = makeWithStore(newStore); 138344779Sdim return Mgr.getOwningEngine().processRegionChange(new_state, R, LCtx); 139226586Sdim} 140226586Sdim 141341825SdimProgramStateRef 142341825SdimProgramState::bindDefaultZero(SVal loc, const LocationContext *LCtx) const { 143341825Sdim ProgramStateManager &Mgr = getStateManager(); 144341825Sdim const MemRegion *R = loc.castAs<loc::MemRegionVal>().getRegion(); 145341825Sdim const StoreRef &newStore = Mgr.StoreMgr->BindDefaultZero(getStore(), R); 146341825Sdim ProgramStateRef new_state = makeWithStore(newStore); 147344779Sdim return Mgr.getOwningEngine().processRegionChange(new_state, R, LCtx); 148341825Sdim} 149341825Sdim 150249423Sdimtypedef ArrayRef<const MemRegion *> RegionList; 151249423Sdimtypedef ArrayRef<SVal> ValueList; 152249423Sdim 153296417SdimProgramStateRef 154249423SdimProgramState::invalidateRegions(RegionList Regions, 155261991Sdim const Expr *E, unsigned Count, 156261991Sdim const LocationContext *LCtx, 157261991Sdim bool CausedByPointerEscape, 158261991Sdim InvalidatedSymbols *IS, 159261991Sdim const CallEvent *Call, 160261991Sdim RegionAndSymbolInvalidationTraits *ITraits) const { 161249423Sdim SmallVector<SVal, 8> Values; 162249423Sdim for (RegionList::const_iterator I = Regions.begin(), 163249423Sdim End = Regions.end(); I != End; ++I) 164249423Sdim Values.push_back(loc::MemRegionVal(*I)); 165249423Sdim 166249423Sdim return invalidateRegionsImpl(Values, E, Count, LCtx, CausedByPointerEscape, 167261991Sdim IS, ITraits, Call); 168226586Sdim} 169226586Sdim 170249423SdimProgramStateRef 171249423SdimProgramState::invalidateRegions(ValueList Values, 172261991Sdim const Expr *E, unsigned Count, 173261991Sdim const LocationContext *LCtx, 174261991Sdim bool CausedByPointerEscape, 175261991Sdim InvalidatedSymbols *IS, 176261991Sdim const CallEvent *Call, 177261991Sdim RegionAndSymbolInvalidationTraits *ITraits) const { 178261991Sdim 179249423Sdim return invalidateRegionsImpl(Values, E, Count, LCtx, CausedByPointerEscape, 180261991Sdim IS, ITraits, Call); 181249423Sdim} 182249423Sdim 183249423SdimProgramStateRef 184249423SdimProgramState::invalidateRegionsImpl(ValueList Values, 185226586Sdim const Expr *E, unsigned Count, 186234353Sdim const LocationContext *LCtx, 187249423Sdim bool CausedByPointerEscape, 188261991Sdim InvalidatedSymbols *IS, 189261991Sdim RegionAndSymbolInvalidationTraits *ITraits, 190261991Sdim const CallEvent *Call) const { 191226586Sdim ProgramStateManager &Mgr = getStateManager(); 192344779Sdim SubEngine &Eng = Mgr.getOwningEngine(); 193249423Sdim 194344779Sdim InvalidatedSymbols InvalidatedSyms; 195261991Sdim if (!IS) 196344779Sdim IS = &InvalidatedSyms; 197261991Sdim 198261991Sdim RegionAndSymbolInvalidationTraits ITraitsLocal; 199261991Sdim if (!ITraits) 200261991Sdim ITraits = &ITraitsLocal; 201261991Sdim 202344779Sdim StoreManager::InvalidatedRegions TopLevelInvalidated; 203344779Sdim StoreManager::InvalidatedRegions Invalidated; 204344779Sdim const StoreRef &newStore 205344779Sdim = Mgr.StoreMgr->invalidateRegions(getStore(), Values, E, Count, LCtx, Call, 206344779Sdim *IS, *ITraits, &TopLevelInvalidated, 207344779Sdim &Invalidated); 208249423Sdim 209344779Sdim ProgramStateRef newState = makeWithStore(newStore); 210249423Sdim 211344779Sdim if (CausedByPointerEscape) { 212344779Sdim newState = Eng.notifyCheckersOfPointerEscape(newState, IS, 213344779Sdim TopLevelInvalidated, 214344779Sdim Call, 215344779Sdim *ITraits); 216226586Sdim } 217226586Sdim 218344779Sdim return Eng.processRegionChanges(newState, IS, TopLevelInvalidated, 219344779Sdim Invalidated, LCtx, Call); 220226586Sdim} 221226586Sdim 222243830SdimProgramStateRef ProgramState::killBinding(Loc LV) const { 223249423Sdim assert(!LV.getAs<loc::MemRegionVal>() && "Use invalidateRegion instead."); 224226586Sdim 225226586Sdim Store OldStore = getStore(); 226243830Sdim const StoreRef &newStore = 227243830Sdim getStateManager().StoreMgr->killBinding(OldStore, LV); 228226586Sdim 229226586Sdim if (newStore.getStore() == OldStore) 230226586Sdim return this; 231226586Sdim 232226586Sdim return makeWithStore(newStore); 233226586Sdim} 234226586Sdim 235296417SdimProgramStateRef 236239462SdimProgramState::enterStackFrame(const CallEvent &Call, 237239462Sdim const StackFrameContext *CalleeCtx) const { 238239462Sdim const StoreRef &NewStore = 239239462Sdim getStateManager().StoreMgr->enterStackFrame(getStore(), Call, CalleeCtx); 240239462Sdim return makeWithStore(NewStore); 241226586Sdim} 242226586Sdim 243226586SdimSVal ProgramState::getSValAsScalarOrLoc(const MemRegion *R) const { 244226586Sdim // We only want to do fetches from regions that we can actually bind 245226586Sdim // values. For example, SymbolicRegions of type 'id<...>' cannot 246226586Sdim // have direct bindings (but their can be bindings on their subregions). 247226586Sdim if (!R->isBoundable()) 248226586Sdim return UnknownVal(); 249226586Sdim 250226586Sdim if (const TypedValueRegion *TR = dyn_cast<TypedValueRegion>(R)) { 251226586Sdim QualType T = TR->getValueType(); 252251662Sdim if (Loc::isLocType(T) || T->isIntegralOrEnumerationType()) 253226586Sdim return getSVal(R); 254226586Sdim } 255226586Sdim 256226586Sdim return UnknownVal(); 257226586Sdim} 258226586Sdim 259226586SdimSVal ProgramState::getSVal(Loc location, QualType T) const { 260341825Sdim SVal V = getRawSVal(location, T); 261226586Sdim 262226586Sdim // If 'V' is a symbolic value that is *perfectly* constrained to 263226586Sdim // be a constant value, use that value instead to lessen the burden 264226586Sdim // on later analysis stages (so we have less symbolic values to reason 265226586Sdim // about). 266327952Sdim // We only go into this branch if we can convert the APSInt value we have 267327952Sdim // to the type of T, which is not always the case (e.g. for void). 268327952Sdim if (!T.isNull() && (T->isIntegralOrEnumerationType() || Loc::isLocType(T))) { 269226586Sdim if (SymbolRef sym = V.getAsSymbol()) { 270243830Sdim if (const llvm::APSInt *Int = getStateManager() 271243830Sdim .getConstraintManager() 272243830Sdim .getSymVal(this, sym)) { 273226586Sdim // FIXME: Because we don't correctly model (yet) sign-extension 274226586Sdim // and truncation of symbolic values, we need to convert 275226586Sdim // the integer value to the correct signedness and bitwidth. 276226586Sdim // 277226586Sdim // This shows up in the following: 278226586Sdim // 279226586Sdim // char foo(); 280226586Sdim // unsigned x = foo(); 281226586Sdim // if (x == 54) 282226586Sdim // ... 283226586Sdim // 284226586Sdim // The symbolic value stored to 'x' is actually the conjured 285226586Sdim // symbol for the call to foo(); the type of that symbol is 'char', 286226586Sdim // not unsigned. 287226586Sdim const llvm::APSInt &NewV = getBasicVals().Convert(T, *Int); 288296417Sdim 289249423Sdim if (V.getAs<Loc>()) 290226586Sdim return loc::ConcreteInt(NewV); 291226586Sdim else 292226586Sdim return nonloc::ConcreteInt(NewV); 293226586Sdim } 294226586Sdim } 295226586Sdim } 296296417Sdim 297226586Sdim return V; 298226586Sdim} 299226586Sdim 300234353SdimProgramStateRef ProgramState::BindExpr(const Stmt *S, 301234353Sdim const LocationContext *LCtx, 302234353Sdim SVal V, bool Invalidate) const{ 303234353Sdim Environment NewEnv = 304234353Sdim getStateManager().EnvMgr.bindExpr(Env, EnvironmentEntry(S, LCtx), V, 305234353Sdim Invalidate); 306226586Sdim if (NewEnv == Env) 307226586Sdim return this; 308226586Sdim 309226586Sdim ProgramState NewSt = *this; 310226586Sdim NewSt.Env = NewEnv; 311226586Sdim return getStateManager().getPersistentState(NewSt); 312226586Sdim} 313226586Sdim 314234353SdimProgramStateRef ProgramState::assumeInBound(DefinedOrUnknownSVal Idx, 315226586Sdim DefinedOrUnknownSVal UpperBound, 316234353Sdim bool Assumption, 317234353Sdim QualType indexTy) const { 318226586Sdim if (Idx.isUnknown() || UpperBound.isUnknown()) 319226586Sdim return this; 320226586Sdim 321226586Sdim // Build an expression for 0 <= Idx < UpperBound. 322226586Sdim // This is the same as Idx + MIN < UpperBound + MIN, if overflow is allowed. 323226586Sdim // FIXME: This should probably be part of SValBuilder. 324226586Sdim ProgramStateManager &SM = getStateManager(); 325226586Sdim SValBuilder &svalBuilder = SM.getSValBuilder(); 326226586Sdim ASTContext &Ctx = svalBuilder.getContext(); 327226586Sdim 328226586Sdim // Get the offset: the minimum value of the array index type. 329226586Sdim BasicValueFactory &BVF = svalBuilder.getBasicValueFactory(); 330234353Sdim if (indexTy.isNull()) 331341825Sdim indexTy = svalBuilder.getArrayIndexType(); 332226586Sdim nonloc::ConcreteInt Min(BVF.getMinValue(indexTy)); 333226586Sdim 334226586Sdim // Adjust the index. 335226586Sdim SVal newIdx = svalBuilder.evalBinOpNN(this, BO_Add, 336249423Sdim Idx.castAs<NonLoc>(), Min, indexTy); 337226586Sdim if (newIdx.isUnknownOrUndef()) 338226586Sdim return this; 339226586Sdim 340226586Sdim // Adjust the upper bound. 341226586Sdim SVal newBound = 342249423Sdim svalBuilder.evalBinOpNN(this, BO_Add, UpperBound.castAs<NonLoc>(), 343226586Sdim Min, indexTy); 344226586Sdim 345226586Sdim if (newBound.isUnknownOrUndef()) 346226586Sdim return this; 347226586Sdim 348226586Sdim // Build the actual comparison. 349249423Sdim SVal inBound = svalBuilder.evalBinOpNN(this, BO_LT, newIdx.castAs<NonLoc>(), 350249423Sdim newBound.castAs<NonLoc>(), Ctx.IntTy); 351226586Sdim if (inBound.isUnknownOrUndef()) 352226586Sdim return this; 353226586Sdim 354226586Sdim // Finally, let the constraint manager take care of it. 355226586Sdim ConstraintManager &CM = SM.getConstraintManager(); 356249423Sdim return CM.assume(this, inBound.castAs<DefinedSVal>(), Assumption); 357226586Sdim} 358226586Sdim 359341825SdimConditionTruthVal ProgramState::isNonNull(SVal V) const { 360341825Sdim ConditionTruthVal IsNull = isNull(V); 361341825Sdim if (IsNull.isUnderconstrained()) 362341825Sdim return IsNull; 363341825Sdim return ConditionTruthVal(!IsNull.getValue()); 364341825Sdim} 365341825Sdim 366341825SdimConditionTruthVal ProgramState::areEqual(SVal Lhs, SVal Rhs) const { 367341825Sdim return stateMgr->getSValBuilder().areEqual(this, Lhs, Rhs); 368341825Sdim} 369341825Sdim 370249423SdimConditionTruthVal ProgramState::isNull(SVal V) const { 371249423Sdim if (V.isZeroConstant()) 372249423Sdim return true; 373249423Sdim 374249423Sdim if (V.isConstant()) 375249423Sdim return false; 376296417Sdim 377251662Sdim SymbolRef Sym = V.getAsSymbol(/* IncludeBaseRegion */ true); 378249423Sdim if (!Sym) 379249423Sdim return ConditionTruthVal(); 380296417Sdim 381249423Sdim return getStateManager().ConstraintMgr->isNull(this, Sym); 382249423Sdim} 383249423Sdim 384234353SdimProgramStateRef ProgramStateManager::getInitialState(const LocationContext *InitLoc) { 385226586Sdim ProgramState State(this, 386226586Sdim EnvMgr.getInitialEnvironment(), 387226586Sdim StoreMgr->getInitialStore(InitLoc), 388226586Sdim GDMFactory.getEmptyMap()); 389226586Sdim 390226586Sdim return getPersistentState(State); 391226586Sdim} 392226586Sdim 393234353SdimProgramStateRef ProgramStateManager::getPersistentStateWithGDM( 394234353Sdim ProgramStateRef FromState, 395234353Sdim ProgramStateRef GDMState) { 396234353Sdim ProgramState NewState(*FromState); 397226586Sdim NewState.GDM = GDMState->GDM; 398226586Sdim return getPersistentState(NewState); 399226586Sdim} 400226586Sdim 401234353SdimProgramStateRef ProgramStateManager::getPersistentState(ProgramState &State) { 402226586Sdim 403226586Sdim llvm::FoldingSetNodeID ID; 404226586Sdim State.Profile(ID); 405226586Sdim void *InsertPos; 406226586Sdim 407226586Sdim if (ProgramState *I = StateSet.FindNodeOrInsertPos(ID, InsertPos)) 408226586Sdim return I; 409226586Sdim 410276479Sdim ProgramState *newState = nullptr; 411226586Sdim if (!freeStates.empty()) { 412226586Sdim newState = freeStates.back(); 413296417Sdim freeStates.pop_back(); 414226586Sdim } 415226586Sdim else { 416226586Sdim newState = (ProgramState*) Alloc.Allocate<ProgramState>(); 417226586Sdim } 418226586Sdim new (newState) ProgramState(State); 419226586Sdim StateSet.InsertNode(newState, InsertPos); 420226586Sdim return newState; 421226586Sdim} 422226586Sdim 423234353SdimProgramStateRef ProgramState::makeWithStore(const StoreRef &store) const { 424234353Sdim ProgramState NewSt(*this); 425226586Sdim NewSt.setStore(store); 426226586Sdim return getStateManager().getPersistentState(NewSt); 427226586Sdim} 428226586Sdim 429226586Sdimvoid ProgramState::setStore(const StoreRef &newStore) { 430226586Sdim Store newStoreStore = newStore.getStore(); 431226586Sdim if (newStoreStore) 432226586Sdim stateMgr->getStoreManager().incrementReferenceCount(newStoreStore); 433226586Sdim if (store) 434226586Sdim stateMgr->getStoreManager().decrementReferenceCount(store); 435226586Sdim store = newStoreStore; 436226586Sdim} 437226586Sdim 438226586Sdim//===----------------------------------------------------------------------===// 439226586Sdim// State pretty-printing. 440226586Sdim//===----------------------------------------------------------------------===// 441226586Sdim 442353358Sdimvoid ProgramState::printJson(raw_ostream &Out, const LocationContext *LCtx, 443353358Sdim const char *NL, unsigned int Space, 444353358Sdim bool IsDot) const { 445353358Sdim Indent(Out, Space, IsDot) << "\"program_state\": {" << NL; 446353358Sdim ++Space; 447353358Sdim 448226586Sdim ProgramStateManager &Mgr = getStateManager(); 449226586Sdim 450353358Sdim // Print the store. 451353358Sdim Mgr.getStoreManager().printJson(Out, getStore(), NL, Space, IsDot); 452353358Sdim 453234353Sdim // Print out the environment. 454353358Sdim Env.printJson(Out, Mgr.getContext(), LCtx, NL, Space, IsDot); 455226586Sdim 456234353Sdim // Print out the constraints. 457353358Sdim Mgr.getConstraintManager().printJson(Out, this, NL, Space, IsDot); 458226586Sdim 459341825Sdim // Print out the tracked dynamic types. 460353358Sdim printDynamicTypeInfoJson(Out, this, NL, Space, IsDot); 461341825Sdim 462353358Sdim // Print checker-specific data. 463353358Sdim Mgr.getOwningEngine().printJson(Out, this, LCtx, NL, Space, IsDot); 464341825Sdim 465353358Sdim --Space; 466353358Sdim Indent(Out, Space, IsDot) << '}'; 467234353Sdim} 468226586Sdim 469353358Sdimvoid ProgramState::printDOT(raw_ostream &Out, const LocationContext *LCtx, 470353358Sdim unsigned int Space) const { 471353358Sdim printJson(Out, LCtx, /*NL=*/"\\l", Space, /*IsDot=*/true); 472234353Sdim} 473226586Sdim 474309124SdimLLVM_DUMP_METHOD void ProgramState::dump() const { 475353358Sdim printJson(llvm::errs()); 476234353Sdim} 477226586Sdim 478341825SdimAnalysisManager& ProgramState::getAnalysisManager() const { 479344779Sdim return stateMgr->getOwningEngine().getAnalysisManager(); 480341825Sdim} 481341825Sdim 482226586Sdim//===----------------------------------------------------------------------===// 483226586Sdim// Generic Data Map. 484226586Sdim//===----------------------------------------------------------------------===// 485226586Sdim 486226586Sdimvoid *const* ProgramState::FindGDM(void *K) const { 487226586Sdim return GDM.lookup(K); 488226586Sdim} 489226586Sdim 490226586Sdimvoid* 491226586SdimProgramStateManager::FindGDMContext(void *K, 492226586Sdim void *(*CreateContext)(llvm::BumpPtrAllocator&), 493226586Sdim void (*DeleteContext)(void*)) { 494226586Sdim 495226586Sdim std::pair<void*, void (*)(void*)>& p = GDMContexts[K]; 496226586Sdim if (!p.first) { 497226586Sdim p.first = CreateContext(Alloc); 498226586Sdim p.second = DeleteContext; 499226586Sdim } 500226586Sdim 501226586Sdim return p.first; 502226586Sdim} 503226586Sdim 504234353SdimProgramStateRef ProgramStateManager::addGDM(ProgramStateRef St, void *Key, void *Data){ 505226586Sdim ProgramState::GenericDataMap M1 = St->getGDM(); 506226586Sdim ProgramState::GenericDataMap M2 = GDMFactory.add(M1, Key, Data); 507226586Sdim 508226586Sdim if (M1 == M2) 509226586Sdim return St; 510226586Sdim 511226586Sdim ProgramState NewSt = *St; 512226586Sdim NewSt.GDM = M2; 513226586Sdim return getPersistentState(NewSt); 514226586Sdim} 515226586Sdim 516234353SdimProgramStateRef ProgramStateManager::removeGDM(ProgramStateRef state, void *Key) { 517226586Sdim ProgramState::GenericDataMap OldM = state->getGDM(); 518226586Sdim ProgramState::GenericDataMap NewM = GDMFactory.remove(OldM, Key); 519226586Sdim 520226586Sdim if (NewM == OldM) 521226586Sdim return state; 522226586Sdim 523226586Sdim ProgramState NewState = *state; 524226586Sdim NewState.GDM = NewM; 525226586Sdim return getPersistentState(NewState); 526226586Sdim} 527226586Sdim 528261991Sdimbool ScanReachableSymbols::scan(nonloc::LazyCompoundVal val) { 529261991Sdim bool wasVisited = !visited.insert(val.getCVData()).second; 530261991Sdim if (wasVisited) 531261991Sdim return true; 532261991Sdim 533261991Sdim StoreManager &StoreMgr = state->getStateManager().getStoreManager(); 534261991Sdim // FIXME: We don't really want to use getBaseRegion() here because pointer 535261991Sdim // arithmetic doesn't apply, but scanReachableSymbols only accepts base 536261991Sdim // regions right now. 537261991Sdim const MemRegion *R = val.getRegion()->getBaseRegion(); 538261991Sdim return StoreMgr.scanReachableSymbols(val.getStore(), R, *this); 539261991Sdim} 540261991Sdim 541226586Sdimbool ScanReachableSymbols::scan(nonloc::CompoundVal val) { 542226586Sdim for (nonloc::CompoundVal::iterator I=val.begin(), E=val.end(); I!=E; ++I) 543226586Sdim if (!scan(*I)) 544226586Sdim return false; 545226586Sdim 546226586Sdim return true; 547226586Sdim} 548226586Sdim 549226586Sdimbool ScanReachableSymbols::scan(const SymExpr *sym) { 550314564Sdim for (SymExpr::symbol_iterator SI = sym->symbol_begin(), 551314564Sdim SE = sym->symbol_end(); 552314564Sdim SI != SE; ++SI) { 553314564Sdim bool wasVisited = !visited.insert(*SI).second; 554314564Sdim if (wasVisited) 555314564Sdim continue; 556296417Sdim 557314564Sdim if (!visitor.VisitSymbol(*SI)) 558314564Sdim return false; 559314564Sdim } 560296417Sdim 561226586Sdim return true; 562226586Sdim} 563226586Sdim 564226586Sdimbool ScanReachableSymbols::scan(SVal val) { 565249423Sdim if (Optional<loc::MemRegionVal> X = val.getAs<loc::MemRegionVal>()) 566226586Sdim return scan(X->getRegion()); 567226586Sdim 568249423Sdim if (Optional<nonloc::LazyCompoundVal> X = 569261991Sdim val.getAs<nonloc::LazyCompoundVal>()) 570261991Sdim return scan(*X); 571239462Sdim 572249423Sdim if (Optional<nonloc::LocAsInteger> X = val.getAs<nonloc::LocAsInteger>()) 573226586Sdim return scan(X->getLoc()); 574226586Sdim 575226586Sdim if (SymbolRef Sym = val.getAsSymbol()) 576226586Sdim return scan(Sym); 577226586Sdim 578226586Sdim if (const SymExpr *Sym = val.getAsSymbolicExpression()) 579226586Sdim return scan(Sym); 580226586Sdim 581249423Sdim if (Optional<nonloc::CompoundVal> X = val.getAs<nonloc::CompoundVal>()) 582226586Sdim return scan(*X); 583226586Sdim 584226586Sdim return true; 585226586Sdim} 586226586Sdim 587226586Sdimbool ScanReachableSymbols::scan(const MemRegion *R) { 588226586Sdim if (isa<MemSpaceRegion>(R)) 589226586Sdim return true; 590296417Sdim 591261991Sdim bool wasVisited = !visited.insert(R).second; 592261991Sdim if (wasVisited) 593226586Sdim return true; 594296417Sdim 595234353Sdim if (!visitor.VisitMemRegion(R)) 596234353Sdim return false; 597226586Sdim 598226586Sdim // If this is a symbolic region, visit the symbol for the region. 599226586Sdim if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) 600226586Sdim if (!visitor.VisitSymbol(SR->getSymbol())) 601226586Sdim return false; 602226586Sdim 603226586Sdim // If this is a subregion, also visit the parent regions. 604239462Sdim if (const SubRegion *SR = dyn_cast<SubRegion>(R)) { 605239462Sdim const MemRegion *Super = SR->getSuperRegion(); 606239462Sdim if (!scan(Super)) 607226586Sdim return false; 608226586Sdim 609239462Sdim // When we reach the topmost region, scan all symbols in it. 610239462Sdim if (isa<MemSpaceRegion>(Super)) { 611239462Sdim StoreManager &StoreMgr = state->getStateManager().getStoreManager(); 612239462Sdim if (!StoreMgr.scanReachableSymbols(state->getStore(), SR, *this)) 613239462Sdim return false; 614239462Sdim } 615239462Sdim } 616226586Sdim 617239462Sdim // Regions captured by a block are also implicitly reachable. 618239462Sdim if (const BlockDataRegion *BDR = dyn_cast<BlockDataRegion>(R)) { 619239462Sdim BlockDataRegion::referenced_vars_iterator I = BDR->referenced_vars_begin(), 620239462Sdim E = BDR->referenced_vars_end(); 621239462Sdim for ( ; I != E; ++I) { 622239462Sdim if (!scan(I.getCapturedRegion())) 623239462Sdim return false; 624239462Sdim } 625239462Sdim } 626226586Sdim 627239462Sdim return true; 628226586Sdim} 629226586Sdim 630226586Sdimbool ProgramState::scanReachableSymbols(SVal val, SymbolVisitor& visitor) const { 631226586Sdim ScanReachableSymbols S(this, visitor); 632226586Sdim return S.scan(val); 633226586Sdim} 634226586Sdim 635344779Sdimbool ProgramState::scanReachableSymbols( 636344779Sdim llvm::iterator_range<region_iterator> Reachable, 637344779Sdim SymbolVisitor &visitor) const { 638226586Sdim ScanReachableSymbols S(this, visitor); 639344779Sdim for (const MemRegion *R : Reachable) { 640344779Sdim if (!S.scan(R)) 641226586Sdim return false; 642226586Sdim } 643226586Sdim return true; 644226586Sdim} 645